research-article

From Uncertainty Data to Robust Policies for Temporal Logic Planning

Authors:

Pier Giuseppe Sessa,

Maryam KamgarpourAuthors Info & Claims

HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)

Pages 157 - 166

https://doi.org/10.1145/3178126.3178136

Published: 11 April 2018 Publication History

Abstract

We consider the problem of synthesizing robust disturbance feedback policies for systems performing complex tasks. We formulate the tasks as linear temporal logic specifications and encode them into an optimization framework via mixed-integer constraints. Both the system dynamics and the specifications are known but affected by uncertainty. The distribution of the uncertainty is unknown, however realizations can be obtained. We introduce a data-driven approach where the constraints are fulfilled for a set of realizations and provide probabilistic generalization guarantees as a function of the number of considered realizations. We use separate chance constraints for the satisfaction of the specification and operational constraints. This allows us to quantify their violation probabilities independently. We compute disturbance feedback policies as solutions of mixed-integer linear or quadratic optimization problems. By using feedback we can exploit information of past realizations and provide feasibility for a wider range of situations compared to static input sequences. We demonstrate the proposed method on two robust motion-planning case studies for autonomous driving.

References

[1]

C. Baier and J-P. Katoen. 2008. Principles of Model Checking. The MIT Press.

Digital Library

[2]

A. Bemporad and M. Morari. 1999. Control of systems integrating logic, dynamics, and constraints. Automatica 35, 3 (1999), 407--427.

Digital Library

[3]

A. Ben-Tal, L. El Ghaoui, and A. Nemirovski. 2009. Robust optimization. Princeton University Press.

[4]

D. Bertsimas and I. Dunning. 2016. Multistage Robust Mixed-Integer Optimization with Adaptive Partitions. Operations Research 64, 4 (2016), 980--998.

Digital Library

[5]

D. Bertsimas and A. Georghiou. 2017. Binary decision rules for multistage adaptive mixed-integer optimization. Mathematical Programming (March 2017).

Digital Library

[6]

A. Biere, K. Heljanko, T. Junttila, T. Latvala, and V. Schuppan. 2006. Linear encodings of bounded LTL model checking. Logical Methods in Computer Science 2, 5 (Nov. 2006), 1--64.

[7]

G. C. Calafiore. 2010. Random convex programs. SIAM Journal on Optimization 20, 6 (2010), 3427--3464.

Digital Library

[8]

G. C. Calafiore, D. Lyons, and L. Fagiano. 2012. On mixed-integer random convex programs. In IEEE Conf. on Decision and Control. 3508--3513.

[9]

M. C. Campi and S. Garatti. 2008. The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization 19, 3 (2008), 1211--1230.

Digital Library

[10]

Marco C. Campi and Simone Garatti. 2018. Wait-and-judge scenario optimization. Mathematical Programming 167, 1 (Jan. 2018), 155--189.

Digital Library

[11]

X. C. Ding, S. L. Smith, C. Belta, and D. Rus. 2011. LTL Control in Uncertain Environments with Probabilistic Satisfaction Guarantees. Proc. 18th IFAC World Congress 44, 1 (2011), 3515--3520.

[12]

P. M. Esfahani, T. Sutter, and J. Lygeros. 2015. Performance Bounds for the Scenario Approach and an Extension to a Class of Non-Convex Programs. IEEE Trans. on Automatic Control 60, 1 (Jan. 2015), 46--58.

[13]

G. E. Fainekos, H. Kress-Gazit, and G.J. Pappas. 2005. Hybrid Controllers for Path Planning: A Temporal Logic Approach. In IEEE Conf. on Decision and Control. 4885--4890.

[14]

S. S. Farahani, R. Majumdar, V. S. Prabhu, and S. E. Z. Soudjani. 2017. Shrinking Horizon Model Predictive Control with chance-constrained signal temporal logic specifications. In American Control Conf. 1740--1746.

[15]

S. S. Farahani, V. Raman, and R. M. Murray. 2015. Robust Model Predictive Control for Signal Temporal Logic Synthesis. IFAC-PapersOnLine 48, 27 (2015), 323--328.

[16]

D. Frick, P. G. Sessa, T. A. Wood, and M. Kamgarpour. 2018. Exploiting submod-uarlity in mixed-integer chance constrained programs. (Jan. 2018), 15 pages. arXiv:1801.03258 (under review).

[17]

D. Frick, T. A. Wood, G. Ulli, and M. Kamgarpour. 2017. Robust Control Policies Given Formal Specifications in Uncertain Environments. IEEE Control Systems Letters 1, 1 (July 2017), 20--25.

[18]

E. A. Gol, M. Lazar, and C. Belta. 2015. Temporal logic model predictive control. Automatica 56 (2015), 78 - 85.

