Algorithms for minimum-violation planning with formal specifications

We consider the problem of control strategy synthesis for robots given a set of complex mission specifications, such as "eventually visit region A and then return to a base", "periodically survery regions A and B" or "do not enter region D". We focus on problem instances where there does not exist a strategy that satisfies all the specifications, and we aim to nd strategies that satisfy the most important specifications albeit violating the least important ones. We focus on two particular problem formulations, both of which take as input the mission specifications in the form of Linear Temporal Logic (LTL) formulae. In our first formulation we model the robot as a discrete transition system and each of the specifications has a reward associated with its satisfaction. We propose an algorithm for finding the strategy of maximum cumulative reward which has a significantly better computational complexity than that of a brute-force approach. In our second formulation we model the robot as a continuous dynamical system and the specifications are associated with priorities in such a way that a specification with priority i is infinitely more important than one with priority level j, for any i < j. For this purpose, we introduce a functional that quantifies the level of violation of a motion plan and we design an algorithm for asymptotically computing the control strategy of minimum level of violation among all strategies that guide the robot from an initial state to a goal set. For each of our two formulations we demonstrate the usefulness of our algorithms in possible applications through simulations, and in the case of our second formulation we also carry experiments on a real-time autonomous test-bed.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Authors dc:creator

• Reyes Castro, Luis I. (Luis Ignacio)
• Tůmová, Jana
• Chaudhari, Pratik
• Karaman, Sertac

Advisor dc:contributor.advisor

• Emilio Frazzoli.

• Aeronautics and Astronautics.

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/90610

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/90610