More Web Proxy on the site http://driver.im/

research-article

Public Access

Sampling-based Approximate Optimal Control Under Temporal Logic Constraints

Authors:

Ufuk TopcuAuthors Info & Claims

HSCC '17: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control

Pages 227 - 235

https://doi.org/10.1145/3049797.3049820

Published: 13 April 2017 Publication History

Abstract

We investigate a sampling-based method for optimal control of continuous-time and continuous-state (possibly nonlinear) systems under co-safe linear temporal logic specifications. We express the temporal logic specification as a deterministic, finite automaton (the specification automaton), and link the automaton's discrete transitions to the continuous system state as it passes through specified regions. The optimal hybrid controller is characterized by a set of coupled partial differential equations. Because these equations are difficult to solve exactly in practice in all cases, we propose instead a sampling based technique to solve for an approximate controller through approximate value iteration. We adopt model reference adaptive search---an importance sampling optimization algorithm---to determine the mixing weights of the approximate value function expressed in a finite basis. Under mild technical assumptions, the algorithm converges, with probability one, to an optimal weight that ensures the satisfaction of temporal logic constraints, while minimizing an upper bound for the optimal cost. We demonstrate the correctness and efficiency of the method through numerical experiments, including temporal logic planning for a linear system, and a nonlinear mobile robot.

References

[1]

M. Abu-Khalaf and F. L. Lewis. Nearly optimal control laws for nonlinear systems with saturating actuators using a neural network HJB approach. Automatica, 41(5):779--791, 2005.

Digital Library

[2]

R. Alur, T. A. Henzinger, G. Lafferriere, and G. J. Pappas. Discrete abstractions of hybrid systems. Proceedings of the IEEE, 88(7):971--984, July 2000.

[3]

G. E. Fainekos, A. Girard, H. Kress-Gazit, and G. J. Pappas. Temporal logic motion planning for dynamic robots. Automatica, 45(2):343--352, 2009.

Digital Library

[4]

P. Gastin and D. Oddoux. Fast LTL to Büchi automata translation. In G. Berry, H. Comon, and A. Finkel, editors, International Conference on Computer Aided Verification (CAV'01), volume 2102 of Lecture Notes in Computer Science, pages 53--65, Paris, France, July 2001. Springer.

[5]

L. C. G. J. M. Habets and C. Belta. Temporal logic control for piecewise-affine hybrid systems on polytopes. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS), pages 195--202, July 2010.

[6]

M. Hauschild and M. Pelikan. An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation, 1(3):111--128, 2011.

[7]

S. Hedlund and A. Rantzer. Optimal control of hybrid systems. In IEEE Conference on Decision and Control (CDC), volume 4, pages 3972--3977, 1999.

[8]

S. Hedlund and A. Rantzer. Convex dynamic programming for hybrid systems. IEEE Transactions on Automatic Control, 47(9):1536--1540, 2002.

[9]

J. Hu, M. C. Fu, and S. I. Marcus. A model reference adaptive search method for global optimization. Operations Research, 55(3):549--568, 2007.

Digital Library

[10]

M. Johansson and A. Rantzer. Computation of piecewise quadratic Lyapunov functions for hybrid systems. IEEE Transactions on Automatic Control, 43(4):555--559, Apr. 1998.

[11]

N. Kariotoglou, S. Summers, T. Summers, M. Kamgarpour, and J. Lygeros. Approximate dynamic programming for stochastic reachability. In European Control Conference (ECC), pages 584--589, July 2013.

[12]

M. Kloetzer and C. Belta. A fully automated framework for control of linear systems from temporal logic specifications. IEEE Transactions on Automatic Control, 53(1):287--297, 2008.

[13]

M. Kobilarov. Cross-entropy motion planning. The International Journal of Robotics Research, 31(7):855--871, 2012.

Digital Library

[14]

M. Kobilarov. Sample complexity bounds for iterative stochastic policy optimization. In Advances in Neural Information Processing Systems, pages 3114--3122, 2015.

[15]

O. Kupferman and M. Y. Vardi. Model checking of safety properties. Formal Methods in System Design, 19(3):291--314, Nov. 2001.

Digital Library

[16]

T. Latvala. Efficient model checking of safety properties. In T. Ball and S. K. Rajamani, editors, International SPIN Workshop on Model Checking of Software, volume 2648 of Lecture Notes in Computer Science, pages 74--88. Springer, 2003.

[17]

F. Lewis, S. Jagannathan, and A. Yesildirak. Neural network control of robot manipulators and non-linear systems. CRC Press, 1998.

[18]

J. Liu and N. Ozay. Abstraction, discretization, and robustness in temporal logic control of dynamical systems. In International Conference on Hybrid Systems: Computation and Control (HSCC), pages 293--302. ACM, 2014.

Digital Library

[19]

S. C. Livingston, E. M. Wolff, and R. M. Murray. Cross-entropy temporal logic motion planning. In International Conference on Hybrid Systems: Computation and Control, pages 269--278. ACM, 2015.

Digital Library

[20]

I. Papusha, J. Fu, U. Topcu, and R. M. Murray. Automata theory meets approximate dynamic programming: Optimal control with temporal logic constraints. In IEEE Conference on Decision and Control (CDC), Dec. 2016.

[21]

N. Piterman, A. Pnueli, and Y. Sa'ar. Synthesis of reactive (1) designs. In International Workshop on Verification, Model Checking, and Abstract Interpretation, pages 364--380. Springer, 2006.

