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.
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
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)
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)
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
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