"> Implementation -- The Pruning System

Implementation--
The Pruning System

The tree pruning system allows memory used in unproductive branches of the search tree to be reclaimed for use elsewhere in the tree. Unproductive branches are ones that currently end with a node containing a current state that shows:

  1. an infinite loop has been entered along the branch,
  2. another branch has lead to the same state, or
  3. all of the test programs have terminated.
To detect an infinite loop, the state of the new child must have the same state as the intended parent node or any ancestor of the intended parent node. To detect another branch that has lead to the same state, the state of the new child node must have the same state as any node currently in the terminal node list. The number of test programs that have terminated is tracked in the search tree node entries. When this number reaches the total number of test programs in the simulation, all of the test programs have terminated.

When the child nodes are generated to a chosen node from the terminal node list, each child is checked against each of the above conditions. If any of the conditions is found to exist, the node is not added to the search tree and the entry is deleted. Otherwise, the node is added to the tree as a child of the selected parent node. When all of the child nodes have been completed and if none were added to the tree, the selected parent node is removed from the tree and its parent node becomes the selected node. If the selected parent node has no children, it is also removed from the tree and its parent node becomes the selected node. This continues until the selected node has at least one remaining child node. If all of the branches for the root node are pruned, the simulation is complete and the goal has not been reached indicating that the fault does not exist.

SimPlan does not check every node in the tree for matching states because it takes too long. I intend to add the capability for the user to say how many nodes up from each terminal node in the tree are to be checked during the terminal node state check. This will allow the user to balance time use against memory use based on his/her situation and requirements.

Figure showing operation of pruning system.

Related include files:

Return ...

Andrew Tompkins
Beaverton, OR 97006
Last rev: 17 JUL 03
URL:
http://home.comcast.net/~andytom/simplan.docs/control/prune.html

Valid XHTML 1.0!