Research
Download my research statement here.
My research interest is in artificial
intelligence with an emphasis on using search techniques for
solving planning
and scheduling problems in single
and multi-agent
systems. Graph-based search algorithms such as A*
are popular means of finding least-cost 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 larger and more
complex problems. In particular, I investigate the different ways one
can speed up existing graph-based search algorithms. Thus far, my research
has focused on two thrusts -- developing incremental
search algorithms for single agent systems and developing distributed
constraint optimization search algorithms for multi-agent systems.
These search algorithms can be used to build the planning and scheduling
modules of single and multi-agent systems.
Single Agents: Incremental Search Algorithms
 |
Incremental search algorithms reuse information from previous searches to speed up the current search and solve search problems potentially much faster than solving them repeatedly from scratch. Incremental search algorithms 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. |
Multi-Agents: Distributed Constraint Optimization Search Algorithms
Image source: http://geoffmerrett.co.uk/research.php |
A distributed constraint optimization (DCOP) problem is a problem where multiple agents coordinate with each other to take on values such that the sum of the resulting constraint costs, that are dependent on the values of the agents, is minimal. DCOP problems are a popular way of formulating and solving multi-agent coordination problems such as the distributed scheduling of meetings, distributed coordination of unmanned air vehicles and the distributed allocation of targets in sensor networks. Privacy concerns in the scheduling of meetings and the limitation of communication and computation resources of each sensor in a sensor network makes centralized constraint optimization difficult. Therefore, the nature of these applications call for a distributed approach. |