Skip to main content
SpringerLink
Log in

A Tree Structure Approach to Reachability Analysis

  • Conference paper
  • First Online:
Advances in Numerical Methods for Hyperbolic Balance Laws and Related Problems (YR 2021)

Part of the book series: SEMA SIMAI Springer Series ((SEMA SIMAI,volume 32))

Included in the following conference series:

  • 159 Accesses

Abstract

Reachability analysis is a powerful tool when it comes to capturing the behaviour, thus verifying the safety, of autonomous systems. However, general-purpose methods, such as Hamilton-Jacobi approaches, suffer from the curse of dimensionality. In this paper, we mitigate this problem for systems of moderate dimension and we propose a new algorithm based on a tree structure approach with geometric pruning. The numerical examples will include a comparison with a standard finite-difference method for linear and nonlinear problems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 199.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Kunisch, K., Volkwein, S., Xie, L.: HJB-POD-based feedback design for the optimal control of evolution problems. SIAM J. Appl. Dyn. Syst. 3(4), 701–722 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alla, A., Falcone, M., Volkwein, S.: Error analysis for POD approximations of infinite horizon problems via the dynamic programming approach. SIAM J. Control Optim. 55(5), 3091–3115 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alla, A., Falcone, M., Saluzzi, L.: An efficient DP algorithm on a tree-structure for finite horizon optimal control problems. SIAM J. Sci. Comput. 41(4), A2384–A2406 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  4. Alla, A., Saluzzi, L.: A HJB-POD approach for the control of nonlinear PDEs on a tree structure. Appl. Numer. Math. 155, 192–207 (2020). Structural Dynamical Systems: Computational Aspects held in Monopoli (Italy) on 12–15 June 2018. https://doi.org/10.1016/j.apnum.2019.11.023

  5. Kalise, D., Kunisch, K.: Polynomial approximation of high-dimensional Hamilton-Jacobi-Bellman equations and applications to feedback control of semilinear parabolic PDEs. SIAM J. Sci. Comput. 40(2), A629–A652 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  6. McEneaney, W.M.: A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J. Control Optim. 46(4), 1239–1276 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. McEneaney, W.M.: Convergence rate for a curse-of-dimensionality-free method for Hamilton-Jacobi-Bellman PDEs represented as maxima of quadratic forms. SIAM J. Control Optim. 48(4), 2651–2685 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chow, Y.T., Darbon, J., Osher, S., Yin, W.: Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations. J. Comput. Phys. 387, 376–409 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  9. Yegorov, I., Dower, P.M.: Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations. Appl. Math. Optim. 83(1), 1–49 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  10. Darbon, J., Langlois, G.P., Meng, T.: Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures. Res. Math. Sci. 7(3), 1–50 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  11. Darbon, J., Meng, T.: On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations. J. Comput. Phys. 425, 109907 (2021)

    Google Scholar 

  12. Dolgov, S., Kalise, D., Kunisch, K.K.: Tensor decomposition methods for high-dimensional Hamilton-Jacobi-Bellman equations. SIAM J. Sci. Comput. 43(3), A1625–A1650 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  13. Oster, M., Sallandt, L., Schneider, R.: Approximating optimal feedback controllers of finite horizon control problems using hierarchical tensor formats. SIAM J. Sci. Comput. 44(3):B746–B770 (2022). https://doi.org/10.1137/21M1412190

  14. Bokanowski, O., Garcke, J., Griebel, M., Klompmaker, I.: An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations. J. Sci. Comput. 55(3), 575–605 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Mitchell, B.A., Tomlin, I.M.C.: A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games. IEEE Trans. Autom. Control 50(7), 947–957 (2005)

    Google Scholar 

  16. Chen, M., Herbert, S., Vashishtha, M., Bansal, S., Tomlin, C.: Decomposition of reachable sets and tubes for a class of nonlinear systems. IEEE Trans. Autom. Control 63(11), 3675–3688 (2018)

    Google Scholar 

  17. Althoff, M., Krogh, B.: Reachability analysis of nonlinear differential-algebraic systems. IEEE Trans. Autom. Control 59(2), 371–383 (2013)

    Google Scholar 

  18. Yang, L., Ozay, N.: Scalable zonotopic under-approximation of backward reachable sets for uncertain linear systems. IEEE Control Syst. Lett. 6, 1555–1560 (2021)

    Article  MathSciNet  Google Scholar 

  19. Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhäuser, Basel (1997)

    Google Scholar 

  20. Crandall, M.G., Lions, P.-L.: Viscosity solutions of Hamilton-Jacobi equations. Trans. Am. Math. Soc. 277(1), 1–42 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  21. Chen, M., Tomlin, C.J.: Hamilton-Jacobi reachability: some recent theoretical advances and applications in unmanned airspace management. Ann. Rev. Control Robot. Auton. Syst. 1(1), 333–358 (2018)

    Article  Google Scholar 

  22. Cannarsa, P., Sinestrari, C.: Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control, vol. 58. Springer Science & Business Media (2004)

    Google Scholar 

  23. Borrelli, F., Bemporad, A., Morari, M.: Predictive Control for Linear and Hybrid Systems. Cambridge University Press (2017)

    Google Scholar 

  24. Rockafellar, R.T.: Convex Analysis, vol. 18. Princeton University Press (1970)

    Google Scholar 

  25. Mitchell, I.M.: A toolbox of level set methods. https://www.cs.ubc.ca/~mitchell/ToolboxLS/

  26. Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Soft. (TOMS) 22(4), 469–483 (1996)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

AA is a member of the InDAMGNCS activity group. AA wants to acknowledge the Overseases Mobility program financed by Università Ca’ Foscari Venezia. Funding for this research was also supported through an Australian Research Council Linkage Project grant (Grant number: LP190100104), an Asian Office of Aerospace Research and Development grant (Grant number: AOARD22IOA074), and the Australian Commonwealth Government through the Ingenium Scholarship. Acknowledgement is also given to BAE systems as a collaborator in the aforementioned research grants.

Author information

Authors and Affiliations

  1. Department of Molecular Sciences and Nanosystems, Universitá Ca’ Foscari Venezia, Venice, Italy

    Alessandro Alla

  2. Department of Electrical and Electronic Engineering, The University of Melbourne, Melbourne, Australia

    Peter M. Dower & Vincent Liu

Authors
  1. Alessandro Alla
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter M. Dower
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vincent Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alessandro Alla .

Editor information

Editors and Affiliations

  1. Department of Informatics, University of Verona, Verona, Italy

    Giacomo Albi

  2. Department of Mathematics and Informatics, University of Ferrara, Ferrara, Italy

    Walter Boscheri

  3. Department of Mathematics, University of Pavia, Pavia, Italy

    Mattia Zanella

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Alla, A., M. Dower, P., Liu, V. (2023). A Tree Structure Approach to Reachability Analysis. In: Albi, G., Boscheri, W., Zanella, M. (eds) Advances in Numerical Methods for Hyperbolic Balance Laws and Related Problems. YR 2021. SEMA SIMAI Springer Series, vol 32. Springer, Cham. https://doi.org/10.1007/978-3-031-29875-2_1

Download citation

Publish with us

Policies and ethics

Search

Navigation