Digital Library

[19]

P. J. Goulart, E. C. Kerrigan, and J. M. Maciejowski. 2006. Optimization over state feedback policies for robust control with constraints. Automatica 42, 4 (2006), 523--533.

Digital Library

[20]

S. Grammatico, X. Zhang, K. Margellos, P. Goulart, and J. Lygeros. 2016. A Scenario Approach for Non-Convex Control Design. IEEE Trans. on Automatic Control 61, 2 (Feb. 2016), 334--345.

[21]

Int. Business Machines Corp. (IBM). 2017. IBM ILOG CPLEX Optimization Studio. (Sept. 2017). http://www.ibm.com/software/commerce/optimization/cplex-optimizer

[22]

M. I. Jordan. 1998. Learning in graphical models. NATO ASI Series, Vol. 89. Springer Science & Business Media.

Digital Library

[23]

M. Kamgarpour, S. Summers, and J. Lygeros. 2013. Control Design for Specifications on Stochastic Hybrid Systems. In Proc. 16th Int. Conf. on Hybrid Systems: Computation and Control. 303--312.

Digital Library

[24]

M. Kamgarpour, T. A. Wood, S. Summers, and J. Lygeros. 2017. Control synthesis for stochastic systems given automata specifications defined by stochastic sets. Automatica 76 (2017), 177--182.

[25]

S. Karaman, R. G. Sanfelice, and E. Frazzoli. 2008. Optimal control of Mixed Logical Dynamical systems with Linear Temporal Logic specifications. In IEEE Conf. on Decision and Control. 2117--2122.

[26]

Z. Kong, A. Jones, A. M. Ayala, E. A. Gol, and Calin Belta. 2014. Temporal Logic Inference for Classification and Prediction from Data. In Proc. 17th Int. Conf. on Hybrid Systems: Computation and Control. 273--282.

Digital Library

[27]

H. Kress-Gazit, G. E. Fainekos, and G. J. Pappas. 2009. Temporal-Logic-Based Reactive Mission and Motion Planning. IEEE Trans. on Robotics 25, 6 (Dec. 2009), 1370--1381.

Digital Library

[28]

M. Lahijanian, S. B. Andersson, and C. Belta. 2012. Temporal Logic Motion Planning and Control With Probabilistic Satisfaction Guarantees. IEEE Trans. on Robotics 28, 2 (April 2012), 396--409.

Digital Library

[29]

J. Löfberg. 2004. YALMIP: a toolbox for modeling and optimization in MATLAB. In IEEE Int. Symp. on Computer Aided Control Systems Design. 284--289.

[30]

K. Margellos, P. Goulart, and J. Lygeros. 2014. On the Road Between Robust Optimization and the Scenario Approach for Chance Constrained Optimization Problems. IEEE Trans. on Automatic Control 59, 8 (Aug. 2014), 2258--2263.

[31]

A. Pnueli. 1977. The Temporal Logic of Programs. In Proc. 18th Ann. Symp. on Foundations of Computer Science. 46--57.

Digital Library

[32]

K. Postek and D. den Hertog. 2016. Multistage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty Set. INFORMS Journal on Computing 28, 3 (2016), 553--574.

Digital Library

[33]

V. Raman, A. Donzé, D. Sadigh, R. M. Murray, and S. A. Seshia. 2015. Reactive Synthesis from Signal Temporal Logic Specifications. In Proc. 18th Int. Conf. on Hybrid Systems: Computation and Control. 239--248.

Digital Library

[34]

D. Sadigh and A. Kapoor. 2016. Safe Control under Uncertainty with Probabilistic Signal Temporal Logic. In Proc. Robotics: Science and Systems. Ann Arbor, Michigan, USA.

[35]

G. Schildbach, L. Fagiano, and M. Morari. 2013. Randomized Solutions to Convex Programs with Multiple Chance Constraints. SIAM Journal on Optimization 23, 4 (2013), 2479--2501.

[36]

A. Shapiro. 2013. Sample Average Approximation. Springer US, Boston, MA, 1350--1355.

[37]

P. Tabuada and G. J. Pappas. 2006. Linear Time Logic Control of Discrete-Time Linear Systems. IEEE Trans. on Automatic Control 51, 12 (Dec. 2006), 1862--1877.

[38]

E. M. Wolff, U. Topcu, and R. M. Murray. 2012. Robust control of uncertain Markov Decision Processes with temporal logic specifications. In IEEE Conf. on Decision and Control. 3372--3379.

[39]

E. M. Wolff, U. Topcu, and R. M. Murray. 2014. Optimization-based trajectory generation with linear temporal logic specifications. In IEEE Int. Conf. on Robotics and Automation. 5319--5325.

