{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:29:35Z","timestamp":1759336175955,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,31]],"date-time":"2019-10-31T00:00:00Z","timestamp":1572480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["Grants No. 61550110506, 61650410658, 61761136011, and 61532019"],"award-info":[{"award-number":["Grants No. 61550110506, 61650410658, 61761136011, and 61532019"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["Advanced Investigators Grant 695614 (POWVER)"],"award-info":[{"award-number":["Advanced Investigators Grant 695614 (POWVER)"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"name":"CAS\/SAFEA","award":["International Partnership Program for Creative Research Teams"],"award-info":[{"award-number":["International Partnership Program for Creative Research Teams"]}]},{"DOI":"10.13039\/501100002367","name":"Chinese Academy of Sciences","doi-asserted-by":"crossref","award":["Fellowship for International Young Scientists"],"award-info":[{"award-number":["Fellowship for International Young Scientists"]}],"id":[{"id":"10.13039\/501100002367","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Grant 389792660, as part of CRC 248"],"award-info":[{"award-number":["Grant 389792660, as part of CRC 248"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["Mobile Autonomy Programme Grant EP\/M019918\/1"],"award-info":[{"award-number":["Mobile Autonomy Programme Grant EP\/M019918\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"H2020","doi-asserted-by":"crossref","award":["Marie Sk?odowska-Curie Actions Individual Fellowship PaVeCo - Parametrised Verification and Control"],"award-info":[{"award-number":["Marie Sk?odowska-Curie Actions Individual Fellowship PaVeCo - Parametrised Verification and Control"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"crossref"}]},{"name":"CDZ","award":["project CAP (GZ 1023)"],"award-info":[{"award-number":["project CAP (GZ 1023)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            Accurate Modelling of a real-world system with probabilistic behaviour is a difficult task. Sensor noise and statistical estimations, among other imprecisions, make the exact probability values impossible to obtain. In this article, we consider Interval Markov decision processes (\n            <jats:italic>IMDP<\/jats:italic>\n            s), which generalise classical\n            <jats:italic>MDP<\/jats:italic>\n            s by having interval-valued transition probabilities. They provide a powerful modelling tool for probabilistic systems with an additional variation or uncertainty that prevents the knowledge of the exact transition probabilities. We investigate the problem of robust multi-objective synthesis for\n            <jats:italic>IMDP<\/jats:italic>\n            s and Pareto curve analysis of multi-objective queries on\n            <jats:italic>IMDP<\/jats:italic>\n            s. We study how to find a robust (randomised) strategy that satisfies multiple objectives involving rewards, reachability, and more general \u03c9-regular properties against all possible resolutions of the transition probability uncertainties, as well as to generate an approximate Pareto curve providing an explicit view of the trade-offs between multiple objectives. We show that the multi-objective synthesis problem is\n            <jats:bold>PSPACE<\/jats:bold>\n            -hard and provide a value iteration-based decision algorithm to approximate the Pareto set of achievable points. We finally demonstrate the practical effectiveness of our proposed approaches by applying them on several case studies using a prototype tool.\n          <\/jats:p>","DOI":"10.1145\/3309683","type":"journal-article","created":{"date-parts":[[2019,11,18]],"date-time":"2019-11-18T13:01:53Z","timestamp":1574082113000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Interval Markov Decision Processes with Multiple Objectives"],"prefix":"10.1145","volume":"29","author":[{"given":"Ernst Moritz","family":"Hahn","sequence":"first","affiliation":[{"name":"The School of Electronics, Electrical Engineering and Computer Science, Queen\u2019s University Belfast, UK and State Key Laboratory of Computer Science, Institute of Software, CAS, Beijing, China"}]},{"given":"Vahid","family":"Hashemi","sequence":"additional","affiliation":[{"name":"Department of Information Technology, Audi AG, Ingolstadt, Germany"}]},{"given":"Holger","family":"Hermanns","sequence":"additional","affiliation":[{"name":"Saarland University, Saarland Informatics Campus, Germany and Institute of Intelligent Software, Guangzhou, Guangzhou, China"}]},{"given":"Morteza","family":"Lahijanian","sequence":"additional","affiliation":[{"name":"Department of Smead Aerospace Engineering and Sciences, University of Colorado, Boulder, CO, USA"}]},{"given":"Andrea","family":"Turrini","sequence":"additional","affiliation":[{"name":"Institute of Intelligent Software, Guangzhou, China and State Key Laboratory of Computer Science, Institute of Software, CAS, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2019,11,18]]},"reference":[{"volume-title":"Principles of Model Checking","author":"Baier Christel","key":"e_1_2_1_1_1","unstructured":"Christel Baier and Joost-Pieter Katoen . 2008. Principles of Model Checking . The MIT Press . Christel Baier and Joost-Pieter Katoen. 2008. Principles of Model Checking. The MIT Press."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44584-6_13"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1957.6.56038"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36742-7_3"},{"key":"e_1_2_1_5_1","volume-title":"Tsitsiklis","author":"Bertsimas Dimitris","year":"1997","unstructured":"Dimitris Bertsimas and John N . Tsitsiklis . 1997 . Introduction to Linear Optimization. Athena Scientific . Dimitris Bertsimas and John N. Tsitsiklis. 1997. Introduction to Linear Optimization. Athena Scientific."},{"key":"e_1_2_1_6_1","first-page":"499","article-title":"Model checking of probabalistic and nondeterministic systems","volume":"1026","author":"Bianco Andrea","year":"1995","unstructured":"Andrea Bianco and Luca de Alfaro . 1995 . Model checking of probabalistic and nondeterministic systems . In Proceedings of the FSTTCS.LNCS , Vol. 1026. 499 -- 513 . Andrea Bianco and Luca de Alfaro. 1995. Model checking of probabalistic and nondeterministic systems. In Proceedings of the FSTTCS.LNCS, Vol. 1026. 499--513.","journal-title":"Proceedings of the FSTTCS.LNCS"},{"volume-title":"Convex Optimization","author":"Boyd Stephen","key":"e_1_2_1_7_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press."},{"key":"e_1_2_1_8_1","volume-title":"Isbell","author":"Cantino Andrew S.","year":"2007","unstructured":"Andrew S. Cantino , David L. Roberts , and Charles L . Isbell . 2007 . Autonomous nondeterministic tour guides: Improving quality of experience with TTD-MDPs. In Proceedings of the AAMAS. 22. Andrew S. Cantino, David L. Roberts, and Charles L. Isbell. 2007. Autonomous nondeterministic tour guides: Improving quality of experience with TTD-MDPs. In Proceedings of the AAMAS. 22."},{"key":"e_1_2_1_9_1","first-page":"325","article-title":"Markov decision processes with multiple objectives","volume":"3884","author":"Chatterjee Krishnendu","year":"2006","unstructured":"Krishnendu Chatterjee , Rupak Majumdar , and Thomas A. Henzinger . 2006 . Markov decision processes with multiple objectives . In Proceedings of the STACS. LNCS , Vol. 3884. 325 -- 336 . Krishnendu Chatterjee, Rupak Majumdar, and Thomas A. Henzinger. 2006. Markov decision processes with multiple objectives. In Proceedings of the STACS. LNCS, Vol. 3884. 325--336.","journal-title":"Proceedings of the STACS. LNCS"},{"key":"e_1_2_1_10_1","volume-title":"Henzinger","author":"Chatterjee Krishnendu","year":"2008","unstructured":"Krishnendu Chatterjee , Koushik Sen , and Thomas A . Henzinger . 2008 . Model-checking -regular properties of interval Markov chains. In Proceedings of the FoSSaCS. 302--317. Krishnendu Chatterjee, Koushik Sen, and Thomas A. Henzinger. 2008. Model-checking -regular properties of interval Markov chains. In Proceedings of the FoSSaCS. 302--317."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40313-2_25"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.01.004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54580-5_8"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ICTAC. 280--294","author":"Daws Conrado","year":"2004","unstructured":"Conrado Daws . 2004 . Symbolic and parametric model checking of discrete-time Markov chains . In Proceedings of the ICTAC. 280--294 . Conrado Daws. 2004. Symbolic and parametric model checking of discrete-time Markov chains. In Proceedings of the ICTAC. 280--294."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1121732"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2012.6227118"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71209-1_6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11691617_5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19835-9_11"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33386-6_25"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00047-3"},{"key":"e_1_2_1_22_1","first-page":"146","article-title":"Synthesis for PCTL in parametric Markov decision processes","volume":"6617","author":"Hahn Ernst Moritz","year":"2011","unstructured":"Ernst Moritz Hahn , Tingting Han , and Lijun Zhang . 2011 . Synthesis for PCTL in parametric Markov decision processes . In Proceedings of the NFM. LNCS , Vol. 6617. 146 -- 161 . Ernst Moritz Hahn, Tingting Han, and Lijun Zhang. 2011. Synthesis for PCTL in parametric Markov decision processes. In Proceedings of the NFM. LNCS, Vol. 6617. 146--161.","journal-title":"Proceedings of the NFM. LNCS"},{"key":"e_1_2_1_23_1","first-page":"207","article-title":"Multi-objective robust strategy synthesis for interval Markov decision processes","volume":"10503","author":"Hahn Ernst Moritz","year":"2017","unstructured":"Ernst Moritz Hahn , Vahid Hashemi , Holger Hermanns , Morteza Lahijanian , and Andrea Turrini . 2017 . Multi-objective robust strategy synthesis for interval Markov decision processes . In Proceedings of the QEST.LNCS , Vol. 10503. 207 -- 223 . Ernst Moritz Hahn, Vahid Hashemi, Holger Hermanns, Morteza Lahijanian, and Andrea Turrini. 2017. Multi-objective robust strategy synthesis for interval Markov decision processes. In Proceedings of the QEST.LNCS, Vol. 10503. 207--223.","journal-title":"Proceedings of the QEST.LNCS"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49122-5_17"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1991.151651"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014745904458"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.10.001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2015.2398883"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7799414"},{"key":"e_1_2_1_30_1","volume-title":"Kavraki","author":"Luna Ryan","year":"2014","unstructured":"Ryan Luna , Morteza Lahijanian , Mark Moll , and Lydia E . Kavraki . 2014 a. Asymptotically optimal stochastic motion planning with temporal goals. In Proceedings of the WAFR. 335--352. Ryan Luna, Morteza Lahijanian, Mark Moll, and Lydia E. Kavraki. 2014a. Asymptotically optimal stochastic motion planning with temporal goals. In Proceedings of the WAFR. 335--352."},{"key":"e_1_2_1_31_1","volume-title":"Kavraki","author":"Luna Ryan","year":"2014","unstructured":"Ryan Luna , Morteza Lahijanian , Mark Moll , and Lydia E . Kavraki . 2014 b. Fast stochastic motion planning with optimality guarantees using local policy reconfiguration. In Proceedings of the ICRA. 3013--3019. Ryan Luna, Morteza Lahijanian, Mark Moll, and Lydia E. Kavraki. 2014b. Fast stochastic motion planning with optimality guarantees using local policy reconfiguration. In Proceedings of the ICRA. 3013--3019."},{"key":"e_1_2_1_32_1","volume-title":"Kavraki","author":"Luna Ryan","year":"2014","unstructured":"Ryan Luna , Morteza Lahijanian , Mark Moll , and Lydia E . Kavraki . 2014 c. Optimal and efficient stochastic motion planning in partially known environments. In Proceedings of the AAAI. 2549--2555. Ryan Luna, Morteza Lahijanian, Mark Moll, and Lydia E. Kavraki. 2014c. Optimal and efficient stochastic motion planning in partially known environments. In Proceedings of the AAAI. 2549--2555."},{"key":"e_1_2_1_33_1","first-page":"2814","article-title":"Multi-objective decision-theoretic plan problem","volume":"3","author":"Mouaddib Abdel-Illah","year":"2004","unstructured":"Abdel-Illah Mouaddib . 2004 . Multi-objective decision-theoretic plan problem . In Proceedings of the ICRA , Vol. 3. 2814 -- 2819 . Abdel-Illah Mouaddib. 2004. Multi-objective decision-theoretic plan problem. In Proceedings of the ICRA, Vol. 3. 2814--2819.","journal-title":"Proceedings of the ICRA"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1050.0216"},{"key":"e_1_2_1_35_1","first-page":"1021","article-title":"A compromise programming approach to multiobjective Markov decision processes","volume":"12","author":"Ogryczak Wlodzimierz","year":"2013","unstructured":"Wlodzimierz Ogryczak , Patrice Perny , and Paul Weng . 2013 . A compromise programming approach to multiobjective Markov decision processes . Int. J. Inform. Technol . Dec. Making 12 , 5 (2013), 1021 -- 1054 . Wlodzimierz Ogryczak, Patrice Perny, and Paul Weng. 2013. A compromise programming approach to multiobjective Markov decision processes. Int. J. Inform. Technol. Dec. Making 12, 5 (2013), 1021--1054.","journal-title":"Int. J. Inform. Technol"},{"key":"e_1_2_1_36_1","volume-title":"Hanna","author":"Perny Patrice","year":"2013","unstructured":"Patrice Perny , Paul Weng , Judy Goldsmith , and Josiah P . Hanna . 2013 . Approximation of Lorenz-optimal solutions in multiobjective Markov decision processes. In Proceedings of the AAAI. 92--94. Patrice Perny, Paul Weng, Judy Goldsmith, and Josiah P. Hanna. 2013. Approximation of Lorenz-optimal solutions in multiobjective Markov decision processes. In Proceedings of the AAAI. 92--94."},{"volume-title":"Proceedings of the FORTE. 121--140","author":"Petrucci Laure","key":"e_1_2_1_37_1","unstructured":"Laure Petrucci and Jaco van de Pol. 2018. Parameter synthesis algorithms for parametric interval Markov chains . In Proceedings of the FORTE. 121--140 . Laure Petrucci and Jaco van de Pol. 2018. Parameter synthesis algorithms for parametric interval Markov chains. In Proceedings of the FORTE. 121--140."},{"key":"e_1_2_1_39_1","volume-title":"Seshia","author":"Puggelli Alberto","year":"2013","unstructured":"Alberto Puggelli , Wenchao Li , Alberto L. Sangiovanni-Vincentelli , and Sanjit A . Seshia . 2013 . Polynomial-time verification of PCTL properties of MDPs with convex uncertainties. In Proceedings of the CAV. 527--542. Alberto Puggelli, Wenchao Li, Alberto L. Sangiovanni-Vincentelli, and Sanjit A. Seshia. 2013. Polynomial-time verification of PCTL properties of MDPs with convex uncertainties. In Proceedings of the CAV. 527--542."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46520-3_4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_8"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3150928.3150945"},{"key":"e_1_2_1_43_1","volume-title":"Murray","author":"Wolff Eric M.","year":"2012","unstructured":"Eric M. Wolff , Ufuk Topcu , and Richard M . Murray . 2012 . Robust control of uncertain Markov decision processes with temporal logic specifications. In Proceedings of the CDC. 3372--3379. Eric M. Wolff, Ufuk Topcu, and Richard M. Murray. 2012. Robust control of uncertain Markov decision processes with temporal logic specifications. In Proceedings of the CDC. 3372--3379."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.12.002"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309683","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:58Z","timestamp":1750208278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309683"}},"subtitle":["From Robust Strategies to Pareto Curves"],"short-title":[],"issued":{"date-parts":[[2019,10,31]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3309683"],"URL":"https:\/\/doi.org\/10.1145\/3309683","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2019,10,31]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}