[22]

R. Reemtsen and J.-J. Rückmann. Semi-infinite programming, volume 25. Springer Science & Business Media, 1998.

[23]

R. Y. Rubinstein and D. P. Kroese. The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning. Springer Science & Business Media, 2013.

[24]

S. L. Smith, J. Tumova, C. Belta, and D. Rus. Optimal path planning for surveilance with temporal-logic constraints. International Journal of Robotics Research, 30(14):1695--1708, Dec. 2011.

Digital Library

[25]

K. Weierstrass. Über die analytische Darstellbarkheit sogenannter willhülicher Functionen einer reellen Veranderlichen. Berliner Berichte, 1885.

[26]

E. M. Wolff, U. Topcu, and R. M. Murray. Automaton-guided controller synthesis for nonlinear systems with temporal logic. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4332--4339, Nov. 2013.

[27]

T. Wongpiromsarn, U. Topcu, and R. M. Murray. Receding horizon temporal logic planning. IEEE Transactions on Automatic Control, 57(11):2817--2830, Nov. 2012.

[28]

X. Xu and P. J. Antsaklis. Optimal control of switched systems based on parameterization of the switching instants. IEEE Transactions on Automatic Control, 49(1):2--16, 2004.

Cited By

Cohen MSerlin ZLeahy KBelta C(2023)Temporal logic guided safe model-based reinforcement learning: A hybrid systems approachNonlinear Analysis: Hybrid Systems10.1016/j.nahs.2022.10129547(101295)Online publication date: Feb-2023
https://doi.org/10.1016/j.nahs.2022.101295
Wen MTopcu U(2021)Constrained Cross-Entropy Method for Safe Reinforcement LearningIEEE Transactions on Automatic Control10.1109/TAC.2020.301593166:7(3123-3137)Online publication date: Jul-2021
https://doi.org/10.1109/TAC.2020.3015931
Chou GOzay NBerenson D(2021)Learning temporal logic formulas from suboptimal demonstrations: theory and experimentsAutonomous Robots10.1007/s10514-021-10004-xOnline publication date: 30-Jul-2021
https://doi.org/10.1007/s10514-021-10004-x
Show More Cited By

Index Terms

Sampling-based Approximate Optimal Control Under Temporal Logic Constraints
1. Computer systems organization
  1. Embedded and cyber-physical systems
2. Theory of computation
  1. Models of computation
    1. Timed and hybrid models

Recommendations

On solving hybrid optimal control problems with higher index DAEs
The 17th British-French-German Conference on Optimization, 15-17 June 2015, London, United Kingdom

The paper deals with hybrid optimal control problems described by higher index differential–algebraic equations DAEs. We introduce a numerical procedure for solving these problems. The procedure has the following features: it is based on the ...
Efficient Regular Linear Temporal Logic Using Dualization and Stratification
TIME '12: Proceedings of the 2012 19th International Symposium on Temporal Representation and Reasoning

We study efficient translations of Regular Linear Temporal Logic (\RLTL) into automata on infinite words. \RLTL is a temporal logic that fuses Linear Temporal Logic (LTL) with regular expressions, extending its expressive power to all $\omega$-regular ...
On Ω-automata and temporal logic
STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

We study here the use of different representation for infinitary regular languages in extended temporal logic. We focus on three different kinds of acceptance conditions for finite automata on infinite words, due to Büchi, Streett, and Emerson and Lei (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '17: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control

April 2017

288 pages

ISBN:9781450345903

DOI:10.1145/3049797

Program Chairs:
Goran Frehse
University Grenoble Alpes
,
Sayan Mitra
University of Illinois at Urbana Champaign

Copyright © 2017 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: 13 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

HSCC '17

Sponsor:

SIGBED

HSCC '17: 20th International Conference on Hybrid Systems: Computation and Control

April 18 - 20, 2017

Pennsylvania, Pittsburgh, USA

Acceptance Rates

HSCC '17 Paper Acceptance Rate 29 of 76 submissions, 38%;

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
542
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)9

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cohen MSerlin ZLeahy KBelta C(2023)Temporal logic guided safe model-based reinforcement learning: A hybrid systems approachNonlinear Analysis: Hybrid Systems10.1016/j.nahs.2022.10129547(101295)Online publication date: Feb-2023
https://doi.org/10.1016/j.nahs.2022.101295
Wen MTopcu U(2021)Constrained Cross-Entropy Method for Safe Reinforcement LearningIEEE Transactions on Automatic Control10.1109/TAC.2020.301593166:7(3123-3137)Online publication date: Jul-2021
https://doi.org/10.1109/TAC.2020.3015931
Chou GOzay NBerenson D(2021)Learning temporal logic formulas from suboptimal demonstrations: theory and experimentsAutonomous Robots10.1007/s10514-021-10004-xOnline publication date: 30-Jul-2021
https://doi.org/10.1007/s10514-021-10004-x
Varnai PDimarogonas D(2019)Prescribed Performance Control Guided Policy Improvement for Satisfying Signal Temporal Logic Tasks2019 American Control Conference (ACC)10.23919/ACC.2019.8814999(286-291)Online publication date: Jul-2019
https://doi.org/10.23919/ACC.2019.8814999
Wen MTopcu U(2018)Constrained cross-entropy method for safe reinforcement learningProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327757.3327846(7461-7471)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327757.3327846

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents