Incremental Sampling-Based Algorithm for Minimum-Violation
Motion Planning

D 2013

Incremental Sampling-Based Algorithm for Minimum-Violation Motion Planning

REYES CASTRO, Luis Ignacio, Pratik CHAUDHARI, Jana TŮMOVÁ, Sertac KARAMAN, Emilio FRAZZOLI et. al.

Základní údaje

Originální název

Incremental Sampling-Based Algorithm for Minimum-Violation Motion Planning

Autoři

REYES CASTRO, Luis Ignacio (840 Spojené státy), Pratik CHAUDHARI (840 Spojené státy), Jana TŮMOVÁ (203 Česká republika, garant, domácí), Sertac KARAMAN (840 Spojené státy), Emilio FRAZZOLI (840 Spojené státy) a Daniela RUS (840 Spojené státy)

Vydání

Florence, Italy, Proceedings of the IEEE 52nd Annual Conference on Decision and Control (CDC), 2013, od s. 3217-3224, 8 s. 2013

Nakladatel

IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

paměťový nosič (CD, DVD, flash disk)

Kód RIV

RIV/00216224:14330/13:00081960

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4673-5717-3

ISSN

DOI

http://dx.doi.org/10.1109/CDC.2013.6760374

UT WoS

000352223503105

Klíčová slova anglicky

motion planning; temporal logic; sampling-based planning; formal methods

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 5. 5. 2016 07:01, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Návaznosti

LH11065, projekt VaV

Název: Řízení a ověřování vlastností komplexních hybridních systémů (Akronym: Řízení a ověřování vlastností komplexních hybridní)

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Řízení a ověřování vlastností komplexních hybridních systémů

MUNI/A/0760/2012, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

REYES CASTRO, Luis Ignacio, Pratik CHAUDHARI, Jana TŮMOVÁ, Sertac KARAMAN, Emilio FRAZZOLI a Daniela RUS. Incremental Sampling-Based Algorithm for Minimum-Violation Motion Planning. In Proceedings of the IEEE 52nd Annual Conference on Decision and Control (CDC), 2013. Florence, Italy: IEEE, 2013, s. 3217-3224. ISBN 978-1-4673-5717-3. Dostupné z: https://dx.doi.org/10.1109/CDC.2013.6760374.

@inproceedings{1163972,
   author = {Reyes Castro, Luis Ignacio and Chaudhari, Pratik and Tůmová, Jana and Karaman, Sertac and Frazzoli, Emilio and Rus, Daniela},
   address = {Florence, Italy},
   booktitle = {Proceedings of the IEEE 52nd Annual Conference on Decision and Control (CDC), 2013},
   doi = {http://dx.doi.org/10.1109/CDC.2013.6760374},
   keywords = {motion planning; temporal logic; sampling-based planning; formal methods},
   howpublished = {paměťový nosič},
   language = {eng},
   location = {Florence, Italy},
   isbn = {978-1-4673-5717-3},
   pages = {3217-3224},
   publisher = {IEEE},
   title = {Incremental Sampling-Based Algorithm for Minimum-Violation Motion Planning},
   year = {2013}
}

TY  - JOUR
ID  - 1163972
AU  - Reyes Castro, Luis Ignacio - Chaudhari, Pratik - Tůmová, Jana - Karaman, Sertac - Frazzoli, Emilio - Rus, Daniela
PY  - 2013
TI  - Incremental Sampling-Based Algorithm for Minimum-Violation Motion Planning
PB  - IEEE
CY  - Florence, Italy
SN  - 9781467357173
KW  - motion planning
KW  - temporal logic
KW  - sampling-based planning
KW  - formal methods
N2  - 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.
ER  -

REYES CASTRO, Luis Ignacio, Pratik CHAUDHARI, Jana TŮMOVÁ, Sertac KARAMAN, Emilio FRAZZOLI a Daniela RUS. Incremental Sampling-Based Algorithm for Minimum-Violation Motion Planning. In \textit{Proceedings of the IEEE 52nd Annual Conference on Decision and Control (CDC), 2013}. Florence, Italy: IEEE, 2013, s.~3217-3224. ISBN~978-1-4673-5717-3. Dostupné z: https://dx.doi.org/10.1109/CDC.2013.6760374.

Podrobný výpis o publikaci