[40]

X. Zhang, S. Grammatico, G. Schildbach, P. Goulart, and J. Lygeros. 2015. On the sample size of random convex programs with structured dependence on the uncertainty. Automatica 60 (2015), 182--188.

Digital Library

Cited By

Gao YZhou CAbate AJohansson K(2024)Adaptive Task Planning and Formal Control Synthesis Using Temporal Logic TreesReal Time and Such10.1007/978-3-031-73751-0_7(64-78)Online publication date: 23-Oct-2024
https://doi.org/10.1007/978-3-031-73751-0_7
Gao YAbate AJiang FGiacobbe MXie LJohansson K(2022)Temporal Logic Trees for Model Checking and Control Synthesis of Uncertain Discrete-Time SystemsIEEE Transactions on Automatic Control10.1109/TAC.2021.311833567:10(5071-5086)Online publication date: Oct-2022
https://doi.org/10.1109/TAC.2021.3118335
Ahn HChen CMitchell IKamgarpour M(2022)Safe Motion Planning Against Multimodal Distributions Based on a Scenario ApproachIEEE Control Systems Letters10.1109/LCSYS.2021.30896416(1142-1147)Online publication date: 2022
https://doi.org/10.1109/LCSYS.2021.3089641
Show More Cited By

Index Terms

From Uncertainty Data to Robust Policies for Temporal Logic Planning
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Stochastic control and optimization
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Sample complexity and generalization bounds

Recommendations

Brief paper: Constrained linear system with disturbance: Convergence under disturbance feedback

This paper proposes a disturbance-based control parametrization under the Model Predictive Control framework for constrained linear discrete time systems with bounded additive disturbances. The proposed approach has the same feasible domain as that ...
Data-Driven Robust Chance Constrained Problems: A Mixture Model Approach

This paper discusses the mixture distribution-based data-driven robust chance constrained problem. We construct a data-driven mixture distribution-based uncertainty set from the perspective of simultaneously estimating higher-order moments. Then, we ...
Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex---concave fractional ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)

April 2018

296 pages

ISBN:9781450356428

DOI:10.1145/3178126

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 April 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

SNSF

Conference

HSCC '18

Sponsor:

SIGBED

HSCC '18: 21st International Conference on Hybrid Systems: Computation and Control

April 11 - 13, 2018

Porto, Portugal

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
178
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gao YZhou CAbate AJohansson K(2024)Adaptive Task Planning and Formal Control Synthesis Using Temporal Logic TreesReal Time and Such10.1007/978-3-031-73751-0_7(64-78)Online publication date: 23-Oct-2024
https://doi.org/10.1007/978-3-031-73751-0_7
Gao YAbate AJiang FGiacobbe MXie LJohansson K(2022)Temporal Logic Trees for Model Checking and Control Synthesis of Uncertain Discrete-Time SystemsIEEE Transactions on Automatic Control10.1109/TAC.2021.311833567:10(5071-5086)Online publication date: Oct-2022
https://doi.org/10.1109/TAC.2021.3118335
Ahn HChen CMitchell IKamgarpour M(2022)Safe Motion Planning Against Multimodal Distributions Based on a Scenario ApproachIEEE Control Systems Letters10.1109/LCSYS.2021.30896416(1142-1147)Online publication date: 2022
https://doi.org/10.1109/LCSYS.2021.3089641
Oh YCho KChoi YOh S(2021)Chance-Constrained Multilayered Sampling-Based Path Planning for Temporal Logic-Based MissionsIEEE Transactions on Automatic Control10.1109/TAC.2020.304427366:12(5816-5829)Online publication date: Dec-2021
https://doi.org/10.1109/TAC.2020.3044273
Lefkopoulos VKamgarpour M(2021)Trajectory planning under environmental uncertainty with finite-sample safety guaranteesAutomatica10.1016/j.automatica.2021.109754131(109754)Online publication date: Sep-2021
https://doi.org/10.1016/j.automatica.2021.109754
Jiang FGao YXie LJohansson K(2020)Ensuring safety for vehicle parking tasks using Hamilton-Jacobi reachability analysis2020 59th IEEE Conference on Decision and Control (CDC)10.1109/CDC42340.2020.9304186(1416-1421)Online publication date: 14-Dec-2020
https://doi.org/10.1109/CDC42340.2020.9304186
Lefkopoulos VKamgarpour M(2019)Using Uncertainty Data in Chance-Constrained Trajectory Planning2019 18th European Control Conference (ECC)10.23919/ECC.2019.8795823(2264-2269)Online publication date: Jun-2019
https://doi.org/10.23919/ECC.2019.8795823

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten