incremental search

(archived 2016)

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

                  1. 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
                  1. 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
                    1. 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
                      1. 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
                      2. AAMAS
                        Moving Target D* Lite
                        Xiaoxun Sun, William Yeoh, and Sven Koenig
                        In International Conference on Autonomous Agents and Multiagent Systems, 2010