Project "Fast Replanning in Symbolic Planning, Robotics and
Games"
(scroll down for publications)
Autonomous agents often need to operate in domains that are only incompletely known or change dynamically. In this case, they need to replan quickly as their knowledge changes. For example, mobile robots or computer-controlled agents in combat games (such as "Total Annihilation" or "Warcraft") might observe obstacles in the terrain that they did not know about or their goal locations might change (for example, if they chase moving targets). Replanning from scratch is often very time consuming but combat games have very tight time requirements, need to control many agents, cannot allocate much processor time for the artificial intelligence, and often run on old computers with slow processors. We therefore study planning methods that are incremental versions of heuristic search methods, and analyze their behavior. Incremental search methods reuse information from previous searches to find solutions to series of similar search tasks potentially much faster than is possible by solving each search task from scratch, while heuristic search methods use heuristic knowledge in form of approximations of the goal distances to focus the search and solve search problems potentially much faster than uninformed search methods. Although incremental search methods have to some degree been studied in the algorithms literature and promise to be very beneficial in artificial intelligence, they have received no major attention in the field and their properties are completely unknown.
We have developed three different classes of incremental heuristic search methods. The first class restarts A* at the point where its current search deviates from the previous one. An example is the Fringe Saving A* algorithm (FSA*). The second class updates the h-values from the previous search during the current search to make them more informed. An example is the Adaptive A* algorithm. 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. An example is the Lifelong Planning A* algorithm (LPA*). All three classes of incremental heuristic search methods differ from other replanning methods (such as planning by analogy) in that the plan-execution time of their plans is as good as that achieved by planning from scratch. Thus, the plan quality does not deteriorate with the number of replanning episodes.
We do not only develop incremental heuristic search methods but also evaluate their utility for a variety of artificial intelligence applications. For example, we have applied LPA* to both STRIPS-type symbolic planning (resulting in our SHERPA and PINCH systems), robot navigation planning (resulting in our Dynamic A* Lite algorithm (= D* Lite), and reinforcement learning and control (resulting in our Minimax LPA*, that we believe to be the first incremental heuristic minimax search algorithm). PINCH, for example, speeds up the planning time of HSP, a heuristic search-based planner, by up to 80 percent in several domains. Similarly, we have demonstrated that D* Lite is fast enough to allow one to build robot architectures that give planning progressively greater control of a robot if reactive navigation continues to fail, until planning controls the robot directly.
David Wooden writes in his dissertation in 2006: "[LPA*} has led to a series of algorithms, including D* lite, ... (The name "lite" is perhaps an unfortunate choice, as the algorithm is indeed not a diluted or handicapped version of D*.) ... In fact, Stentz's lab (where D* was introduced) uses D* Lite in many of its current implementations in place of D* ..." citing "Ferguson, D. personal communication, May 2006." It is therefore not surprising that our D* Lite algorithm has been extended at Carnegie Mellon University for use on their robots. Dave Ferguson and Tony Stentz from Carnegie Mellon University used elements of D* Lite in a highly optimized version of their Field D* system. Joseph Carsten and Art Rankin from NASA's Jet Propulsion Laboratory installed this version of Field D* on the Mars rovers "Spirit" and "Opportunity" (without any involvement by us) and first let it control a rover on Mars in February 2007 after testing it on a rover on Mars in November 2006. Maxim Likhachev (now at the University of Pennsylvania) and Dave Ferguson from CMU used a combination of ARA* and D* Lite called Anytime D* to plan long motions involving complex maneuvers (such as traversal of parking lots and complex u-turns) for the winning DARPA Urban Challenge entry from CMU. D* Lite has also been used as part of the 3DMark05 Pro Tests, according to the website of Futuremark Corporation (note that this link points of a local copy of one of their webpages and the links thus are not guaranteed to work): "3DMark05 CPU Tests: The CPU not only calculates the vertex shaders in the first CPU test, but it also continuously calculates the flight path of the air ship. The air ship actually flies the same path as in game test 3 every time, but the calculations are performed as if it would intelligently steer according to the canyon shape and other obstacles like the sea monster jumping up from the water. The path finding algorithm used is D* Lite [webreference deleted]. The CPU tests are run fixed frame to make a more equal CPU load for all systems. The resolution is locked to 640x480 to decrease the graphics performance influence on the result." The way our PINCH system calculates the heuristics has been used as part of a planning system for interactive storytelling, according to F. Charles et al, Planning Formalisms and Authoring in Interactive Storytelling, Proceedings of the First International Conference on Technologies for Interactive Digital Storytelling and Entertainment, 2003.
The "Artificial Intelligence Topics" webpages on "Search" of the Association for the Advancement of Artificial Intelligence link to this page. The game programming webpages on "Amit's Thoughts on Path-Finding and A*" link to this page as well.
Tutorial
Applet
Code
The following code should be correct but is somewhat out of date. In particular, Lifelong Planning A* and D* Lite can now use buckets as priority queue or, if they use a heap as priority queue, break ties towards larger g-values. These improvements are not yet reflected in the code.
Class Project
Representative Overview Publications
Representative Publications on Heuristic Search
Representative Publications on Symbolic Planning
Representative Publications on Robotics
Representative Publications on Reinforcement Learning
Some of this material is based upon work supported by the National Science Foundation under Grant No. 0350584. Any opinions, findings, and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.