{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T17:30:54Z","timestamp":1772040654520,"version":"3.50.1"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030440503","type":"print"},{"value":"9783030440510","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-44051-0_45","type":"book-chapter","created":{"date-parts":[[2020,5,7]],"date-time":"2020-05-07T16:02:40Z","timestamp":1588867360000},"page":"778-795","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Fast, High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups"],"prefix":"10.1007","author":[{"given":"Rahul","family":"Shome","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiril","family":"Solovey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingjin","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas","family":"Bekris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,8]]},"reference":[{"key":"45_CR1","doi-asserted-by":"crossref","unstructured":"Adler, A., de Berg, M., Halperin, D., Solovey, K.: Efficient multi-robot motion planning for unlabeled discs in simple polygons. IEEE T-ASE 12(4) (2015)","DOI":"10.1109\/TASE.2015.2470096"},{"key":"45_CR2","doi-asserted-by":"publisher","unstructured":"Ajtai, M., Koml\u00f3s, J., Tusn\u00e1dy, G.: On optimal matchings. Combinatorica 4(4) (1984). https:\/\/doi.org\/10.1007\/BF02579135","DOI":"10.1007\/BF02579135"},{"issue":"4","key":"45_CR3","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1109\/70.704220","volume":"14","author":"O Ben-Shahar","year":"1998","unstructured":"Ben-Shahar, O., Rivlin, E.: Practical pushing planning for rearrangement tasks. IEEE Trans. Robot. Autom. 14(4), 549\u2013565 (1998)","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"12","key":"45_CR4","first-page":"1435","volume":"30","author":"D Berenson","year":"2011","unstructured":"Berenson, D., Srinivasa, S., Kuffner, J.: Task space regions: a framework for pose-constrained manipulation planning. IJRR 30(12), 1435\u20131460 (2011)","journal-title":"IJRR"},{"issue":"5","key":"45_CR5","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/S0167-8191(03)00046-2","volume":"29","author":"P Caricato","year":"2003","unstructured":"Caricato, P., Ghiani, G., Grieco, A., Guerriero, E.: Parallel tabu search for a pickup and delivery problem under track contention. Parallel Comput. 29(5), 631\u2013639 (2003)","journal-title":"Parallel Comput."},{"issue":"2","key":"45_CR6","first-page":"305","volume":"33","author":"B Cohen","year":"2014","unstructured":"Cohen, B., Chitta, S., Likhachev, M.: Single-and dual-arm motion planning with heuristic search. IJRR 33(2), 305\u2013320 (2014)","journal-title":"IJRR"},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Coltin, B.: Multi-agent pickup and delivery planning with transfers. Ph.D. thesis, Carnegie Mellon University, CMU-RI-TR-14-05 (2014)","DOI":"10.1109\/ICRA.2014.6907709"},{"issue":"5","key":"45_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.entcs.2011.06.003","volume":"264","author":"B Dezs\u0151","year":"2011","unstructured":"Dezs\u0151, B., J\u00fcttner, A., Kov\u00e1cs, P.: Lemon-an open source C++ graph template library. Electron. Notes Theor. Comput. Sci. 264(5), 23\u201345 (2011)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"3","key":"45_CR9","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s10514-019-09832-9","volume":"44","author":"R Shome","year":"2020","unstructured":"Shome, R., Solovey, K., Dobson, A., Halperin, D., Bekris, K.E.: Scalable and informed asymptotically-optimal multi-robot motion planning. Auton. Robot. 44(3), 443\u2013467 (2020). https:\/\/doi.org\/10.1007\/s10514-019-09832-9 . ISSN 1573-7527","journal-title":"Auton. Robot."},{"issue":"125\u2013130","key":"45_CR10","first-page":"55","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl. Bureau Stand. B 69(125\u2013130), 55\u201356 (1965)","journal-title":"J. Res. Natl. Bureau Stand. B"},{"key":"45_CR11","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: FOCS (1976)","DOI":"10.1109\/SFCS.1976.6"},{"key":"45_CR12","doi-asserted-by":"crossref","unstructured":"Friggstad, Z.: Multiple traveling salesmen in asymmetric metrics. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer (2013)","DOI":"10.1007\/978-3-642-40328-6_13"},{"issue":"1","key":"45_CR13","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/0215009","volume":"15","author":"Z Galil","year":"1986","unstructured":"Galil, Z., Micali, S., Gabow, H.: An O(EV log V) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15(1), 120\u2013130 (1986)","journal-title":"SIAM J. Comput."},{"key":"45_CR14","doi-asserted-by":"crossref","unstructured":"Gharbi, M., Cort\u00e9s, J., Sim\u00e9on, T.: Roadmap composition for multi-arm systems path planning. In: IROS (2009)","DOI":"10.1109\/IROS.2009.5354415"},{"key":"45_CR15","first-page":"17","volume":"43","author":"B Ghosh","year":"1951","unstructured":"Ghosh, B.: Random distances within a rectangle and between two rectangles. Bull. Calcutta Math. Soc. 43, 17\u201324 (1951)","journal-title":"Bull. Calcutta Math. Soc."},{"key":"45_CR16","unstructured":"LLC Gurobi Optimization: Gurobi optimizer reference manual (2016)"},{"issue":"3\u20134","key":"45_CR17","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s004539910025","volume":"26","author":"D Halperin","year":"2000","unstructured":"Halperin, D., Latombe, J.C., Wilson, R.H.: A general framework for assembly planning: the motion space approach. Algorithmica 26(3\u20134), 577\u2013601 (2000)","journal-title":"Algorithmica"},{"key":"45_CR18","first-page":"1775","volume":"37","author":"SD Han","year":"2018","unstructured":"Han, S.D., Stiffler, N., Krontiris, A., Bekris, K., Yu, J.: Complexity results and fast methods for optimal tabletop rearrangement with overhand grasps. IJRR 37, 1775\u20131795 (2018)","journal-title":"IJRR"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Havur, G., Ozbilgin, G., Erdem, E., Patoglu, V.: Geometric rearrangement of multiple movable objects on cluttered surfaces. In: ICRA (2014)","DOI":"10.1109\/ICRA.2014.6906894"},{"key":"45_CR20","unstructured":"Kirkpatrick, D., Liu, P.: Characterizing minimum-length coordinated motions for two discs. arXiv preprint arXiv:1607.04005 (2016)"},{"key":"45_CR21","doi-asserted-by":"crossref","unstructured":"Krontiris, A., Bekris, K.E.: Dealing with difficult instances of object rearrangement. In: Robotics: Science and Systems (2015)","DOI":"10.15607\/RSS.2015.XI.045"},{"key":"45_CR22","doi-asserted-by":"crossref","unstructured":"Krontiris, A., Bekris, K.E.: Efficiently solving general rearrangement tasks: a fast extension primitive for an incremental sampling-based planner. In: ICRA (2016)","DOI":"10.1109\/ICRA.2016.7487581"},{"issue":"2","key":"45_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/net.3230110211","volume":"11","author":"JK Lenstra","year":"1981","unstructured":"Lenstra, J.K., Kan, A.: Complexity of vehicle routing and scheduling problems. Networks 11(2), 221\u2013227 (1981)","journal-title":"Networks"},{"key":"45_CR24","unstructured":"Leroy, S., Laumond, J.P., Sim\u00e9on, T.: Multiple path coordination for mobile robots: a geometric algorithm. In: IJCAI, vol. 99 (1999)"},{"key":"45_CR25","doi-asserted-by":"crossref","unstructured":"Ota, J.: Rearrangement of multiple movable objects-integration of global and local planning methodology. In: ICRA, vol. 2 (2004)","DOI":"10.1109\/ROBOT.2004.1308111"},{"issue":"2","key":"45_CR26","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s11301-008-0036-4","volume":"58","author":"SN Parragh","year":"2008","unstructured":"Parragh, S.N., Doerner, K.F., Hartl, R.F.: A survey on pickup and delivery models part ii: Transportation between pickup and delivery locations. J. Betriebswirtschaft 58(2), 81\u2013117 (2008)","journal-title":"J. Betriebswirtschaft"},{"key":"45_CR27","unstructured":"Rathinam, S., Sengupta, R.: Matroid intersection and its application to a multiple depot, multiple TSP (2006)"},{"key":"45_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511617331","volume-title":"Integral Geometry and Geometric Probability","author":"LA Santal\u00f3","year":"2004","unstructured":"Santal\u00f3, L.A.: Integral Geometry and Geometric Probability. Cambridge University Press, Cambridge (2004)"},{"issue":"1","key":"45_CR29","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/trsc.29.1.17","volume":"29","author":"MW Savelsbergh","year":"1995","unstructured":"Savelsbergh, M.W., Sol, M.: The general pickup and delivery problem. Transp. Sci. 29(1), 17\u201329 (1995)","journal-title":"Transp. Sci."},{"key":"45_CR30","doi-asserted-by":"crossref","unstructured":"Schmitt, P.S., Neubauer, W., Feiten, W., Wurm, K.M., Wichert, G.V., Burgard, W.: Optimal, sampling-based manipulation planning. In: ICRA. IEEE (2017)","DOI":"10.1109\/ICRA.2017.7989390"},{"key":"45_CR31","doi-asserted-by":"crossref","unstructured":"Shome, R., Bekris, K.E.: Improving the scalability of asymptotically optimal motion planning for humanoid dual-arm manipulators. In: Humanoids (2017)","DOI":"10.1109\/HUMANOIDS.2017.8246885"},{"key":"45_CR32","unstructured":"Shome, R., Solovey, K., Yu, J., Bekris, K., Halperin, D.: Fast, high-quality dual-arm rearrangement in synchronous, monotone tabletop setups. arXiv:1810.12202 [cs.RO] (2018)"},{"issue":"14","key":"45_CR33","first-page":"1750","volume":"35","author":"K Solovey","year":"2016","unstructured":"Solovey, K., Halperin, D.: On the hardness of unlabeled multi-robot motion planning. IJRR 35(14), 1750\u20131759 (2016)","journal-title":"IJRR"},{"issue":"5","key":"45_CR34","first-page":"501","volume":"35","author":"K Solovey","year":"2016","unstructured":"Solovey, K., Salzman, O., Halperin, D.: Finding a needle in an exponential haystack: discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. IJRR 35(5), 501\u2013513 (2016)","journal-title":"IJRR"},{"key":"45_CR35","doi-asserted-by":"crossref","unstructured":"Solovey, K., Yu, J., Zamir, O., Halperin, D.: Motion planning for unlabeled discs with optimality guarantees. arXiv preprint arXiv:1504.05218 (2015)","DOI":"10.15607\/RSS.2015.XI.011"},{"key":"45_CR36","doi-asserted-by":"crossref","unstructured":"Srivastava, S., Fang, E., Riano, L., Chitnis, R., Russell, S., Abbeel, P.: Combined task and motion planning through an extensible planner-independent interface layer. In: ICRA (2014)","DOI":"10.1109\/ICRA.2014.6906922"},{"key":"45_CR37","doi-asserted-by":"crossref","unstructured":"Stilman, M., Schamburek, J.U., Kuffner, J., Asfour, T.: Manipulation planning among movable obstacles. In: ICRA (2007)","DOI":"10.1109\/ROBOT.2007.363986"},{"issue":"9","key":"45_CR38","doi-asserted-by":"publisher","first-page":"2261","DOI":"10.1109\/TAC.2013.2259993","volume":"59","author":"K Treleaven","year":"2013","unstructured":"Treleaven, K., Pavone, M., Frazzoli, E.: Asymptotically optimal algorithms for one-to-one pickup and delivery problems with applications to transportation systems. IEEE Trans. Autom. Control 59(9), 2261\u20132276 (2013)","journal-title":"IEEE Trans. Autom. Control"},{"key":"45_CR39","doi-asserted-by":"crossref","unstructured":"Van Den\u00a0Berg, J., Stilman, M., Kuffner, J., Lin, M., Manocha, D.: Path planning among movable obstacles: a probabilistically complete approach. In: WAFR (2008)","DOI":"10.1007\/978-3-642-00312-7_37"},{"key":"45_CR40","doi-asserted-by":"crossref","unstructured":"Van Den\u00a0Berg, J.P., Overmars, M.H.: Prioritized motion planning for multiple robots. In: IROS (2005)","DOI":"10.1109\/IROS.2005.1545306"},{"key":"45_CR41","unstructured":"Vega-Brown, W., Roy, N.: Asymptotically optimal planning under piecewise-analytic constraints. In: WAFR (2016)"},{"key":"45_CR42","doi-asserted-by":"crossref","unstructured":"Wagner, G., Kang, M., Choset, H.: Probabilistic path planning for multiple robots with subdimensional expansion. In: ICRA (2012)","DOI":"10.1109\/ICRA.2012.6225297"},{"issue":"1","key":"45_CR43","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF01530890","volume":"3","author":"G Wilfong","year":"1991","unstructured":"Wilfong, G.: Motion planning in the presence of movable obstacles. Ann. Math. Artif. Intell. 3(1), 131\u2013150 (1991)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"2","key":"45_CR44","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/0004-3702(94)90048-5","volume":"71","author":"RH Wilson","year":"1994","unstructured":"Wilson, R.H., Latombe, J.C.: Geometric reasoning about mechanical assembly. Artif. Intell. J. 71(2), 371\u2013396 (1994)","journal-title":"Artif. Intell. J."},{"issue":"2","key":"45_CR45","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1109\/TAC.2014.2344291","volume":"60","author":"J Yu","year":"2015","unstructured":"Yu, J., Chung, S.J., Voulgaris, P.G.: Target assignment in robotic networks: distance optimality guarantees and hierarchical strategies. IEEE Trans. Autom. Control 60(2), 327\u2013341 (2015)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"5","key":"45_CR46","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1109\/TRO.2016.2593448","volume":"32","author":"J Yu","year":"2016","unstructured":"Yu, J., LaValle, S.M.: Optimal multirobot path planning on graphs: complete algorithms and effective heuristics. IEEE Trans. Robot. 32(5), 1163\u20131177 (2016)","journal-title":"IEEE Trans. Robot."}],"container-title":["Springer Proceedings in Advanced Robotics","Algorithmic Foundations of Robotics XIII"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-44051-0_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,23]],"date-time":"2022-10-23T03:59:08Z","timestamp":1666497548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-44051-0_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030440503","9783030440510"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-44051-0_45","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"value":"2511-1256","type":"print"},{"value":"2511-1264","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"8 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAFR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on the Algorithmic Foundations of Robotics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Merida","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wafr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/parasol.tamu.edu\/wafr\/wafr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}