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!

  • $\begingroup$ I've got a thought about the no-goods. I think (level, mutexes) will do the job, where mutexes is a set of pairs of states that are mutex with each other in the level. It doesn't suffer the problem described above, but I don't know if it's suitable in other conditions I haven't thought of. plz help me check it out. $\endgroup$
    – Maybe
    Jul 29, 2017 at 1:50
  • $\begingroup$ Kindly,please go through the community guide lines artificial intelligence $\endgroup$
    – quintumnia
    Jul 29, 2017 at 11:07
  • $\begingroup$ Thanks for your comment. May I ask whether you were suggesting I provide my 'answer' along with the question? If that's the case, I want to explain myself. I didn't have any answer about this problem in the first place, I was totally confused by the no-goods defined in the book at that time. That was why I asked it. The 'answer' I provided above was what I worked out later, four days later exactly. And I don't think that was a truly answer, 'cause it doesn't match up with the no-goods described in the book. I provided it in the comment just as a personal opinion.. $\endgroup$
    – Maybe
    Jul 29, 2017 at 11:57


You must log in to answer this question.

Browse other questions tagged .