{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:44:18Z","timestamp":1760244258918,"version":"3.41.2"},"reference-count":56,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T00:00:00Z","timestamp":1727913600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["324674"],"award-info":[{"award-number":["324674"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Software Testing Verif &amp;amp; Rel"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>Autonomous systems such as space\u2010 or underwater\u2010exploration robots or elderly people assistance robots often include an artificial intelligence (AI) planner as a component. Starting from the initial state of a system, an AI planner automatically generates sequential plans to reach final states that satisfy user\u2010specified goals. Generating plans having a minimum number of intermediate steps or taking the least time to execute is usually strongly desired, as these plans exhibit minimal costs. Unfortunately, testing if an AI planner generates optimal plans is almost impossible because the expected cost of these plans is usually unknown. Based on mutation adequacy test suite selection, this article proposes a novel metamorphic testing framework for detecting the lack of optimality in AI planners. The general idea is to perform a systematic but non\u2010exhaustive state space exploration from the initial state and to select mutant\u2010adequate states to instantiate new planning tasks as follow\u2010up test cases. We then check a metamorphic relation between the automatically generated solutions of the AI planner for these new test cases and the cost of the initial plan. We implemented this metamorphic testing framework in a tool called <jats:sc>MorphinPlan<\/jats:sc>. Our experimental evaluation shows that <jats:sc>MorphinPlan<\/jats:sc> can detect non\u2010optimal behaviour in both mutated AI planners and off\u2010the\u2010shelf, configurable planners. It also shows that our proposed mutation adequacy test selection strategy outperforms three alternative test generation and selection strategies, including both random state selection and random walks through the state space in terms of mutation scores.<\/jats:p>","DOI":"10.1002\/stvr.1898","type":"journal-article","created":{"date-parts":[[2024,10,4]],"date-time":"2024-10-04T04:40:02Z","timestamp":1728016802000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Mutation\u2010Guided Metamorphic Testing of Optimality in AI Planning"],"prefix":"10.1002","volume":"35","author":[{"given":"Quentin","family":"Mazouni","sequence":"first","affiliation":[{"name":"VIAS Department Simula Research Laboratory  Oslo Norway"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8980-7585","authenticated-orcid":false,"given":"Arnaud","family":"Gotlieb","sequence":"additional","affiliation":[{"name":"VIAS Department Simula Research Laboratory  Oslo Norway"}]},{"given":"Helge","family":"Spieker","sequence":"additional","affiliation":[{"name":"VIAS Department Simula Research Laboratory  Oslo Norway"}]},{"given":"Mathieu","family":"Acher","sequence":"additional","affiliation":[{"name":"DiVerSE Team INRIA\u2010IRISA\u2010INSA  Rennes France"}]},{"given":"Benoit","family":"Combemale","sequence":"additional","affiliation":[{"name":"DiVerSE Team INRIA\u2010IRISA\u2010INSA  Rennes France"}]}],"member":"311","published-online":{"date-parts":[[2024,10,3]]},"reference":[{"key":"e_1_2_11_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139583923"},{"key":"e_1_2_11_3_1","unstructured":"\u201cAIPlan4EU H2020 European Project \u201d (2021) https:\/\/www.aiplan4eu\u2010project.eu."},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00900ED2V01Y201902AIM042"},{"key":"e_1_2_11_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-013-0294-x"},{"key":"e_1_2_11_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:FORM.0000040027.28662.a4"},{"key":"e_1_2_11_7_1","doi-asserted-by":"crossref","unstructured":"H. F.Eniser T. P.Gros V.W\u00fcstholz J.Hoffmann andM.Christakis \u201cMetamorphic Relations Via Relaxations: An Approach to Obtain Oracles for Action\u2010Policy Testing \u201d inProc. of the 31st ACM SIGSOFT Int. Symp. on Software Testing and Analysis (ISSTA)(2022) https:\/\/doi.org\/10.1145\/3533767.3534392.","DOI":"10.1145\/3533767.3534392"},{"key":"e_1_2_11_8_1","unstructured":"J.Penix C.Pecheur andK.Havelund \u201cUsing Model Checking to Validate AI Planner Domain Models \u201d inProc. of the 23rd Annual Software Engineering Workshop(Nasa Goddard 1999) 1\u20139 https:\/\/ntrs.nasa.gov\/citations\/19990054671."},{"key":"e_1_2_11_9_1","doi-asserted-by":"crossref","unstructured":"J.Zhang Z.Zheng B.Yin K.Qiu andY.Liu \u201cTesting Graph Searching Based Path Planning Algorithms by Metamorphic Testing \u201d in2019 IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC)(2019) 158\u201315809 https:\/\/doi.org\/10.1109\/PRDC47002.2019.00046.","DOI":"10.1109\/PRDC47002.2019.00046"},{"key":"e_1_2_11_10_1","doi-asserted-by":"crossref","unstructured":"M.AbdulazizandF.Kurz \u201cFormally Verified SAT\u2010Based AI Planning \u201d inProc. of the AAAI Conference on Artificial Intelligence(2023) 14665\u201314673 https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/26714.","DOI":"10.1609\/aaai.v37i12.26714"},{"key":"e_1_2_11_11_1","unstructured":"F.Raimondi C.Pecheur andG.Brat \u201cPDVer a Tool to Verify PDDL Planning Domains \u201d inProc. of ICAPS'09 Workshop on Verification and Validation of Planning and Scheduling Systems(Thessaloniki Greece 2009) 223\u2013228."},{"key":"e_1_2_11_12_1","unstructured":"A.ShrinahandK.Eder \u201cGoal\u2010Constrained Planning Domain Model Verification of Safety Properties \u201d inProceedings of the 9th European Starting AI Researchers' Symposium 2020 Co\u2010located with 24th European Conference on Artificial Intelligence (ECAI 2020) CEUR Workshop Proceedings Vol.\u00a02655 (2020) 1\u20138."},{"key":"e_1_2_11_13_1","doi-asserted-by":"crossref","unstructured":"M. H.Smith G. J.Holzmann G. C.Cucullu andB. D.Smith \u201cModel Checking Autonomous Planners: Even the Best Laid Plans Must Be Verified \u201d inProc. of the IEEE Aerospace Conference. Big Sky Montana(2005) 1\u201311.","DOI":"10.1109\/AERO.2005.1559607"},{"key":"e_1_2_11_14_1","doi-asserted-by":"crossref","unstructured":"C.Hutchison M.Zizyte P. E.Lanigan et\u00a0al. \u201cRobustness Testing of Autonomy Software \u201d in2018 IEEE\/ACM 40th International Conference on Software Engineering: Software Engineering in Practice Track (ICSE\u2010SEIP)(Gothenburg Sweden 2018) 276\u2013285.","DOI":"10.1145\/3183519.3183534"},{"key":"e_1_2_11_15_1","unstructured":"R.HoweyandD.Long \u201cVal's Progress: The Automatic Validation Tool for PDDL2.1 Used in the International Planning Competition \u201d inProceedings of the ICAPS 2003 Workshop on \u201cthe Competition: Impact Organization Evaluation Benchmarks\u201d(2003) 28\u201337."},{"key":"e_1_2_11_16_1","doi-asserted-by":"crossref","unstructured":"G.Penna D.Magazzeni F.Mercorio andI.Benedetto \u201cUpmurphi: A Tool for Universal Planning on PDDL+ Problems \u201d inProc. of the 19th Int. Conf. on Automated Planning and Scheduling (ICAPS'09)(Thessaloniki Greece 2009) 106\u2013113.","DOI":"10.1609\/icaps.v19i1.13352"},{"key":"e_1_2_11_17_1","doi-asserted-by":"crossref","unstructured":"K.Havelund A.Groce G.Holzmann R.Joshi andM.Smith \u201cAutomated Testing of Planning Models \u201d inModel Checking and Artificial Intelligence: 5th International Workshop MoChArt 2008 Patras Greece July 21 2008. Revised Selected and Invited Papers 5(2009) 90\u2013105.","DOI":"10.1007\/978-3-642-00431-5_6"},{"key":"e_1_2_11_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-38561-3_11"},{"key":"e_1_2_11_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2007.08.011"},{"key":"e_1_2_11_20_1","doi-asserted-by":"crossref","unstructured":"J.Bo\u017ei\u0107 O.Tazl andF.Wotawa \u201cChatbot Testing Using AI Planning \u201d inIEEE International Conference on Artificial Intelligence Testing AITest 2019 \u00a0(2019) 37\u201344 https:\/\/doi.org\/10.1109\/AITest.2019.00\u201010.","DOI":"10.1109\/AITest.2019.00-10"},{"key":"e_1_2_11_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008607721339"},{"key":"e_1_2_11_22_1","doi-asserted-by":"publisher","DOI":"10.14201\/ADCAIJ2017645569"},{"key":"e_1_2_11_23_1","doi-asserted-by":"crossref","unstructured":"Y.DinitzandS.Solomon \u201cOn Optimal Solutions for the Bottleneck Tower of Hanoi Problem \u201d inInt. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM) LNCS Vol.\u00a04362(2007) 248\u2013259.","DOI":"10.1007\/978-3-540-69507-3_20"},{"key":"e_1_2_11_24_1","doi-asserted-by":"crossref","unstructured":"Y.Chen T.Su C.Sun Z.Su andJ.Zhao \u201cCoverage\u2010Directed Differential Testing of JVM Implementations \u201d inProceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'16)(2016) 85\u201399.","DOI":"10.1145\/2908080.2908095"},{"key":"e_1_2_11_25_1","unstructured":"T. Y.Chen S. C.Cheung andS. M.Yiu \u201cMetamorphic Testing: A New Approach for Generating Next Test Cases \u201d Technical Report HKUST\u2010CS98\u201001 Department of Computer Science Hong Kong University of Science and Technology (Hong Kong 1998)."},{"key":"e_1_2_11_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3143561"},{"key":"e_1_2_11_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2016.2532875"},{"key":"e_1_2_11_28_1","doi-asserted-by":"crossref","unstructured":"T. Y.ChenandT. H.Tse \u201cNew Visions on Metamorphic Testing After a Quarter of a Century of Inception \u201d inProc. of the 29th ACM Joint Meet. on European Soft. Eng. Conf. and Symp. on the Foundations of Soft. Eng. (ESEC\/FSE)(2021) 1487\u20131490.","DOI":"10.1145\/3468264.3473136"},{"key":"e_1_2_11_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2020.110574"},{"key":"e_1_2_11_30_1","doi-asserted-by":"crossref","unstructured":"D.Xiao Z.Liu Y.Yuan Q.Pang andS.Wang \u201cMetamorphic Testing of Deep Learning Compilers \u201d inProceedings of the ACM on Measurement and Analysis of Computing Systems Vol.\u00a06 (New York NY USA:Association for Computing Machinery 2022) 1\u201328 https:\/\/doi.org\/10.1145\/3508035.","DOI":"10.1145\/3508035"},{"key":"e_1_2_11_31_1","doi-asserted-by":"crossref","unstructured":"X.Xie J.Ho C.Murphy G.Kaiser B.Xu andT.Chen \u201cApplication of Metamorphic Testing to Supervised Classifiers \u201d in2009 Ninth Int. Conf. on Quality Software Vol.\u00a033 (2009):135\u2013144.","DOI":"10.1109\/QSIC.2009.26"},{"key":"e_1_2_11_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2010.11.920"},{"key":"e_1_2_11_33_1","doi-asserted-by":"crossref","unstructured":"L.Xu D.Towey A. P.French S.Benford Z. Q.Zhou andT. Y.Chen \u201cEnhancing Supervised Classifications With Metamorphic Relations \u201d inProceedings of the 3rd International Workshop on Metamorphic Testing \u2010 MET \u201818(2018):46\u201353 https:\/\/doi.org\/10.1145\/3193977.3193978.","DOI":"10.1145\/3193977.3193978"},{"key":"e_1_2_11_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.1594"},{"key":"e_1_2_11_35_1","doi-asserted-by":"crossref","unstructured":"S.Yoo \u201cMetamorphic Testing of Stochastic Optimisation \u201d in2010 Third International Conference on Software Testing Verification and Validation Workshops(2010) 192\u2013201 https:\/\/doi.org\/10.1109\/ICSTW.2010.26.","DOI":"10.1109\/ICSTW.2010.26"},{"key":"e_1_2_11_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.1863"},{"key":"e_1_2_11_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2022.3193070"},{"key":"e_1_2_11_38_1","doi-asserted-by":"crossref","unstructured":"Y.Deng G.Lou X.Zheng et\u00a0al. \u201cBMT: Behavior Driven Development\u2010Based Metamorphic Testing for Autonomous Driving Models \u201d in2021 IEEE\/ACM 6th International Workshop on Metamorphic Testing (MET)(2021) 32\u201336 https:\/\/doi.org\/10.1109\/MET52542.2021.00012.","DOI":"10.1109\/MET52542.2021.00012"},{"key":"e_1_2_11_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241979"},{"key":"e_1_2_11_40_1","unstructured":"C.Muise \u201cPlanning Domains \u201d inProc. of Int. Conf. on Automated Planning and Scheduling. System Demo. Track. London UK(2016) 242\u2013250."},{"volume-title":"SICStus Prolog User's Manual","year":"2019","author":"Carlsson M.","key":"e_1_2_11_41_1"},{"key":"e_1_2_11_42_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1677"},{"key":"e_1_2_11_43_1","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v22i3.1571"},{"key":"e_1_2_11_44_1","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v21i2.1506"},{"key":"e_1_2_11_45_1","unstructured":"Y.Dimopoulos A.Gerevini P.Haslum andA.Saetti \u201cThe Benchmark Domains of the Deterministic Part of IPC\u20105\u201d inSpecial Booklet for the Planning Competition in the Working Notes of the 16th International Conference on Automated Planning and Scheduling (ICAP\u2010S\u201006)(Monterey CA USA June \u20105\u201010 2006) 14\u201319."},{"key":"e_1_2_11_46_1","unstructured":"IPC 2008 Organizers \u201cIPC 2008 Website \u201d (2008) https:\/\/ipc08.icaps\u2010conference.org\/deterministic\/index.html."},{"key":"e_1_2_11_47_1","unstructured":"R.Sasak \u201cProlog Planning Library \u201d (2021) https:\/\/github.com\/RobertSasak\/Prolog\u2010Planning\u2010Library."},{"key":"e_1_2_11_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2013.44"},{"key":"e_1_2_11_49_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1705"},{"key":"e_1_2_11_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2022.3206427"},{"key":"e_1_2_11_51_1","doi-asserted-by":"crossref","unstructured":"R.Li H.Liu G.Lou X.Zheng X.Liu andT. Y.Chen \u201cMetamorphic Testing on Multi\u2010Module UAV Systems \u201d in2021 36th IEEE\/ACM International Conference on Automated Software Engineering (ASE)(2021) 1171\u20131173 https:\/\/doi.org\/10.1109\/ASE51524.2021.9678841.","DOI":"10.1109\/ASE51524.2021.9678841"},{"key":"e_1_2_11_52_1","doi-asserted-by":"crossref","unstructured":"M.Lindvall A.Porter G.Magnusson andC.Schulze \u201cMetamorphic Model\u2010Based Testing of Autonomous Systems \u201d in2nd International Workshop on Metamorphic Testing MET 2017(2017) 35\u201341 https:\/\/doi.org\/10.1109\/MET.2017.6.","DOI":"10.1109\/MET.2017.6"},{"key":"e_1_2_11_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/MS.2018.2875968"},{"key":"e_1_2_11_54_1","unstructured":"M.Cheng Y.Zhou X.Xie J.Wang G.Meng andK.Yang \u201cEvaluating Decision Optimality of Autonomous Driving Via Metamorphic Testing \u201d (2024) https:\/\/arxiv.org\/abs\/2402.18393."},{"key":"e_1_2_11_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3669663"},{"key":"e_1_2_11_56_1","doi-asserted-by":"crossref","unstructured":"M.Papadakis D.Shin S.Yoo andD.\u2010H.Bae \u201cAre Mutation Scores Correlated With Real Fault Detection? A Large Scale Empirical Study on the Relationship Between Mutants and Real Faults \u201d inProc. of the 40th Int. Conf. on Software Engineering (ICSE)(2018) https:\/\/doi.org\/10.1145\/3180155.3180183.","DOI":"10.1145\/3180155.3180183"},{"key":"e_1_2_11_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10664\u2010019\u201009778\u20107"}],"container-title":["Software Testing, Verification and Reliability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/stvr.1898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T01:12:39Z","timestamp":1735261959000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/stvr.1898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,3]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.1002\/stvr.1898"],"URL":"https:\/\/doi.org\/10.1002\/stvr.1898","archive":["Portico"],"relation":{},"ISSN":["0960-0833","1099-1689"],"issn-type":[{"type":"print","value":"0960-0833"},{"type":"electronic","value":"1099-1689"}],"subject":[],"published":{"date-parts":[[2024,10,3]]},"assertion":[{"value":"2023-11-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e1898"}}