{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T02:49:13Z","timestamp":1774147753418,"version":"3.50.1"},"reference-count":79,"publisher":"SAGE Publications","issue":"10","license":[{"start":{"date-parts":[[2024,6,8]],"date-time":"2024-06-08T00:00:00Z","timestamp":1717804800000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1934924"],"award-info":[{"award-number":["CCF-1934924"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1845888"],"award-info":[{"award-number":["IIS-1845888"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-2132972"],"award-info":[{"award-number":["IIS-2132972"]}],"id":[{"id":"10.13039\/100000001","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,9]]},"abstract":"<jats:p> For rearranging objects on tabletops with overhand grasps, temporarily relocating objects to some buffer space may be necessary. This raises the natural question of how many simultaneous storage spaces, or \u201crunning buffers,\u201d are required so that certain classes of tabletop rearrangement problems are feasible. In this work, we examine the problem for both labeled and unlabeled settings. On the structural side, we observe that finding the minimum number of running buffers (MRB) can be carried out on a dependency graph abstracted from a problem instance and show that computing MRB is NP-hard. We then prove that under both labeled and unlabeled settings, even for uniform cylindrical objects, the number of required running buffers may grow unbounded as the number of objects to be rearranged increases. We further show that the bound for the unlabeled case is tight. On the algorithmic side, we develop effective exact algorithms for finding MRB for both labeled and unlabeled tabletop rearrangement problems, scalable to over a hundred objects under very high object density. More importantly, our algorithms also compute a sequence witnessing the computed MRB that can be used for solving object rearrangement tasks. Employing these algorithms, empirical evaluations reveal that random labeled and unlabeled instances, which more closely mimic real-world setups generally have fairly small MRBs. Using real robot experiments, we demonstrate that the running buffer abstraction leads to state-of-the-art solutions for the in-place rearrangement of many objects in a tight, bounded workspace. <\/jats:p>","DOI":"10.1177\/02783649231178565","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T14:52:35Z","timestamp":1686235955000},"page":"755-776","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":8,"title":["Minimizing running buffers for tabletop object rearrangement: Complexity, fast algorithms, and applications"],"prefix":"10.1177","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9670-6918","authenticated-orcid":false,"given":"Kai","family":"Gao","sequence":"first","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}]},{"given":"Si Wei","family":"Feng","sequence":"additional","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9658-6071","authenticated-orcid":false,"given":"Baichuan","family":"Huang","sequence":"additional","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4112-2250","authenticated-orcid":false,"given":"Jingjin","family":"Yu","sequence":"additional","affiliation":[{"name":"Computer Science Department, Rutgers, the State University of New Jersey, Piscataway, NJ, USA"}]}],"member":"179","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"bibr1-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1137\/0125042"},{"key":"bibr2-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100254"},{"key":"bibr3-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/70.704220"},{"key":"bibr4-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1239-x"},{"key":"bibr5-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"bibr6-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2289018"},{"key":"bibr7-02783649231178565","volume-title":"Chilitags 2: Robust fiducial markers for augmented reality and robotics","author":"Bonnard Q","year":"2013"},{"key":"bibr8-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9378"},{"key":"bibr9-02783649231178565","volume-title":"Fast Motion Planning for Multiple Moving Robots","author":"Buckley SJ","year":"1988"},{"key":"bibr10-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224575"},{"key":"bibr11-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7354264"},{"key":"bibr12-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.12.003"},{"key":"bibr13-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907062"},{"key":"bibr14-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"bibr15-02783649231178565","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2011.VII.009"},{"key":"bibr16-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-28619-4_32"},{"key":"bibr17-02783649231178565","volume-title":"Graph Partitioning-A Survey","author":"Elsner U","year":"1997"},{"key":"bibr18-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73055"},{"key":"bibr19-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005091317243"},{"key":"bibr20-02783649231178565","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2021.XVII.033"},{"key":"bibr21-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA46639.2022.9812367"},{"key":"bibr22-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/IROS47612.2022.9981715"},{"key":"bibr23-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"bibr24-02783649231178565","volume-title":"Some Np-Complete Problems on Graphs","author":"Gavril F","year":"2011"},{"key":"bibr25-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"bibr26-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891840"},{"key":"bibr27-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759114"},{"key":"bibr28-02783649231178565","volume-title":"Gurobi optimizer reference manual","author":"Gurobi Optimization L","year":"2021"},{"key":"bibr29-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00407-7"},{"key":"bibr30-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918780999"},{"key":"bibr31-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906894"},{"key":"bibr32-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2017.322"},{"key":"bibr33-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"bibr34-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561073"},{"key":"bibr35-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3123373"},{"key":"bibr36-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793946"},{"issue":"229","key":"bibr37-02783649231178565","first-page":"2","volume":"11","author":"Istv\u00e1n F","year":"1948","journal-title":"Acta Scientiarum Mathematicarum"},{"key":"bibr38-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980391"},{"key":"bibr39-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"bibr40-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487583"},{"key":"bibr41-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90234-M"},{"key":"bibr42-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90146-5"},{"key":"bibr43-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2004.1389727"},{"key":"bibr44-02783649231178565","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2015.XI.045"},{"key":"bibr45-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487581"},{"key":"bibr46-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2980984"},{"key":"bibr47-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/COASE.2016.7743488"},{"key":"bibr48-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793616"},{"issue":"1","key":"bibr49-02783649231178565","first-page":"1334","volume":"17","author":"Levine S","year":"2016","journal-title":"The Journal of Machine Learning Research"},{"key":"bibr50-02783649231178565","doi-asserted-by":"publisher","DOI":"10.2307\/2273574"},{"key":"bibr51-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"bibr52-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1177\/027836499901800105"},{"key":"bibr53-02783649231178565","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2017.XIII.058"},{"key":"bibr54-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8202206"},{"key":"bibr55-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90028-X"},{"key":"bibr56-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2020.3047472"},{"key":"bibr57-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9560782"},{"key":"bibr58-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280884"},{"key":"bibr59-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"bibr60-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1177\/0278364907087172"},{"key":"bibr61-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1137\/0208002"},{"key":"bibr62-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2011.5722178"},{"key":"bibr63-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9341532"},{"key":"bibr64-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1142\/S0219843605000545"},{"key":"bibr65-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363986"},{"key":"bibr66-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"bibr67-02783649231178565","unstructured":"Taylor RH, Mason MT, Goldberg KY (1988) Sensor-based manipulation planning as a game with nature. In Proceedings of the 4th International Symposium on Robotics Research. Cambridge, MA, 1988, pp. 421\u2013429."},{"key":"bibr68-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2259993"},{"key":"bibr69-02783649231178565","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2009.V.018"},{"key":"bibr70-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA46639.2022.9811848"},{"key":"bibr71-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2020.3024291"},{"key":"bibr72-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561716"},{"key":"bibr73-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v32i1.19824"},{"key":"bibr74-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2894861"},{"key":"bibr75-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530890"},{"key":"bibr76-02783649231178565","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2018.XIV.019"},{"key":"bibr77-02783649231178565","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2021.XVII.014"},{"key":"bibr78-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2018.8593986"},{"key":"bibr79-02783649231178565","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8461044"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231178565","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649231178565","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231178565","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231178565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T12:40:47Z","timestamp":1740919247000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649231178565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,8]]},"references-count":79,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["10.1177\/02783649231178565"],"URL":"https:\/\/doi.org\/10.1177\/02783649231178565","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,8]]}}}