{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:08:33Z","timestamp":1761808113568},"publisher-location":"Cham","reference-count":44,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319515311"},{"type":"electronic","value":"9783319515328"}],"license":[{"start":{"date-parts":[[2017,7,27]],"date-time":"2017-07-27T00:00:00Z","timestamp":1501113600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-51532-8_30","type":"book-chapter","created":{"date-parts":[[2017,7,26]],"date-time":"2017-07-26T13:56:19Z","timestamp":1501077379000},"page":"495-511","source":"Crossref","is-referenced-by-count":25,"title":["An Effective Algorithmic Framework for Near Optimal Multi-robot Path Planning"],"prefix":"10.1007","author":[{"given":"Jingjin","family":"Yu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniela","family":"Rus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,27]]},"reference":[{"key":"30_CR1","unstructured":"Alonso-Mora, J.: Collaborative Motion Planning for Multi-Agent Systems. Ph.D. thesis, ETH Zurich, March 2014"},{"issue":"3","key":"30_CR2","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1109\/70.143360","volume":"8","author":"Z Bien","year":"1992","unstructured":"Bien, Z., Lee, J.: A minimum-time trajectory planning method for two robots. IEEE Trans. Robot. Autom. 8(3), 414\u2013418 (1992)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Buckley, S.J.: Fast motion planning for multiple moving robots. In: ICRA (1989)","DOI":"10.1109\/ROBOT.1989.100008"},{"key":"30_CR4","unstructured":"Cgal, Computational Geometry Algorithms Library. http:\/\/www.cgal.org"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Erdmann, M.A., Lozano-P\u00e9rez, T.: On multiple moving objects. In: ICRA (1986)","DOI":"10.1109\/ROBOT.1986.1087401"},{"issue":"4","key":"30_CR6","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0925-7721(93)90010-4","volume":"3","author":"SK Ghosh","year":"1993","unstructured":"Ghosh, S.K., Maheshwari, A., Pal, S.P., Saluja, S., Madhavan, C.V.: Characterizing and recognizing weak visibility polygons. Comput. Geom. 3(4), 213\u2013233 (1993)","journal-title":"Comput. Geom."},{"issue":"11","key":"30_CR7","first-page":"997","volume":"24","author":"R Ghrist","year":"2005","unstructured":"Ghrist, R., O\u2019Kane, J.M., LaValle, S.M.: Computing Pareto optimal coordinations on roadmaps. IJRR 24(11), 997\u20131010 (2005)","journal-title":"IJRR"},{"issue":"11","key":"30_CR8","first-page":"933","volume":"24","author":"EJ Griffith","year":"2005","unstructured":"Griffith, E.J., Akella, S.: Coordinating multiple droplets in planar array digital microfluidic systems. IJRR 24(11), 933\u2013949 (2005)","journal-title":"IJRR"},{"key":"30_CR9","unstructured":"Gurobi\u00a0Optimization Inc. Gurobi optimizer reference manual (2015)"},{"issue":"4","key":"30_CR10","first-page":"76","volume":"3","author":"JE Hopcroft","year":"1984","unstructured":"Hopcroft, J.E., Schwartz, J.T., Sharir, M.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the \u201cwarehouseman\u2019s problem\u201d. IJRR 3(4), 76\u201388 (1984)","journal-title":"IJRR"},{"issue":"3","key":"30_CR11","first-page":"72","volume":"5","author":"K Kant","year":"1986","unstructured":"Kant, K., Zucker, S.: Towards efficient trajectory planning: the path velocity decomposition. IJRR 5(3), 72\u201389 (1986)","journal-title":"IJRR"},{"issue":"4","key":"30_CR12","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"LE Kavraki","year":"1996","unstructured":"Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566\u2013580 (1996)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Knepper, R.A., Rus, D.: Pedestrian-inspired sampling-based multi-robot collision avoidance. In: RO-MAN (2012)","DOI":"10.1109\/ROMAN.2012.6343737"},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"Kornhauser, D., Miller, G., Spirakis, P.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: FOCS (1984)","DOI":"10.1109\/SFCS.1984.715921"},{"key":"30_CR15","unstructured":"Krontiris, A., Sajid, Q., Bekris, K.: Towards using discrete multiagent pathfinding to address continuous problems. In: AAAI-WoMP (2012)"},{"key":"30_CR16","unstructured":"LaValle, S.M.: Rapidly-exploring random trees: A new tool for path planning. Technical report, Iowa State University, October 1998. Computer Science Department TR 98-11"},{"issue":"6","key":"30_CR17","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1109\/70.736775","volume":"14","author":"SM LaValle","year":"1998","unstructured":"LaValle, S.M., Hutchinson, S.A.: Optimal motion planning for multiple robots having independent goals. IEEE Trans. Robot. Autom. 14(6), 912\u2013925 (1998)","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"10","key":"30_CR18","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T Lozano-P\u00e9rez","year":"1979","unstructured":"Lozano-P\u00e9rez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22(10), 560\u2013570 (1979)","journal-title":"Commun. ACM"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, P.A., Lozano-P\u00e9rez, T.: Deadlock-free and collision-free coordination of two robot manipulators. In: ICRA (1989)","DOI":"10.1109\/ROBOT.1989.100033"},{"issue":"2","key":"30_CR20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1109\/TRO.2008.918056","volume":"24","author":"M Peasgood","year":"2008","unstructured":"Peasgood, M., Clark, C., McPhee, J.: A complete and scalable strategy for coordinating multiple robots within roadmaps. IEEE Trans. Robot. 24(2), 283\u2013292 (2008)","journal-title":"IEEE Trans. Robot."},{"key":"30_CR21","first-page":"221","volume-title":"Algorithmic Foundations of Robotics V","author":"J Peng","year":"2002","unstructured":"Peng, J., Akella, S.: Coordinating multiple robots with kinodynamic constraints along specified paths. In: Boissonat, J.-D., Burdick, J., Goldberg, K., Hutchinson, S. (eds.) Algorithmic Foundations of Robotics V, pp. 221\u2013237. Springer, Berlin (2002)"},{"key":"30_CR22","volume-title":"The Geometrical Foundation of Natural Structure. A Source Book of Design","author":"W Robert","year":"1978","unstructured":"Robert, W.: The Geometrical Foundation of Natural Structure. A Source Book of Design. Dover, New York (1978)"},{"key":"30_CR23","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1613\/jair.2408","volume":"31","author":"MRK Ryan","year":"2008","unstructured":"Ryan, M.R.K.: Exploiting subgraph structure in multi-robot path planning. J. Artif. Intell. Res. 31, 497\u2013542 (2008)","journal-title":"J. Artif. Intell. Res."},{"issue":"3","key":"30_CR24","first-page":"46","volume":"2","author":"J Schwartz","year":"1983","unstructured":"Schwartz, J., Sharir, M.: On the piano movers\u2019 problem: III. coordinating the motion of several independent bodies: the special case of circular bodies moving amidst polygonal barriers. IJRR 2(3), 46\u201375 (1983)","journal-title":"IJRR"},{"key":"30_CR25","volume-title":"Experimental Robotics","author":"J Snape","year":"2014","unstructured":"Snape, J., Guy, S.J., van den Berg, J., Manocha, D.: Smooth coordination and navigation for multiple differential-drive robots. In: Khatib, O., Kumar, V., Sukhatme, G. (eds.) Experimental Robotics. Springer, Heidelberg (2014)"},{"key":"30_CR26","unstructured":"Snape, J.R.: Smooth and collision-free navigation for multiple mobile robots and video game characters. Ph.D. thesis, University of North Carolina at Chapel Hill (2012)"},{"key":"30_CR27","doi-asserted-by":"crossref","unstructured":"Solovey, K., Halperin, D.: $$k$$ k -color multi-robot motion planning. In: WAFR (2012)","DOI":"10.1007\/978-3-642-36279-8_12"},{"key":"30_CR28","doi-asserted-by":"crossref","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. In: WAFR (2014)","DOI":"10.1007\/978-3-319-16595-0_34"},{"key":"30_CR29","doi-asserted-by":"crossref","unstructured":"Solovey, K., Yu, J., Zamir, O., Halperin, D.: Motion planning for unlabeled discs with optimality guarantees. In: RSS (2015)","DOI":"10.15607\/RSS.2015.XI.011"},{"key":"30_CR30","unstructured":"Standley, T., Korf, R.: Complete algorithms for cooperative pathfinding problems. In: IJCAI (2011)"},{"issue":"3","key":"30_CR31","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0921-8890(97)00033-X","volume":"23","author":"P \u0160vestka","year":"1998","unstructured":"\u0160vestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23(3), 125\u2013152 (1998)","journal-title":"Robot. Auton. Syst."},{"key":"30_CR32","doi-asserted-by":"crossref","unstructured":"Turpin, M., Michael, N., Kumar, V.: Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In: ICRA (2013)","DOI":"10.1109\/ICRA.2013.6630671"},{"key":"30_CR33","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Lin, M.C., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: ICRA (2008)","DOI":"10.1109\/ROBOT.2008.4543489"},{"key":"30_CR34","doi-asserted-by":"crossref","unstructured":"van\u00a0den Berg, J., Overmars, M.: Prioritized motion planning for multiple robots. In: IROS (2005)","DOI":"10.1109\/IROS.2005.1545306"},{"key":"30_CR35","doi-asserted-by":"crossref","unstructured":"van\u00a0den Berg, J., Snoeyink, J., Lin, M., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: RSS (2009)","DOI":"10.15607\/RSS.2009.V.018"},{"key":"30_CR36","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Snape, J., Guy, S.J., Manocha, D.: Reciprocal collision avoidance with acceleration-velocity obstacles. In: ICRA (2011)","DOI":"10.1109\/ICRA.2011.5980408"},{"key":"30_CR37","unstructured":"van der\u00a0Stappen, A.F., Karamouzas, I., Geraerts, R.: Space-time group motion planning. In: WAFR (2012)"},{"key":"30_CR38","doi-asserted-by":"crossref","unstructured":"Wagner, G., Choset, H.: M*: a complete multirobot path planning algorithm with performance bounds. In: IROS (2011)","DOI":"10.1109\/IROS.2011.6048671"},{"key":"30_CR39","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"RM Wilson","year":"1974","unstructured":"Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Combinat. Theo. (B) 16, 86\u201396 (1974)","journal-title":"J. Combinat. Theo. (B)"},{"issue":"1","key":"30_CR40","first-page":"9","volume":"29","author":"PR Wurman","year":"2008","unstructured":"Wurman, P.R., D\u2019Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Mag. 29(1), 9\u201319 (2008)","journal-title":"AI Mag."},{"key":"30_CR41","unstructured":"Yu, J., LaValle, S.M.: Fast, near-optimal computation for multi-robot path planning on graphs. In: AAAI (2013). Late breaking papers"},{"key":"30_CR42","doi-asserted-by":"crossref","unstructured":"Yu, J., LaValle, S.M.: Planning optimal paths for multiple robots on graphs. In: ICRA (2013)","DOI":"10.1109\/ICRA.2013.6631084"},{"key":"30_CR43","doi-asserted-by":"crossref","unstructured":"Yu, J., LaValle, S.M.: Structure and intractability of optimal multi-robot path planning on graphs. In: AAAI (2013)","DOI":"10.1609\/aaai.v27i1.8541"},{"key":"30_CR44","doi-asserted-by":"crossref","unstructured":"Yu, J., Rus, D.: Pebble motion on graphs with rotations: efficient feasibility tests and planning. In: WAFR (2014)","DOI":"10.1007\/978-3-319-16595-0_42"}],"container-title":["Springer Proceedings in Advanced Robotics","Robotics Research"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-51532-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T10:16:46Z","timestamp":1659262606000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-51532-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,27]]},"ISBN":["9783319515311","9783319515328"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-51532-8_30","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"type":"print","value":"2511-1256"},{"type":"electronic","value":"2511-1264"}],"subject":[],"published":{"date-parts":[[2017,7,27]]}}}