{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T09:11:30Z","timestamp":1779268290629,"version":"3.51.4"},"reference-count":26,"publisher":"SAGE Publications","issue":"14","license":[{"start":{"date-parts":[[2016,11,1]],"date-time":"2016-11-01T00:00:00Z","timestamp":1477958400000},"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":[[2016,12]]},"abstract":"<jats:p>In unlabeled multi-robot motion planning, several interchangeable robots operate in a common workspace. The goal is to move the robots to a set of target positions such that each position will be occupied by some robot. In this paper, we study this problem for the specific case of unit-square robots moving amidst polygonal obstacles and show that it is PSPACE-hard. We also consider three additional variants of this problem and show that they are all PSPACE-hard as well. To the best of our knowledge, this is the first hardness proof for the unlabeled case. Furthermore, our proofs can be used to show that the labeled variant (where each robot is assigned a specific target position), again, for unit-square robots, is PSPACE-hard as well, which sets another precedent, as previous hardness results require the robots to be of different shapes (or at least in different orientations). Lastly, we settle an open problem regarding the complexity of the well-known Rush-Hour puzzle for unit-square cars in environments with polygonal obstacles.<\/jats:p>","DOI":"10.1177\/0278364916672311","type":"journal-article","created":{"date-parts":[[2016,11,1]],"date-time":"2016-11-01T21:16:19Z","timestamp":1478034979000},"page":"1750-1759","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":54,"title":["On the hardness of unlabeled multi-robot motion planning"],"prefix":"10.1177","volume":"35","author":[{"given":"Kiril","family":"Solovey","sequence":"first","affiliation":[{"name":"Blavatnik School of Computer Science, Tel-Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel-Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2016,11,1]]},"reference":[{"key":"bibr1-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2015.2470096"},{"key":"bibr2-0278364916672311","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.20.719"},{"key":"bibr3-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45030-3_25"},{"key":"bibr4-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00173-6"},{"key":"bibr5-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.008"},{"key":"bibr6-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1201\/b10581"},{"key":"bibr7-0278364916672311","first-page":"239","volume-title":"Workshop on the algorithmic foundations of robotics (WAFR)","author":"Hirsch S","year":"2002"},{"key":"bibr8-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30347-0_22"},{"key":"bibr9-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"bibr10-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.014"},{"issue":"4","key":"bibr11-0278364916672311","first-page":"650","volume":"22","author":"Kloder S","year":"2006","journal-title":"International conference on robotics and automation"},{"key":"bibr12-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1109\/HUMANOIDS.2014.7041499"},{"key":"bibr13-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00076-0"},{"key":"bibr14-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2014.2331983"},{"key":"bibr15-0278364916672311","first-page":"2112","volume-title":"International conference on robotics and automation (ICRA)","author":"S\u00e1nchez-Ante G","year":"2002"},{"key":"bibr16-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1177\/027836498300200304"},{"key":"bibr17-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530889"},{"key":"bibr18-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913506268"},{"key":"bibr19-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915615688"},{"key":"bibr20-0278364916672311","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2015.XI.011"},{"key":"bibr21-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90130-3"},{"key":"bibr22-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1016\/S0921-8890(97)00033-X"},{"key":"bibr23-0278364916672311","unstructured":"Tromp J, Cilibrasi R (2005) Limits of rush hour logic complexity.\n                      CoRR\n                      abs\/cs\/0502068."},{"key":"bibr24-0278364916672311","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913515307"},{"key":"bibr25-0278364916672311","doi-asserted-by":"crossref","unstructured":"Wagner G, Choset H (2011) M*: A complete multirobot path planning algorithm with performance bounds. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 25\u201330 September, pp. 3260\u20133267. Available at http:\/\/dx.doi.org\/10.1109\/IROS.2011.6095022.","DOI":"10.1109\/IROS.2011.6095022"},{"key":"bibr26-0278364916672311","unstructured":"Yap CK (1984) Coordinating the motion of several discs. Technical report, Courant Institute of Mathematical Sciences, New York."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364916672311","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364916672311","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364916672311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:17Z","timestamp":1777457717000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364916672311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,1]]},"references-count":26,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["10.1177\/0278364916672311"],"URL":"https:\/\/doi.org\/10.1177\/0278364916672311","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,1]]}}}