Computing That Serves

Multi-Agent Planning


Thursday, November 11, 2004 - 10:00am


Geoff Gordon, Carnegie Mellon University

Robots acting in the real world can't afford to plan in isolation. Instead, they must reason about external agents who may interfere with their actions or help them to achieve goals.  Unfortunately, this sort of reasoning quickly becomes intractable as the number of relevant agents in the world increases.  I will talk about two techniques which can help make this sort of reasoning tractable: no-regret learning and auction algorithms.  No-regret learning allows robots to adapt quickly to interference from other agents: if the other agents are acting adversarially the robot will retreat to a minimax strategy, while if the other agents are friendlier the robot can learn to achieve much higher reward than minimax can.  Auction algorithms allow teams of robots to cooperate to achieve joint goals: each robot shares its reward for achieving goals with the other robots who help it achieve them.  I will describe recent advances in no-regret learning and auction algorithms which let us apply them to larger and more realistic planning problems.


Dr. Gordon is a member of the research faculty in the Center for Automated Learning and Discovery at CMU.  He works on multi-robot systems, statistical machine learning, and planning in probabilistic and adversarial domains.  His previous appointments include Visiting Professor at the Stanford Computer Science Department, as well as Principal Scientist at Burning Glass Technologies in San Diego.  Dr. Gordon received his B.A. in Computer Science from Cornell University in 1991, and his Ph.D. in Computer Science from CarnegieMellon University in 1999.