Incremental heuristic search
Encyclopedia
Incremental heuristic search algorithms combine both incremental and heuristic search to speed up searches of sequences of similar search problems, which is important in domains that are only incompletely known or change dynamically. Incremental search has been studied at least since the late 1960s. Incremental search algorithms reuse information from previous searches to speed up the current search and solve search problems potentially much faster than solving them repeatedly from scratch. Similarly, heuristic search has been studied at least since the late 1960s. Heuristic search algorithms, often based on A*, use heuristic knowledge in the form of approximations of the goal distances to focus the search and solve search problems potentially much faster than uninformed search algorithms. The resulting search problems, sometimes called dynamic path planning problems, are graph search problems where paths have to be found repeatedly because the topology
of the graph, its edge costs, the start vertex or the goal vertices change over time.
So far, three main classes of incremental heuristic search algorithms have been developed:
All three classes of incremental heuristic search algorithms are different from other replanning algorithms, such as planning by analogy, in that their plan quality does not deteriorate with the number of replanning episodes.
, where a larger number of path planning systems are based on either D* (typically
earlier systems) or D* Lite (current systems), two different incremental heuristic search algorithms.
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
of the graph, its edge costs, the start vertex or the goal vertices change over time.
So far, three main classes of incremental heuristic search algorithms have been developed:
- The first class restarts A* at the point where its current search deviates from the previous one (example: Fringe Saving A*).
- The second class updates the h-values from the previous search during the current search to make them more informed (example: Generalized Adaptive A*).
- The third class updates the g-values from the previous search during the current search to correct them when necessary, which can be interpreted as transforming the A* search tree from the previous search into the A* search tree for the current search (examples: Lifelong Planning A*, D*, D* Lite).
All three classes of incremental heuristic search algorithms are different from other replanning algorithms, such as planning by analogy, in that their plan quality does not deteriorate with the number of replanning episodes.
Applications
Incremental heuristic search has been extensively used in roboticsRobotics
Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
, where a larger number of path planning systems are based on either D* (typically
earlier systems) or D* Lite (current systems), two different incremental heuristic search algorithms.