Abstract
This paper investigates the coordination of multiple robots with pre-specified paths, considering motion safety and minimizing the traveling time. A method to estimate possible collision point along the local paths of the robots is proposed. The repulsive potential energy is computed based on the distances between the robots and the potential collision points. This repulsive potential energy is used as the cost map of the probabilistic roadmap (PRM), which is constructed in the coordination space for multiple robots taking into account both motion time cost and safety cost. We propose a search method on the PRM to obtain the Pareto-optimal coordination solution for multiple robots. Both simulation and experimental results are presented to demonstrate the effectiveness of the algorithms.
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
Barraquand, J., & Latombe, J. (1991). Robot motion planning: a distributed representation approach. Int. J. Robot. Res., 10(6), 628–649.
Chakravarthy, A., & Ghose, D. (1998). Obstacle avoidance in a dynamic environment: a collision cone approach. IEEE Trans. Syst. Man Cybern., Part A, Syst. Hum., 28(5), 562–574.
Chitsaz, H., O’Kane, J. M., & LaValle, S. M. (2004). Exact Pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap. In Proceedings of 2004 IEEE international conference on robotics and automation (Vol. 4, pp. 3981–3986).
Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., & Thrun, S. (2005). Principles of robot motion: theory, algorithms and implementation. Cambridge: MIT Press.
Cui, R., Ge, S. S., How, V. E. B., & Choo, Y. S. (2010). Leader-Follower formation control of underactuated autonomous underwater vehicles. Ocean Eng., 37(17–18), 1491–1502.
Durfee, E. H. (1999). Distributed continual planning for unmanned ground vehicle teams. AI Mag., 20(4), 55–61.
Fua, C. H., Ge, S. S., Do, K. D., & Lim, K. W. (2007). Multirobot formations based on the queue-formation scheme with limited communication. IEEE Trans. Robot., 23(6), 1160–1169.
Ge, S. S., & Cui, Y. J. (2002a). New potential functions for mobile robot path planning. IEEE Trans. Robot. Autom., 16(5), 615–620.
Ge, S. S., & Cui, Y. J. (2002b). Dynamic motion planning for mobile robots using potential field method. Auton. Robots, 13(3), 207–222.
Ge, S. S., & Fua, C. H. (2004). Queues and artificial potential trenches for multirobot formations. IEEE Trans. Robot., 21(4), 646–656.
Ghrist, R., O’Kane, J. M., & LaValle, S. M. (2005a). Computing Pareto optimal coordinations on roadmaps. Int. J. Robot. Res., 24(11), 997–1010.
Ghrist, R., O’Kane, J. M., & LaValle, S. M. (2005b). Pareto optimal coordination on roadmaps. In Algorithmic foundations of robotics VI (pp. 171–186).
Hsu, D. (2000). Randomized single-query motion planning in expansive spaces. Ph.D. dissertation, Stanford University.
Hu, H., Brady, M., & Probert, P. (2002). Coping with uncertainty in control and planning for a mobile robot. In Proceedings of IEEE/RSJ international workshop on intelligent robots and systems (pp. 1025–1030).
Hu, J., Prandini, M., & Sastry, S. (2002). Optimal coordinated maneuvers for three-dimensional aircraft conflict resolution. J. Guid. Control Dyn., 25(5), 888–900.
Kant, K., & Zucker, S. (1986). Toward efficient trajectory planning: the path velocity decomposition. Int. J. Robot. Res., 5(3), 72–89.
Kavraki, L. E., Svestka, P., Latombe, J. C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom., 12(4), 566–580.
Kuchar, J. K., & Yang, L. C. (2002). A review of conflict detection and resolution modeling methods. IEEE Trans. Intell. Transp. Syst., 1(4), 179–189.
Kuffner, J. (2004). Effective sampling and distance metrics for 3d rigid body path planning. In Proceedings of IEEE international conference on robotics and automation (Vol. 4, pp. 3993–3998).
Kuffner, J. J., & LaValle, S. M. (2000). Rrt-connect: an efficient approach to single-query path planning. In Proceedings of IEEE international conference on robotics and automation (Vol. 2, pp. 995–1001).
Ladd, A., & Kavraki, L. E. (2002). Generalizing the analysis of PRM. In Proceedings of IEEE international conference on robotics and automation (Vol. 2, pp. 2120–2125).
Laffary, M. (2002). MobileRobots advanced robotics interface for applications (ARIA) developer’s reference manual. http://robots.mobilerobots.com/wiki/ARIA.
LaValle, S. M. (2006). Planning algorithms. Cambridge: Cambridge University Press.
LaValle, S. M., & Hinrichsen, J. (2001). Visibility-based pursuit-evasion: the case of curved environments. IEEE Trans. Robot. Autom., 17(2), 196–202.
Liu, G., & Li, Z. (2002). A unified geometric approach to modeling and control of constrained mechanical systems. IEEE Trans. Robot. Autom., 18(4), 574–587.
Mataric, M. (1995). Issues and approaches in the design of collective autonomous agents. Robot. Auton. Syst., 16(2), 321–332.
Mortezaie, F. (1991). Constrained voronoi diagram and its application to autonomous mobile robot path planning. Ph.D. dissertation, University of California, Irvine.
Parker, L. E. (1997). ‘Cooperative motion control for multi-target observation. In Proceedings of the 1997 IEEE/RSJ international conference on intelligent robots and systems (Vol. 3, pp. 1591–1597).
Plaku, E., & Kavraki, L. (2005). Distributed sampling-based roadmap of trees for large-scale motion planning. In IEEE international conference on robotics and automation (Vol. 4, pp. 3868–3873).
Purwin, O., D’Andrea, R., & Lee, J. W. (2008). Theory and implementation of path planning by negotiation for decentralized agents. Robot. Auton. Syst., 56(5), 422–436.
Schouwenaars, T., How, J., & Feron, E. (2004). Decentralized cooperative trajectory planning of multiple aircraft with hard safety guarantees. In Proceedings of the AIAA guidance, navigation and control conference.
Schwarzer, F., Saha, M., & Latombe, J. C. (2003). Exact collision checking of robot paths. In Algorithmic foundations of robotics V (pp. 25–42).
Shanmugavel, M., Tsourdos, A., White, B., & Zbikowski, R. (2009). Co-operative path planning of multiple UAVs using Dubins paths with clothoid arcs. Control Eng. Pract., 18(9), 1084–1092.
Shin, K. G., & Zheng, Q. (1992). Minimum-time collision free trajectory planning for dual robot systems. IEEE Trans. Robot. Autom., 8(5), 641–644.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cui, R., Gao, B. & Guo, J. Pareto-optimal coordination of multiple robots with safety guarantees. Auton Robot 32, 189–205 (2012). https://doi.org/10.1007/s10514-011-9265-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-011-9265-9