{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T14:25:46Z","timestamp":1762957546981,"version":"3.41.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T00:00:00Z","timestamp":1742256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Assuring Autonomy International Programme"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>\n            In dynamic environments, safety-critical autonomous systems must adapt to environmental changes without violating safety requirements. Model verification at runtime supports adaptation through the periodic analysis of continually updated models. A major limitation of the technique is the high overhead associated with the regular analyses of large state-space models. Our article introduces an\n            <jats:italic>adaptive approximation strategy<\/jats:italic>\n            that tackles this limitation by delaying unnecessary model updates, significantly reducing the overheads of these analyses. The strategy is applicable to Markov decision processes (MDPs) and is partitioned into components that can be analyzed independently and approximately. Each component is assigned a priority that depends on its impact on the accuracy of verification, and only the highest-priority components affected by changes are scheduled for updating\/approximating. A complete update and verification of the entire model is triggered infrequently when the accuracy drops below a predefined threshold. We provide theoretical guarantees and proofs which ensure that our strategy can be applied without impacting the overall safety of the verified autonomous system. The experimental results from a case study in which we applied the strategy to a rescue robot team show that it is fully robust against safety-critical errors and can achieve a decision accuracy of over 97%.\n          <\/jats:p>","DOI":"10.1145\/3708560","type":"journal-article","created":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T11:56:24Z","timestamp":1734177384000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Model Verification at Runtime through Adaptive Dynamic Approximation"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7274-9569","authenticated-orcid":false,"given":"Mehran","family":"Alidoost Nia","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Shahid Beheshti University, Tehran, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2678-9260","authenticated-orcid":false,"given":"Radu","family":"Calinescu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of York, York, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9300-4665","authenticated-orcid":false,"given":"Mehdi","family":"Kargahi","sequence":"additional","affiliation":[{"name":"Department of Computer and Electrical Engineering, University of Tehran, Tehran, Iran, and School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5627-9093","authenticated-orcid":false,"given":"Alessandro","family":"Abate","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom of Great Britain and Northern Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,18]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.1016\/j.entcs.2013.12.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2","DOI":"10.1016\/j.peva.2021.102207"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","DOI":"10.1016\/j.sysarc.2021.102177"},{"doi-asserted-by":"publisher","key":"e_1_3_2_5_2","DOI":"10.1016\/j.micpro.2019.102943"},{"key":"e_1_3_2_6_2","volume-title":"Principles of Model Checking","author":"Baier Christel","year":"2008","unstructured":"Christel Baier and Joost-Pieter Katoen. 2008. Principles of Model Checking. MIT press."},{"doi-asserted-by":"publisher","key":"e_1_3_2_7_2","DOI":"10.1145\/2304696.2304716"},{"doi-asserted-by":"publisher","key":"e_1_3_2_8_2","DOI":"10.1016\/j.sysarc.2010.09.004"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/978-3-662-54458-7_19","volume-title":"Proceedings of 20th International Conference on Foundations of Software Science and Computation Structures","author":"Bian Gaoang","year":"2017","unstructured":"Gaoang Bian and Alessandro Abate. 2017. On the relationship between bisimulation and trace equivalence in an approximate probabilistic context. In Proceedings of 20th International Conference on Foundations of Software Science and Computation Structures. Javier Esparza and Andrzej S. Murawski (Eds.), Springer, Berlin, 321\u2013337."},{"doi-asserted-by":"publisher","key":"e_1_3_2_10_2","DOI":"10.1016\/j.jcss.2013.11.003"},{"doi-asserted-by":"publisher","key":"e_1_3_2_11_2","DOI":"10.1109\/TIT.2022.3148923"},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1007\/978-3-319-74183-3_8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_13_2","DOI":"10.1007\/978-3-662-49674-9_32"},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1109\/ACSOS49614.2020.00047"},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1109\/TSE.2019.2912958"},{"doi-asserted-by":"publisher","key":"e_1_3_2_16_2","DOI":"10.1109\/TSE.2017.2738640"},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.1145\/3387939.3391591"},{"issue":"4","key":"e_1_3_2_18_2","first-page":"300","article-title":"Comprehensive survey on distance\/similarity measures between probability density functions","volume":"1","author":"Cha Sung-Hyuk","year":"2007","unstructured":"Sung-Hyuk Cha. 2007. Comprehensive survey on distance\/similarity measures between probability density functions. International Journal of Mathematical Models and Methods in Applied Sciences 1, 4 (2007), 300\u2013307.","journal-title":"International Journal of Mathematical Models and Methods in Applied Sciences"},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.1109\/ASEEZone1.2014.6820644"},{"doi-asserted-by":"publisher","key":"e_1_3_2_20_2","DOI":"10.1007\/978-3-540-24611-4_5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1016\/j.sysarc.2016.04.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_22_2","DOI":"10.1117\/12.2307575"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1007\/978-3-319-63390-9_31","volume-title":"Computer Aided Verification","author":"Dehnert Christian","year":"2017","unstructured":"Christian Dehnert, Sebastian Junges, Joost-Pieter Katoen, and Matthias Volk. 2017. A storm is coming: A modern probabilistic model checker. In Computer Aided Verification, Rupak Majumdar and Viktor Kun\u010dak (Eds.), Springer International Publishing, Cham, 592\u2013600."},{"doi-asserted-by":"publisher","key":"e_1_3_2_24_2","DOI":"10.1007\/978-3-030-30942-8_26"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.1007\/s10009-021-00609-z"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.1109\/ICSE43902.2021.00081"},{"key":"e_1_3_2_27_2","volume":"40","author":"Feinberg Eugene A.","year":"2012","unstructured":"Eugene A. Feinberg and Adam Shwartz. 2012. Handbook of Markov Decision Processes: Methods and Applications, Vol. 40. Springer Science & Business Media.","journal-title":"Handbook of Markov Decision Processes: Methods and Applications"},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.1145\/3024188"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/978-3-319-99154-2_9","volume-title":"Quantitative Evaluation of Systems","author":"Gainer Paul","year":"2018","unstructured":"Paul Gainer, Ernst Moritz Hahn, and Sven Schewe. 2018. Incremental verification of parametric and reconfigurable Markov chains. In Quantitative Evaluation of Systems, Annabelle McIver and Andras Horvath (Eds.), Springer International Publishing, Cham, 140\u2013156."},{"key":"e_1_3_2_30_2","volume-title":"Runtime Quantitative Verification of Self-Adaptive Systems","author":"Gerasimou Simos","year":"2016","unstructured":"Simos Gerasimou. 2016. Runtime Quantitative Verification of Self-Adaptive Systems. Ph.D. Dissertation. University of York."},{"doi-asserted-by":"publisher","key":"e_1_3_2_31_2","DOI":"10.1111\/j.1751-5823.2002.tb00178.x"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-3-319-43425-4_16","volume-title":"Quantitative Evaluation of Systems","author":"Haesaert Sofie","year":"2016","unstructured":"Sofie Haesaert, Alessandro Abate, and Paul M. J. Van den Hof. 2016. Verification of general Markov decision processes by approximate similarity relations and policy refinement. In Quantitative Evaluation of Systems. Gul Agha and Benny Van Houdt (Eds.), Springer International Publishing, Cham, 227\u2013243."},{"doi-asserted-by":"publisher","key":"e_1_3_2_33_2","DOI":"10.1287\/deca.1120.0260"},{"key":"e_1_3_2_34_2","first-page":"1","volume-title":"Proceedings of the 1st workshop on Recent Advances in Resilient and Trustworthy Machine Learning (ARTMAN \u201924)","author":"Hasani Afshin","year":"2024","unstructured":"Afshin Hasani, Mehran Alidoost Nia, and Reza Ebrahimi Atani. 2024. Balancing safety and security in autonomous driving systems: A machine learning approach with safety-first prioritization. In Proceedings of the 1st workshop on Recent Advances in Resilient and Trustworthy Machine Learning (ARTMAN \u201924). IEEE Press, 1\u201312."},{"doi-asserted-by":"publisher","key":"e_1_3_2_35_2","DOI":"10.1145\/1380584.1380585"},{"doi-asserted-by":"publisher","key":"e_1_3_2_36_2","DOI":"10.1109\/MC.2003.1160055"},{"doi-asserted-by":"publisher","key":"e_1_3_2_37_2","DOI":"10.1016\/j.pmcj.2014.09.009"},{"doi-asserted-by":"publisher","key":"e_1_3_2_38_2","DOI":"10.1109\/SOSCYPS.2016.7579999"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/978-3-642-22110-1_47","volume-title":"Computer Aided Verification","author":"Kwiatkowska Marta","year":"2011","unstructured":"Marta Kwiatkowska, Gethin Norman, and David Parker. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In Computer Aided Verification. Ganesh Gopalakrishnan and Shaz Qadeer (Eds.), Springer, Berlin, 585\u2013591."},{"doi-asserted-by":"publisher","key":"e_1_3_2_40_2","DOI":"10.1109\/DSN.2011.5958249"},{"doi-asserted-by":"publisher","key":"e_1_3_2_41_2","DOI":"10.1109\/CDC.2017.8264180"},{"doi-asserted-by":"publisher","key":"e_1_3_2_42_2","DOI":"10.1016\/j.jss.2020.110742"},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/978-3-030-34968-4_18","volume-title":"Integrated Formal Methods","author":"Lohar Debasmita","year":"2019","unstructured":"Debasmita Lohar, Milos Prokop, and Eva Darulova. 2019. Sound probabilistic numerical error analysis. In Integrated Formal Methods. Wolfgang Ahrendt and Silvia Lizeth Tapia Tarifa (Eds.), Springer International Publishing, Cham, 322\u2013340."},{"doi-asserted-by":"publisher","key":"e_1_3_2_44_2","DOI":"10.1145\/3342355"},{"doi-asserted-by":"publisher","key":"e_1_3_2_45_2","DOI":"10.1109\/ASE.2019.00094"},{"issue":"14","key":"e_1_3_2_46_2","doi-asserted-by":"crossref","first-page":"3912","DOI":"10.3390\/s20143912","article-title":"An acceptance test for assistive robots","volume":"20","author":"Rico Francisco Mart\u00edn","year":"2020","unstructured":"Francisco Mart\u00edn Rico, Francisco J. Rodr\u00edguez-Lera, Jonatan Gin\u00e9s Clavero, \u00c1ngel Manuel Guerrero-Higueras, and Vicente Matell\u00e1n Olivera. 2020. An acceptance test for assistive robots. Sensors 20, 14 (2020), 3912.","journal-title":"Sensors"},{"doi-asserted-by":"publisher","key":"e_1_3_2_47_2","DOI":"10.1145\/3149180"},{"unstructured":"Mehran Alidoost Nia. 2021. An Exemplar of Runtime Approximation Framework for Self-Adaptive Systems in Safety-Critical Applications. Retrieved December 10 2024 from https:\/\/github.com\/alidoostnia\/Runtime-Approximation-Framework-for-Self-Adaptive-Systems","key":"e_1_3_2_48_2"},{"key":"e_1_3_2_49_2","volume-title":"Runtime Probabilistic Analysis of Self-Adaptive Systems via Formal Approximation Techniques","author":"Nia Mehran Alidoost","year":"2022","unstructured":"Mehran Alidoost Nia. 2022. Runtime Probabilistic Analysis of Self-Adaptive Systems via Formal Approximation Techniques. Ph.D. Dissertation. University of Tehran, Iran."},{"doi-asserted-by":"publisher","key":"e_1_3_2_50_2","DOI":"10.1109\/RTEST49666.2020.9140148"},{"key":"e_1_3_2_51_2","volume-title":"Quantitative Verification: Formal Guarantees for Timeliness, Reliability and Performance","author":"Norman Gethin","year":"2014","unstructured":"Gethin Norman and David Parker. 2014. Quantitative Verification: Formal Guarantees for Timeliness, Reliability and Performance. Technical Report. The London Mathematical Society and the Smith Institute."},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-319-66335-7_16","volume-title":"Quantitative Evaluation of Systems","author":"Polgreen Elizabeth","year":"2017","unstructured":"Elizabeth Polgreen, Viraj B. Wijesuriya, Sofie Haesaert, and Alessandro Abate. 2017. Automated experiment design for data-efficient verification of parametric Markov decision processes. In Quantitative Evaluation of Systems. Nathalie Bertrand and Luca Bortolussi (Eds.), Springer International Publishing, Cham, 259\u2013274."},{"doi-asserted-by":"publisher","key":"e_1_3_2_53_2","DOI":"10.1109\/CDC42340.2020.9304029"},{"doi-asserted-by":"publisher","key":"e_1_3_2_54_2","DOI":"10.1145\/3213846.3213852"},{"doi-asserted-by":"publisher","key":"e_1_3_2_55_2","DOI":"10.1145\/3057267"},{"doi-asserted-by":"publisher","key":"e_1_3_2_56_2","DOI":"10.1109\/SWAT.1971.10"},{"doi-asserted-by":"publisher","key":"e_1_3_2_57_2","DOI":"10.1145\/2562059.2562118"},{"doi-asserted-by":"publisher","key":"e_1_3_2_58_2","DOI":"10.3389\/fpubh.2017.00307"},{"doi-asserted-by":"publisher","key":"e_1_3_2_59_2","DOI":"10.1145\/3387939.3391605"},{"doi-asserted-by":"publisher","key":"e_1_3_2_60_2","DOI":"10.1145\/3170708"},{"doi-asserted-by":"publisher","key":"e_1_3_2_61_2","DOI":"10.1007\/s10270-021-00916-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_62_2","DOI":"10.1016\/j.cnsns.2021.105720"},{"doi-asserted-by":"publisher","key":"e_1_3_2_63_2","DOI":"10.1007\/978-3-030-28374-2_17"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708560","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708560","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:02Z","timestamp":1750298222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708560"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,18]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3708560"],"URL":"https:\/\/doi.org\/10.1145\/3708560","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2025,3,18]]},"assertion":[{"value":"2023-12-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}