{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T05:05:09Z","timestamp":1774501509668,"version":"3.50.1"},"reference-count":138,"publisher":"Annual Reviews","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annu. Rev. Control Robot. Auton. Syst."],"published-print":{"date-parts":[[2021,5,3]]},"abstract":"<jats:p> Reachability analysis consists in computing the set of states that are reachable by a dynamical system from all initial states and for all admissible inputs and parameters. It is a fundamental problem motivated by many applications in formal verification, controller synthesis, and estimation, to name only a few. This article focuses on a class of methods for computing a guaranteed overapproximation of the reachable set of continuous and hybrid systems, relying predominantly on set propagation; starting from the set of initial states, these techniques iteratively propagate a sequence of sets according to the system dynamics. After a review of set representation and computation, the article presents the state of the art of set propagation techniques for reachability analysis of linear, nonlinear, and hybrid systems. It ends with a discussion of successful applications of reachability analysis to real-world problems. <\/jats:p>","DOI":"10.1146\/annurev-control-071420-081941","type":"journal-article","created":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T00:49:05Z","timestamp":1606956545000},"page":"369-395","source":"Crossref","is-referenced-by-count":221,"title":["Set Propagation Techniques for Reachability Analysis"],"prefix":"10.1146","volume":"4","author":[{"given":"Matthias","family":"Althoff","sequence":"first","affiliation":[{"name":"Department of Informatics, Technical University of Munich, 85748 Garching, Germany;"}]},{"given":"Goran","family":"Frehse","sequence":"additional","affiliation":[{"name":"Computer Science and Systems Engineering Laboratory (U2IS), ENSTA Paris, 91762 Palaiseau, France;"}]},{"given":"Antoine","family":"Girard","sequence":"additional","affiliation":[{"name":"Laboratoire des Signaux et Syst\u00e8mes, Universit\u00e9 Paris-Saclay, CNRS, and CentraleSup\u00e9lec, 91190 Gif-sur-Yvette, France;"}]}],"member":"22","reference":[{"key":"B1","volume-title":"Model Checking","author":"Clarke EM","year":"2018"},{"key":"B2","volume-title":"Principles of Model Checking","author":"Baier C","year":"2008"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(71)90066-5"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00202-T"},{"key":"B5","first-page":"323","volume-title":"ADPM 2000 Conference Proceedings: The 4th International Conference on Automation of Mixed Processes: Hybrid Dynamic Systems","author":"Silva BI","year":"2000"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45657-0_30"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1145\/3302504.3311796"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1581"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_33"},{"key":"B10","first-page":"59","volume-title":"Proceedings of the 14th Conference on Formal Methods in Computer-Aided Design","author":"Chen X","year":"2014"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(99)00113-2"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2672859"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2017.7963126"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2006.05.003"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2018.8619781"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1109\/CDC40024.2019.9029873"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2005.1583327"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2016.02.036"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2017.2710132"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1109\/TIV.2016.2622920"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2017.2707129"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2176409"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2017.08.1617"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1145\/2883817.2883828"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1145\/3306157"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2005.851439"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-060117-104941"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24743-2_32"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96145-3_24"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/11730637_22"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71493-4_16"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.3182\/20080706-5-KR-1001.01515"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1109\/EMSOFT.2013.6658604"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1145\/2968478.2968482"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1145\/1210268.1210276"},{"key":"B36","first-page":"105","volume-title":"2013 Formal Methods in Computer-Aided Design","author":"Gao S","year":"2013"},{"key":"B37","volume-title":"ARCH19: 6th International Workshop on Applied Verification of Continuous and Hybrid Systems","author":"Frehse G","year":"2019"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2011.6160872"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1134\/S000511790709007X"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.70"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1145\/2461328.2461358"},{"key":"B42","unstructured":"Kochdumper N, Althoff M. 2020. Constrained polynomial zonotopes. arXiv:2005.08849 [math.CO]"},{"key":"B43","volume-title":"Applied Interval Analysis","author":"Jaulin L","year":"2006"},{"key":"B44","volume-title":"Ellipsoidal toolbox","author":"Kurzhanskiy AA","year":"2006"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1145\/3178126.3178128"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00023-5"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00032-3"},{"key":"B48","volume-title":"On the complexity of vertex and facet enumeration for convex polytopes","author":"Bremner DD.","year":"1997"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7799418"},{"key":"B50","unstructured":"Kochdumper N, Althoff M. 2019. Sparse polynomial zonotopes: a novel set representation for reachability analysis. arXiv:1901.01780 [cs.SY]"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1145\/3358230"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63387-9_20"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002850"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-04-01657-6"},{"key":"B55","first-page":"379","volume":"4","author":"Makino K","year":"2003","journal-title":"Int. J. Pure Appl. Math."},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_26"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46430-1_10"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46430-1_19"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2002.806655"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46430-1_6"},{"key":"B61","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31954-2_19"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2009.03.009"},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2009.03.002"},{"key":"B64","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_30"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1145\/1967701.1967717"},{"key":"B66","doi-asserted-by":"publisher","DOI":"10.1007\/BF02684450"},{"key":"B67","doi-asserted-by":"publisher","DOI":"10.1007\/11730637_21"},{"key":"B68","doi-asserted-by":"publisher","DOI":"10.23919\/ACC.2004.1386733"},{"key":"B69","doi-asserted-by":"publisher","DOI":"10.1007\/11730637_23"},{"key":"B70","doi-asserted-by":"publisher","DOI":"10.1007\/s10626-017-0244-y"},{"key":"B71","doi-asserted-by":"publisher","DOI":"10.29007\/b8zr"},{"key":"B72","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2019.2906432"},{"key":"B73","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24743-2_3"},{"key":"B74","doi-asserted-by":"publisher","DOI":"10.1080\/00207179.2010.543703"},{"key":"B75","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025364227563"},{"key":"B76","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48983-5_12"},{"key":"B77","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2016.011"},{"key":"B78","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009958918582"},{"key":"B79","first-page":"63","volume-title":"Computational Differentiation: Techniques, Applications, and Tools","author":"Makino K","year":"1996"},{"key":"B80","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9092-3_13"},{"key":"B81","doi-asserted-by":"publisher","DOI":"10.1145\/1967701.1967723"},{"key":"B82","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2015.08.006"},{"key":"B83","doi-asserted-by":"publisher","DOI":"10.1109\/9.664156"},{"key":"B84","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36580-X_5"},{"key":"B85","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-006-0035-7"},{"key":"B86","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2015.7059096"},{"key":"B87","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2008.4738704"},{"key":"B88","doi-asserted-by":"publisher","DOI":"10.1145\/1755952.1755956"},{"key":"B89","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142996313154"},{"key":"B90","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2006.1656431"},{"key":"B91","doi-asserted-by":"publisher","DOI":"10.1007\/11730637_13"},{"key":"B92","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-64358-3_34"},{"key":"B93","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_19"},{"key":"B94","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2003.817920"},{"key":"B95","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2009.10.002"},{"key":"B96","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78929-1_30"},{"key":"B97","doi-asserted-by":"publisher","DOI":"10.1145\/2728606.2728607"},{"key":"B98","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2012.09.020"},{"key":"B99","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2008.4586828"},{"key":"B100","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78929-1_51"},{"key":"B101","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30494-4_3"},{"key":"B102","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2285751"},{"key":"B103","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57318-6_30"},{"key":"B104","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(98)00178-2"},{"key":"B105","doi-asserted-by":"publisher","DOI":"10.1109\/MCS.2008.931718"},{"key":"B106","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1996.561342"},{"key":"B107","doi-asserted-by":"publisher","DOI":"10.1145\/2883817.2883825"},{"key":"B108","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58485-4_43"},{"key":"B109","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32304-2_10"},{"key":"B110","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48168-0_10"},{"key":"B111","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"B112","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-007-0062-x"},{"key":"B113","doi-asserted-by":"publisher","DOI":"10.23919\/ECC.2013.6669815"},{"key":"B114","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02658-4_40"},{"key":"B115","doi-asserted-by":"publisher","DOI":"10.1145\/2461328.2461361"},{"key":"B116","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48288-9_18"},{"key":"B117","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7353861"},{"key":"B118","first-page":"218","volume-title":"ARCH18: 5th International Workshop on Applied Verification of Continuous and Hybrid Systems","author":"Hobbs K","year":"2018"},{"key":"B119","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382573"},{"key":"B120","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2006.244113"},{"key":"B121","doi-asserted-by":"publisher","DOI":"10.1145\/2507771.2507783"},{"key":"B122","doi-asserted-by":"publisher","DOI":"10.1016\/j.conengprac.2004.04.002"},{"key":"B123","doi-asserted-by":"publisher","DOI":"10.1109\/IVS.2010.5548121"},{"key":"B124","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942751"},{"key":"B125","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2312453"},{"key":"B126","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2017.2742141"},{"key":"B127","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2012.2194168"},{"key":"B128","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.2013.2295168"},{"key":"B129","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2014.2306731"},{"key":"B130","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2015.2509649"},{"key":"B131","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2017.2780804"},{"key":"B132","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2162998"},{"key":"B133","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8202313"},{"key":"B134","doi-asserted-by":"publisher","DOI":"10.1126\/scirobotics.aaw1924"},{"key":"B135","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71493-4_8"},{"key":"B136","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03845-7_9"},{"key":"B137","doi-asserted-by":"publisher","DOI":"10.1145\/2185632.2185644"},{"key":"B138","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17297-8_6"}],"container-title":["Annual Review of Control, Robotics, and Autonomous Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.annualreviews.org\/doi\/pdf\/10.1146\/annurev-control-071420-081941","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,8]],"date-time":"2021-10-08T10:32:25Z","timestamp":1633689145000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.annualreviews.org\/doi\/10.1146\/annurev-control-071420-081941"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,3]]},"references-count":138,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,5,3]]}},"alternative-id":["10.1146\/annurev-control-071420-081941"],"URL":"https:\/\/doi.org\/10.1146\/annurev-control-071420-081941","relation":{},"ISSN":["2573-5144","2573-5144"],"issn-type":[{"value":"2573-5144","type":"print"},{"value":"2573-5144","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,3]]}}}