Adaptive Directions for Bernstein-Based Polynomial Set Evolution | SpringerLink
Skip to main content
Springer Nature Link
Log in

Adaptive Directions for Bernstein-Based Polynomial Set Evolution

  • Conference paper
  • First Online:
Reachability Problems (RP 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14235))

Included in the following conference series:

  • 153 Accesses

Abstract

Dynamical systems are systems in which states evolve according to some laws. Their simple definition hides a powerful tool successfully adopted in many domains from physics to economy and medicine. Many techniques have been proposed so far to study properties, forecast behaviors, and synthesize controllers for dynamical systems, in particular, for the continuous-time case. Recently, methods based on Bernstein polynomials emerged as tools to investigate non-linear evolutions for sets of states in discrete-time dynamical systems. These approaches represent sets as parallelotopes having fixed axis/directions, and, during the evolution, they update the parallelotope boundaries to over-approximate the reached set.

This work suggests a heuristic to identify a new set of axis/directions to reduce over-approximation. The heuristic has been implemented and successfully tested in some examples.

This work is partially supported by PRIN project NiRvAna CUP G23C22000400005 and National Recovery and Resilience Plan (NRRP), Mission 4 Component 2 Investment 1.4 - Call for tender No. 3138 of 16 December 202, rectified by Decree n.3175 of 18 December 2021 of Italian Ministry of University and Research funded by the European Union - NextGenerationEU; Project code CN_00000033, Concession Decree No. 1034 of 17 June 2022 adopted by the Italian Ministry of University and Research, CUP G23C22001110007, Project title “National Biodiversity Future Center - NBFC”.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6634
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 8293
Price includes VAT (Japan)
  • Compact, lightweight 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

Similar content being viewed by others

