A Caltech Library Service

Optimal Path Planning for ω-regular Objectives with Abstraction-Refinement

Leong, Yoke Peng and Prabhakar, Pavithra (2019) Optimal Path Planning for ω-regular Objectives with Abstraction-Refinement. In: 2019 International Conference on Robotics and Automation (ICRA). IEEE , Piscataway, NJ, pp. 7683-7689. ISBN 978-1-5386-6027-0.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


This paper presents an abstraction-refinement based framework for optimal controller synthesis of discrete-time systems with respect to ω-regular objectives. It first abstracts the discrete-time “concrete” system into a finite weighted transition system using a finite partition of the state-space. Then, a two-player mean payoff parity game is solved on the product of the abstract system and the Büchi automaton corresponding to the ω-regular objective, to obtain an optimal “abstract” controller that satisfies the ω-regular objective. The abstract controller is guaranteed to be implementable in the concrete discrete-time system, with a sub-optimal cost. The abstraction is refined with finer partitions to reduce the suboptimality. In contrast to existing formal controller synthesis algorithms based on abstractions, this technique provides an upper bound on the trajectory cost when implementing the suboptimal controller. A robot surveillance scenario is presented to illustrate the feasibility of the approach.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Leong, Yoke Peng0000-0001-8560-8856
Additional Information:© 2019 IEEE. Pavithra Prabhakar was partially supported by NSF CAREER Award No. 1552668 and ONR YIP Award No. N00014-17-1-257.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-17-1-257
Record Number:CaltechAUTHORS:20190815-125325649
Persistent URL:
Official Citation:Y. P. Leong and P. Prabhakar, "Optimal Path Planning for ω-regular Objectives with Abstraction-Refinement," 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada, 2019, pp. 7683-7689. doi: 10.1109/ICRA.2019.8794209
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97923
Deposited By: Tony Diaz
Deposited On:15 Aug 2019 19:59
Last Modified:16 Nov 2021 17:35

Repository Staff Only: item control page