Demonstration of Lifelong Planning A* (Java Applet)

Short Instructions

The above Java applet allows you to compare the searches performed by Lifelong Planning A* and A*. Both search algorithms find shortest paths and, in the Java applet, break ties in favor of vertices with smaller g-values. Lifelong Planning A* generalizes A*. Like A*, it uses heuristics to speed up the current search. Different from A*, it also uses information from previous searches to speed up the current one. Press the "Run" button to start a Lifelong Planning A* search in the left gridworld and an A* search in the right gridworld. Then click on cells in the gridworlds to make them blocked or empty and watch the search effort (green and blue cells) of the two search algorithms as they find shortest paths from the start cell (S) to the goal cell (G). The search effort of Lifelong Planning A* is especially small if the changes occur close to the goal cell. It is usually much smaller than the search effort of A* although it can also be larger (especially if the changes occur close to the start cell). Longer instructions are given below.

The version of Lifelong Planning A* for moving robots is called Dynamic A* Lite (= D* Lite). More information on D* Lite and our fast replanning methods can be found on our project pages on fast replanning. D* Lite has been extended at Carnegie Mellon University for use on their robots (without any involvement by us). For example, 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 used Field D* on the Mars rovers "Spirit" and "Opportunity" on Mars. More information on Field D* and how it relates to D* Lite can be found in D. Ferguson and A. Stentz, Using Interpolation to Improve Path Planning: The Field D* Algorithm, Journal of Field Robotics, Volume 23(2), 2006, pages 79-101. If you like their Field D* system, then you will likely also like our Theta* algorithm. 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, whose team lead was Red Whittaker. More information on Anytime D* and how it relates to D* Lite can be found in M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, and S. Thrun, Anytime Dynamic A*: An Anytime, Replanning Algorithm, Proceedings of the International Conference on Autonomous Planning and Scheduling, 2005, pages 262-271 and M. Likhachev and D. Ferguson, Planning Long Dynamically-Feasible Maneuvers for Autonomous Vehicles, International Journal of Robotics Research, Volume 28(8), 2009, pages 933-945. (Images courtesy of NASA/JPL-Caltech and CMU.)

Additional Information

There are two identical gridworlds. The left one shows the search performed by Lifelong Planning A* and the right one shows the search performed by A*. In both cases, the cell marked S is the start cell of the search and the cell marked G is the goal cell. One can move from any cell to any of its eight neighboring cells as long as it is empty. Thus, one can squeeze diagonally through two blocked cells. The cost of each move (including diagonal moves) is one. Both Lifelong Planning A* and A* use the maximum of the absolute differences of the x and y coordinates of two cells as an approximation of their distance.

White, green, and blue cells are empty and black cells are blocked. You can click on an empty cell to make it blocked and vice versa. A white cell was not expanded during the search, a green cell was expanded once, and a blue cell was expanded twice. Each cell (except for the start cell and goal cell) contains its g-value at the end of the search, which approximates the length of a shortest path from the start cell to that cell. A dash means infinity. The shortest path from the start cell to the goal cell is shown by a line. The line is missing if there is no path from the start cell to the goal cell.

Initially, no searches are performed to allow you to make some cells blocked by clicking on them. Once you press the "Run" button, a Lifelong Planning A* search is performed in the left gridworld and an A* search is performed in the right gridworld and the results are shown. The results of the first search should be completely identical. You can then continue to make empty cells blocked and blocked cells empty by clicking on them. After every change, another search is performed and the results are shown. The shortest paths should always be identical but in many cases Lifelong Planning A* now expands many fewer cells than A*. It might not even expand any cells at all! In general, the search effort of Lifelong Planning A* is especially small if the changes occur close to the goal cell. If you want to make several changes at once, you can press the "Stop" button to suspend the searches and make all changes. Once you press the "Run" button again, the searches continue, as before. The "Reset" button resets the applet into its initial state. (Note that you need to press the "Run" button again after pressing the "Reset" button.)

Truth in Advertizing

The applet compares the number of cell expansions of Lifelong Planning A* and A* with the same tie-breaking rule. However, it is important to note that A* expands cells faster than Lifelong Planning A*. Also, Lifelong Planning A* and A* can break ties in favor of vertices with larger g-values and then tend to expand fewer cells (especially in empty gridworlds, where the number of ties is large). These issues are discussed in the papers given below. You might also want to have a look at C. Hernandez, J. Baier, T. Uras and S. Koenig. Position Paper: Incremental Search Algorithms Considered Poorly Understood.

The programming was done by Colin Bauer as part of a student project. Please send bug reports to Sven Koenig, after checking that you have indeed enabled Java in your preferences. Note that the code is not efficient and thus not what you want to use as a starting point for an implementation! Better code is given below. Note that this code still breaks ties in favor of vertices with smaller g-values, but the papers given below explain how to change the tie-breaking rule.

Others have created similar applets as well, see for example a Lifelong Planning A* applet and a D* Lite applet. We are not affiliated with them and cannot guarantee their correctness but they show more information than our applet.

Overview Publications

Technical Publications

Code

Additional Information

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.

Home Page of Sven Koenig