[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Classifying the multi robot path finding problem into a quadratic competitive complexity class

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

We explore two motion planning problems where a group of mobile robots has to reach a target located in an a priori unknown environment while on-line planning the next step. In the first problem the target position is unknown and should be found by the robots, while in the second problem the target position is known and only a path to it should be found. We focus on optimizing the cost of the task in terms of motion time, which, under the assumption of uniform velocity of all the robots, correlates to the path length passed by the robot which reaches the target. The performance of an on-line algorithm is usually expressed in terms of Competitiveness, the constant ratio between the on-line and the optimal off-line solutions. Specifically, the ratio between the lengths of the actual path made by the robot which reached the target to the shortest path to the target. We use generalized competitiveness, i.e., the ratio is not necessarily constant, but could be any function. Classification of a motion planning task in the sense of performance is done by finding an upper and a lower bounds on the competitiveness of all algorithms solving that task. If the two bounds belong to the same functional class this is the Competitive Complexity Class of the task. We find the two bounds for the aforementioned common on-line motion planning problems, and classify them into competitive classes. It is shown that in general any on-line motion planning algorithm that tries to solve these problems must have at least a quadratic competitive performance. This is a lower bound of the problems. This paper describes two new on-line navigation algorithm which solve the problems under discussion. The first is called MRSAM, short for Multi-Robot Search Area Multiplication, and the second is called MRBUG, short for Multi-Robot BUG which extends Lumelsky famous BUG algorithm. Both algorithms have quadratic upper bounds, which prove that the problems they solve have quadratic upper bounds. Thus it is shown that navigation in an unknown environment by a group of robots belongs to a quadratic competitive class. MRSAM and MRBUG have a quadratic competitive performance and thus have optimal competitiveness. The algorithms’ performance is simulated in office-like environments.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Antonelli, G., Arrichiello, F., Chiaverini, S., Setola, R.: A self-configuring MANET for coverage area adaptation through kinematic control of a platoon of mobile robot. In: Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 1307–1312. Edmonton, Alberta, Canada (2005)

  2. Arkin, R.C., Diaz, J.: Line-of-sight constrained exploration for reactive multiagent robotic teams. In: 7th International Workshop on Advanced Motion Control, pp. 455–461 (2002)

  3. Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. Comput. 106(2), 234–252 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  4. Chen, J., Li, L.-R.: Path planning protocol for collaborative multi-robot systems. In: Proceedings 2005 IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 721–726. Espoo, Finland (2005)

  5. Chung, T.H., Burdick, J.W., Murray, R.M.: A decentralized motion coordination strategy for dynamic target tracking. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2416– 2422 (2006)

  6. Fox, D., Burgard, W., Kruppa, H., Thrun, S.: Collaborative multi-robot localization. In: Proc. of the 23rd German Conference on Artificial Intelligence (KI), Germany (1999)

  7. Franchi, A., Freda, L., Oriolo, G., Vendittelli, M.: A randomized strategy for cooperative robot exploration. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 768–774 (2007)

  8. Gabriely, Y., Rimon, E.: Spanning-tree based coverage of continuous areas by a mobile robot. Ann. Math. Artif. Intell. 31, 77–98 (2001)

    Article  Google Scholar 

  9. Gabriely, Y., Rimon, E.: Competitive on-line coverage of grid environments by a mobile robot. Comput. Geom. Theory Appl. 24(3), 197–224 (2003)

    MATH  MathSciNet  Google Scholar 

  10. Gabriely, Y., Rimon, E.: Competitive complexity of mobile robot on line motion planning problems. In: Workshop on Algorithmic Foundations of Robotics, pp. 249–264 (2004)

  11. Gabriely, Y., Rimon, E.: CBUG: a quadratically competitive mobile robot navigation algorithm. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 954–960 (2005)

  12. Ge, S.S., Fua, C.-H.: Complete multi-robot coverage of unknown environments with minimum repeated coverage. In: Proc. IEEE Int. Conf. on Robotics and Automation (2005)

  13. Gonzalez, E., Alvarez, O., Diaz, Y., Parra, C., Bustacara, C.: BSA: a complete coverage algorithm. In: Proc. IEEE Int. Conf. on Robotics and Automation (2005)

  14. Guo, Y., Parker, L.E.: A distributed and optimal motion planning approach for multiple mobile robots. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2612–2619. Washington, DC (2002)

  15. Hazon, N., Kaminka, G.A.: Redundancy, efficiency, and robustness in multi-robot coverage. In: Proc. IEEE Int. Conf. on Robotics and Automation (2005)

  16. Icking, C., Kamphans, T., Klein, R., Langetepe, E.: On the competitive complexity of navigation tasks. In: Revised Papers from the International Workshop on Sensor Based Intelligent Robots, pp. 245–258. Springer, London, UK (2002)

  17. Icking, C., Klein, R.: Competitive strategies for autonomous systems. In: Bunke, H., Kanade, T., Noltemeier, H. (eds.) Modelling and Planning for Sensor Based Intelligent Robot Systems, pp. 23–40. World Scientific, Singapore (1995)

    Google Scholar 

  18. Koenig, S., Liu, Y.: Terrain coverage with ant robots: a simulation study. In: AGENTS’01: Proceedings of the Fifth International Conference on Autonomous Agents, pp. 600–607. ACM, New York, NY, USA (2001)

    Chapter  Google Scholar 

  19. Kong, C.S., Peng, N.A., Rekleitis, I.: Distributed coverage with multi-robot system. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2423–2429 (2006)

  20. Kurabayashi, D., Ota, J., Arai, T., Yoshida, E.: Cooperative sweeping by multiple mobile robots. In: Proc. IEEE Int. Conf. on Robotics and Automation. Minneapolis, Minnesota (1996)

  21. Latimer IV, D.T., Srinivasa, S., Shue, V.L., Sonne, S., Choset, H., Hurst, A.: Towards sensor based coverage with robot teams. In: Proceedings of the 2002 IEEE International Conference on Robotics and Automation, vol. 1, pp. 961–967. IEEE (2002)

  22. Lumelsky, V.J., Stepanov, A.A.: Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica 2, 403–430 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  23. Pinto, A.G., Fraisse, P., Zapata, R.: An decentralized adaptive trajectory planning approach for a group of mobile robots. In: Proceedings of Towards Autonomous Robotic Systems, pp. 65–72 (2005)

  24. Rekleitis, I., Lee-Shue, V., New, A.P., Choset, H.: Limited communication, multi-robot team based coverage. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 3462–3468. New Orleans, LA (2004)

  25. Rekleitis, I.M., New, A.P., Choset, H.: Distributed coverage of unknown/unstructured environments by mobile sensor networks. In: Schultz, A.C., Parker, L.E., Schneider, F. (eds.) 3rd International NRL Workshop on Multi-Robot Systems, pp. 145–155. Kluwer, Washington, D.C. (2005)

  26. Sarid, S., Shapiro, A., Gabriely, Y.: MRSAM: a quadratically competitive multi robots navigation algorithm. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2699–2704. Orlando, FL (2006)

  27. Sgorbissa, A., Arkin, R.C.: Local navigation strategies for a team of robots. Robotica 21(05), 461–473 (2003)

    Article  Google Scholar 

  28. Sheng, W., Yang, Q., Tan, J., Xi, N.: Distributed multi-robot coordination in area exploration. Robot. Auton. Syst. 54(12), 945–955 (2006)

    Article  Google Scholar 

  29. Stachniss, C., Mozos, O.M., Burgard, W.: Speeding-up multi-robot exploration by considering semantic place information. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 1692–1697 (2006)

  30. Williams, K., Burdick, J: Multi-robot boundary coverage with plan revision. In: Proc. IEEE Int. Conf. on Robotics and Automation, pp. 1716–1723 (2006)

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, Ben Gurion University of the Negev, Beer-Sheva, Israel

    Shahar Sarid & Amir Shapiro

  2. Paul Ivanier Center for Robotics Research and Production, Perlstone Center for Aeronautical Engineering, Ben Gurion University of the Negev, Beer-Sheva, Israel

    Amir Shapiro

Authors
  1. Shahar Sarid
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Amir Shapiro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shahar Sarid.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sarid, S., Shapiro, A. Classifying the multi robot path finding problem into a quadratic competitive complexity class. Ann Math Artif Intell 52, 169–203 (2008). https://doi.org/10.1007/s10472-009-9122-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10472-009-9122-0

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation