In section 10.3.2 in Artificial Intelligence: a Modern Approach there is a piece of pseudocode that describes the graph plan algorithm. The graph plan algorithm constructs a planning graph for a problem and extract a solution from it if there is one.
Here is the pseudocode:
function GRAPHPLAN(problem) returns solution or failure
graph ← INITIAL-PLANNING-GRAPH(problem)
goals ← CONJUNCTS(problem.GOAL)
nogoods ← an empty hash table
for tl=0 to ∞ do
if goals all non-mutex in St of graph then
solution ← EXTRACT-SOLUTION(graph, goals, NUMLEVELS(graph), nogoods)
if solution != failure
then return solution
if graph and nogoods have both leveled off
then return failure
graph ← EXPAND-GRAPH(graph, problem)
Also a PPT for Graphplan
What confuses me for a long time is when the nogoods levels off? The book describe no-goods as follows:
In the case where EXTRACT-SOLUTION fails to find a solution for a set of goals at a given level, we record the (level,goals) pair as a no-good.
But in that case, every time the first EXTRACT-SOLUTION after EXPAN-GRAPH fails, there will always be at least a new no-good produced: whose level becomes the new level of the planning graph and the goals is always the same--which is the goal of the problem. So when does it level off?
There is another sentence about no-goods in the book:
If the function EXTRACT-SOLUTION fails to find a solution, then there must have been at least one set of goals that were not achievable and were marked as a no-good.
From above excerpt, I learn that goals in no-goods is a set of goals that are not achievable in the level. But, IMHO, that could vary when we chose different actions in EXTRACT-SOLUTION. The example in the book provides a good instance:
Consider an air cargo domain with one plane and n pieces of cargo at airport A, all of which have airport B as their destination. In this version of the problem, only one piece of cargo can fit in the plane at a time. The graph will level off at level 4, reflecting the fact that for any single piece of cargo, we can load it, fly it, and unload it at the destination in three steps. But that does not mean that a solution can be extracted from the graph at level 4; in fact a solution will require 4n − 1 steps: for each piece of cargo we load, fly, and unload, and for all but the last piece we need to fly back to airport A to get the next piece.
In the example above, the set of goals not achievable at level 4 varies based on what actions has been taken.
Could someone help clear up this problem? I know there must be some misunderstanding, welcome to point it out, please. Thanks in advance:)
Ps. I'm a English leaner, I may not present this problem very well, so I'm very sorry for any reason that you may want to down vote it. But I‘m very serious about it and I've try my best to make it as clear as I can. So if you're about to down vote it, please comment below and give me some advice to improve it, I'll be very grateful for that. Thanks again!
