research-article

A stochastic reach-avoid problem with random obstacles

Authors:

Maryam Kamgarpour,

Claire TomlinAuthors Info & Claims

HSCC '11: Proceedings of the 14th international conference on Hybrid systems: computation and control

Pages 251 - 260

https://doi.org/10.1145/1967701.1967738

Published: 12 April 2011 Publication History

Abstract

We present a dynamic programming based solution to a stochastic reachability problem for a controlled discrete-time stochastic hybrid system. A sum-multiplicative cost function is introduced along with a corresponding dynamic recursion which quantifies the probability of hitting a target set at some point during a finite time horizon, while avoiding an obstacle set during each time step preceding the target hitting time. In contrast with earlier works which consider the reach and avoid sets as both deterministic and time invariant, we consider the avoid set to be both time-varying and probabilistic. Optimal reach-avoid control policies are derived as the solution to an optimal control problem via dynamic programming. A computational example motivated by aircraft motion planning is provided.

References

[1]

A. Abate, S. Amin, M. Prandini, J. Lygeros, and S. Sastry. Computational approaches to reachability analysis of stochastic hybrid systems. In A. Bemporad, A. Bicchi, and G. C. Buttazzo, editors, Hybrid Systems: Computation and Control, volume 4416 of Lecture Notes in Computer Science, pages 4--17. Springer, 2007.

Digital Library

[2]

A. Abate, M. Prandini, J. Lygeros, and S. Sastry. Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems. Automatica, 44(11):2724--2734, November 2008.

Digital Library

[3]

S. A. Amburn and P. L. Wolf. VIL density as a hail indicator. Weather and Forecasting, 12(3):473--478, 1997.

[4]

S. Amin, A. Abate, M. Prandini, J. Lygeros, and S. Sastry. Reachability analysis for controlled discrete time stochastic hybrid systems. In Hespanha and Tiwari {15}, pages 49--63.

Digital Library

[5]

J.-P. Aubin. Viability theory. Birkhauser Boston Inc., Cambridge, MA, USA, 1991.

Digital Library

[6]

R. Bellman. Dynamic Programming. Princeton University Press, Princeton, New Jersey, USA, 1957.

[7]

D. P. Bertsekas and S. E. Shreve. Stochastic Optimal Control: The Discrete-Time Case. Athena Scientific, February 2007.

Digital Library

[8]

B. Boudevillain and H. Andrieu. Assessment of vertically integrated liquid (VIL) water content radar measurement. Journal of Atmospheric and Oceanic Technology, 20(6):807--819, 2003.

[9]

M. L. Bujorianu and J. Lygeros. Reachability questions in piecewise deterministic markov processes. In O. Maler and A. Pnueli, editors, Hybrid Systems: Computation and Control, volume 2623 of Lecture Notes in Computer Science, pages 126--140. Springer, 2003.

Digital Library

[10]

N. Cressie and G. M. Laslett. Random set theory and problems of modeling. SIAM Review, 29(4):pp. 557--574, December 1987.

Digital Library

[11]

M. Davis. Markov Models and Optimization. Chapman &#38; Hall, London, 1993.

[12]

J. Evans, K. Carusone, M. Wolfson, B. Crowe, D. Meyer, and D. Klingle-Wilson. The Corridor Integrated Weather System (CIWS). In 10th Conference on Aviation, Range, and Aerospace Meteorology, 2001.

[13]

Y. Gao, J. Lygeros, and M. Quincampoix. On the Reachability Problem for Uncertain Hybrid Systems. IEEE Transactions on Automatic Control, 52(9):1572--1586, September 2007.

[14]

M. K. Ghosh, A. Arapostathis, and S. I. Marcus. Ergodic control of switching diffusions. SIAM J. Control Optim., 35(6):1952--1988, November 1997.

Digital Library

[15]

J. P. Hespanha and A. Tiwari, editors. Hybrid Systems: Computation and Control, volume 3927 of Lecture Notes in Computer Science. Springer, 2006.

Digital Library

[16]

