Xiaoxun Sun



Site Navigation








Research Interest

My research interest is in artificial intelligence with an emphasis on developing efficient search techniques for solving automated planning and scheduling problems in single and multi-agent systems. Graph-based search algorithms such as A* are popular means of finding cost-minimal plans because they are applicable to arbitrary graphs, easy to understand and implement, and theoretically well grounded. However, they can be inefficient in solving large and complex problems. Therefore, my research goal is to develop efficient, graph-based search algorithms that can be applied to large, dynamic and complex planning problems, such as robotic motion planning and unmanned ground vehicle path planning problems. In particular, I investigate the different ways one can speed up existing graph-based search algorithms. Thus far, my research has focused on developing novel incremental heuristic search algorithms, real-time search algorithms and anytime search algorithms. Example applications of such algorithms are seen in the fields of robot navigation, homeland security, disaster rescue and video games.

One of the biggest challenges associated with solving automated planning problem by using search algorithms in realistic applications is to deal with dynamic or imperfect information inherited from the real world. As in such situations, the planner has to take dynamic information of the environment into account. Thus, the path planer has to be able to repeatedly generate new feasible plans accordingly. The search-based planning problems are usually repetitive processes. Incremental heuristic search algorithms can reuse information from previous searches to speed up the current search and potentially solve search problems much faster than repeatedly solving them from scratch. Incremental search algorithms are popular for solving dynamic path planning problems such as unmanned ground vehicles (UGVs) navigation (see figure above) and motion planning for robotic systems (see figure below). For example, existing incremental search algorithms, such as D* Lite and Anytime D*, have been adapted and implemented in the path planning modules of various robotic applications including the NASA's twin robot geologists, the Mars Exploration Rovers and the UGVs in the Defense Advanced Research Projects Agency (DARPA) Urban Challenge.

However, most of the state-of-the-art incremental search algorithms have limitations that prevent them from optimally and efficiently solving planning problems. For example, D* Lite is inefficient for solving the Moving Target Search (MTS) problem, where a robot has to chase and catch a moving target. As in the MTS problem, both the locations of the robot and the target can change over time, which makes the planning problem even more complex. The MTS problem is extremely important for robotic applications. For example, UGVs often have to (a) follow other friendly or hostile UGVs, (b) move from one surveillance position to the next one as their surveillance target moves or (c) intercept a moving object. Together with my advisor and colleagues, I have developed two classes of incremental search algorithms to build the planning and scheduling modules of single and multi-agent systems.

  • The first class uses information from the previous searches to update the h-values of the current search so that they become more informed and focus the current search better. Examples include MT-Adaptive A* and its generalization Generalized Adaptive A* [AAMAS 08].
  • The second class transforms the previous search tree to the current search tree so that the current search does not need to start from scratch. Examples include Fringe-Saving A* [IJCAI 07], Fringe-Retrieving A* [IJCAI 09], Generalized Fringe-Retrieving A* [AAMAS 10] and Moving Target D* Lite [AAMAS 10].

In real world planning problems, the deliberation time for the autonomous agents, such as robots, to plan their paths is usually limited. Anytime search algorithms are able to find an initial, highly sub-optimal solution quickly and then continually work on improving it until the deliberation time per search runs out. This feature of anytime search algorithms is favorable for applications of robot navigation problems since they can speed up the search to meet the constraints on the deliberation time. My current work is to combine the principle of incremental search algorithms with anytime search, resulting in anytime incremental search, to speed up the search even further and apply these algorithms to realistic applications, such as computer games and robotic navigation systems.


Program for my dissertation (tar.gz file)

SBPL program that I extended for the UGV navigation application (.rar file)