References

  1. Althoff, M., Frehse, G., Girard, A.: Set propagation techniques for reachability analysis. Ann. Rev. Control Rob. Auton. Syst. 4, 369–395 (2021)

    Article  Google Scholar 

  2. Bak, S., Duggirala, P.S.: Simulation-equivalent reachability of large linear systems with inputs. In: Majumdar, R., Kunčak, V. (eds.) CAV 2017. LNCS, vol. 10426, pp. 401–420. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63387-9_20

    Chapter  Google Scholar 

  3. Bird, T.J., Pangborn, H.C., Jain, N., Koeln, J.P.: Hybrid zonotopes: a new set representation for reachability analysis of mixed logical dynamical systems. Automatica 154, 111107 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  4. Brin, M., Stuck, G.: Introduction to Dynamical Systems. Cambridge University Press, Cambridge (2002)

    Book  MATH  Google Scholar 

  5. Casagrande, A., Dang, T., Dorigo, L., Dreossi, T., Piazza, C., Pippia, E.: Parameter synthesis of polynomial dynamical systems. Inf. Comput. 289, 104941 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chen, X., Ábrahám, E., Sankaranarayanan, S.: Flow*: an analyzer for non-linear hybrid systems. In: Computer Aided Verification, CAV, pp. 258–263 (2013)

    Google Scholar 

  7. Dang, T., Dreossi, T., Fanchon, E., Maler, O., Piazza, C., Rocca, A.: Set-based analysis for biological modeling. In: Liò, P., Zuliani, P. (eds.) Automated Reasoning for Systems Biology and Medicine. CB, vol. 30, pp. 157–189. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17297-8_6

    Chapter  Google Scholar 

  8. Dang, T., Dreossi, T., Piazza, C.: Parameter synthesis using parallelotopic enclosure and applications to epidemic models. In: Hybrid Systems and Biology, HSB, pp. 67–82 (2014)

    Google Scholar 

  9. Dang, T., Dreossi, T., Piazza, C.: Parameter synthesis through temporal logic specifications. In: Formal Methods, FM, pp. 213–230 (2015)

    Google Scholar 

  10. Dreossi, T.: Sapo: reachability computation and parameter synthesis of polynomial dynamical systems. In: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control, pp. 29–34 (2017)

    Google Scholar 

  11. Dreossi, T., Dang, T., Piazza, C.: Reachability computation for polynomial dynamical systems. Formal Methods Syst. Des. 50(1), 1–38 (2017). https://doi.org/10.1007/s10703-016-0266-3

    Article  MATH  Google Scholar 

  12. Galor, O.: Discrete Dynamical Systems. Springer, Heidelberg (2007)

    Book  MATH  Google Scholar 

  13. Geretti, L., et al.: ARCH-COMP20 category report: continuous and hybrid systems with nonlinear dynamics. In: Frehse, G., Althoff, M. (eds.) ARCH20. 7th International Workshop on Applied Verification of Continuous and Hybrid Systems (ARCH20), vol. 74 of EPiC Series in Computing, pp. 49–75. EasyChair (2020)

    Google Scholar 

  14. Geretti, L., et al.: Arch-comp21 category report: continuous and hybrid systems with nonlinear dynamics. In: Frehse, G., Althoff, M. (eds.) 8th International Workshop on Applied Verification of Continuous and Hybrid Systems (ARCH21), vol. 80 of EPiC Series in Computing, pp. 32–54. EasyChair (2021)

    Google Scholar 

  15. Girard, A.: Reachability of uncertain linear systems using zonotopes. In: Morari, M., Thiele, L. (eds.) HSCC 2005. LNCS, vol. 3414, pp. 291–305. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31954-2_19

    Chapter  MATH  Google Scholar 

  16. Kurzhanski, A.B., Varaiya, P.: Ellipsoidal techniques for reachability analysis. In Hybrid Systems: Computation and Control, HSCC, pp. 202–214 (2000)

    Google Scholar 

  17. Le Guernic, C.: Reachability analysis of hybrid systems with linear continuous dynamics. PhD thesis, Université Joseph-Fourier-Grenoble I (2009)

    Google Scholar 

  18. Nuzzo, P., Sangiovanni-Vincentelli, A.L., Bresolin, D., Geretti, L., Villa, T.: A platform-based design methodology with contracts and related tools for the design of cyber-physical systems. Proc. IEEE 103(11), 2104–2132 (2015)

    Article  Google Scholar 

  19. Sassi, M.A.B., Testylier, R., Dang, T., Girard, A.: Reachability analysis of polynomial systems using linear programming relaxations. In Automated Technology for Verification and Analysis, ATVA, pp. 137–151 (2012)

    Google Scholar 

  20. Schupp, S., Ábrahám, E., Makhlouf, I.B., Kowalewski, S.: HyPro: a C++ library of state set representations for hybrid systems reachability Analysis. In: Barrett, C., Davies, M., Kahsai, T. (eds.) NFM 2017. LNCS, vol. 10227, pp. 288–294. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57288-8_20

    Chapter  Google Scholar 

  21. Shisha, O.: The Bernstein form of a polynomial. J. Res. Natl. Bureau Stand. Math. Math. Phys. B 70, 79 (1966)

    Google Scholar 

  22. Siefert, J.A., Bird, T.J., Koeln, J.P., Jain, N., Pangborn, H.C.: Successor sets of discrete-time nonlinear systems using hybrid zonotopes (2023)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dip. di Matematica e Geoscienze, Università di Trieste, Trieste, Italy

    Alberto Casagrande

  2. Dip. di Matematica, Informatica e Fisica, Università di Udine, Udine, Italy

    Carla Piazza

Authors
  1. Alberto Casagrande
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carla Piazza
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto Casagrande .

Editor information

Editors and Affiliations

  1. École Polytechnique, Paris, France

    Olivier Bournez

  2. Université Côte d’Azur, Nice, France

    Enrico Formenti

  3. University of Liverpool, Liverpool, UK

    Igor Potapov

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

Casagrande, A., Piazza, C. (2023). Adaptive Directions for Bernstein-Based Polynomial Set Evolution. In: Bournez, O., Formenti, E., Potapov, I. (eds) Reachability Problems. RP 2023. Lecture Notes in Computer Science, vol 14235. Springer, Cham. https://doi.org/10.1007/978-3-031-45286-4_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-45286-4_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-45285-7

  • Online ISBN: 978-3-031-45286-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation