# Overview Heuristics derived from the planning graph are defined in Chapter 10 of Artificial Intelligence: a Modern Approach (AIMA) 3rd edition (Chapter 11 in the 2nd edition–linked in the project readme). The pseudocode below provides functional descriptions of the three planning graph heuristics that must be implemented for this project. Note that the pseudocode is _accurate_, but it isn't necessarily _efficient_ to compute them this way. The most significant inefficiency is that each function starts by building a _complete_ planning graph until it levels off. However, in many cases the heuristics can be computed before the full planning graph is built. See the last section below for an example of changing the pseudocode for the MaxLevel heuristic so that it incrementally constructs the planning graph, cutting the runtime for that heuristic on most problems in half. You should discuss the other heuristics below with your peers to look for more efficient implementations. ## LevelCost The level cost is a helper function used by MaxLevel and LevelSum. The level cost of a goal is equal to the level number of the first literal layer in the planning graph where the goal literal appears. --- **function** LevelCost(_graph_, _goal_) **returns** a value  **inputs:**   _graph_, a leveled planning graph   _goal_, a literal that is a goal in the planning graph  **for each** _layeri_ in _graph.literalLayers_ **do**   **if** _goal_ in _layeri_ **then return** i --- ## MaxLevel > The max-level heuristic simply takes the maximum level cost of any of the goals; this is admissible, but not necessarily accurate.  —AIMA Chapter 10 --- **function** MaxLevel(_graph_) **returns** a value  **inputs:**   _graph_, an initialized (unleveled) planning graph  _costs_ = []  _graph_.fill() _/* fill the planning graph until it levels off */_  **for each** _goal_ in _graph.goalLiterals_ **do**   _costs_.append(**LevelCost**(_graph_, _goal_))  **return max**(_costs_) --- ## LevelSum > The level sum heuristic, following the subgoal independence assumption, returns the sum of the level costs of the goals; this can be inadmissible but works well in practice for problems that are largely decomposable.  —AIMA Chapter 10 --- **function** LevelSum(_graph_) **returns** a value  **inputs:**   _graph_, an initialized (unleveled) planning graph  _costs_ = []  _graph_.fill() _/* fill the planning graph until it levels off */_  **for each** _goal_ in _graph.goalLiterals_ **do**   _costs_.append(**LevelCost**(_graph_, _goal_))  **return sum**(_costs_) --- ## SetLevel > The set-level heuristic finds the level at which all the literals in the conjunctive goal appear in the planning graph without any pair of them being mutually exclusive.  —AIMA Chapter 10 --- **function** SetLevel(_graph_) **returns** a value  **inputs:**   _graph_, an initialized (unleveled) planning graph  _graph_.fill() _/* fill the planning graph until it levels off */_  **for** _layeri_ in _graph.literalLayers_ **do**   _allGoalsMet_ <- _true_   **for each** _goal_ in _graph.goalLiterals_ **do**    **if** _goal_ not in _layeri_ **then** _allGoalsMet_ <- _false_   **if** not _allGoalsMet_ **then** continue   _goalsAreMutex_ <- _false_   **for each** _goalA_ in _graph.goalLiterals_ **do**    **for each** _goalB_ in _graph.goalLiterals_ **do**     **if** _layeri_.isMutex(_goalA_, _goalB_) **then** _goalsAreMutex_ <- _true_   **if** not _goalsAreMutex_ **then return** _i_ --- ## Improving Efficiency These heuristics can be made _much_ more efficient by incrementally growing the graph rather than building until it levels off. A straightforward implementation of the alternate MaxLevel pseudocode shown below is at least 2x faster than the simple version above. --- **function** MaxLevel(_graph_) **returns** a value  **inputs:** _graph_, an initialized (unleveled) planning graph  _i_ <- 0  **loop until** _graph_.isLeveled **do**   _allGoalsMet_ <- true   **for each** _goal_ in _graph.goalLiterals_ **do**    **if** _goal_ not in _graph_.getLastLiteralLayer() **then** _allGoalsMet_ <- false   **if** _allGoalsMet_ **then return** _i_   **else** _graph_.extend() /* add the next literal layer */   _i_ <- _i_ + 1 ---