J. Hu, J. Lygeros, and S. Sastry. Towards a theory of stochastic hybrid systems. In N. A. Lynch and B. H. Krogh, editors, Hybrid Systems: Computation and Control, volume 1790 of Lecture Notes in Computer Science, pages 160--173. Springer, 2000.

Digital Library

[17]

J. Lygeros. On reachability and minimum cost optimal control. Automatica, 40(6):917--927, 2004.

Digital Library

[18]

G. Matheron. Random Sets and Integral Geometry. Wiley, New York, 1975.

[19]

I. Mitchell. The flexible, extensible and efficient toolbox of level set methods. J. Sci. Comput., 35(2-3):300--329, 2008.

Digital Library

[20]

I. Mitchell and C. Tomlin. Level set methods for computation in hybrid systems. In Hybrid Systems: Computation and Control, pages 310--323, London, UK, 2000. Springer-Verlag.

Digital Library

[21]

I. Molchanov. Theory of Random Sets. Springer, New York, 2005.

[22]

F. Ramponi, D. Chatterjee, S. Summers, and J. Lygeros. On the connections between PCTL and dynamic programming. In HSCC '10: Proceedings of the 13th ACM international conference on Hybrid systems: computation and control, pages 253--262, New York, NY, USA, 2010. ACM.

Digital Library

[23]

W. Rudin. Real and complex analysis, 3rd ed. McGraw-Hill, Inc., New York, NY, USA, 1987.

Digital Library

[24]

D. Stoyan. Random sets: Models and statistics. International Statistical Review, 66(1):pp. 1--27, April 1998.

[25]

S. Summers and J. Lygeros. Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem. Automatica, 46(12):1951--1961, 2010.

Digital Library

[26]

C. Tomlin, J. Lygeros, and S. Sastry. A Game Theoretic Approach to Controller Design for Hybrid Systems. Proceedings of IEEE, 88:949--969, July 2000.

[27]

C. Tomlin, G. J. Pappas, and S. Sastry. Conflict resolution for air traffic management: a study in multiagent hybrid systems. Automatic Control, IEEE Transactions on, 43(4):509--521, 1998.

[28]

C. J. Tomlin, I. Mitchell, A. M. Bayen, and M. Oishi. Computational techniques for the verification of hybrid systems. Proceedings of the IEEE, 91(7):986--1001, July 2003.

Cited By

Bansal AKim HYu SLi BHovakimyan NCaccamo MSha L(2024)Perception simplex: Verifiable collision avoidance in autonomous vehicles amidst obstacle detection faultsSoftware Testing, Verification and Reliability10.1002/stvr.1879Online publication date: 28-May-2024
https://doi.org/10.1002/stvr.1879
Guitart ADelahaye DCamino FFeron E(2023)Collaborative Generation of Local Conflict Free Trajectories With Weather Hazards AvoidanceIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.328919124:11(12831-12842)Online publication date: Nov-2023
https://doi.org/10.1109/TITS.2023.3289191
Yao CChen S(2023)A Dynamic Obstacle Avoidance Method for Mobile Robots Based on Stochastic Reachable SetsIECON 2023- 49th Annual Conference of the IEEE Industrial Electronics Society10.1109/IECON51785.2023.10312012(1-6)Online publication date: 16-Oct-2023
https://doi.org/10.1109/IECON51785.2023.10312012
Show More Cited By

Index Terms

A stochastic reach-avoid problem with random obstacles
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation

Recommendations

The stochastic reach-avoid problem and set characterization for diffusions

In this article we approach a class of stochastic reachability problems with state constraints from an optimal control perspective. Preceding approaches to solving these reachability problems are either confined to the deterministic setting or address ...
Stochastic system controller synthesis for reachability specifications encoded by random sets

We consider a reach-avoid specification for a stochastic hybrid dynamical system defined as reaching a goal set at some finite time, while avoiding an unsafe set at all previous times. In contrast with earlier works which consider the target and avoid ...
Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem

