My research interests lie mainly in two areas:
- The coordination of teams of robots, using principled techniques that
are both effective and amenable to analysis.
- The design and implementation of programmatic interfaces and
simulations for robots.
I pursue these research interests in the
Stanford AI Lab.
I am currently involved in the following research projects (see below for past projects):
Pursuit-evasion with teams of robots
We study a form of the pursuit-evasion problem, in which one or
more searchers must move through a given environment so as to guarantee
detection of any and all evaders, which can move arbitrarily fast.
Our goal is to develop techniques for coordinating teams of robots to
execute this task in application domains such as clearing a building,
for reasons of security or safety. To this end, we introduce a new
class of searcher, with limited field of view, which can be readily
instantiated as a physical mobile robot. To date, we have shown that
computing the minimum number of such searchers required to search a given
environment is NP-hard, and have developed the first complete search
algorithm for a single searcher.
Player / Stage
The Player/Stage project develops and distributes open-source robot control and
simulation software. The primary products of this project are Player,
a device server that provides a powerful, flexible, language- and
platform-neutral interface to a variety of sensors and actuators (e.g.,
Stage, a highly parameterizable sensor-based multiple robot simulator.
Player & Stage are widely used in labs and classrooms around the world.
I am a founding developer on the project and I head development of Player.
I have in the past worked on the following research projects (see above for current projects):
Multi-Robot Task Allocation
Important theoretical aspects of mechanisms for multi-robot task allocation
have, to date, been largely ignored. In this project, we are trying to address
part of this negligence by formally studying the problem within an
organizational framework developed in the Operations Research community. In
particular, we are currently exploring multi-robot task allocation as an
instance of the well-known Optimal Assignment Problem. In this light, we have
recently analyzed and compared the algorithmic characteristics of several
existing approaches to the problem.
The key to utilizing the potential of multi-robot systems is
coordination. In this project, we are exploring economically-inspired
approaches to achieving robust multi-robot coordination. In
particular, we have developed MURDOCH, an highly-scalable,
distributed, auction-based multi-robot coordination system. A variant of the
well-known Contract Net Protocol, MURDOCH has been
experimentally validated in a variety of task domains with physical robots.
Mathematical Modeling of Multi-Agent Systems
(Led by Kristina Lerman)
Our research goals are two-fold:
Mathematical analysis is important for several reasons: a designer of
multi-agent systems can use it to show that the proposed agent strategy leads
to the desired group behavior, find the parameters that optimize system
performance (collective behavior), and predict the global dynamics of the
system. We plan to apply this type of analysis to several software agent and
- show that a distributed mechanism based on purely local interactions can
lead to the desired group behavior in several different agent-based systems;
- model and analyze these systems mathematically.
Hi-Scale User-System Interaction (HiSUSI)
(Led by Ashley Tews)
This project is concerned with investigating the high-level interaction
dynamics between people and multiple robotic and embedded systems. The
key question is how to connect possibly hundreds of users to hundreds
of systems and maintain personal interaction. An interaction
infrastructure has been developed for this purpose that allows
interaction at both extremes. This project is part of the larger Human-System
Interaction project at USC Robotics.