{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,14]],"date-time":"2026-06-14T18:54:47Z","timestamp":1781463287671,"version":"3.54.1"},"reference-count":18,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2026,10]]},"DOI":"10.1016\/j.dam.2026.04.047","type":"journal-article","created":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T11:32:37Z","timestamp":1779190357000},"page":"294-316","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Hostile, Compatible, or Free: A constant time classification of pairwise shortest path conflicts in obstacle-free MAPF"],"prefix":"10.1016","volume":"391","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9312-6088","authenticated-orcid":false,"given":"Lifeng","family":"Guo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hang","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Changhong","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/j.dam.2026.04.047_b1","doi-asserted-by":"crossref","first-page":"1941","DOI":"10.1109\/LRA.2017.2715406","article-title":"Intractability of time-optimal multirobot path planning on 2D grid graphs with holes","volume":"2","author":"Banfi","year":"2017","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"1","key":"10.1016\/j.dam.2026.04.047_b2","first-page":"19","article-title":"Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem","volume":"5","author":"Barer","year":"2021","journal-title":"Proc. Int. Symp. Comb. Search"},{"key":"10.1016\/j.dam.2026.04.047_b3","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1613\/jair.3907","article-title":"NuMVC: An efficient local search algorithm for minimum vertex cover","volume":"46","author":"Cai","year":"2013","journal-title":"J. Artificial Intelligence Res."},{"issue":"2","key":"10.1016\/j.dam.2026.04.047_b4","doi-asserted-by":"crossref","first-page":"72","DOI":"10.3390\/a17020072","article-title":"An attention-based method for the minimum vertex cover problem on complex networks","volume":"17","author":"Lazzarinetti","year":"2024","journal-title":"Algorithms"},{"key":"10.1016\/j.dam.2026.04.047_b5","first-page":"10256","article-title":"MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search","volume":"vol. 36, no. 9","author":"Li","year":"2022"},{"key":"10.1016\/j.dam.2026.04.047_b6","series-title":"Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence","first-page":"442","article-title":"Improved heuristics for multi-agent path finding with conflict-based search","author":"Li","year":"2019"},{"key":"10.1016\/j.dam.2026.04.047_b7","doi-asserted-by":"crossref","DOI":"10.1016\/j.artint.2021.103574","article-title":"Pairwise symmetry reasoning for multi-agent path finding search","volume":"301","author":"Li","year":"2021","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.dam.2026.04.047_b8","series-title":"Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.65109\/YQID4918","article-title":"Engineering LaCAM*: Towards real-time, large-scale, and near-optimal multi-agent pathfinding","author":"Okumura","year":"2024"},{"key":"10.1016\/j.dam.2026.04.047_b9","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","year":"2015","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.dam.2026.04.047_b10","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1016\/j.artint.2012.11.006","article-title":"The increasing cost tree search for optimal multi-agent pathfinding","volume":"195","author":"Sharon","year":"2013","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.dam.2026.04.047_b11","series-title":"Cooperative Reward Shaping for Multi-Agent Pathfinding","author":"Song","year":"2025"},{"key":"10.1016\/j.dam.2026.04.047_b12","first-page":"173","article-title":"Finding optimal solutions to cooperative pathfinding problems","volume":"vol. 24, no. 1","author":"Standley","year":"2010"},{"key":"10.1016\/j.dam.2026.04.047_b13","series-title":"Artificial Intelligence: 5th RAAI Summer School, Dolgoprudny, Russia, July 4\u20137, 2019, Tutorial Lectures","first-page":"96","article-title":"Multi-agent path finding \u2013 an overview","author":"Stern","year":"2019"},{"key":"10.1016\/j.dam.2026.04.047_b14","first-page":"151","article-title":"Multi-agent pathfinding: Definitions, variants, and benchmarks","volume":"vol. 10, no. 1","author":"Stern","year":"2021"},{"key":"10.1016\/j.dam.2026.04.047_b15","series-title":"2024 IEEE International Conference on Robotics and Automation","first-page":"15076","article-title":"POAQL: A partially observable altruistic Q-learning method for cooperative multi-agent reinforcement learning","author":"Tao","year":"2024"},{"key":"10.1016\/j.dam.2026.04.047_b16","series-title":"2011 IEEE\/RSJ International Conference on Intelligent Robots and Systems","first-page":"3260","article-title":"M*: A complete multirobot path planning algorithm with performance bounds","author":"Wagner","year":"2011"},{"key":"10.1016\/j.dam.2026.04.047_b17","series-title":"Where paths collide: A comprehensive survey of classic and learning-based multi-agent pathfinding","author":"Wang","year":"2025"},{"issue":"18","key":"10.1016\/j.dam.2026.04.047_b18","doi-asserted-by":"crossref","first-page":"7831","DOI":"10.3390\/s23187831","article-title":"TIVC: An efficient local search algorithm for minimum vertex cover in large graphs","volume":"23","author":"Zhang","year":"2023","journal-title":"Sensors"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X26002763?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X26002763?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,6,14]],"date-time":"2026-06-14T18:06:26Z","timestamp":1781460386000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X26002763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10]]},"references-count":18,"alternative-id":["S0166218X26002763"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2026.04.047","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2026,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Hostile, Compatible, or Free: A constant time classification of pairwise shortest path conflicts in obstacle-free MAPF","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.dam.2026.04.047","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}]}}