{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:37:34Z","timestamp":1760056654983,"version":"build-2065373602"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:p>Explaining unsolvability of planning problems is of significant research interest in Explainable AI Planning. A number of research efforts on generating explanations of solutions to planning problems have been reported in AI planning literature. However, explaining the unsolvability of planning problems remains a largely open and understudied problem. A widely practiced approach to plan generation and automated problem solving, in general, is to decompose tasks into sub-problems that help progressively converge towards the goal. In this article, we propose to adopt the same philosophy of sub-problem identification as a mechanism for analyzing and explaining unsolvability of planning problems in hybrid systems. In particular, for a given unsolvable planning problem, we propose to identify common waypoints, which are universal obstacles to plan existence, in other words, they appear on every plan from the source to the planning goal. This work envisions such waypoints as sub-problems of the planning problem and the unreachability of any of these waypoints as an explanation for the unsolvability of the original planning problem. We propose a novel method of waypoint identification by casting the problem as an instance of the longest common subsequence problem, a widely popular problem in computer science, typically considered as an illustrative example for the dynamic programming paradigm. Once the waypoints are identified, we perform symbolic reachability analysis on them to identify the earliest unreachable waypoint and report it as the explanation of unsolvability. We present experimental results on unsolvable planning problems in hybrid domains.<\/jats:p>","DOI":"10.1145\/3767745","type":"journal-article","created":{"date-parts":[[2025,9,15]],"date-time":"2025-09-15T11:30:21Z","timestamp":1757935821000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0029-9252","authenticated-orcid":false,"given":"Mir Md Sajid","family":"Sarwar","sequence":"first","affiliation":[{"name":"School of Mathematical and Computational sciences, Indian Association for the Cultivation of Science","place":["Kolkata, India"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7990-6416","authenticated-orcid":false,"given":"Rajarshi","family":"Ray","sequence":"additional","affiliation":[{"name":"School of Mathematical and Computational Sciences, Indian Association for the Cultivation of Science","place":["Kolkata, India"]}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00202-T"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/646874.709849"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2000.878178"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.29007\/nv67"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2008.ECP.13"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v29i1.3463"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/669"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.24963\/IJCAI.2017\/23"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.ASOC.2020.106499"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i06.6534"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v30i1.6649"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v27i1.13818"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v28i1.13899"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32759-9_17"},{"key":"e_1_3_2_16_2","unstructured":"Maria Fox Derek Long and Daniele Magazzeni. 2017. Explainable planning. arXiv:1709.10256. Retrieved from https:\/\/arxiv.org\/abs\/1709.10256"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","unstructured":"Sicun Gao Soonho Kong Wei Chen and Edmund M. Clarke. 2014. Delta-complete analysis for bounded reachability of hybrid systems. arXiv:1404.7171. Retrieved from https:\/\/arxiv.org\/abs\/1404.7171","DOI":"10.21236\/ADA613813"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v20i1.13421"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03237-0_7"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1996.561342"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31423-1_9"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1613\/JAIR.1492"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"e_1_3_2_24_2","first-page":"1093","volume-title":"Proceedings of the Doklady Akademii Nauk","author":"Khachiyan Leonid Genrikhovich","year":"1979","unstructured":"Leonid Genrikhovich Khachiyan. 1979. A polynomial algorithm in linear programming. In Proceedings of the Doklady Akademii Nauk. Russian Academy of Sciences, 1093\u20131096."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1613\/JAIR.1.12813"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/9.24200"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.ENTCS.2006.12.023"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-61499-098-7-540"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/322063.322075"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056797"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","unstructured":"Daniel S. Hirschberg. 1975. A linear space algorithm for computing maximal common subsequences. Commun. ACM 18 6 (1975) 341\u2013343. DOI:10.1145\/360825.360861","DOI":"10.1145\/360825.360861"},{"key":"e_1_3_2_32_2","first-page":"975","volume-title":"Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008","author":"Richter Silvia","year":"2008","unstructured":"Silvia Richter, Malte Helmert, and Matthias Westphal. 2008. Landmarks revisited. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, Dieter Fox and Carla P. Gomes (Eds.). AAAI,975\u2013982. Retrieved from http:\/\/www.aaai.org\/Library\/AAAI\/2008\/aaai08-155.php"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3561532"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3610579.3611082"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/197"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","unstructured":"Richard S. Sutton Doina Precup and Satinder Singh. 1999. Between MDPs and Semi-MDPs: A framework for temporal abstraction in reinforcement learning. ArtificialIntelligence 112 1-2 (1999) 181\u2013211. DOI:10.1016\/S0004-3702(99)00052-1","DOI":"10.1016\/S0004-3702(99)00052-1"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90084-6"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13431"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2005.13"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767745","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T12:41:05Z","timestamp":1760013665000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767745"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1145\/3767745"],"URL":"https:\/\/doi.org\/10.1145\/3767745","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-01-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-30","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}