Optimization and Systems Theory Seminar
Tuesday, April 11, 2000, 11.00-12.00, Room 3721, Lindstedtsv. 25

Magnus Egerstedt
Optimization and Systems Theory
Division of Engineering and Applied Sciences
Harvard University
Cambridge, Massachusetts
E-mail: magnuse@hrl.harvard.edu

On the control complexity of motion languages

When giving navigation instructions, we typically use statements that contain feedback information. In this work we try to give an account for this observation in a rigorous way, i.e. explain why feedback is an essential ingredient when giving navigation instructions. We propose a formal language for expressing motion commands, and introduce the notion of control complexity. This computational complexity measure has somewhat of the same flavor as the program complexity measure for Turing machines, even though our so called kinematic machines are continuous in nature. Our main application is robot navigation, and we show that in a world populated by fixed, rigid obstacles, closed loop controllers outperform open loop controllers in terms of complexity in almost all situations.

Calendar of seminars
Last update: March 28, 2000 by Anders Forsgren, anders.forsgren@math.kth.se.