{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:13:49Z","timestamp":1775873629053,"version":"3.50.1"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T00:00:00Z","timestamp":1732147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Youth Fund of the National Natural Science Foundation of China","award":["62302035"],"award-info":[{"award-number":["62302035"]}]},{"name":"Young Teachers of USTB","award":["FRF-IDRY-23-016"],"award-info":[{"award-number":["FRF-IDRY-23-016"]}]},{"name":"Engineerable AI Techniques for Practical Applications of High-Quality Machine Learning-Based Systems Project","award":["JPMJMI20B8"],"award-info":[{"award-number":["JPMJMI20B8"]}]},{"name":"ERATO HASUO Metamathematics for Systems Design Project","award":["JPMJER1603"],"award-info":[{"award-number":["JPMJER1603"]}]},{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61802349"],"award-info":[{"award-number":["61802349"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["62372021"],"award-info":[{"award-number":["62372021"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2024,11,30]]},"abstract":"<jats:p>The Multi-Agent Path Finding (MAPF) problem, i.e., the scheduling of multiple agents to reach their destinations, has been widely investigated. Testing MAPF systems is challenging, due to the complexity and variety of scenarios and the agents\u2019 distribution and interaction. Moreover, MAPF testing suffers from the oracle problem, i.e., it is not always clear whether a test shows a failure or not. Indeed, only considering whether the agents reach their destinations without collision is not sufficient. Other properties related to the \u2018quality\u2019 of the generated paths should be assessed, e.g., an agent should not follow an unnecessarily long path. To tackle this issue, this article proposes MET-MAPF, a Metamorphic Testing approach for MAPF systems. We identified 10 Metamorphic Relations (MRs) that a MAPF system should guarantee, designed over the environment in which agents operate, the behaviour of the single agents and the interactions among agents. Starting from the different MRs, MET-MAPF automatically generates test cases addressing them, so possibly exposing different types of failures. Experimental results show that MET-MAPF can indeed find MR violations not exposed by approaches that only consider the completion of the mission as test oracle. Moreover, experiments show that different MRs expose different types of violations.<\/jats:p>","DOI":"10.1145\/3669663","type":"journal-article","created":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T21:28:32Z","timestamp":1718227712000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["MET-MAPF: A Metamorphic Testing Approach for Multi-Agent Path Finding Algorithms"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7414-8057","authenticated-orcid":false,"given":"Xiao-Yi","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Science and Technology Beijing, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2222-3232","authenticated-orcid":false,"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"Beijing Jiaotong University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6253-4062","authenticated-orcid":false,"given":"Paolo","family":"Arcaini","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0758-1616","authenticated-orcid":false,"given":"Mingyue","family":"Jiang","sequence":"additional","affiliation":[{"name":"Zhejiang Sci-Tech University, Zhejiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7922-9067","authenticated-orcid":false,"given":"Zheng","family":"Zheng","sequence":"additional","affiliation":[{"name":"Beihang University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,21]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"16","volume-title":"Proceedings of the 3rd International Workshop on Quantum Software Engineering (Q-SE\u201922)","author":"Abreu Rui","year":"2023","unstructured":"Rui Abreu, Jo\u00e3o Paulo Fernandes, Luis Llana, and Guilherme Tavares. 2023. Metamorphic Testing of Oracle Quantum Programs. In Proceedings of the 3rd International Workshop on Quantum Software Engineering (Q-SE\u201922). ACM, New York, NY, 16\u201323. DOI: 10.1145\/3528230.3529189"},{"key":"e_1_3_2_3_2","first-page":"140","volume-title":"Proceedings of the 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP\u201921)","author":"Ahlgren John","year":"2021","unstructured":"John Ahlgren, Maria Eugenia Berezin, Kinga Bojarczuk, Elena Dulskyte, Inna Dvortsova, Johann George, Natalija Gucevska, Mark Harman, Maria Lomeli, Erik Meijer, Silvia Sapora, and Justin Spahr-Summers. 2021. Testing Web Enabled Simulation at Scale Using Metamorphic Testing. In Proceedings of the 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP\u201921). IEEE Press, 140\u2013149. DOI: 10.1109\/ICSE-SEIP52600.2021.00023"},{"key":"e_1_3_2_4_2","first-page":"104","volume-title":"Proceedings of the IEEE 31st International Symposium on Software Reliability Engineering (ISSRE\u201920)","author":"Ayerdi Jon","year":"2020","unstructured":"Jon Ayerdi, Sergio Segura, Aitor Arrieta, Goiuria Sagardui, and Maite Arratibel. 2020. QoS-Aware Metamorphic Testing: An Elevation Case Study. In Proceedings of the IEEE 31st International Symposium on Software Reliability Engineering (ISSRE\u201920). 104\u2013114. DOI: 10.1109\/ISSRE5003.2020.00019"},{"key":"e_1_3_2_5_2","first-page":"1264","volume-title":"Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE\u201921)","author":"Ayerdi Jon","year":"2021","unstructured":"Jon Ayerdi, Valerio Terragni, Aitor Arrieta, Paolo Tonella, Goiuria Sagardui, and Maite Arratibel. 2021. Generating Metamorphic Relations for Cyber-Physical Systems with Genetic Programming: An Industrial Case Study. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE\u201921). ACM, New York, NY, 1264\u20131274. DOI: 10.1145\/3468264.3473920"},{"key":"e_1_3_2_6_2","first-page":"827","volume-title":"IEEE Transactions on Reliability","volume":"72","author":"Ayerdi Jon","year":"2023","unstructured":"Jon Ayerdi, Pablo Valle, Sergio Segura, Aitor Arrieta, Goiuria Sagardui, and Maite Arratibel. 2023. Performance-Driven Metamorphic Testing of Cyber-Physical Systems. IEEE Transactions on Reliability 72, 2 (2023), 827\u2013845. DOI: 10.1109\/TR.2022.3193070"},{"key":"e_1_3_2_7_2","first-page":"507","volume-title":"IEEE Transactions on Software Engineering","volume":"41","author":"Barr Earl T.","year":"2015","unstructured":"Earl T. Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. 2015. The Oracle Problem in Software Testing: A Survey. IEEE Transactions on Software Engineering 41, 5 (2015), 507\u2013525. DOI: 10.1109\/TSE.2014.2372785"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol6.12191.21"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1609\/SOCS.V16I1.27278"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2023.3265169"},{"key":"e_1_3_2_11_2","first-page":"387","volume-title":"Proceedings of the 1st International Conference on Pervasive and Embedded Computing and Communication Systems","volume":"1","author":"Chen Tsong Yueh","year":"2011","unstructured":"Tsong Yueh Chen, Fei-Ching Kuo, Wing K. Tam, and Robert G. Merkel. 2011. Testing a Software-Based PID Controller Using Metamorphic Testing. In Proceedings of the 1st International Conference on Pervasive and Embedded Computing and Communication Systems, Vol. 1 . INSTICC, SciTePress, Algarve, Portugal, 387\u2013396."},{"issue":"1","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3143561","article-title":"Metamorphic Testing: A Review of Challenges and Opportunities","volume":"51","author":"Chen Tsong Yueh","year":"2018","unstructured":"Tsong Yueh Chen, Fei-Ching Kuo, Huai Liu, Pak-Lok Poon, Dave Towey, TH Tse, and Zhi Quan Zhou. 2018. Metamorphic Testing: A Review of Challenges and Opportunities. ACM Computing Surveys (CSUR) 51, 1 (2018), 1\u201327.","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2015.07.037"},{"issue":"4","key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1145\/566171.566202","article-title":"Semi-Proving: An Integrated Method Based On Global Symbolic Evaluation and Metamorphic Testing","volume":"27","author":"Chen Tsong Yueh","year":"2002","unstructured":"Tsong Yueh Chen, T. H. Tse, and Zhiquan Zhou. 2002. Semi-Proving: An Integrated Method Based On Global Symbolic Evaluation and Metamorphic Testing. ACM SIGSOFT Software Engineering Notes 27, 4 (2002), 191\u2013195.","journal-title":"ACM SIGSOFT Software Engineering Notes"},{"key":"e_1_3_2_15_2","first-page":"172","volume-title":"Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI\u201922)","author":"Chen Xinning","year":"2022","unstructured":"Xinning Chen, Xuan Liu, Shigeng Zhang, Bo Ding, and Kenli Li. 2022. Goal Consistency: An Effective Multi-Agent Cooperative Method for Multistage Tasks. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI\u201922). Lud De Raedt (Ed.), International Joint Conferences on Artificial Intelligence Organization, 172\u2013178. DOI: 10.24963\/ijcai.2022\/25"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1080\/0952813X.2017.1310142"},{"key":"e_1_3_2_17_2","volume-title":"Statistical Power Analysis for the Behavioral Sciences","author":"Cohen Jacob","year":"1969","unstructured":"Jacob Cohen. 1969. Statistical Power Analysis for the Behavioral Sciences. Academic Press, New York, NY, USA ."},{"key":"e_1_3_2_18_2","first-page":"1964","volume-title":"IEEE Transactions on Software Engineering","volume":"49","author":"Deng Yao","year":"2023","unstructured":"Yao Deng, Xi Zheng, Tianyi Zhang, Huai Liu, Guannan Lou, Miryung Kim, and Tsong Yueh Chen. 2023. A Declarative Metamorphic Testing Framework for Autonomous Driving. IEEE Transactions on Software Engineering 49, 4 (2023), 1964\u20131982. DOI: 10.1109\/TSE.2022.3206427"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840371"},{"key":"e_1_3_2_20_2","first-page":"29","volume-title":"Proceedings of the 10th Annual Symposium on Combinatorial Search","author":"Felner Ariel","year":"2017","unstructured":"Ariel Felner, Roni Stern, Solomon Eyal Shimony, Eli Boyarski, Meir Goldenberg, Guni Sharon, Nathan Sturtevant, Glenn Wagner, and Pavel Surynek. 2017. Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges. In Proceedings of the 10th Annual Symposium on Combinatorial Search. 29\u201337."},{"key":"e_1_3_2_21_2","first-page":"9","volume-title":"Proceedings of the International Workshop on Planning Under Uncertainty for Autonomous Systems, International Conference on Automated Planning and Scheduling (ICAPS)","author":"Ferguson Dave","year":"2005","unstructured":"Dave Ferguson, Maxim Likhachev, and Anthony Stentz. 2005. A Guide to Heuristic-Based Path Planning. In Proceedings of the International Workshop on Planning Under Uncertainty for Autonomous Systems, International Conference on Automated Planning and Scheduling (ICAPS). 9\u201318."},{"key":"e_1_3_2_22_2","first-page":"1350","volume-title":"IEEE Robotics and Automation Letters","volume":"5","author":"Han Shuai D.","year":"2020","unstructured":"Shuai D. Han and Jingjin Yu. 2020. DDM: Fast Near-Optimal Multi-Robot Path Planning Using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics. IEEE Robotics and Automation Letters 5, 2 (2020), 1350\u20131357. DOI: 10.1109\/LRA.2020.2967326"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-3-030-26601-1_5","volume-title":"International Conference on Computer Safety, Reliability, and Security","author":"Hauer Florian","year":"2019","unstructured":"Florian Hauer, Alexander Pretschner, and Bernd Holzm\u00fcller. 2019. Fitness Functions for Testing Automated and Autonomous Driving Systems. In International Conference on Computer Safety, Reliability, and Security. Springer, Cham, 69\u201384."},{"key":"e_1_3_2_24_2","first-page":"997","volume-title":"IEEE Transactions on Intelligent Transportation Systems","volume":"23","author":"Ho Florence","year":"2020","unstructured":"Florence Ho, R\u00faben Geraldes, Artur Gon\u00e7alves, Bastien Rigault, Benjamin Sportich, Daisuke Kubo, Marc Cavazza, and Helmut Prendinger. 2020. Decentralized Multi-Agent Path Finding for UAV Traffic Management. IEEE Transactions on Intelligent Transportation Systems 23, 2 (2020), 997\u20131008."},{"key":"e_1_3_2_25_2","first-page":"131","volume-title":"Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS\u201919). International Foundation for Autonomous Agents and Multiagent Systems","author":"Ho Florence","year":"2019","unstructured":"Florence Ho, Ana Salta, Ruben Geraldes, Artur Goncalves, Marc Cavazza, and Helmut Prendinger. 2019. Multi-Agent Path Finding for UAV Traffic Management. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS\u201919). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, USA, 131\u2013139."},{"key":"e_1_3_2_26_2","first-page":"477","volume-title":"Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS\u201916)","author":"H\u00f6nig Wolfgang","year":"2016","unstructured":"Wolfgang H\u00f6nig, T. K. Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, and Sven Koenig. 2016. Multi-Agent Path Finding with Kinematic Constraints. In Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS\u201916). Amanda Jane Coles, Andrew Coles, Stefan Edelkamp, Daniele Magazzeni, and Scott Sanner (Eds.). AAAI Press, 477\u2013485."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2018.2853613"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2019.2942921"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2022.107104"},{"issue":"1","key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1109\/TR.2020.3003313","article-title":"Input Test Suites for Program Repair: A Novel Construction Method Based on Metamorphic Relations","volume":"70","author":"Jiang Mingyue","year":"2020","unstructured":"Mingyue Jiang, Tsong Yueh Chen, Zhi Quan Zhou, and Zuohua Ding. 2020. Input Test Suites for Program Repair: A Novel Construction Method Based on Metamorphic Relations. IEEE Transactions on Reliability 70, 1 (2020), 285\u2013303.","journal-title":"IEEE Transactions on Reliability"},{"key":"e_1_3_2_31_2","first-page":"11479","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201920)","author":"Kantaros Yiannis","year":"2020","unstructured":"Yiannis Kantaros, Matthew Malencia, Vijay Kumar, and George J. Pappas. 2020. Reactive Temporal Logic Planning for Multiple Robots in Unknown Environments. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201920). IEEE, 11479\u201311485. DOI: 10.1109\/ICRA40945.2020.9197570"},{"key":"e_1_3_2_32_2","first-page":"1907","volume-title":"Proceedings of the IEEE Intelligent Vehicles Symposium (IV)","author":"Kuhn Christopher B.","year":"2020","unstructured":"Christopher B. Kuhn, Markus Hofbauer, Goran Petrovic, and Eckehard Steinbach. 2020. Introspective Black Box Failure Prediction for Autonomous Driving. In Proceedings of the IEEE Intelligent Vehicles Symposium (IV). IEEE, 1907\u20131913."},{"key":"e_1_3_2_33_2","first-page":"388","volume-title":"Proceedings of the IEEE\/ACM 42nd International Conference on Software Engineering Workshops","author":"Lee Dickson T. S.","year":"2020","unstructured":"Dickson T. S. Lee, Zhi Quan Zhou, and T. H. Tse. 2020. Metamorphic Robustness Testing of Google Translate. In Proceedings of the IEEE\/ACM 42nd International Conference on Software Engineering Workshops. ACM, New York, NY, 388\u2013395."},{"key":"e_1_3_2_34_2","first-page":"477","volume-title":"Proceedings of the International Conference on Automated Planning and Scheduling","volume":"31","author":"Li Jiaoyang","year":"2021","unstructured":"Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma, and Sven Koenig. 2021a. Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge. Proceedings of the International Conference on Automated Planning and Scheduling 31, 1 (May 2021), 477\u2013485. DOI: 10.1609\/icaps.v31i1.15994"},{"key":"e_1_3_2_35_2","first-page":"442","volume-title":"Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI\u201919)","author":"Li Jiaoyang","year":"2019","unstructured":"Jiaoyang Li, Ariel Felner, Eli Boyarski, Hang Ma, and Sven Koenig. 2019. Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI\u201919). AAAI Press, 442\u2013449."},{"key":"e_1_3_2_36_2","volume-title":"Proceedings of the 37th AAAI Conference on Artificial Intelligence and 35th Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence (AAAI\u201923\/IAAI\u201923\/EAAI\u201923)","author":"Li Jiaoyang","year":"2023","unstructured":"Jiaoyang Li, The Anh Hoang, Eugene Lin, Hai L. Vu, and Sven Koenig. 2023. Intersection Coordination with Priority-Based Search for Autonomous Vehicles. In Proceedings of the 37th AAAI Conference on Artificial Intelligence and 35th Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence (AAAI\u201923\/IAAI\u201923\/EAAI\u201923). AAAI Press, Article 1299, 8 pages. DOI: 10.1609\/aaai.v37i10.26368"},{"key":"e_1_3_2_37_2","first-page":"11272","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"35","author":"Li Jiaoyang","year":"2021","unstructured":"Jiaoyang Li, Andrew Tinka, Scott Kiesel, Joseph W. Durham, T. K. Satish Kumar, and Sven Koenig. 2021b. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 11272\u201311281."},{"issue":"1","key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/TSE.2013.46","article-title":"How Effectively Does Metamorphic Testing Alleviate the Oracle Problem?","volume":"40","author":"Liu Huai","year":"2013","unstructured":"Huai Liu, Fei-Ching Kuo, Dave Towey, and Tsong Yueh Chen. 2013. How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? IEEE Transactions on Software Engineering 40, 1 (2013), 4\u201322.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2022.3146323"},{"key":"e_1_3_2_40_2","first-page":"294","volume-title":"Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI\u201911)","volume":"1","author":"Luna Ryan","year":"2011","unstructured":"Ryan Luna and Kostas E. Bekris. 2011. Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI\u201911), Vol. 1. AAAI Press, 294\u2013300."},{"key":"e_1_3_2_41_2","first-page":"515","volume-title":"Proceedings of the 7th International Conference on Dependable Systems and Their Applications (DSA\u201920)","author":"Lv Shuxiao","year":"2020","unstructured":"Shuxiao Lv and Beibei Yin. 2020. Testing DNN-Based Path Planning Algorithms by Metamorphic Testing. In Proceedings of the 7th International Conference on Dependable Systems and Their Applications (DSA\u201920). 515\u2013526. DOI: 10.1109\/DSA51864.2020.00088"},{"key":"e_1_3_2_42_2","volume-title":"Proceedings of the 33rd AAAI Conference on Artificial Intelligence and 31st Innovative Applications of Artificial Intelligence Conference and 9th AAAI Symposium on Educational Advances in Artificial Intelligence (AAAI\u201919\/IAAI\u201919\/EAAI\u201919)","author":"Ma Hang","year":"2019","unstructured":"Hang Ma, Daniel Harabor, Peter J. Stuckey, Jiaoyang Li, and Sven Koenig. 2019. Searching with Consistent Prioritization for Multi-Agent Path Finding. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence and 31st Innovative Applications of Artificial Intelligence Conference and 9th AAAI Symposium on Educational Advances in Artificial Intelligence (AAAI\u201919\/IAAI\u201919\/EAAI\u201919). AAAI Press, Article 938, 8 pages. DOI: 10.1609\/aaai.v33i01.33017643"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2023.107263"},{"key":"e_1_3_2_44_2","unstructured":"Robert Morris Corina S. Pasareanu Kasper S\u00f8e Luckow Waqar Malik Hang Ma T. K. Satish Kumar and Sven Koenig. 2016. Planning Scheduling and Monitoring for Airport Surface Operations. In Planning for Hybrid Systems Papers from the 2016 AAAI Workshop AAAI Technical Report Vol. WS-16-12. Daniele Magazzeni Scott Sanner and Sylvie Thi\u00e9baux (Eds.). AAAI Press. Retrieved from http:\/\/www.aaai.org\/ocs\/index.php\/WS\/AAAIW16\/paper\/view\/12611"},{"key":"e_1_3_2_45_2","first-page":"99","volume-title":"Proceedings of the IEEE 22nd International Conference on Information Reuse and Integration for Data Science (IRI\u201921)","author":"Naidu Prudhviraj","year":"2021","unstructured":"Prudhviraj Naidu, Hemanth Gudaparthi, and Nan Niu. 2021. Metamorphic Testing for Convolutional Neural Networks: Relations Over Image Classification. In Proceedings of the IEEE 22nd International Conference on Information Reuse and Integration for Data Science (IRI\u201921). IEEE Press, 99\u2013106. DOI: 10.1109\/IRI51335.2021.00020"},{"key":"e_1_3_2_46_2","unstructured":"Keisuke Okumura. 2022. Repository with Implementations of HCA PIBT and PIBT \\(+\\) . Retrieved from https:\/\/github.com\/Kei18\/pibt2"},{"key":"e_1_3_2_47_2","volume-title":"Proceedings of the 37th AAAI Conference on Artificial Intelligence and 35th Conference on Innovative Applications of Artificial Intelligence and 13th Symposium on Educational Advances in Artificial Intelligence (AAAI\u201923\/IAAI\u201923\/EAAI\u201923)","author":"Okumura Keisuke","year":"2023","unstructured":"Keisuke Okumura. 2023. LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding. In Proceedings of the 37th AAAI Conference on Artificial Intelligence and 35th Conference on Innovative Applications of Artificial Intelligence and 13th Symposium on Educational Advances in Artificial Intelligence (AAAI\u201923\/IAAI\u201923\/EAAI\u201923). AAAI Press, Article 1308, 8 pages. DOI: 10.1609\/aaai.v37i10.26377"},{"key":"e_1_3_2_48_2","first-page":"535","volume-title":"Proceedings of the 28th International Joint Conference on Artificial Intelligence","author":"Okumura Keisuke","year":"2019","unstructured":"Keisuke Okumura, Manao Machida, Xavier D\u00e9fago, and Yasumasa Tamura. 2019. Priority Inheritance with Backtracking for Iterative Multi-Agent Path Finding. In Proceedings of the 28th International Joint Conference on Artificial Intelligence. AAAI Press, 535\u2013542."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103752"},{"key":"e_1_3_2_50_2","first-page":"9690","volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS\u201921)","author":"Okumura Keisuke","year":"2021","unstructured":"Keisuke Okumura, Yasumasa Tamura, and Xavier D\u00e9fago. 2021. Iterative Refinement for Real-Time Multi-Robot Path Planning. In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS\u201921). 9690\u20139697. DOI: 10.1109\/IROS51168.2021.9636071"},{"key":"e_1_3_2_51_2","first-page":"2413","volume-title":"Proceedings of the 45th International Conference on Software Engineering (ICSE\u201923)","author":"Paltenghi Matteo","year":"2023","unstructured":"Matteo Paltenghi and Michael Pradel. 2023. MorphQ: Metamorphic Testing of the Qiskit Quantum Computing Platform. In Proceedings of the 45th International Conference on Software Engineering (ICSE\u201923). IEEE Press, 2413\u20132424. DOI: 10.1109\/ICSE48619.2023.00202"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2020.3009698"},{"issue":"9","key":"e_1_3_2_53_2","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1109\/TSE.2016.2532875","article-title":"A Survey on Metamorphic Testing","volume":"42","author":"Segura Sergio","year":"2016","unstructured":"Sergio Segura, Gordon Fraser, Ana B. Sanchez, and Antonio Ruiz-Cort\u00e9s. 2016. A Survey on Metamorphic Testing. IEEE Transactions on Software Engineering 42, 9 (2016), 805\u2013824.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2010.11.002"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/MS.2018.2875968"},{"key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","article-title":"Conflict-Based Search for Optimal Multi-Agent Pathfinding","volume":"219","author":"Sharon Guni","year":"2015","unstructured":"Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. 2015. Conflict-Based Search for Optimal Multi-Agent Pathfinding. Artificial Intelligence 219, 40\u201366.","journal-title":"Artificial Intelligence"},{"key":"e_1_3_2_57_2","first-page":"117","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment","volume":"1","author":"Silver David","year":"2005","unstructured":"David Silver. 2005. Cooperative Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 1, 1 (Sep. 2005), 117\u2013122. DOI: 10.1609\/aiide.v1i1.18726"},{"key":"e_1_3_2_58_2","first-page":"151","article-title":"Multi-Agent Path Finding: Definitions, Variants, and Benchmarks","author":"Stern Roni","year":"2019","unstructured":"Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Eli Boyarski, and Roman Bartak. 2019. Multi-Agent Path Finding: Definitions, Variants, and Benchmarks. In Proceedings of the International Symposium on Combinatorial Search (SoCS\u201919), 151\u2013158.","journal-title":"Proceedings of the International Symposium on Combinatorial Search (SoCS\u201919)"},{"key":"e_1_3_2_59_2","unstructured":"Nathan Sturtevant. 2019. Multi-Agent Path-Finding (MAPF) Benchmarks. Retrieved from https:\/\/movingai.com\/benchmarks\/mapf\/index.html"},{"key":"e_1_3_2_60_2","first-page":"1764","volume-title":"IEEE Transactions on Software Engineering","volume":"47","author":"Sun Chang-Ai","year":"2021","unstructured":"Chang-Ai Sun, An Fu, Pak-Lok Poon, Xiaoyuan Xie, Huai Liu, and Tsong Yueh Chen. 2021. METRIC+: A Metamorphic Relation Identification Technique Based on Input Plus Output Domains. IEEE Transactions on Software Engineering 47, 9 (2021), 1764\u20131785."},{"key":"e_1_3_2_61_2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1145\/3180155.3180220","volume-title":"Proceedings of the 40th International Conference on Software Engineering","author":"Tian Yuchi","year":"2018","unstructured":"Yuchi Tian, Kexin Pei, Suman Jana, and Baishakhi Ray. 2018. DeepTest: Automated Testing of Deep-Neural-Network-Driven Autonomous Cars. In Proceedings of the 40th International Conference on Software Engineering (ICSE 18). ACM, New York, NY, 303\u2013314. DOI: 10.1145\/3180155.3180220"},{"key":"e_1_3_2_62_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/3293882.3330567","volume-title":"Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis","author":"Tolksdorf Sandro","year":"2019","unstructured":"Sandro Tolksdorf, Daniel Lehmann, and Michael Pradel. 2019. Interactive Metamorphic Testing of Debuggers. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis. ACM, New York, NY, 273\u2013283."},{"key":"e_1_3_2_63_2","first-page":"4423","volume-title":"Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI\u201915)","author":"Veloso Manuela","year":"2015","unstructured":"Manuela Veloso, Joydeep Biswas, Brian Coltin, and Stephanie Rosenthal. 2015. CoBots: Robust Symbiotic Autonomous Mobile Service Robots. In Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI\u201915). AAAI Press, 4423\u20134429."},{"key":"e_1_3_2_64_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2014.11.001","article-title":"Subdimensional Expansion for Multirobot Path Planning","volume":"219","author":"Wagner Glenn","year":"2015","unstructured":"Glenn Wagner and Howie Choset. 2015. Subdimensional Expansion for Multirobot Path Planning. Artificial Intelligence 219, 1\u201324.","journal-title":"Artificial Intelligence"},{"key":"e_1_3_2_65_2","volume-title":"Proceedings of the 19th AAAI Conference on Artificial Intelligence and Interactive Digital EntertainmentArticle","volume":"37","author":"Wang Shuwei","year":"2023","unstructured":"Shuwei Wang, Vadim Bulitko, Taoan Huang, Sven Koenig, and Roni Stern. 2023. Synthesizing Priority Planning Formulae for Multi-Agent Pathfinding. In Proceedings of the 19th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE\u201923). AAAI Press, Article 37, 10 pages. DOI: 10.1609\/aiide.v19i1.27532"},{"key":"e_1_3_2_66_2","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1145\/3324884.3416584","volume-title":"Proceedings of the 35th IEEE\/ACM International Conference on Automated Software Engineering","author":"Wang Shuai","year":"2020","unstructured":"Shuai Wang and Zhendong Su. 2020. Metamorphic Object Insertion for Testing Object Detection Systems. In Proceedings of the 35th IEEE\/ACM International Conference on Automated Software Engineering (ASE 20). ACM, New York, NY, 1053\u20131065. DOI: 10.1145\/3324884.3416584"},{"key":"e_1_3_2_67_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-29044-2","volume-title":"Experimentation in Software Engineering","author":"Wohlin Claes","year":"2012","unstructured":"Claes Wohlin, Per Runeson, Martin Hst, Magnus C. Ohlsson, Bjrn Regnell, and Anders Wessln. 2012. Experimentation in Software Engineering. Springer Publishing Company, Incorporated."},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2023.111769"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v29i1.2082"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3508035"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","unstructured":"Xiaoyuan Xie W. Eric Wong Tsong Yueh Chen and Baowen Xu. 2013. Metamorphic Slice: An Application in Spectrum-Based Fault Localization. Information and Software Technology 55 5 (May 2013) 866\u2013879. DOI: 10.1016\/j.infsof.2012.08.008","DOI":"10.1016\/j.infsof.2012.08.008"},{"key":"e_1_3_2_72_2","unstructured":"Konstantin Yakovlev and Anton Andreychuk. 2019. City\/Street Maps. Retrieved from https:\/\/movingai.com\/benchmarks\/street\/index.html"},{"key":"e_1_3_2_73_2","first-page":"1443","volume-title":"Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI\u201913)","author":"Yu Jingjin","year":"2013","unstructured":"Jingjin Yu and Steven M. LaValle. 2013. Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI\u201913). AAAI Press, 1443\u20131449."},{"issue":"5","key":"e_1_3_2_74_2","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1109\/TRO.2016.2593448","article-title":"Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics","volume":"32","author":"Yu Jingjin","year":"2016","unstructured":"Jingjin Yu and Steven M LaValle. 2016. Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics. IEEE Transactions on Robotics 32, 5 (2016), 1163\u20131177.","journal-title":"IEEE Transactions on Robotics"},{"key":"e_1_3_2_75_2","first-page":"16903","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201921)","author":"Yuan Yuanyuan","year":"2021","unstructured":"Yuanyuan Yuan, Shuai Wang, Mingyue Jiang, and Tsong Yueh Chen. 2021. Perception Matters: Detecting Perception Failures of VQA Models Using Metamorphic Testing. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201921). 16903\u201316912. DOI: 10.1109\/CVPR46437.2021.01663"},{"key":"e_1_3_2_76_2","first-page":"235","volume-title":"Proceedings of the IEEE International Conference on Software Maintenance and Evolution (ICSME\u201919)","author":"Zhang Bo","year":"2019","unstructured":"Bo Zhang, Hongyu Zhang, Junjie Chen, Dan Hao, and Pablo Moscato. 2019a. Automatic Discovery and Cleansing of Numerical Metamorphic Relations. In Proceedings of the IEEE International Conference on Software Maintenance and Evolution (ICSME\u201919). 235\u2013245. DOI: 10.1109\/ICSME.2019.00035"},{"key":"e_1_3_2_77_2","first-page":"158","volume-title":"Proceedings of the IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC\u201919)","author":"Zhang Jiantao","year":"2019","unstructured":"Jiantao Zhang, Zheng Zheng, Beibei Yin, Kun Qiu, and Yang Liu. 2019b. Testing Graph Searching Based Path Planning Algorithms by Metamorphic Testing. In Proceedings of the IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC\u201919). IEEE, 158\u2013167. DOI: 10.1109\/PRDC47002.2019.00046"},{"key":"e_1_3_2_78_2","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1145\/3238147.3238187","volume-title":"Proceedings of the 33rd ACM\/IEEE International Conference on Automated Software Engineering (ASE\u201918)","author":"Zhang Mengshi","year":"2018","unstructured":"Mengshi Zhang, Yuqun Zhang, Lingming Zhang, Cong Liu, and Sarfraz Khurshid. 2018. DeepRoad: GAN-Based Metamorphic Testing and Input Validation Framework for Autonomous Driving Systems. In Proceedings of the 33rd ACM\/IEEE International Conference on Automated Software Engineering (ASE\u201918). ACM, New York, NY, 132\u2013142. DOI: 10.1145\/3238147.3238187"},{"key":"e_1_3_2_79_2","doi-asserted-by":"crossref","unstructured":"Xiao-Yi Zhang Yang Liu Paolo Arcaini Mingyue Jiang and Zheng Zheng. 2024. Code and Experimental Results of the Paper \u201cMET-MAPF: A Metamorphic Testing Approach for Multi-Agent Path Finding Algorithms.\u201d Retrieved from https:\/\/github.com\/NeNeSakura\/MET-MAPF","DOI":"10.1145\/3669663"},{"key":"e_1_3_2_80_2","first-page":"61","volume-title":"Commun. ACM","volume":"62","author":"Zhou Zhi Quan","year":"2019","unstructured":"Zhi Quan Zhou and Liqun Sun. 2019. Metamorphic Testing of Driverless Cars. Commun. ACM 62, 3 (2019), 61\u201367."},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2018.2876433"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3669663","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3669663","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:56:40Z","timestamp":1750291000000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3669663"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,21]]},"references-count":80,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,11,30]]}},"alternative-id":["10.1145\/3669663"],"URL":"https:\/\/doi.org\/10.1145\/3669663","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"value":"1049-331X","type":"print"},{"value":"1557-7392","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,21]]},"assertion":[{"value":"2023-08-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}