{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:47:57Z","timestamp":1773154077476,"version":"3.50.1"},"reference-count":51,"publisher":"SAGE Publications","issue":"12","license":[{"start":{"date-parts":[[2015,8,12]],"date-time":"2015-08-12T00:00:00Z","timestamp":1439337600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2015,10]]},"abstract":"<jats:p> As robots are being integrated into our daily lives, it becomes necessary to provide guarantees on their safe and provably correct operation. Such guarantees can be provided using automata theoretic task and mission planning where the requirements are expressed as temporal logic specifications. However, in real-life scenarios, it is to be expected that not all user task requirements can be realized by the robot. In such cases, the robot must provide feedback to the user on why it cannot accomplish a given task. Moreover, the robot should indicate what tasks it can accomplish which are as \u201cclose\u201d as possible to the initial user intent. This paper establishes that the latter problem, which is referred to as the minimal specification revision problem, is NP-complete. A heuristic algorithm is presented that can compute good approximations to the Minimal Revision Problem (MRP) in polynomial time. The experimental study of the algorithm demonstrates that in most problem instances the heuristic algorithm actually returns the optimal solution. Finally, some cases where the algorithm does not return the optimal solution are presented. <\/jats:p>","DOI":"10.1177\/0278364915587034","type":"journal-article","created":{"date-parts":[[2015,8,13]],"date-time":"2015-08-13T00:48:34Z","timestamp":1439426914000},"page":"1515-1535","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":27,"title":["On the minimal revision problem of specification automata"],"prefix":"10.1177","volume":"34","author":[{"given":"Kangjin","family":"Kim","sequence":"first","affiliation":[{"name":"School of Computing, Informatics and Decision Systems Engineering, Arizona State University, Tempe, AZ, USA"}]},{"given":"Georgios","family":"Fainekos","sequence":"additional","affiliation":[{"name":"School of Computing, Informatics and Decision Systems Engineering, Arizona State University, Tempe, AZ, USA"}]},{"given":"Sriram","family":"Sankaranarayanan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Colorado, Boulder, CO, USA"}]}],"member":"179","published-online":{"date-parts":[[2015,8,12]]},"reference":[{"key":"bibr1-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509503"},{"key":"bibr2-0278364915587034","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2011.VII.003"},{"key":"bibr3-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"bibr4-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45069-6_21"},{"key":"bibr5-0278364915587034","volume-title":"Principles of Robot Motion: Theory, Algorithms and Implementations","author":"Choset H","year":"2005"},{"key":"bibr6-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78163-9_9"},{"key":"bibr7-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696976"},{"key":"bibr8-0278364915587034","volume-title":"Model Checking","author":"Clarke EM","year":"1999"},{"key":"bibr9-0278364915587034","volume-title":"Introduction to Algorithms","author":"Cormen TH","year":"2001","edition":"2"},{"key":"bibr10-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1007\/11425274_45"},{"key":"bibr11-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2009.5152776"},{"key":"bibr12-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5979895"},{"key":"bibr13-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2008.08.008"},{"key":"bibr14-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2012.6426027"},{"key":"bibr15-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88190-2_21"},{"key":"bibr16-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44585-4_6"},{"key":"bibr17-0278364915587034","first-page":"226","volume-title":"European conference on planning","volume":"1809","author":"Giacomo GD","year":"1999"},{"key":"bibr18-0278364915587034","volume-title":"Proceedings of the 20th international conference on automated planning and scheduling (ICAPS)","author":"G\u00f6belbecker M","year":"2010"},{"key":"bibr19-0278364915587034","volume-title":"IEEE conference on decision and control","author":"Guo M","year":"2013"},{"key":"bibr20-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907485"},{"key":"bibr21-0278364915587034","volume-title":"IEEE international conference on robotics and automation","author":"Guo M","year":"2013"},{"key":"bibr22-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1145\/605466.605488"},{"key":"bibr23-0278364915587034","volume-title":"Proceedings of the international workshop on the algorithmic foundations of robotics (WAFR)","author":"Hauser K","year":"2012"},{"key":"bibr24-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2008.4739370"},{"key":"bibr25-0278364915587034","unstructured":"Kim K (2014a) LTL2BA modification for indexing. Available at: https:\/\/git.assembla.com\/ltl2ba_cpslab.git."},{"key":"bibr26-0278364915587034","unstructured":"Kim K (2014b) Temporal logic specification revision and planning toolbox. Available at: https:\/\/subversion.assembla.com\/svn\/temporal-logic-specification-revision-and-planning-toolbox\/."},{"key":"bibr27-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6386215"},{"key":"bibr28-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907644"},{"key":"bibr29-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224826"},{"key":"bibr30-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2035776"},{"key":"bibr31-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2009.5351127"},{"key":"bibr32-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1163\/156855308X344864"},{"key":"bibr33-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2030225"},{"key":"bibr34-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2008.ECP.29"},{"key":"bibr35-0278364915587034","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2011.VII.024"},{"key":"bibr36-0278364915587034","volume-title":"The twenty-ninth AAAI conference (AAAI-15)","author":"Lahijanian M","year":"2015"},{"key":"bibr37-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr38-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ICCPS.2011.10"},{"key":"bibr39-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017309"},{"key":"bibr40-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_54"},{"key":"bibr41-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696436"},{"key":"bibr42-0278364915587034","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2013.IX.023"},{"key":"bibr43-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1145\/1967701.1967748"},{"key":"bibr44-0278364915587034","first-page":"393","volume-title":"Proceedings of the 14th international conference on automated planning and scheduling (ICAPS-04)","author":"Smith DE","year":"2004"},{"key":"bibr45-0278364915587034","first-page":"599","volume":"35","author":"Sniedovich M","year":"2006","journal-title":"Control and Cybernetics"},{"key":"bibr46-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012991217524"},{"key":"bibr47-0278364915587034","volume-title":"American control conference","author":"Tumova J","year":"2013"},{"key":"bibr48-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224792"},{"key":"bibr49-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6094884"},{"key":"bibr50-0278364915587034","first-page":"562","volume-title":"Proceedings of the 19th national conference on artifical intelligence (AAAI\u201904)","author":"van den Briel M","year":"2004"},{"key":"bibr51-0278364915587034","doi-asserted-by":"publisher","DOI":"10.1145\/1755952.1755968"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915587034","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915587034","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915587034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T11:42:38Z","timestamp":1737978158000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915587034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,12]]},"references-count":51,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["10.1177\/0278364915587034"],"URL":"https:\/\/doi.org\/10.1177\/0278364915587034","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,12]]}}}