{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:59:11Z","timestamp":1777715951198,"version":"3.51.4"},"reference-count":50,"publisher":"SAGE Publications","issue":"10","license":[{"start":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:00:00Z","timestamp":1675296000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"NSF","award":["CCF-1934924"],"award-info":[{"award-number":["CCF-1934924"]}]},{"name":"NSF","award":["IIS-1734419"],"award-info":[{"award-number":["IIS-1734419"]}]},{"name":"NSF","award":["IIS-1845888"],"award-info":[{"award-number":["IIS-1845888"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:p>We study a class of rearrangement problems under a novel pick-n-swap prehensile manipulation model, in which a robotic manipulator, capable of carrying an item and making item swaps, is tasked to sort items stored in lattices of variable dimensions in a time-optimal manner. We systematically analyze the intrinsic optimality structure, which is fairly rich and intriguing, under different levels of item distinguishability (fully-labeled, where each item has a unique label, or partially-labeled, where multiple items may be of the same type) and different lattice dimensions. Focusing on the most practical setting of one and two dimensions, we develop low polynomial time cycle-following-based algorithms that optimally perform rearrangements on 1D lattices under both fully- and partially-labeled settings. On the other hand, we show that rearrangement on 2D and higher-dimensional lattices become computationally intractable to optimally solve. Despite their NP-hardness, we prove that efficient cycle-following-based algorithms remain optimal in the asymptotic sense for 2D fully- and partially-labeled settings, in expectation, using the interesting fact that random permutations induce only a small number of cycles. We further improve these algorithms to provide 1. x-optimality when the number of items is small. Simulation studies corroborate the effectiveness of our algorithms. The implementation of the algorithms from the paper can be found at github.com\/arc-l\/lattice-rearrangement.<\/jats:p>","DOI":"10.1177\/02783649231153901","type":"journal-article","created":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T08:49:59Z","timestamp":1675327799000},"page":"957-973","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Rearrangement on lattices with pick-n-swaps: Optimality structures and efficient algorithms"],"prefix":"10.1177","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7594-7798","authenticated-orcid":false,"given":"Jingjin","family":"Yu","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2023,2,2]]},"reference":[{"key":"bibr1-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/HUMANOIDS.2018.8624977"},{"key":"bibr2-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/70.704220"},{"key":"bibr3-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9378"},{"key":"bibr4-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.42"},{"key":"bibr5-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224575"},{"key":"bibr6-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7354264"},{"key":"bibr7-02783649231153901","first-page":"1396","volume":"14","author":"Chu YJ","year":"1965","journal-title":"Scientia Sinica"},{"key":"bibr8-02783649231153901","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2011.VII.009"},{"key":"bibr9-02783649231153901","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"bibr10-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-28619-4_32"},{"key":"bibr11-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"bibr12-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891840"},{"key":"bibr13-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918780999"},{"key":"bibr14-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139621"},{"key":"bibr15-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906894"},{"key":"bibr16-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"bibr17-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561073"},{"key":"bibr18-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793946"},{"key":"bibr19-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90001-0"},{"key":"bibr20-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980391"},{"key":"bibr21-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"bibr22-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487583"},{"key":"bibr23-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139535"},{"key":"bibr24-02783649231153901","volume-title":"Robotics: Science and Systems","volume":"1123","author":"Krontiris A","year":"2015"},{"key":"bibr25-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487581"},{"key":"bibr26-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"bibr27-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/COASE.2016.7743488"},{"key":"bibr28-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793616"},{"issue":"1","key":"bibr29-02783649231153901","first-page":"1334","volume":"17","author":"Levine S","year":"2016","journal-title":"The Journal of Machine Learning Research"},{"key":"bibr30-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1177\/027836499901800105"},{"key":"bibr31-02783649231153901","doi-asserted-by":"crossref","unstructured":"Mahler J, Liang J, Niyaz S, et al. (2017) Dex-net 2.0: deep learning to plan robust grasps with synthetic point clouds and analytic grasp metrics. arXiv preprint arXiv:1703.09312.","DOI":"10.15607\/RSS.2017.XIII.058"},{"key":"bibr32-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-060117-104848"},{"key":"bibr33-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997839"},{"issue":"2","key":"bibr34-02783649231153901","first-page":"712","volume":"3","author":"Moll M","year":"2017","journal-title":"IEEE Robotics and Automation Letters"},{"key":"bibr35-02783649231153901","unstructured":"Nam C, Lee J, Cho Y, et al. (2019) Planning for target retrieval using a robotic manipulator in cluttered and occluded environments. arXiv preprint arXiv:1907.03956."},{"key":"bibr36-02783649231153901","doi-asserted-by":"crossref","unstructured":"Pan Z, Hauser K (2020) Decision making in joint push-grasp action space for large-scale object sorting. arXiv preprint arXiv:2010.10064.","DOI":"10.1109\/ICRA48506.2021.9560782"},{"key":"bibr37-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"bibr38-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"bibr39-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511617331"},{"key":"bibr40-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2021.3055144"},{"key":"bibr41-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913506268"},{"key":"bibr42-02783649231153901","doi-asserted-by":"crossref","unstructured":"Song H, Haustein JA, Yuan W, et al. (2019) Multi-object rearrangement with monte carlo tree search: a case study on planar nonprehensile sorting. arXiv preprint arXiv:1912.07024.","DOI":"10.1109\/IROS45743.2020.9341532"},{"key":"bibr43-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1142\/S0219843605000545"},{"key":"bibr44-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363986"},{"key":"bibr45-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2259993"},{"key":"bibr46-02783649231153901","first-page":"2","volume-title":"Robotics: Science and Systems","volume":"2","author":"van Den Berg J","year":"2009"},{"key":"bibr47-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530890"},{"key":"bibr48-02783649231153901","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2021.XVII.014"},{"key":"bibr49-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2018.8593986"},{"key":"bibr50-02783649231153901","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919868017"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231153901","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649231153901","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231153901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:58Z","timestamp":1777457818000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649231153901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,2]]},"references-count":50,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["10.1177\/02783649231153901"],"URL":"https:\/\/doi.org\/10.1177\/02783649231153901","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,2]]}}}