Implementation--
The Search Algorithms

There are three search algorithms that are currently supplied for performing the tree search:

the Heuristic Search
the Random Search (weighted to the heuristic)
the Breadth-First Search

More are currently being considered.

Since a single program simulation will generate a tree with only one branch, choice of search algorithm is not important for them. For concurrent program simulations, which generate multiple branch trees, choice of search algorithm is very important as using the wrong algorithm may cause the simulation to take a lot of time to find the goal and may result in the simulation not terminating at all.

The Heuristic Search Algorithm:

The heuristic search algorithm always choses the node in the Terminal Node List that appears to be the closest to achieving the goal by its heuristic value. The heuristic value is calculated by adding the differences of the current and goal values of the variables given in the goal state. A lower heuristic value indicates that the node is closer to achieving the goal than a higher heuristic value. A heuristic value of 0 indicates that the goal has been found. Heuristic values are never negative. The heuristic algorithm choses the node with the lowest heuristic value at the time of the choice.

The heuristic search algorithm will tend to follow one branch of the search tree until the goal is found, a better branch is found, or the branch is pruned. This leads to a depth-first type search. On occasion, the heuristic search can get caught following an unproductive branch for a long time or even infinitely. When the algorithm choses the right path, the goal can be found quite quickly.

The heuristic search algorithm should be used in situations where there are few 'while' loops and where those loops are not nested. It is usually best not to use it when the goal state is most likely not going to be found or where there are many loops.

The Random Search Algorithm:

The random search algorithm still uses the heuristic value to chose the next node to process but doesn't always pick the node with the lowest heuristic value. This allows the algorithm to explore other paths in case the one that appears to be the best is actually not leading to the goal. This often leads to a solution that the heuristic algorithm may not find. When the heuristic algorithm finds a solution, the random algorithm may find it in a shorter amount of time. It can also take longer.

The Breadth-First Search Algorithm:

The breadth-first search algorithm extends each branch of the tree one level before going back and extending any one branch again keeping the depth of the branches uniform over the entire tree (except for the pruned branches which are removed). If the goal can be found, the breadth-first algorithm will find the shortest branch to it. The breadth-first algorithm makes the best use of the pruning system as the identical parallel execution paths usually start at the same level so the match state nodes will still be in the Terminal Node List. Once the matching state nodes are processed and leave the Terminal Node List, as happens frequently in the heuristic algorithm, the top of the identical parallel execution path subtree can no longer be checked for matching state.

The breadth-first search algorithm is best used in concurrent program simulations where at least one of the programs has nested loops or a loop that could become infinite (while TRUE do). It is also best used where it is suspected that the goal cannot be reached or the given error does not exist. The simulation, in this case, can finish as much as 40 to 50 times faster than the heuristic algorithm because of the extensive use of the pruning system.

Related include files:

planner.h

Return ...

Andrew Tompkins
Beaverton, OR 97006
Last rev: 17 JUL 03
URL: