Body: <p>In section 10.3.2 in <em>Artificial Intelligence: a Modern Approach</em> 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.</p>
  
  <p>Here is the pseudocode:</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>Also a PPT for <a href="http://www.cs.mtu.edu/~nilufer/classes/cs5811/2014-fall/lecture-slides/cs5811-ch10b-graphplan.pdf" rel="nofollow noreferrer">Graphplan</a></p>
  
  <p>What confuses me for a long time is when the <code>nogoods</code> levels off? The book describe no-goods as follows:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>But in that case, every time the first <code>EXTRACT-SOLUTION</code> after <code>EXPAN-GRAPH</code> fails, there will always be at least a new no-good produced: whose <code>level</code> becomes the new level of the planning graph and the <code>goals</code> is always the same--which is the goal of the problem. So when does it level off?</p>
  
  <p>There is another sentence about no-goods in the book:</p>
  
  <blockquote>
    <p>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. </p>
  </blockquote>
  
  <p>From above excerpt, I learn that <code>goals</code> in no-goods is a set of goals that are not achievable in the <code>level</code>. But, IMHO, that could vary when we chose different actions in <code>EXTRACT-SOLUTION</code>. The example in the book provides a good instance:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>In the example above, the set of goals not achievable at level 4 varies based on what actions has been taken.</p>
  
  <p>Could someone help clear up this problem? I know there must be some misunderstanding, welcome to point it out, please. Thanks in advance:)</p>
  
  <p>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!</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-29T01:50:58.360Z
Comments.Text: 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.
Comments.UserDisplayName: Maybe
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-29T11:07:23.230Z
Comments.Text: Kindly,please go through the community guide lines [artificial intelligence](https://ai.stackexchange.com/help)
Comments.UserDisplayName: quintumnia
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-29T11:57:46.247Z
Comments.Text: 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..
Comments.UserDisplayName: Maybe
Tags: <path-planning>
Title: What is a no-good? When does the no-goods level off?
UserDisplayName: Maybe
ThreadText: # What is a no-good? When does the no-goods level off?
  
  (Asked by: username_0 on 2017-07-27)
  
  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](http://www.cs.mtu.edu/~nilufer/classes/cs5811/2014-fall/lecture-slides/cs5811-ch10b-graphplan.pdf)
  
  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!
  
  **Tags:** path-planning
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: Kindly,please go through the community guide lines [artificial intelligence](https://ai.stackexchange.com/help)  
  > **username_0**: 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..  
  
  ---
  
  ## 0 answers
  
  