iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-642-36279-8_10
Multi-agent Path Planning and Network Flow | SpringerLink
Skip to main content
Springer Nature Link
Log in

Multi-agent Path Planning and Network Flow

  • Conference paper
Algorithmic Foundations of Robotics X

Part of the book series: Springer Tracts in Advanced Robotics ((STAR,volume 86))

Abstract

This paper connects multi-agent path planning on graphs (roadmaps) to network flow problems, showing that the former can be reduced to the latter, therefore enabling the application of combinatorial network flow algorithms, as well as general linear program techniques, tomulti-agent path planning problems on graphs. Exploiting this connection, we show that when the goals are permutation invariant, the problem always has a feasible solution path set with a longest finish time of no more than n + V - 1 steps, in which n is the number of agents and V is the number of vertices of the underlying graph.We then give a complete algorithm that finds such a solution in O(nVE) time, with E being the number of edges of the graph. Taking a further step, we study time and distance optimality of the feasible solutions, show that they have a pairwise Pareto optimal structure, and again provide efficient algorithms for optimizing two of these practical objectives.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aronson, J.E.: A survey on dynamic network flows. Annals of Operations Research 20(1), 1–66 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  2. Balch, T., Arkin, R.C.: Behavior-based formation control for multirobot teams. IEEE Transaction on Robotics and Automation 14(6), 926–939 (1998)

    Article  Google Scholar 

  3. Canny, J.F.: The Complexity of Robot Motion Planning. MIT Press, Cambridge (1988)

    Google Scholar 

  4. Chalmet, L.G., Francis, R.L., Saunders, P.B.: Network models for building evacuation. Management Science 28(1), 86–105 (1982)

    Article  Google Scholar 

  5. 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)

    Google Scholar 

  6. Collins, G.E.: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 134–183. Springer, Heidelberg (1975)

    Google Scholar 

  7. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  8. Costa, M.-C., Létocart, L., Roupin, F.: Minimal Multicut and Maximal Integer Multiflow: A Survey. European Journal of Operational Research 162, 55–69 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  9. Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248–264 (1972)

    Article  MATH  Google Scholar 

  10. Erdmann, M.A., Lozano-Pérez, T.: On multiple moving objects. In: Proceedings IEEE International Conference on Robotics & Automation, pp. 1419–1424 (1986)

    Google Scholar 

  11. Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Research Memorandum RM-1400, The RAND Corporation (November 1954)

    Google Scholar 

  12. Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Operations Research 6, 419–433 (1958)

    Article  MathSciNet  Google Scholar 

  13. Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, New Jersey (1962)

    MATH  Google Scholar 

  14. Fox, D., Burgard, W., Kruppa, H., Thrun, S.: A probabilistic approach to collaborative multi-robot localization. Autom. Robots 8(3), 325–344 (2000)

    Article  Google Scholar 

  15. 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–146. ACM, New York (1986)

    Google Scholar 

  16. Grötschel, M., Schrijver, A., Lovász, L.: Complexity, Oracles, and Numerical Computation. Springer (1988)

    Google Scholar 

  17. 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–2619 (2002)

    Google Scholar 

  18. Halperin, D., Latombe, J.-C., Wilson, R.: A general framework for assembly planning: The motion space approach. Algorithmica 26(3-4), 577–601 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  19. Hoppe, B., Tardos, É.: The quickest transshipment problem. Mathematics of Operations Research 25(1), 36–62 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  20. 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)

    Google Scholar 

  21. Kant, K., Zucker, S.: Towards efficient trajectory planning: The path velocity decomposition. International Journal of Robotics Research 5(3), 72–89 (1986)

    Article  Google Scholar 

  22. 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 12(4), 566–580 (1996)

    Article  Google Scholar 

  23. Kloder, S., Hutchinson, S.: Path planning for permutation-invariant multirobot formations. IEEE Transactions on Robotics 22(4), 650–665 (2006)

    Article  Google Scholar 

  24. Latombe, J.-C.: Robot Motion Planning. Kluwer, Boston (1991)

    Book  Google Scholar 

  25. LaValle, S.M.: Rapidly-exploring random trees: A new tool for path planning. TR 98-11, Computer Science Dept., Iowa State University (October 1998)

    Google Scholar 

  26. LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006), http://planning.cs.uiuc.edu/

    Book  MATH  Google Scholar 

  27. Lozano-Pérez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM 22(10), 560–570 (1979)

    Article  Google Scholar 

  28. 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–300 (2011)

    Google Scholar 

  29. Matarić, 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–561 (1995)

    Google Scholar 

  30. 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–3755 (2009)

    Google Scholar 

  31. Nnaji, B.: Theory of Automatic Robot Assembly and Programming. Chapman and Hall (1992)

    Google Scholar 

  32. O’Donnell, P.A., Lozano-Pérez, T.: Deadlock-free and collision-free coordination of two robot manipulators. In: Proceedings IEEE International Conference on Robotics & Automation, pp. 484–489 (1989)

    Google Scholar 

  33. O’Dúnlaing, C., Yap, C.K.: A retraction method for planning the motion of a disc. Journal of Algorithms 6, 104–111 (1982)

    Article  Google Scholar 

  34. Peasgood, M., Clark, C., McPhee, J.: A complete and scalable strategy for coordinating multiple robots within roadmaps. IEEE Transactions on Robotics 24(2), 283–292 (2008)

    Article  Google Scholar 

  35. 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. 7, pp. 221–237. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  36. Poduri, S., Sukhatme, G.S.: Constrained coverage for mobile sensor networks. In: Proceedings IEEE International Conference on Robotics & Automation (2004)

    Google Scholar 

  37. Rodriguez, S., Amato, N.M.: Behavior-based evacuation planning. In: Proceedings IEEE International Conference on Robotics and Automation, pp. 350–355 (2010)

    Google Scholar 

  38. 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–242 (1995)

    Google Scholar 

  39. Shucker, B., Murphey, T., Bennett, J.K.: Switching rules for decentralized control with simple control laws. In: American Control Conference (July 2007)

    Google Scholar 

  40. Siméon, T., Leroy, S., Laumond, J.-P.: Path coordination for multiple mobile robots: A resolution complete algorithm. IEEE Transactions on Robotics & Automation 18(1) (February 2002)

    Google Scholar 

  41. 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 14(3), 322–335 (2009)

    Article  Google Scholar 

  42. 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–1263 (2010)

    Google Scholar 

  43. Tanner, H., Pappas, G., Kumar, V.: Leader-to-formation stability. IEEE Transactions on Robotics and Automation 20(3), 443–455 (2004)

    Article  Google Scholar 

  44. Tardos, É.: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3), 247–255 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  45. van den Berg, J., Overmars, M.: Prioritized motion planning for multiple robots. In: Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (2005)

    Google Scholar 

  46. 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)

    Google Scholar 

  47. Švestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robotics and Autonomous Systems 23, 125–152 (1998)

    Article  Google Scholar 

  48. 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–1875. Morgan Kaufmann Publishers Inc., San Francisco (2009)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, USA

    Jingjin Yu

  2. Department of Computer Science, University of Illinois, Urbana-Champaign, USA

    Steven M. LaValle

Authors
  1. Jingjin Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Steven M. LaValle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jingjin Yu .

Editor information

Editors and Affiliations

  1. Associate Professor of Aeronautics and, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

    Emilio Frazzoli

  2. MIT Comp. Sci. & Artificial Intel. Lab., Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

    Tomas Lozano-Perez

  3. Robust Robotics Group, Massachusetts Institute of Technology CSAIL, Cambridge, Massachusetts, USA

    Nicholas Roy

  4. Massachusetts Institute of Technology, Cambridge, Massachusetts, USA

    Daniela Rus

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Yu, J., LaValle, S.M. (2013). Multi-agent Path Planning and Network Flow. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds) Algorithmic Foundations of Robotics X. Springer Tracts in Advanced Robotics, vol 86. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36279-8_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-36279-8_10

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-36278-1

  • Online ISBN: 978-3-642-36279-8

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation