Incremental Sampling-Based Algorithm for Minimum-Violation Motion Planning

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

REYES CASTRO Luis Ignacio CHAUDHARI Pratik TŮMOVÁ Jana KARAMAN Sertac FRAZZOLI Emilio RUS Daniela

Rok publikování 2013
Druh Článek ve sborníku
Konference Proceedings of the IEEE 52nd Annual Conference on Decision and Control (CDC), 2013
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1109/CDC.2013.6760374
Obor Informatika
Klíčová slova motion planning; temporal logic; sampling-based planning; formal methods
Popis This paper studies the problem of control strategy synthesis for dynamical systems with differential constraints to fulfill a given reachability goal specification while satisfying a set of safety rules. Particular attention is devoted to goals that become feasible only if a subset of the safety rules are violated. The proposed algorithm computes a control law, that minimizes the level of unsafety while the desired goal is guaranteed to be reached. This problem is motivated by an autonomous car navigating an urban environment while following rules of the road such as "always travel in right lane" and "do not change lanes frequently". Ideas behind sampling based motion-planning algorithms, such as Probabilistic Road Maps (PRMs) and Rapidly-exploring Random Trees (RRTs), are employed to incrementally construct a finite concretization of the dynamics as a durational Kripke structure. In conjunction with this, a weighted finite automaton that captures the safety rules is used in order to find an optimal trajectory that minimizes the violation of safety rules. We prove that the proposed algorithm guarantees asymptotic optimality, i.e., almost-sure convergence to optimal solutions. We present results of simulation experiments and an implementation on an autonomous urban mobility-on-demand system.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.