{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:53:49Z","timestamp":1777715629448,"version":"3.51.4"},"reference-count":69,"publisher":"SAGE Publications","issue":"13-14","license":[{"start":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T00:00:00Z","timestamp":1532044800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"NSF","award":["CCF-1330789"],"award-info":[{"award-number":["CCF-1330789"]}]},{"name":"NSF","award":["IIS-1451737"],"award-info":[{"award-number":["IIS-1451737"]}]},{"name":"NSF","award":["IIS-1617744"],"award-info":[{"award-number":["IIS-1617744"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p>This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them from above and perform pick-and-place operations to rearrange them. The paper considers both the case where the start and goal object poses overlap, and where they do not. For overlapping poses, the primary objective is to minimize the number of pick-and-place actions and then to minimize the distance traveled by the end-effector. For the non-overlapping case, the objective is solely to minimize the travel distance of the end-effector. Although such problems do not involve all the complexities of general rearrangement, they remain computationally hard in both cases. This is shown through reductions from well-understood, hard combinatorial challenges to these rearrangement problems. The reductions are also shown to hold in the reverse direction, which enables the convenient application on rearrangement of well-studied algorithms. These algorithms can be very efficient in practice despite the hardness results. The paper builds on these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problems. Experimental evaluation, including hardware-based trials, shows that the proposed pipeline computes high-quality paths with regards to the optimization objectives. Furthermore, it exhibits highly desirable scalability as the number of objects increases in both the overlapping and non-overlapping setup.<\/jats:p>","DOI":"10.1177\/0278364918780999","type":"journal-article","created":{"date-parts":[[2018,7,20]],"date-time":"2018-07-20T05:49:22Z","timestamp":1532065762000},"page":"1775-1795","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":49,"title":["Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps"],"prefix":"10.1177","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7741-2378","authenticated-orcid":false,"given":"Shuai D","family":"Han","sequence":"first","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0164-1809","authenticated-orcid":false,"given":"Nicholas M","family":"Stiffler","sequence":"additional","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Athanasios","family":"Krontiris","sequence":"additional","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas E","family":"Bekris","sequence":"additional","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingjin","family":"Yu","sequence":"additional","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2018,7,20]]},"reference":[{"key":"bibr1-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220408"},{"key":"bibr2-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841103"},{"key":"bibr3-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009476"},{"key":"bibr4-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009259"},{"key":"bibr5-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"bibr6-0278364918780999","unstructured":"Baharev A, Schichl H, Neumaier A (2015) An exact method for the minimum feedback arc set problem. University of Vienna. Available at: http:\/\/www.mat.univie.ac.at\/neum\/ms\/minimum_feedback_arc_set.pdf"},{"key":"bibr7-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/70.704220"},{"key":"bibr8-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/s11750-007-0009-0"},{"key":"bibr9-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.04.024"},{"key":"bibr10-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910396389"},{"key":"bibr11-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24803-3_5"},{"key":"bibr12-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2289018"},{"key":"bibr13-0278364918780999","unstructured":"Bonnard Q, Lemaignan S, Zufferey G, et al. (2013) Chilitags 2: robust fiducial markers for augmented reality and robotics. Available at: http:\/\/chili.epfl.ch\/software."},{"key":"bibr14-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1137\/060652063"},{"key":"bibr15-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097884"},{"key":"bibr16-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1991.131618"},{"key":"bibr17-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1969.75"},{"key":"bibr18-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909105606"},{"key":"bibr19-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913507983"},{"key":"bibr20-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6094737"},{"key":"bibr21-0278364918780999","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2016.XII.002"},{"key":"bibr22-0278364918780999","first-page":"211","volume-title":"Proceedings Candadian Conference on Computational Geometry","author":"Demaine E","year":"2000"},{"key":"bibr23-0278364918780999","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"bibr24-0278364918780999","author":"Dogar MR","year":"2011","journal-title":"Proceedings Robotics: Science and Systems"},{"key":"bibr25-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"bibr26-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1029"},{"key":"bibr27-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.6"},{"key":"bibr28-0278364918780999","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey MR","year":"1979"},{"key":"bibr29-0278364918780999","volume-title":"Proceedings Workshop on the Algorithmic Foundations of Robotics","author":"Garrett CR","year":"2014"},{"key":"bibr30-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7354286"},{"key":"bibr31-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9290-7"},{"key":"bibr32-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.05.009"},{"key":"bibr33-0278364918780999","unstructured":"Gurobi Optimization I (2016) Gurobi Optimizer Reference Manual. Available at: http:\/\/www.gurobi.com."},{"key":"bibr34-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/s004539910025"},{"key":"bibr35-0278364918780999","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2017.XIII.051"},{"key":"bibr36-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913507795"},{"key":"bibr37-0278364918780999","volume-title":"Proceedings IEEE International Conference on Robotics and Automation","author":"Havur G","year":"2014"},{"key":"bibr38-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-006-0164-7"},{"key":"bibr39-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"bibr40-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715921"},{"key":"bibr41-0278364918780999","author":"Krontiris A","year":"2015","journal-title":"Proceedings Robotics: Science and Systems"},{"key":"bibr42-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487581"},{"key":"bibr43-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/HUMANOIDS.2014.7041499"},{"key":"bibr44-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(92)90192-C"},{"key":"bibr45-0278364918780999","first-page":"1118","volume-title":"Proceedings International Joint Conferences on Artificial Intelligence","author":"Leroy S","year":"1999"},{"key":"bibr46-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290149"},{"key":"bibr47-0278364918780999","volume-title":"Proceedings of the Workshop on the Algorithmic Foundations of Robotics","author":"Nieuwenhuisen D","year":"2006"},{"key":"bibr48-0278364918780999","volume-title":"Proceedings IEEE International Conference on Robotics and Automation","author":"Ota J","year":"2004"},{"key":"bibr49-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"bibr50-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509563"},{"key":"bibr51-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696520"},{"key":"bibr52-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.006"},{"key":"bibr53-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045471"},{"key":"bibr54-0278364918780999","author":"Solovey K","year":"2015","journal-title":"Proceedings Robotics: Science and Systems"},{"key":"bibr55-0278364918780999","author":"Solovey K","year":"2015","journal-title":"Proceedings Robotics: Science and Systems"},{"key":"bibr56-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906922"},{"key":"bibr57-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363986"},{"key":"bibr58-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.932818"},{"key":"bibr59-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2259993"},{"key":"bibr60-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2005.1545306"},{"key":"bibr61-0278364918780999","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2009.V.018"},{"key":"bibr62-0278364918780999","volume-title":"Proceedings of the Workshop on the Algorithmic Foundations of Robotics","author":"van den Berg J","year":"2008"},{"key":"bibr63-0278364918780999","volume-title":"Proceedings of the Workshop on the Algorithmic Foundations of Robotics","author":"Vega-Brown W","year":"2016"},{"key":"bibr64-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225297"},{"key":"bibr65-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530890"},{"key":"bibr66-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90048-5"},{"key":"bibr67-0278364918780999","volume-title":"Proceedings of the Workshop on the Algorithmic Foundations of Robotics","author":"Yu J","year":"2012"},{"key":"bibr68-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2593448"},{"key":"bibr69-0278364918780999","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913488805"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918780999","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364918780999","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918780999","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918780999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:44Z","timestamp":1777457744000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364918780999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,20]]},"references-count":69,"journal-issue":{"issue":"13-14","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1177\/0278364918780999"],"URL":"https:\/\/doi.org\/10.1177\/0278364918780999","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,20]]}}}