Duke Computer Science Colloquium

The Topology of Uncertain and Adversarial Strategies

Speaker:Michael Erdmann
Carnegie Mellon University
Date: Monday, October 29, 2012
Time: 11:45am - 12:45pm
Location: D106 LSRC, Duke


Programming robots to perform tasks reliably involves coping with uncertainty. Frequently one builds planners that anticipate multiple outcomes of desired actions. This talk shows how combinatorial topology informs the design and planning process by characterizing the capabilities of uncertain and possibly adversarial systems topologically.

Planning problems, particularly for robotic manipulation tasks, may often be cast as discrete graph search problems. Motions in the graph are generally nondeterministic or stochastic as a result of control and sensing errors in the underlying physical system. The global capabilities of such a system may be modeled by the homotopy type of a "strategy complex". The simplices of this complex may be viewed as the eventually-convergent control laws (aka plans or strategies) possible on the graph.

One result that appears via this perspective is a controllability theorem: The robot can move anywhere in its state graph despite control uncertainty (adversarial or stochastic) precisely when the graph's strategy complex is homotopic to a sphere of dimension two less than the number of states. This talk discusses that and related results.


Michael Erdmann is a Professor of Computer Science and Robotics at Carnegie Mellon University. He obtained his PhD in 1989 from MIT under the supervision of Tomas Lozano-Perez, received an NSF Presidential Young Investigator Award in 1991, and is a Fellow of the IEEE. He was a Technical Editor of the IEEE Transactions on Robotics and Automation and is currently on the Editorial Board of the International Journal of Robotics Research. His recent research has focused on applying topological methods to engineering problems, including modeling protein structure, planning with uncertainty, and understanding privacy.

Hosted by:
Bruce Donald