### Optimization and Systems Theory Seminar

Tuesday, April 11, 2000, 11.00-12.00, Room 3721, Lindstedtsv. 25

**Magnus Egerstedt**

Optimization and Systems Theory

KTH

and

Division of Engineering and Applied Sciences

Harvard University

Cambridge, Massachusetts

USA

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.
*