Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-24T13:03:41.421Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimizing coordinated motion planning for multiple car-like robots on a segment of highway

Published online by Cambridge University Press:  23 January 2015

Ricardo Reghelin Open the ORCID record for Ricardo Reghelin [Opens in a new window]  and
Lucia Valeria Arruda
Ricardo Reghelin*
Affiliation:
Instituto Federal Catarinense - IFC, Brazil
Lucia Valeria Arruda
Affiliation:
Universidade Tecnológica Federal do Paraná - UTFPR, CPGEI, Brazil
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

Real-time responses for multiple robots motion planning demand heuristic algorithms. This paper presents a method to evaluate the efficiency of these algorithms in order to compute coordinated trajectories for multiple car-like robots on a segment of a highway. The idea is to compare the results of these algorithms with the optimal result obtained by a proposed mixed-integer linear programming (MILP) optimization model. The MILP model considers the main elements of a traffic system, such as topography of lanes, traffic rules and individual capacity of acceleration. Moreover, new indexes for microscopic traffic assessment are proposed a well. Several tests have been carried out to validate both the MILP model and the algorithm used.

Keywords

Autonomous vehiclesTraffic optimizationMultiple robot motion planningMILP
Type
Articles
Information
Robotica , Volume 34 , Issue 10 , October 2016 , pp. 2274 - 2290
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Varaiya, P., “Smart cars on smart roads: Problems of control,” IEEE Trans. Autom. Control 38, 195–207 (1993).Google Scholar
2. Latombe, J.-C., Robot Motion Planning (Kluwer Academic Publishers, Norwell, MA, USA, 1991).Google Scholar
3. Hopcroft, J. E., Schwartz, J. T. and Sharir, M., “On the complexity of motion planning for multiple independent objects: Pspace-hardness of the “warehousemans problem”,” Int. J. Robot. Res. 3 (4), 76–88 (1984).CrossRefGoogle Scholar
4. LaValle, S. M., Planning Algorithms (Cambridge University Press, Cambridge, UK, 2006).Google Scholar
5. Kavraki, L. E., Svestka, J. C., Latombe, P. and Overmars, M. H., “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom. 12, 566–580 (1996).Google Scholar
6. Geraerts, R. and Overmars, M. H., “A comparative study of probabilistic roadmap planners,” Algorithmic Found. Robot. V 7 (2), 43–58 (2002).CrossRefGoogle Scholar
7. LaValle, S. M. and Kuffner, J. J., “Randomized kinodynamic planning,” Int. J. Robot. Res. 20 (5), 378–400 (2001).CrossRefGoogle Scholar
8. Svestka, P. and Overmars, M. H., “Coordinated path planning for multiple robots,” Robot. Auton. Syst. 23, 125–152 (1998).Google Scholar
9. Peasgood, M., Clark, C. M. and McPhee, J., “A complete and scalable strategy for coordinating multiple robots within roadmaps,” IEEE Trans. Robot. 24 (2), 283–292 (2008).Google Scholar
10. Erdmann, M. and Lozano-Perez, T., “On multiple moving objects,” Algorithmica 2, 1419–1424 (1987).CrossRefGoogle Scholar
11. Van Den Berg, J. and Overmars, M., “Prioritized Motion Planning for Multiple Robots,” Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Edmonton, Canada (2005) pp. 2217–2222.Google Scholar
12. Bennewitz, M., Burgard, W. and Thrun, S., “Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots,” Robot. Auton. Syst. 41 (2–3), 89–99 (2002).Google Scholar
13. Peng, J. and Akella, S., “Coordinating multiple robots with kinodynamic constraints along specified paths,” Int. J. Robot. Res. 24, 295–310 (2005).Google Scholar
14. Kant, K. and Zucker, S., “Towards efficient trajectory planning: The path-velocity decomposition,” Int. J. Robot. Res. 5, 72–89 (1986).Google Scholar
15. Saha, M. and Isto, P., “Multi-Robot Motion Planning by Incremental Coordination,” Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Beijing, China (2006) pp. 5960–5963.Google Scholar
16. LaValle, S. M. and Hutchinson, S. A., “Optimal motion planning for multiple robots having independent goals,” IEEE Trans. Robot. Autom. 14, 912–925 (1998).Google Scholar
17. Akella, S. and Hutchinson, S., “Coordinating the Motions of Multiple Robots with Specified Trajectories,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, D.C., USA (2002) pp. 624–631.Google Scholar
18. Simeon, T., Leroy, S. and Laumond, J., “Path coordination for multiple mobile robots: A resolution complete algorithm,” IEEE Trans. Robot. Autom. 24, 42–49 (2002).Google Scholar
19. Ghrist, R., O'Kane, J. M. and LaValle, S. M., “Computing pareto optimal coordinations on roadmaps,” Int. J. Robot. Res. 24 (11), 997–1010 (2005).Google Scholar
20. Schouwenaars, T., De Moor, B., Feron, E. and How, J., “Mixed Integer Programming for Multi-Vehicle Path Planning,” Proceedings 2001 European Control Conference, Porto, Portugal (Sep. 2001) pp. 2603–2608.Google Scholar
21. Kala, R., “Multi-robot path planning using co-evolutionary genetic programming,” Expert Syst. Appl. 39 (3), 3817–3831 (2012).Google Scholar
22. Kato, S., Tsugawa, S., Tokuda, K., Matsui, T. and Fujii, H., “Vehicle control algorithms for cooperative driving with automated vehicles and intervehicle communications,” IEEE Trans. Intell. Transp. Syst. 3 (3), 155–161 (2002).Google Scholar
23. Asama, H., Ozaki, K., Itakura, H., Matsumoto, A., Ishida, Y. and Endo, I., “Collision Avoidance among Multiple Mobile Robots based on Rules and Communication,” Proceedings IROS 91IEEERSJ International Workshop on Intelligent Robots and Systems 91, Osaka, Japan (1991) pp. 1215–1220.Google Scholar
24. Yuta, S. and Premvuti, S., “Coordinating Autonomous and Centralized Decision making to Achieve Cooperative Behaviors between Multiple Mobile Robots,” Proceedings of the 1992 IEEE/RSJ International Conference on Intelligent Robots and Systems, Raleigh, USA (1992) pp. 1566–1574.Google Scholar
25. Wang, J., “Fully Distributed Traffic Control Strategies for Many-Agv Systems,” Proceedings of the IEEE International Workshop on Intelligent Robots and Systems, Osaka, Japan (Nov. 1991) pp. 1199–1204.Google Scholar
26. Alami, R., Fleury, S., Herrb, M., Ingrand, F. and Robert, F., “Multi-robot cooperation in the Martha project,” IEEE Robot. Autom. Mag. 5, 36–47 (1998).Google Scholar
27. Pallottino, V. G., Scordio, L., Bicchi, A. and Frazzoli, E., “Decentralized cooperative policy for conflict resolution in multi-vehicle systems,” IEEE Trans. Robot. 23 1170–1183 (2007).Google Scholar
28. Synodinos, A. and Aspragathos, N. A., “Path Planning of a Mobile Robot using Solid Modeling Techniques on Potential Fields,” Proceedings of 2010 IEEE/ASME International Conference on Mechatronic and Embedded Systems and Applications MESA, Qingdao, China (2010) pp. 549–553.Google Scholar
29. Reghelin, R. and Arruda, L. V. R., “An Optimization Model for Microscopic Centralized Traffic Management of Intelligent Vehicles in a Segment of a Single Lane,” Proceedings of IEEE Intelligent Vehicles Symposium, Alcala de Henares, Spain (2012) pp. 908–913.Google Scholar
30. Reghelin, R. and Arruda, L. V. R., “A Centralized Traffic Controller for Intelligent Vehicles in a Segment of a Multilane Highway,” Proceedings of IEEE Intelligent Vehicles Symposium. Alcala de Henares, Spain (2012) pp. 135–140.Google Scholar
31. Gipps, P., “A behavioral car following model for computer simulation,” Transp. Res. B 15, 105–111 (1981).Google Scholar
32. Reghelin, R. and Arruda, L. V. R., “Using a Centralized Controller to Optimize the Traffic of Intelligent Vehicles in a Single Lane Highway Provided with a Suicide Lane,” 15th International IEEE Conference on Intelligent Transportation Systems (ITSC), Anchorage, AK (Sep. 2012) pp. 1049–1054.Google Scholar