{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T16:34:04Z","timestamp":1784392444520,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642362781","type":"print"},{"value":"9783642362798","type":"electronic"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36279-8_10","type":"book-chapter","created":{"date-parts":[[2013,2,14]],"date-time":"2013-02-14T09:26:18Z","timestamp":1360833978000},"page":"157-173","source":"Crossref","is-referenced-by-count":92,"title":["Multi-agent Path Planning and Network Flow"],"prefix":"10.1007","author":[{"given":"Jingjin","family":"Yu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven M.","family":"LaValle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02216922","volume":"20","author":"J.E. Aronson","year":"1989","unstructured":"Aronson, J.E.: A survey on dynamic network flows. Annals of Operations Research\u00a020(1), 1\u201366 (1989)","journal-title":"Annals of Operations Research"},{"issue":"6","key":"10_CR2","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1109\/70.736776","volume":"14","author":"T. Balch","year":"1998","unstructured":"Balch, T., Arkin, R.C.: Behavior-based formation control for multirobot teams. IEEE Transaction on Robotics and Automation\u00a014(6), 926\u2013939 (1998)","journal-title":"IEEE Transaction on Robotics and Automation"},{"key":"10_CR3","volume-title":"The Complexity of Robot Motion Planning","author":"J.F. Canny","year":"1988","unstructured":"Canny, J.F.: The Complexity of Robot Motion Planning. MIT Press, Cambridge (1988)"},{"issue":"1","key":"10_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1287\/mnsc.28.1.86","volume":"28","author":"L.G. Chalmet","year":"1982","unstructured":"Chalmet, L.G., Francis, R.L., Saunders, P.B.: Network models for building evacuation. Management Science\u00a028(1), 86\u2013105 (1982)","journal-title":"Management Science"},{"key":"10_CR5","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"H. Choset","year":"2005","unstructured":"Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Cambridge (2005)"},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/3-540-07407-4_17","volume-title":"Automata Theory and Formal Languages","author":"G.E. Collins","year":"1975","unstructured":"Collins, G.E.: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol.\u00a033, pp. 134\u2013183. Springer, Heidelberg (1975)"},{"key":"10_CR7","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.ejor.2003.10.037","volume":"162","author":"M.-C. Costa","year":"2005","unstructured":"Costa, M.-C., L\u00e9tocart, L., Roupin, F.: Minimal Multicut and Maximal Integer Multiflow: A Survey. European Journal of Operational Research\u00a0162, 55\u201369 (2005)","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"10_CR9","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM\u00a019(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Erdmann, M.A., Lozano-P\u00e9rez, T.: On multiple moving objects. In: Proceedings IEEE International Conference on Robotics & Automation, pp. 1419\u20131424 (1986)","DOI":"10.1109\/ROBOT.1986.1087401"},{"key":"10_CR11","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Research Memorandum RM-1400, The RAND Corporation (November 1954)"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1287\/opre.6.3.419","volume":"6","author":"L.R. Ford","year":"1958","unstructured":"Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Operations Research\u00a06, 419\u2013433 (1958)","journal-title":"Operations Research"},{"key":"10_CR13","volume-title":"Flows in Networks","author":"L.R. Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, New Jersey (1962)"},{"issue":"3","key":"10_CR14","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1023\/A:1008937911390","volume":"8","author":"D. Fox","year":"2000","unstructured":"Fox, D., Burgard, W., Kruppa, H., Thrun, S.: A probabilistic approach to collaborative multi-robot localization. Autom. Robots\u00a08(3), 325\u2013344 (2000)","journal-title":"Autom. Robots"},{"key":"10_CR15","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1145\/12130.12144","volume-title":"STOC 1986: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing","author":"A.V. Goldberg","year":"1986","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. In: STOC 1986: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp. 136\u2013146. ACM, New York (1986)"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Schrijver, A., Lov\u00e1sz, L.: Complexity, Oracles, and Numerical Computation. Springer (1988)","DOI":"10.1007\/978-3-642-97881-4_2"},{"key":"10_CR17","unstructured":"Guo, Y., Parker, L.E.: A distributed and optimal motion planning approach for multiple mobile robots. In: Proceedings IEEE International Conference on Robotics and Automation, pp. 2612\u20132619 (2002)"},{"issue":"3-4","key":"10_CR18","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.: A general framework for assembly planning: The motion space approach. Algorithmica\u00a026(3-4), 577\u2013601 (2000)","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR19","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.25.1.36.15211","volume":"25","author":"B. Hoppe","year":"2000","unstructured":"Hoppe, B., Tardos, \u00c9.: The quickest transshipment problem. Mathematics of Operations Research\u00a025(1), 36\u201362 (2000)","journal-title":"Mathematics of Operations Research"},{"key":"10_CR20","unstructured":"Jennings, J.S., Whelan, G., Evans, W.F.: Cooperative search and rescue with a team of mobile robots. In: Proceedings IEEE International Conference on Robotics & Automation (1997)"},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1177\/027836498600500304","volume":"5","author":"K. Kant","year":"1986","unstructured":"Kant, K., Zucker, S.: Towards efficient trajectory planning: The path velocity decomposition. International Journal of Robotics Research\u00a05(3), 72\u201389 (1986)","journal-title":"International Journal of Robotics Research"},{"issue":"4","key":"10_CR22","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"L.E. 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 Transactions on Robotics & Automation\u00a012(4), 566\u2013580 (1996)","journal-title":"IEEE Transactions on Robotics & Automation"},{"issue":"4","key":"10_CR23","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1109\/TRO.2006.878952","volume":"22","author":"S. Kloder","year":"2006","unstructured":"Kloder, S., Hutchinson, S.: Path planning for permutation-invariant multirobot formations. IEEE Transactions on Robotics\u00a022(4), 650\u2013665 (2006)","journal-title":"IEEE Transactions on Robotics"},{"key":"10_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot Motion Planning","author":"J.-C. Latombe","year":"1991","unstructured":"Latombe, J.-C.: Robot Motion Planning. Kluwer, Boston (1991)"},{"key":"10_CR25","unstructured":"LaValle, S.M.: Rapidly-exploring random trees: A new tool for path planning. TR 98-11, Computer Science Dept., Iowa State University (October 1998)"},{"key":"10_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning Algorithms","author":"S.M. LaValle","year":"2006","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006), http:\/\/planning.cs.uiuc.edu\/"},{"issue":"10","key":"10_CR27","doi-asserted-by":"publisher","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. Communications of the ACM\u00a022(10), 560\u2013570 (1979)","journal-title":"Communications of the ACM"},{"key":"10_CR28","unstructured":"Luna, R., Bekris, K.E.: Push and swap: Fast cooperative path-finding with completeness guarantees. In: Twenty-Second International Joint Conference on Artificial Intelligence, pp. 294\u2013300 (2011)"},{"key":"10_CR29","doi-asserted-by":"crossref","unstructured":"Matari\u0107, M.J., Nilsson, M., Simsarian, K.T.: Cooperative multi-robot box pushing. In: Proceedings IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 556\u2013561 (1995)","DOI":"10.1109\/IROS.1995.525940"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Miklic, D., Bogdan, S., Fierro, R., Nestic, S.: A discrete grid abstraction for formation control in the presence of obstacles. In: Proceedings IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 3750\u20133755 (2009)","DOI":"10.1109\/IROS.2009.5354291"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Nnaji, B.: Theory of Automatic Robot Assembly and Programming. Chapman and Hall (1992)","DOI":"10.1007\/978-94-011-1590-2"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, P.A., Lozano-P\u00e9rez, T.: Deadlock-free and collision-free coordination of two robot manipulators. In: Proceedings IEEE International Conference on Robotics & Automation, pp. 484\u2013489 (1989)","DOI":"10.1109\/ROBOT.1989.100033"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/0196-6774(85)90021-5","volume":"6","author":"C. O\u2019D\u00fanlaing","year":"1982","unstructured":"O\u2019D\u00fanlaing, C., Yap, C.K.: A retraction method for planning the motion of a disc. Journal of Algorithms\u00a06, 104\u2013111 (1982)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"10_CR34","doi-asserted-by":"publisher","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 Transactions on Robotics\u00a024(2), 283\u2013292 (2008)","journal-title":"IEEE Transactions on Robotics"},{"key":"10_CR35","series-title":"STAR","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-540-45058-0_14","volume-title":"Algorithmic Foundations of Robotics V","author":"J. Peng","year":"2004","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. STAR, vol.\u00a07, pp. 221\u2013237. Springer, Heidelberg (2004)"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Poduri, S., Sukhatme, G.S.: Constrained coverage for mobile sensor networks. In: Proceedings IEEE International Conference on Robotics & Automation (2004)","DOI":"10.1109\/ROBOT.2004.1307146"},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"Rodriguez, S., Amato, N.M.: Behavior-based evacuation planning. In: Proceedings IEEE International Conference on Robotics and Automation, pp. 350\u2013355 (2010)","DOI":"10.1109\/ROBOT.2010.5509502"},{"key":"10_CR38","doi-asserted-by":"crossref","unstructured":"Rus, D., Donald, B., Jennings, J.: Moving furniture with teams of autonomous robots. In: Proceedings IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 235\u2013242 (1995)","DOI":"10.1109\/IROS.1995.525802"},{"key":"10_CR39","doi-asserted-by":"crossref","unstructured":"Shucker, B., Murphey, T., Bennett, J.K.: Switching rules for decentralized control with simple control laws. In: American Control Conference (July 2007)","DOI":"10.1109\/ACC.2007.4282736"},{"key":"10_CR40","doi-asserted-by":"crossref","unstructured":"Sim\u00e9on, T., Leroy, S., Laumond, J.-P.: Path coordination for multiple mobile robots: A resolution complete algorithm. IEEE Transactions on Robotics & Automation\u00a018(1) (February 2002)","DOI":"10.1109\/70.988973"},{"issue":"3","key":"10_CR41","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/s11036-009-0153-x","volume":"14","author":"B. Smith","year":"2009","unstructured":"Smith, B., Egerstedt, M., Howard, A.: Automatic generation of persistent formations for multi-agent networks under range constraints. ACM\/Springer Mobile Networks and Applications Journal\u00a014(3), 322\u2013335 (2009)","journal-title":"ACM\/Springer Mobile Networks and Applications Journal"},{"key":"10_CR42","doi-asserted-by":"crossref","unstructured":"Surynek, P.: An optimization variant of multi-robot path planning is intractable. In: The Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 1261\u20131263 (2010)","DOI":"10.1609\/aaai.v24i1.7767"},{"issue":"3","key":"10_CR43","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/TRA.2004.825275","volume":"20","author":"H. Tanner","year":"2004","unstructured":"Tanner, H., Pappas, G., Kumar, V.: Leader-to-formation stability. IEEE Transactions on Robotics and Automation\u00a020(3), 443\u2013455 (2004)","journal-title":"IEEE Transactions on Robotics and Automation"},{"issue":"3","key":"10_CR44","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"\u00c9. Tardos","year":"1985","unstructured":"Tardos, \u00c9.: A strongly polynomial minimum cost circulation algorithm. Combinatorica\u00a05(3), 247\u2013255 (1985)","journal-title":"Combinatorica"},{"key":"10_CR45","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Overmars, M.: Prioritized motion planning for multiple robots. In: Proceedings IEEE\/RSJ International Conference on Intelligent Robots and Systems (2005)","DOI":"10.1109\/IROS.2005.1545306"},{"key":"10_CR46","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Snoeyink, J., Lin, M., Manocha, D.: Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In: Proceedings Robotics: Science and Systems (2009)","DOI":"10.15607\/RSS.2009.V.018"},{"key":"10_CR47","doi-asserted-by":"publisher","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. Robotics and Autonomous Systems\u00a023, 125\u2013152 (1998)","journal-title":"Robotics and Autonomous Systems"},{"key":"10_CR48","first-page":"1870","volume-title":"Proceedings of the 21st International Jont Conference on Artifical Intelligence, IJCAI 2009","author":"K.-H.C. Wang","year":"2009","unstructured":"Wang, K.-H.C., Botea, A.: Tractable multi-agent path planning on grid maps. In: Proceedings of the 21st International Jont Conference on Artifical Intelligence, IJCAI 2009, pp. 1870\u20131875. Morgan Kaufmann Publishers Inc., San Francisco (2009)"}],"container-title":["Springer Tracts in Advanced Robotics","Algorithmic Foundations of Robotics X"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36279-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T21:18:05Z","timestamp":1745961485000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-36279-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642362781","9783642362798"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36279-8_10","relation":{},"ISSN":["1610-7438","1610-742X"],"issn-type":[{"value":"1610-7438","type":"print"},{"value":"1610-742X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}