Abstract
Real-time motion planning and control for groups of heterogeneous and under-actuated robots subject to disturbances and uncertainties in cluttered constrained environments is the key problem addressed in this paper. Here we present the Multi-agent Rapidly-exploring Pseudo-random Tree (MRPT), a novel technique based on a classical Probabilistic Road Map (PRM) algorithm for application in robot team cooperation. Our main contribution lies in the proposal of an extension of a probabilistic approach to be used as a deterministic planner in distributed complex multi-agent systems, keeping the main advantages of PRM strategies like simplicity, fast convergence, and probabilistic completeness. Our methodology is fully distributed, addressing missions with multi-robot teams represented by high nonlinear models and a great number of Degrees of Freedom (DoFs), endowing each agent with the ability of coordinating its own movement with other agents while avoiding collisions with obstacles. The inference of the entire team’s behavior at each time instant by each individual agent is the main improvement of our method. This scheme, which is behavioral in nature, also makes the system less susceptible to failures due to intensive traffic communication among robots. We evaluate the time complexity of our method and show its applicability in planning and executing search and rescue missions for a group of robots in S E3 outdoor scenarios and present both simulated and real-world results.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5 (1), 90–98 (1986)
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 (June 2005)
LaValle, S. M.: Planning Algorithms. Cambridge University Press, Illinois (2006)
Lee, S. M., Kim, H., Myung, H., Yao, X.: Cooperative coevolutionary algorithm-based model predictive control guaranteeing stability of multirobot formation. IEEE Trans. Control Syst. Technol. 23 (1), 37–51 (2015)
LaValle, S., Kuffner J., Jr: Randomized kinodynamic planning. IEEE Int. Conf. Robot. Autom. 1, 473–479 (1999)
Kuwata, Y., Teo, J., Karaman, S., Fiore, G., Frazzoli, E., How, J. P.: Motion planning in complex environments using closed-loop prediction. In: AIAA Guidance, Navigation, and Control Conference and Exhibit (2008)
Luders, B. D., Karaman, S., Frazzoli, E., How, J. P.: Bounds on tracking error using closed-loop rapidly-exploring random trees. In: American Control Conference (2010)
Kamio, S., Iba, H.: Cooperative object transport with humanoid robots using RRT path planning and re-planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (2006)
Vahrenkamp, N., Kuhn, E., Asfour, T., Dillmann, R.: Planning Multi-Robot Grasping Motions. In: IEEE/RAS International Conference on Humanoid Robots, Nashville (2010)
Frazzoli, E.: Quasi-random algorithms for real-time spacecraft motion planning and coordination. Acta Astronaut. 53(4-10), 485–495 (2003)
Desaraju, V. R., How, J. P.: Decentralized path planning for multi-agent teams with complex constraints. Auton. Robot. 32(4), 385–403 (2012)
Otte, M., Bialkowski, J., Frazzoli, E.: Any-com collision checking: Sharing certificates in decentralized multi-robot teams. In: IEEE International Conference on Robotics and Automation, pp. 563–570 (2014)
Alves Neto, A., Macharet, D. G., Campos, M. F. M.: On the generation of trajectories for multiple uavs in environments with obstacles. J. Intell. Robot. Syst. 57(4), 123–141 (2010)
Alves Neto, A., Macharet, D. G., Chaimowicz, L., Campos, M. F. M.: Path planning with multiple rapidly-exploring random trees for teams of robots. in IEEE International Conference on Advanced Robotics. Montevideo, Uruguay (2013)
LaValle, S. M., Branicky, M. S., Lindemann, S. R.: On the relationship between classical grid search and probabilistic roadmaps. Int. J. Robot. Res. 23(7–8), 673–692 (2004)
Frazzoli, E., Dahleh, M. A., Feron, E.: Real-time motion planning for agile autonomous vehicles. AIAA J. Guid. Control. Dyn. 25, 116–129 (2002)
Kuwata, Y., Teo, J., Fiore, G., Karaman, S., Frazzoli, E., How, J. P.: Real-time motion planning with applications to autonomous urban driving. IEEE Trans. Control Syst. Technol. 17 (5), 1105–1118 (2009)
Svenstrup, M., Bak, T., Andersen, H. J.: Minimising computational complexity of the rrt algorithm a practical approach. In: IEEE International Conference on Robotics and Automation, pp. 5602–5607. (2011)
Vemuri, B. C., Cao, Y., Chen, L.: Fast collision detection algorithms with applications to particle flow. Comput. Graph. Forum 17(2), 121–134 (1998)
Pnevmatikakis, E. A., Rad, K. R., Huggins, J., Paninski, L.: Fast kalman filtering and forward-backward smoothing via a low-rank perturbative approach. J. Comput. Graph. Stat. 23(2), 316–339 (2014)
Michael, N, Mellinger, D., Lindsey, Q., Kumar, V.: The grasp multiple micro-uav testbed. IEEE Robot. Autom. Mag. 17(3), 56–65 (2010)
Mozelli, L. A., Alves Neto, A., Campos, M. F. M.: Attitude of quadrotor-like vehicles: Fuzzy modeling and control with prescribed rate of convergence. In: IEEE International Conference on Robotics and Automation, pp. 1710–1715. (2015)
Acknowledgments
This work was developed with support of Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) and Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Neto, A.A., Macharet, D.G. & M. Campos, M.F. Multi-agent Rapidly-exploring Pseudo-random Tree. J Intell Robot Syst 89, 69–85 (2018). https://doi.org/10.1007/s10846-017-0516-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-017-0516-7