Dynamic systems and subadditive functionals

Consider a problem where a number of dynamic systems are required to travel between points in minimum time. The study of this problem is traditionally divided into two parts: A combinatorial part that assigns points to every dynamic system and assigns the order of the traversal of the points, and a path planning part that produces the appropriate control for the dynamic systems to allow them to travel between the points. The first part of the problem is usually studied without consideration for the dynamic constraints of the systems, and this is usually compensated for in the second part. Ignoring the dynamics of the system in the combinatorial part of the problem can significantly compromise performance. In this work, we introduce a framework that allows us to tackle both of these parts at the same time. To that order, we introduce a class of functionals we call the Quasi-Euclidean functionals, and use them to study such problems for dynamic systems. We determine the asymptotic behavior of the costs of these problems, when the points are randomly distributed and their number tends to infinity. We show the applicability of our framework by producing results for the Traveling Salesperson Problem (TSP) and Minimum Bipartite Matching Problem (MBMP) for dynamic systems.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Itani, Sleiman M

Advisor dc:contributor.advisor

• Munther A. Dahleh and Emilio Frazzoli.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/53282

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/53282