
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 multiagent systems.
Graphbased search algorithms such as A* are popular means of finding
costminimal 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, graphbased 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 graphbased search algorithms. Thus far, my research has
focused on developing novel incremental heuristic search algorithms,
realtime 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 searchbased 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 stateoftheart 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 multiagent
systems.
 The first class uses information from the previous
searches to update the hvalues of the current search so that they
become more informed and focus the current search better. Examples
include MTAdaptive 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 FringeSaving A* [IJCAI 07], FringeRetrieving A*
[IJCAI 09], Generalized FringeRetrieving 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 suboptimal 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.
Dissertation title: INCREMENTAL SEARCHBASED PATH
PLANNING FOR MOVING TARGET SEARCH
Program for my dissertation (tar.gz file)
SBPL program that I extended for the UGV navigation
application (.rar file)

