How can I modify the backtracking algorithm so it can run on "and/or" graphs?

In Artificial Intelligence we studied the backtracking algorithm. Here is the pseudocode our book offers:

function backtrack;
begin
    SL:= [Start]; NSL := [Start]; DE := [] CS := Start;
    while NSL != [] do
        begin
            if CS = goal (or meets goal description)
                then return SL;
            if CS has no children (excluding nodes already on DE, SL, and NSL)
                then begin
                    while SL is not empty and CS = the first element of SL do
                        begin
                            add CS to DE
                            remove first element froM SL;
                            remove first element from NSL;
                            CS := first element of NSL;
                        end
                    add CS to SL;
             end
             else begin
                 place children of CS (except nodes already on DE, SL or NSL) on NSL;
                 CS := first element of NSL;
                 add CS to SL;
             end
      end
      return FAIL;
end

• SL: the state list, lists the states in the current path being tried.
• NSL: the new state list, contains nodes awaiting evaluation.
• DE: dead ends, lists states whose descendants have failed to contain a goal node.
• CS: the current state

I understand this and have not only hand run the algorithm but written programs in class that utilize it as well.

开发者_运维技巧However, now we have been tasked with modifying it so it can be run on "and/or" graphs.

(Example and/or graph) alt text http://starbase.trincoll.edu/~ram/cpsc352/notes/gifs/whereisfred.gif

The textbook had the following sentence talking about backtracking and/or graphs:

"And/or graph search requires only slightly more record keeping than search in regular graphs, an example of which was the backtrack algorithm. The or descendants are checked as they were in backtrack: once a path is found connecting a goal to a start node along or nodes, the problem will be solved. If a path leads to a failure, the algorithm may backtrack and try another branch. In searching and nodes, however, all of the and descendants of a node must be solved (or proved true) to solve the parent node.

While I understand what "and/or" graphs are, I'm having trouble modifying the above backtracking algorithm so that it works with "and/or" graphs. As the book says, if they are "OR" nodes, it should proceed as normal but what I'm having difficulty with are "and" nodes. Do I need to do something like:

if CS has children and is "AND" node   then  
     resolve all children of CS  
         if children are all true, add children to NSL  
         else backtrack?  

This is as close as I can get conceptually in my head, but it still doesn't feel right. Can anyone help me flesh it out a little further?

---

The book excerpt you listed has the solution you are looking for.

First, the pseudo code you listed is quite difficult to look at if you don't know what the variables stand for. The one I understood first was CS which is pretty standard for current state. Then I'm guessing DE is dead ends, SL is current state up to the current node, and NSL is all unchecked branches. After that I just used my own understanding of the backtracking algorithm, which I normally implement recursively. In the future, please try to use more descriptive variables when posting general questions.

Basically when you get to an OR node, you can continue searching with an unmodified backtracking algorithm because as soon as you hit a single true node, it will percolate success back to the source. When you reach an AND node however, you have to check all the descendants at that location and make sure all are true, or easier to understand, as soon as one of the descendants is false, you can backtrack.

At OR nodes you are assuming everyone is false until proven true at least once. At AND nodes you are assuming everyone is true until proven false at least once.

The modification you have added should be placed in the else clause of the original algorithm. You know it has children, so all you need to do is force a way to make it check all the descendants and not stop at a single good instance for AND nodes. The modification you have listed is the right idea, but it doesn't fit with how the original pseudo code is written. The algorithm you have listed does not allow for a call to "resolve all children of CS" because that would be a recursive call, and your algorithm wants a straight loop. On the same note, if all children are true, adding them to NSL would also require recursion because you don't know how deep the tree is beyond the current state and immediate children.

I recommend rewriting it as a recursive solution. If that is not an option, the answer isn't popping out at me.

Here is a good video to watch if you have an hour.