|
|
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.
|
|
