In many applications, one may need to rerun a search algorithm to find an updated solution when the environment changes. In such scenarios, instead of rerunning search algorithms from scratch each time, incremental search algorithms reuse information from previous searches to speed up the current search. Consequently, incremental search algorithms are typically much faster than solving the problem repeatedly from scratch. They are widely popular in solving dynamic path-planning problems such as navigation for unmanned ground vehicles and motion planning for articulated robots. For example, existing incremental search algorithms such as D* and D* Lite have been adapted for use with much success in various robotic applications including the Mars rovers and autonomous vehicles in the DARPA Urban Challenge.
selected publications
IAT
Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems
William Yeoh, Pradeep Varakantham, Xiaoxun Sun, and
1 more author
In International Conferences on Intelligent Agent Technology, 2015
Distributed constraint optimization (DCOP) problems are well-suited for modeling multi-agent coordination problems. However, it only models static problems, which do not change over time. Consequently, researchers have introduced the Dynamic DCOP (DDCOP) model to model dynamic problems. In this paper, we make two key contributions: (a) a procedure to reason with the incremental changes in DDCOP problems and (b) an incremental pseudo-tree construction algorithm that can be used by DCOP algorithms such as any-space ADOPT and any-space BnB-ADOPT to solve DDCOP problems. Due to the incremental reasoning employed, our experimental results show that any-space ADOPT and any-space BnB-ADOPT are up to 42% and 38% faster, respectively, with the incremental procedure and the incremental pseudo-tree reconstruction algorithm than without them.
@inproceedings{conf/iat/YeohVSK15,author={Yeoh, William and Varakantham, Pradeep and Sun, Xiaoxun and Koenig, Sven},title={Incremental {DCOP} Search Algorithms for Solving Dynamic {DCOP} Problems},booktitle={International Conferences on Intelligent Agent Technology},pages={257--264},year={2015},}
AAAI
Solving Uncertain MDPs by Reusing State Information and Plans
Ping Hou, William Yeoh, and Tran Cao Son
In AAAI Conference on Artificial Intelligence, 2014
While MDPs are powerful tools for modeling sequential decision making problems under uncertainty, they are sensitive to the accuracy of their parameters. MDPs with uncertainty in their parameters are called Uncertain MDPs. In this paper, we introduce a general framework that allows off-the-shelf MDP algorithms to solve Uncertain MDPs by planning based on currently available information and replan if and when the problem changes. We demonstrate the generality of this approach by showing that it can use the VI, TVI, ILAO*, LRTDP, and UCT algorithms to solve Uncertain MDPs. We experimentally show that our approach is typically faster than replanning from scratch and we also provide a way to estimate the amount of speedup based on the amount of information being reused.
@inproceedings{conf/aaai/HouYS14,author={Hou, Ping and Yeoh, William and Son, Tran Cao},title={Solving Uncertain {MDP}s by Reusing State Information and Plans},booktitle={{AAAI} Conference on Artificial Intelligence},pages={2285--2292},year={2014},}
ICAPS
Incremental ARA*: An Incremental Anytime Search Algorithm for Moving-Target Search
Xiaoxun Sun, Tansel Uras, Sven Koenig, and
1 more author
In International Conference on Automated Planning and Scheduling, 2012
Moving-target search, where a hunter has to catch a moving target, is an important problem for video game developers. In our case, the hunter repeatedly moves towards the target and thus has to solve similar search problems repeatedly. We develop Incremental ARA* (I-ARA*) for this purpose, the first incremental anytime search algorithm for movingtarget search in known terrain. We provide an error bound on the lengths of the paths found by I-ARA* and show experimentally in known four-neighbor gridworlds that I-ARA* can be used with smaller time limits between moves of the hunter than competing state-of-the-art moving-target search algorithms, namely repeated A*, G-FRA*, FRA*, and sometimes repeated ARA*. The hunter tends to make more moves with I-ARA* than repeated A*, G-FRA* or FRA*, which find shortest paths for the hunter, but fewer moves with I-ARA* than repeated ARA*, which finds suboptimal paths for the hunter like I-ARA*. Also, the error bounds on the lengths of the paths of the hunter tend to be smaller with I-ARA* than repeated ARA*.
@inproceedings{conf/icaps/SunYUK12,author={Sun, Xiaoxun and Uras, Tansel and Koenig, Sven and Yeoh, William},title={Incremental {ARA}*: An Incremental Anytime Search Algorithm for Moving-Target Search},booktitle={International Conference on Automated Planning and Scheduling},year={2012},}
AAMAS
Generalized Fringe-Retrieving A*: Faster Moving Target Search on State Lattices
Xiaoxun Sun, William Yeoh, and Sven Koenig
In International Conference on Autonomous Agents and Multiagent Systems, 2010
Moving target search is important for robotics applications where unmanned ground vehicles (UGVs) have to follow other friendly or hostile UGVs. Artificial intelligence researchers have recently used incremental search to speed up the computation of a simple strategy for the hunter. The fastest incremental search algorithm, Fringe-Retrieving A*, solves moving target search problems only on two-dimensional grids, which are rather unrealistic models for robotics applications. We therefore generalize it to Generalized Fringe-Retrieving A*, which solves moving target search problems on arbitrary graphs, including the state lattices used for UGV navigation.
@inproceedings{conf/aamas/SunYK10a,author={Sun, Xiaoxun and Yeoh, William and Koenig, Sven},title={Generalized Fringe-Retrieving A*: Faster Moving Target Search on State Lattices},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={1081--1088},year={2010},}
AAMAS
Moving Target D* Lite
Xiaoxun Sun, William Yeoh, and Sven Koenig
In International Conference on Autonomous Agents and Multiagent Systems, 2010
Incremental search algorithms, such as Generalized FringeRetrieving A* and D* Lite, reuse search trees from previous searches to speed up the current search and thus often find cost-minimal paths for series of similar search problems faster than by solving each search problem from scratch. However, existing incremental search algorithms have limitations. For example, D* Lite is slow on moving target search problems, where both the start and goal states can change over time. In this paper, we therefore introduce Moving Target D* Lite, an extension of D* Lite that uses the principle behind Generalized Fringe-Retrieving A* to repeatedly calculate a cost-minimal path from the hunter to the target in environments whose blockages can change over time. We demonstrate experimentally that Moving Target D* Lite can be three to seven times faster than Generalized Adaptive A*, which so far was believed to be the fastest incremental search algorithm for solving moving target search problems in dynamic environments.
@inproceedings{conf/aamas/SunYK10,author={Sun, Xiaoxun and Yeoh, William and Koenig, Sven},title={Moving Target D* Lite},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={67--74},year={2010},}