{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:49:34Z","timestamp":1778496574224,"version":"3.51.4"},"reference-count":36,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1734419"],"award-info":[{"award-number":["1734419"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1845888"],"award-info":[{"award-number":["1845888"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1934924"],"award-info":[{"award-number":["1934924"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>\n                    A great number of robotics applications demand the rearrangement of many mobile objects, for example, organizing products on store shelves, shuffling containers at shipping ports, reconfiguring fleets of mobile robots, and so on. To boost the efficiency\/throughput in systems designed for solving these rearrangement problems, it is essential to minimize the number of atomic operations that are involved, for example, the pick-n-places of individual objects. However, this optimization task poses a rather difficult challenge due to the complex inter-dependency between the objects, especially when they are tightly packed together. In this work, in tackling the aforementioned challenges, we have developed a novel algorithmic tool, called Rubik Tables, that provides a clean abstraction of object rearrangement problems as the proxy problem of shuffling items stored in a table or lattice. In its basic form, a Rubik Table is an n \u00d7 n table containing n\n                    <jats:sup>2<\/jats:sup>\n                    items. We show that the reconfiguration of items in such a Rubik Table can be achieved using at most n column and n row shuffles in the partially labeled setting, where each column (resp., row) shuffle may arbitrarily permute the items stored in a column (resp., row) of the table. When items are fully distinguishable, additional n shuffles are needed. Rubik Tables allow many generalizations, for example, adding an additional depth dimension or extending to higher dimensions. Using Rubik Table results, we have designed a first constant-factor optimal algorithm for stack rearrangement problems where items are stored in stacks, accessible only from the top. We show that, for nd items stored in n stacks of depth d each, using one empty stack as the swap space, O( nd) stack pop-push operations are sufficient for an arbitrary reconfiguration of the stacks where [Formula: see text] for arbitrary fixed m &gt; 0. Rubik Table results also allow the development of constant-factor optimal solutions for solving multi-robot motion planning problems under extreme robot density. These algorithms based on Rubik Table results run in low-polynomial time.\n                  <\/jats:p>","DOI":"10.1177\/02783649211059844","type":"journal-article","created":{"date-parts":[[2022,3,1]],"date-time":"2022-03-01T00:55:25Z","timestamp":1646096125000},"page":"459-472","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":4,"title":["Rubik Tables and object rearrangement"],"prefix":"10.1177","volume":"42","author":[{"given":"Mario","family":"Szegedy","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4112-2250","authenticated-orcid":false,"given":"Jingjin","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rutgers University, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2022,2,28]]},"reference":[{"key":"bibr1-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808726"},{"key":"bibr2-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2715406"},{"key":"bibr3-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/70.704220"},{"key":"bibr4-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/s00291-010-0205-4"},{"key":"bibr5-02783649211059844","first-page":"1975","volume":"8","author":"Brousseau BA","year":"1980","journal-title":"Journal of Recreational Mathematics"},{"key":"bibr6-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.577"},{"key":"bibr7-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"key":"bibr8-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.06.018"},{"key":"bibr9-02783649211059844","volume-title":"Pushpush and push-1 are np-hard in 2d","author":"Demaine ED","year":"2000"},{"key":"bibr10-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1137\/18M1194341"},{"key":"bibr11-02783649211059844","unstructured":"Demaine ED, Hoffmann M (2001) Pushing blocks is np-complete for noncrossing solution paths. In: Proceeding 13th Canadian conference computational geometry, pp. 1\u20135."},{"key":"bibr12-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840371"},{"key":"bibr13-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_11"},{"key":"bibr14-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1137\/100812513"},{"key":"bibr15-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2006.02.001"},{"key":"bibr16-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4842-8_4"},{"key":"bibr17-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2800116"},{"key":"bibr18-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918780999"},{"key":"bibr19-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906894"},{"key":"bibr20-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793946"},{"key":"bibr21-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715921"},{"key":"bibr22-02783649211059844","first-page":"1","volume-title":"Robotics: Science and Systems","author":"Krontiris A","year":"2015"},{"key":"bibr23-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487581"},{"key":"bibr24-02783649211059844","unstructured":"Li J, Tinka A, Kiesel S, et al. (2020) Lifelong multi-agent path finding in large-scale warehouses. In: Proceedings International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1898\u20131900."},{"key":"bibr25-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2021.3055144"},{"key":"bibr26-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1177\/0278364916672311"},{"key":"bibr27-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908098457"},{"key":"bibr28-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49116-3_33"},{"key":"bibr29-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-66723-8_31"},{"key":"bibr30-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00312-7_37"},{"key":"bibr31-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90321-J"},{"key":"bibr32-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530890"},{"issue":"1","key":"bibr33-02783649211059844","first-page":"9","volume":"29","author":"Wurman PR","year":"2008","journal-title":"AI Magazine"},{"key":"bibr34-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2015.2503143"},{"key":"bibr35-02783649211059844","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2018.XIV.013"},{"key":"bibr36-02783649211059844","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v27i1.8541"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211059844","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649211059844","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211059844","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211059844","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:04Z","timestamp":1777457824000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649211059844"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,28]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.1177\/02783649211059844"],"URL":"https:\/\/doi.org\/10.1177\/02783649211059844","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,28]]}}}