Catalogue of Artificial Intelligence Techniques
Keywords: NONLIN, backtracking
Categories: Problem Solving
Author(s): Austin Tate
Since there is often good local information available to indicate the preferred solution path, it is often best to try out that indicated by heuristic information before considering the many alternatives that may be available should the local choice prove faulty. Taken to the extreme, Depth-first Search gives something of the flavour of such a search strategy. However, gradual wandering from a valid solution path could entail backtracking through many levels when a failure is detected. An alternative is to focus on the choice currently being made and try to select one of the local choices which seems most promising. This continues while all is going well (perhaps with some cut-off points to take a long, hard look at how well things are going). However, if a failure occurs, the whole set of alternatives which have been generated (and ranked by a heuristic evaluator) are reconsidered to select a re-focussing point for the search. Such a search strategy is used in Tate's NONLIN, for example.
- Adeli, H., ed., AI Planning, McGraw-Hill, pp.157--199.