We present a dynamic programming based solution to a probabilistic reach-avoid problem for a controlled discrete time stochastic hybrid system. We address two distinct interpretations of the reach-avoid problem via stochastic optimal control. In the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '11: Proceedings of the 14th international conference on Hybrid systems: computation and control

April 2011

330 pages

ISBN:9781450306294

DOI:10.1145/1967701

General Chair:
Marco Caccamo
University of Illinois at Urbana-Champaign, USA
,
Program Chairs:
Emilio Frazzoli
Massachusetts Institute of Technology, USA
,
Radu Grosu
State University of New York at Stony Brook, USA

Copyright © 2011 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

In-Cooperation

IEEE

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 April 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

HSCC '11

Sponsor:

SIGBED

HSCC '11: Hybrid Systems: Computation and Control

April 12 - 14, 2011

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
360
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)2

Reflects downloads up to 24 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bansal AKim HYu SLi BHovakimyan NCaccamo MSha L(2024)Perception simplex: Verifiable collision avoidance in autonomous vehicles amidst obstacle detection faultsSoftware Testing, Verification and Reliability10.1002/stvr.1879Online publication date: 28-May-2024
https://doi.org/10.1002/stvr.1879
Guitart ADelahaye DCamino FFeron E(2023)Collaborative Generation of Local Conflict Free Trajectories With Weather Hazards AvoidanceIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.328919124:11(12831-12842)Online publication date: Nov-2023
https://doi.org/10.1109/TITS.2023.3289191
Yao CChen S(2023)A Dynamic Obstacle Avoidance Method for Mobile Robots Based on Stochastic Reachable SetsIECON 2023- 49th Annual Conference of the IEEE Industrial Electronics Society10.1109/IECON51785.2023.10312012(1-6)Online publication date: 16-Oct-2023
https://doi.org/10.1109/IECON51785.2023.10312012
Bansal AKim HYu SLi BHovakimyan NCaccamo MSha L(2022)Verifiable Obstacle Detection2022 IEEE 33rd International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE55969.2022.00017(61-72)Online publication date: Oct-2022
https://doi.org/10.1109/ISSRE55969.2022.00017
Pan ZYuan MWang RWen JBi QYuan JZhang X(2022)D$$^2$$WA: “dynamic” DWA for motion planning of mobile robots in dynamic environmentsInternational Journal of Dynamics and Control10.1007/s40435-022-01092-311:6(3136-3144)Online publication date: 20-Dec-2022
https://doi.org/10.1007/s40435-022-01092-3
Bujorianu MWisniewski RBoulougouris E(2021)Stochastic Safety for Random Dynamical Systems2021 American Control Conference (ACC)10.23919/ACC50511.2021.9483422(1340-1345)Online publication date: 25-May-2021
https://doi.org/10.23919/ACC50511.2021.9483422
Vinod AOishi M(2021)Probabilistic Occupancy via Forward Stochastic Reachability for Markov Jump Affine SystemsIEEE Transactions on Automatic Control10.1109/TAC.2020.301412766:7(3068-3083)Online publication date: Jul-2021
https://doi.org/10.1109/TAC.2020.3014127
Andrés EKamgarpour MSoler MSanjurjo-Rivo MGonzález-Arribas D(2021)RRT*-Based Algorithm for Trajectory Planning Considering Probabilistic Weather ForecastsAir Traffic Management and Systems IV10.1007/978-981-33-4669-7_14(245-258)Online publication date: 24-Mar-2021
https://doi.org/10.1007/978-981-33-4669-7_14
Lu YKamgarpour M(2020)Safe Mission Planning under Dynamical Uncertainties2020 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA40945.2020.9196515(2209-2215)Online publication date: May-2020
https://doi.org/10.1109/ICRA40945.2020.9196515
Mothes F(2019)Trajectory Planning in Time-Varying Adverse Weather for Fixed-Wing Aircraft Using Robust Model Predictive ControlAerospace10.3390/aerospace60600686:6(68)Online publication date: 5-Jun-2019
https://doi.org/10.3390/aerospace6060068
Show More Cited By

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