Abstract
This paper combines probabilistic roadmaps with potential fields in order to enable a robotic swarm to effectively move to a desired destination while avoiding collisions with obstacles and each other. Potential fields provide the robots with local, reactive, behaviors that seek to keep the swarm moving in cohesion and away from the obstacles. The probabilistic roadmap provides global path planning which guides the swarm through a series of intermediate goals in order to effectively reach the desired destination. Random walks in combination with adjustments to the potential fields and intermediate goals are used to help stuck robots escape local minima. Experimental results provide promising validation on the efficiency and scalability of the proposed approach. Source code is made publicly available.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Reynolds, C.W.: Flocks, herds and schools: a distributed behavioral model. ACM SIGGRAPH Comput. Graph. 21, 25–34 (1987)
Şahin, E.: Swarm robotics: from sources of inspiration to domains of application. In: Şahin, E., Spears, W.M. (eds.) Swarm Robotics 2004. LNCS, vol. 3342, pp. 10–20. Springer, Heidelberg (2005)
Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M.: Swarm robotics: a review from the swarm engineering perspective. Swarm Intell. 7, 1–41 (2012)
Reif, J.: Complexity of the mover’s problem and generalizations. In: IEEE Symposium on Foundations of Computer Science, pp. 421–427 (1979)
Canny, J.: The Complexity of Robot Motion Planning. MIT Press, Cambridge, MA (1988)
Schwartz, J.T., Sharir, M.: A survey of motion planning and related geometric algorithms. Artif. Intell. 37, 157–169 (1988)
Khatib, O.: Real time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5(1), 90–99 (1986)
Reif, J.H., Wang, H.: Social potential fields: a distributed behavioral control for autonomous robots. Robot. Auton. Syst. 27(3), 171–194 (1999)
Spears, W.M., Spears, D.F.: Physicomimetics: Physics-Based Swarm Intelligence. Springer, Heidelberg (2012)
Tanner, H.G., Kumar, A.: Formation stabilization of multiple agents using decentralized navigation functions. In: Robotics: Science and Systems, pp. 49–56 (2005)
Rimon, E., Koditschek, D.: Exact robot navigation using artificial potential functions. IEEE Trans. Robot. Autom. 8, 501–518 (1992)
Kavraki, L.E., Švestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580 (1996)
Denny, J., Amato, N.M.: Toggle PRM: a coordinated mapping of C-free and C-obstacle in arbitrary dimension. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X. Springer Tracts in Advanced Robotics, pp. 297–312. Springer, Heidelberg (2013)
Yeh, H.Y., Thomas, S., Eppstein, D., Amato, N.M.: UOBPRM: A uniformly distributed obstacle-based PRM. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2655–2662 (2012)
Plaku, E., Bekris, K.E., Chen, B.Y., Ladd, A.M., Kavraki, L.E.: Sampling-based roadmap of trees for parallel motion planning. IEEE Trans. Robot. 21(4), 587–608 (2005)
Sun, Z., Hsu, D., Jiang, T., Kurniawati, H., Reif, J.: Narrow passage sampling for probabilistic roadmap planners. IEEE Trans. Robot. 21(6), 1105–1115 (2005)
Boor, V., Overmars, M.H., van der Stappen, A.F.: The Gaussian sampling strategy for probabilistic roadmap planners. In: IEEE International Conference on Robotics and Automation, pp. 1018–1023 (1999)
Pan, J., Chitta, S., Manocha, D.: Faster sample-based motion planning using instance-based learning. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X. Springer Tracts in Advanced Robotics, vol. 86, pp. 381–396. Springer, Heidelberg (2013)
Aarno, D., Kragic, D., Christensen, H.I.: Artificial potential biased probabilistic roadmap method. In: IEEE International Conference on Robotics and Automation, pp. 461–466 (2004)
Katz, R., Hutchinson, S.: Efficiently biasing PRMS with passage potentials. In: IEEE International Conference on Robotics and Automation, pp. 889–894 (2006)
Bayazıt, O.B., Lien, J.-M., Amato, N.M.: Swarming behavior using probabilistic roadmap techniques. In: Şahin, E., Spears, W.M. (eds.) Swarm Robotics 2004. LNCS, vol. 3342, pp. 112–125. Springer, Heidelberg (2005)
Bayazıt, O.B., Lien, J.M., Amato, N.M.: Better group behaviors using rule-based roadmaps. In: International Workshop on Algorithmic Foundations of Robotics, pp. 95–112 (2004)
Harrison, J.F., Vo, C., Lien, J.-M.: Scalable and robust shepherding via deformable shapes. In: Boulic, R., Chrysanthou, Y., Komura, T. (eds.) MIG 2010. LNCS, vol. 6459, pp. 218–229. Springer, Heidelberg (2010)
Krontiris, A., Louis, S., Bekris, K.E.: Multi-level formation roadmaps for collision-free dynamic shape changes with non-holonomic teams. In: IEEE International Conference on Robotics and Automation (2012)
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)
LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge, MA (2006)
Wallar, A., Plaku, E.: Source code for CRoPS: combined roadmaps and potentials for swarm path planning (2013). http://aw204.host.cs.st-andrews.ac.uk/CRoPS/
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wallar, A., Plaku, E. (2014). Path Planning for Swarms by Combining Probabilistic Roadmaps and Potential Fields. In: Natraj, A., Cameron, S., Melhuish, C., Witkowski, M. (eds) Towards Autonomous Robotic Systems. TAROS 2013. Lecture Notes in Computer Science(), vol 8069. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43645-5_43
Download citation
DOI: https://doi.org/10.1007/978-3-662-43645-5_43
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43644-8
Online ISBN: 978-3-662-43645-5
eBook Packages: Computer ScienceComputer Science (R0)