Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-21T17:08:56.260Z Has data issue: false hasContentIssue false
  • English
  • Français

A survey of formation control and motion planning of multiple unmanned vehicles

Published online by Cambridge University Press:  21 March 2018

Yuanchang Liu  and
Richard Bucknall
Yuanchang Liu*
Affiliation:
Department of Mechanical Engineering, University College London, Torrington Place, London, WC1E 7JE, UK.
Richard Bucknall
Affiliation:
Department of Mechanical Engineering, University College London, Torrington Place, London, WC1E 7JE, UK.
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

The increasing deployment of multiple unmanned vehicles systems has generated large research interest in recent decades. This paper therefore provides a detailed survey to review a range of techniques related to the operation of multi-vehicle systems in different environmental domains, including land based, aerospace and marine with the specific focuses placed on formation control and cooperative motion planning. Differing from other related papers, this paper pays a special attention to the collision avoidance problem and specifically discusses and reviews those methods that adopt flexible formation shape to achieve collision avoidance for multi-vehicle systems. In the conclusions, some open research areas with suggested technologies have been proposed to facilitate the future research development.

Keywords

Collision avoidanceCooperative path planningFormation controlTrajectory optimisationUnmanned vehicle formation
Type
Articles
Information
Robotica , Volume 36 , Issue 7 , July 2018 , pp. 1019 - 1047
Copyright
Copyright © Cambridge University Press 2018 

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. US Military, Unmanned System Integrated Roadmap, FY2011-2036. Technical report, US Department of Defense (DoD), 2011.Google Scholar
2. Royal Navy, UNMANNED WARRIOR, year = 2016, url = https://www.royalnavy.mod.uk/news-and-latest-activity/operations/uk-home-waters/unmanned-warrior”, Accessed: 2017-11-08.Google Scholar
3. Zhang, Y. and Mehrjerdi, H., “A Survey on Multiple Unmanned Vehicles Formation Control and Coordination: Normal and Fault Situations,” Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS), IEEE (2013) pp. 1087–1096.Google Scholar
4. Matthies, L., Kelly, A., Litwin, T. and Tharp, G., “Obstacle Detection for Unmanned Ground Vehicles: A Progress Report,” In: Robotics Research (Giralt, G. and Hirzinger, G., eds.) (Springer 1996) pp. 475–486.Google Scholar
5. Manley, J. E., “Unmanned Surface Vehicles, 15 Years of Development,” Proceedings of the OCEANS, IEEE (2008) pp. 1–4.Google Scholar
6. Oh, K.-K., Park, M.-C. and Ahn, H.-S., “A survey of multi-agent formation control,” Automatica 53, 424–440 (2015).Google Scholar
7. Bellingham, J. S., Tillerson, M., Alighanbari, M. and How, J. P., “Cooperative Path Planning for Multiple Uavs in Dynamic and Uncertain Environments,” Proceedings of the 41st IEEE Conference on Decision and Control, volume 3, IEEE (2002) pp. 2816–2822.Google Scholar
8. Tsourdos, A., White, B. and Shanmugavel, M., Cooperative Path Planning of Unmanned Aerial Vehicles, volume 32 (John Wiley & Sons, The Atrium, United Kingdom, 2010).Google Scholar
9. Egerstedt, M. and Hu, X., “Formation constrained multi-agent control,” IEEE Trans. Robot. Autom. 17 (6), 947–951 (2001).Google Scholar
10. Garrido, S., Moreno, L. and Lima, P. U., “Robot formation motion planning using fast marching,” Robot. Auton. Syst. 59 (9), 675–683 (2011).Google Scholar
11. Gómez, J. V., Lumbier, A., Garrido, S. and Moreno, L., “Planning robot formations with fast marching square including uncertainty conditions,” Robot. Auton. Syst. 61 (2), 137–152 (2013).Google Scholar
12. Stone, P. and Veloso, M., “Multiagent systems: A survey from a machine learning perspective,” Auton. Robots 8 (3), 345–383 (2000).CrossRefGoogle Scholar
13. Scharf, D. P., Hadaegh, F. Y. and Ploen, S. R., “A Survey of Spacecraft Formation Flying Guidance and Control. Part II: Control,” Proceedings of the American Control Conference, volume 4, IEEE (2004) pp. 2976–2985.Google Scholar
14. Ren, W., Beard, R. W. and Atkins, E. M., “A Survey of Consensus Problems in Multi-Agent Coordination,” Proceedings of the American Control Conference, IEEE (2005) pp. 1859–1864.Google Scholar
15. Tam, C. K., Motion Planning Algorithm for Ships in Close Range Encounters. Ph.D. Thesis, UCL (University College London, 2009).Google Scholar
16. Campbell, S., Naeem, W. and Irwin, G. W., “A review on improving the autonomy of unmanned surface vehicles through intelligent collision avoidance manoeuvres,” Annu. Rev. Control 36 (2), 267–283 (2012).Google Scholar
17. Elbanhawi, M. and Simic, M., “Sampling-based robot motion planning: A review,” IEEE Access 2, 56–77 (2014).Google Scholar
18. Goerzen, C., Kong, Z. and Mettler, B., “A survey of motion planning algorithms from the perspective of autonomous uav guidance,” J. Intell. Robot. Syst. 57 (1–4), 65 (2010).CrossRefGoogle Scholar
19. Chandler, P. R., Pachter, M. and Rasmussen, S., “UAV Cooperative Control,” Proceedings of the 2001 American Control Conference, volume 1, IEEE, (2001), pp. 50–55.Google Scholar
20. Fukuda, T. and Nakagawa, S., “Dynamically Reconfigurable Robotic System,” Proceedings of the IEEE International Conference on Robotics and Automation, IEEE (1988) pp. 1581–1586.Google Scholar
21. Asama, H., Matsumoto, A. and Ishida, Y., “Design of an Autonomous and Distributed Robot System: Actress,” Proceedings of the IEEE/RSJ IROS (1989) pp. 283–290.Google Scholar
22. Balakirsky, S., Carpin, S., Kleiner, A., Lewis, M., Visser, A., Wang, J. and Ziparo, V. A., “Towards heterogeneous robot teams for disaster mitigation: Results and performance metrics from robocup rescue,” J. Field Robot. 24 (11–12), 943–967 (2007).CrossRefGoogle Scholar
23. Liu, Y. and Nejat, G., “Multirobot cooperative learning for semiautonomous control in urban search and rescue applications,” J. Field Robot. 33 (4), 512–536 (2016).Google Scholar
24. Guzman, R., Navarro, R., Ferre, J. and Moreno, M., “Rescuer: Development of a modular chemical, biological, radiological, and nuclear robot for intervention, sampling, and situation awareness,” J. Field Robot. 33 (7), 931–945 (2016).Google Scholar
25. Nagatani, K. et al, “Multirobot exploration for search and rescue missions: A report on map building in robocuprescue 2009,” J. Field Robot. 28 (3), 373–387 (2011).Google Scholar
26. Saeedi, S., Trentini, M., Seto, M. and Li, H., “Multiple-robot simultaneous localization and mapping: A review,” J. Field Robot. 33 (1), 3–46 (2016).Google Scholar
27. Girard, A. R., Howell, A. S. and Hedrick, J. K., “Border Patrol and Surveillance Missions using Multiple Unmanned Air Vehicles,” Proceedings of the43rd IEEE Conference on Decision and Control, volume 1, IEEE (2004) pp. 620–625.Google Scholar
28. Roehr, T. M., Cordes, F. and Kirchner, F., “Reconfigurable integrated multirobot exploration system (RIMRES): Heterogeneous modular reconfigurable robots for space exploration,” J. Field Robot. 31 (1), 3–34 (2014).Google Scholar
29. Breivik, M. and Hovstein, V. E., “Formation Control for Unmanned Surface Vehicles: Theory and Practice,” Proceedings of the IFAC World Congress (2008).Google Scholar
30. Liu, Y. and Bucknall, R., “Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment,” Ocean Eng. 97, 126–144 (2015).Google Scholar
31. Shanmugavel, M., Tsourdos, A., White, B. and Zbikowski, R., “Co-operative path planning of multiple UAVs using dubins paths with clothoid arcs,” Control Eng. Pract. 18 (9), 1084–1092 (2010).Google Scholar
32. Cui, R., Guo, J. and Gao, B., “Game theory-based negotiation for multiple robots task allocation,” Robotica 31 (06), 923–934 (2013).Google Scholar
33. Gerkey, B. P. and Matarić, M. J., “A formal analysis and taxonomy of task allocation in multi-robot systems,” Int. J. Robot. Res. 23 (9), 939–954 (2004).Google Scholar
34. Khamis, A., Hussein, A. and Elmogy, A., “Multi-Robot Task Allocation: A Review of the State-of-the-Art,” In: Cooperative Robots and Sensor Networks 2015 (Koubâa, A., Ramiro, J. and Dios, Martínez-de, eds.) (Springer, Switzerland, 2015) pp. 31–51.Google Scholar
35. Zhu, D., Huang, H. and Yang, S. X., “Dynamic task assignment and path planning of multi-auv system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace,” IEEE Trans. Cybern. 43 (2), 504–514 (2013).Google Scholar
36. Faigl, J. and Hollinger, G. A., “Autonomous data collection using a self-organizing map,” IEEE Trans. Neural Netw. Learning Syst. PP(99), 1–13 (2017).Google Scholar
37. Liu, Y. and Bucknall, R., “Efficient multi-task allocation and path planning for unmanned surface vehicle in support of ocean operations,” Neurocomputing 275: 1550–1566 (2018).Google Scholar
38. Muñoz, P., R-Moreno, M. D. and Barrero, D. F., “Unified framework for path-planning and task-planning for autonomous robots,” Robot. Auton. Syst. 82, 1–14 (2016).Google Scholar
39. Mahmoud Zadeh, S., Powers, D. M. W., Sammut, K. and Yazdani, A., “Toward efficient task assignment and motion planning for large-scale underwater missions,” Int. J. Adv. Robot. Syst. 13 (5)(2016), Art. no. 1729881416657974.Google Scholar
40. Zhu, D., Cao, X., Sun, B. and Luo, C., “Biologically inspired self-organizing map applied to task assignment and path planning of an auv system,” IEEE Trans. Cogn. Develop. Syst. PP(99), 1–11 (2017).Google Scholar
41. Dong, X., Zhou, Y., Ren, Z. and Zhong, Y., “Time-varying formation control for unmanned aerial vehicles with switching interaction topologies,” Control Eng. Pract. 46, 26–36 (2016).Google Scholar
42. Yamchi, M. H. and Esfanjani, R. M., “Distributed predictive formation control of networked mobile robots subject to communication delay,” Robot. Auton. Syst. 91, 194–207 (2017).Google Scholar
43. Li, H., Xie, P. and Yan, W., “Receding horizon formation tracking control of constrained underactuated autonomous underwater vehicles,” IEEE Trans. Ind. Electron. 64 (6), 5004–5013 (2017).Google Scholar
44. Chen, Y. Q. and Wang, Z., “Formation Control: A Review and A New Consideration,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE (2005) pp. 3181–3186.Google Scholar
45. Wang, P. K. C., “Navigation strategies for multiple autonomous mobile robots moving in formation,” J. Robot. Syst. 8 (2), 177–195 (1991).Google Scholar
46. Yang, T., Liu, Z., Chen, H. and Pei, R., “Formation control of mobile robots: State and open problems,” Zhineng Xitong Xuebao (CAAI Trans. Intell. Syst.) 2 (4), 21–27 (2007).Google Scholar
47. Peng, Z., Wen, G., Rahmani, A. and Yu, Y., “Leader–follower formation control of nonholonomic mobile robots based on a bioinspired neurodynamic based approach,” Robot. Auton. Syst. 61 (9), 988–996 (2013).Google Scholar
48. Desai, J. P., Ostrowski, J. and Kumar, V., “Controlling Formations of Multiple Mobile Robots,” Proceedings of the IEEE International Conference on Robotics and Automation, volume 4, IEEE (1998) pp. 2864–2869.Google Scholar
49. Consolini, L., Morbidi, F., Prattichizzo, D. and Tosques, M., “Leader–follower formation control of nonholonomic mobile robots with input constraints,” Automatica 44 (5), 1343–1349 (2008).Google Scholar
50. Edwards, D. B., Bean, T. A., Odell, D. L. and Anderson, M. J., “A leader-follower algorithm for multiple AUV formations,” IEEE/OES Autonomous Underwater Vehicles (IEEE Cat. No.04CH37578), 2004, pp. 40–46.Google Scholar
51. Orqueda, O. A. A., Zhang, X. T. and Fierro, R., “An output feedback nonlinear decentralized controller for unmanned vehicle co-ordination,” Int. J. Robust Nonlinear Control 17 (12), 1106–1128 (2007).Google Scholar
52. Peng, Z., Wang, D., Lan, W. and Sun, G., “Robust leader-follower formation tracking control of multiple underactuated surface vessels,” China Ocean Eng. 26, 521–534 (2012).Google Scholar
53. Tan, K.-H. and Lewis, M. A., “Virtual Structures for High-Precision Cooperative Mobile Robotic Control,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems' 96, volume 1, IEEE (1996) pp. 132–139.Google Scholar
54. Lewis, M. A. and Tan, K.-H., “High precision formation control of mobile robots using virtual structures,” Auton. Robots 4 (4), 387–403 (1997).Google Scholar
55. Do, K. D., “Bounded controllers for formation stabilization of mobile agents with limited sensing ranges,” IEEE Trans. Autom. Control 52 (3), 569–576 (2007).Google Scholar
56. Do, K. D., “Formation control of multiple elliptical agents with limited sensing ranges,” Automatica 48 (7), 1330–1338 (2012).Google Scholar
57. Balch, T. and Arkin, R. C., “Behavior-based formation control for multirobot teams,” IEEE Trans. Robot. Autom. 14 (6), 926–939 (1998).Google Scholar
58. Do, K. D. and Pan, J., “Nonlinear formation control of unicycle-type mobile robots,” Robot. Auton. Syst. 55 (3), 191–204 (2007).Google Scholar
59. Cao, Z., Tan, M., Wang, S., Fan, Y. and Zhang, B., “The Optimization Research of Formation Control for Multiple Mobile Robots,” Proceedings of the 4th World Congress on Intelligent Control and Automation, volume 2, IEEE (2002) pp. 1270–1274.Google Scholar
60. Cao, Z., Xie, L., Zhang, B., Wang, S. and Tan, M., “Formation Constrained Multi-Robot System in Unknown Environments,” Proceedings of the IEEE International Conference on Robotics and Automation, volume 1, IEEE (2003) pp. 735–740.Google Scholar
61. Yang, F., Liu, F., Liu, S. and Zhong, C., “Hybrid Formation Control of Multiple Mobile Robots with Obstacle Avoidance,” Proceedings of the 8th World Congress on Intelligent Control and Automation (WCICA), IEEE (2010) pp. 1039–1044.Google Scholar
62. Forsyth, D. R. and Elliott, T. R., “Group dynamics and psychological well-being: The impact of groups on adjustment and dysfunction,” In: The social psychology of emotional and behavioral problems: Interfaces of social and clinical psychology (Kowalski, R. M. and Leary, M. R., eds.), (1999) pp. 339–361.Google Scholar
63. Tousi, M. M., Aghdam, A. G. and Khorasani, K., “A Hybrid Fault Diagnosis and Recovery for a Team of Unmanned Vehicles,” Proceedings of the IEEE International Conference on System of Systems Engineering, IEEE (2008) pp. 1–6.Google Scholar
64. Yang, H., Staroswiecki, M., Jiang, B. and Liu, J., “Fault tolerant cooperative control for a class of nonlinear multi-agent systems,” Syst. Control Lett. 60 (4), 271–277 (2011).Google Scholar
65. Tousi, M. M. and Khorasani, K., “Optimal hybrid fault recovery in a team of unmanned aerial vehicles,” Automatica 48 (2), 410–418 (2012).Google Scholar
66. Tam, C., Bucknall, R. and Greig, A., “Review of collision avoidance and path planning methods for ships in close range encounters,” J. Navig. 62 (03), 455–476 (2009).Google Scholar
67. Korf, R. E., “Real-time heuristic search,” Artif. Intell. 42 (2), 189–211 (1990).Google Scholar
68. Tam, C. and Bucknall, R., “Cooperative path planning algorithm for marine surface vessels,” Ocean Eng. 57, 25–33 (2013).Google Scholar
69. Sharma, S., Sutton, R., Hatton, D. and Singh, Y., “Path Planning of an Autonomous Surface Vehicle Based on Artificial Potential Fields in a Real Time Marine Environment,” Proceedings of the 16th Conference on Computer and IT Application in the Maritime Industries (2017) pp. 48–54.Google Scholar
70. Khatib, O., “Real-time obstacle avoidance for manipulators and mobile robots,” Int. J. Robot. Res. 5 (1), 90–98 (1986).Google Scholar
71. Lee, S.-M., Kwon, K.-Y. and Joh, J., “A fuzzy logic for autonomous navigation of marine vehicles satisfying colreg guidelines,” Int. J. Control Autom. Syst. 2 (2), 171–181 (2004).Google Scholar
72. Wang, J., Wu, X. and Xu, Z., “Potential-based obstacle avoidance in formation control,” J. Control Theory Appl. 6 (3), 311–316 (2008).Google Scholar
73. Paul, T., Krogstad, T. R. and Gravdahl, J. T., “Modelling of UAV formation flight using 3D potential field,” Simul. Model. Pract. Theor. 16 (9), 1453–1462 (2008).Google Scholar
74. Yang, Y., Wang, S., Wu, Z. and Wang, Y., “Motion planning for multi-HUG formation in an environment with obstacles,” Ocean Eng. 38 (17), 2262–2269 (2011).Google Scholar
75. Kim, J.-O. and Khosla, P. K., “Real-time obstacle avoidance using harmonic potential functions,” IEEE Trans. Robot. Autom. 8 (3), 338–349 (1992).Google Scholar
76. Masoud, S. et al, “Motion planning in the presence of directional and regional avoidance constraints using nonlinear, anisotropic, harmonic potential fields: A physical metaphor,” IEEE Trans. Syst. Man Cybern., Part A: Syst. Humans 32 (6), 705–723 (2002).Google Scholar
77. Connolly, C. I., Burns, J. B. and Weiss, R., “Path Planning using Laplace's Equation,” Proceedings of the IEEE International Conference on Robotics and Automation, IEEE (1990) pp. 2102–2106.Google Scholar
78. Daily, R. and Bevly, David M, “Harmonic Potential Field Path Planning for High Speed Vehicles,” Proceedings of the American Control Conference, IEEE (2008) pp. 4609–4614.Google Scholar
79. Zheng, C., Ding, M., Zhou, C. and Li, L., “Coevolving and cooperating path planner for multiple unmanned air vehicles,” Eng. Appl. Artif. Intell. 17 (8), 887–896 (2004).Google Scholar
80. Kala, R., “Multi-robot path planning using co-evolutionary genetic programming,” Expert Syst. Appli. 39 (3), 3817–3831 (2012).Google Scholar
81. Qu, H., Xing, K. and Alexander, T., “An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots,” Neurocomputing 120, 509–517 (2013).Google Scholar
82. Kendoul, F., “Survey of advances in guidance, navigation, and control of unmanned rotorcraft systems,” J. Field Robot. 29 (2), 315–378 (2012).Google Scholar
83. Schouwenaars, T., How, J. and Feron, E., “Receding Horizon Path Planning with Implicit Safety Guarantees,” Proceedings of the American Control Conference, volume 6, IEEE (2004) pp. 5576–5581.Google Scholar
84. Yilmaz, N. K., Evangelinos, C., Lermusiaux, P. F. J. and Patrikalakis, N. M., “Path planning of autonomous underwater vehicles for adaptive sampling using mixed integer linear programming,” IEEE J. Ocean. Eng. 33 (4), 522–537 (2008).Google Scholar
85. Bemporad, A. and Rocchi, C., “Decentralized Linear Time-Varying Model Predictive Control of a Formation of Unmanned Aerial Vehicles,” Proceedings ofthe 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), IEEE (2011) pp. 7488–7493.Google Scholar
86. Chen, Y., Yu, J., Su, X. and Luo, G., “Path planning for multi-UAV formation,” J. Intell. Robot. Syst. 77 (1), 229–246 (2015).Google Scholar
87. Nishitani, I., Matsumura, T., Ozawa, M., Yorozu, A. and Takahashi, M., “Human-centered X-Y–T space path planning for mobile robot in dynamic environments,” Robot. Auton. Syst. 66, 18–26 (2015).Google Scholar
88. Dakulović, M. and Petrović, I., “Two-way D star algorithm for path planning and replanning,” Robot. Auton. Syst. 59 (5), 329–342 (2011).Google Scholar
89. Cagigas, D., “Hierarchical D star algorithm with materialization of costs for robot path planning,” Robot. Auton. Syst. 52 (2), 190–208 (2005).Google Scholar
90. Rashid, A. T., Ali, A. A., Frasca, M. and Fortuna, L., “Path planning with obstacle avoidance based on visibility binary tree algorithm,” Robot. Auton. Syst. 61 (12), 1440–1449 (2013).Google Scholar
91. Qureshi, A. H. and Ayaz, Y., “Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments,” Robot. Auton. Syst. 68, 1–11 (2015).Google Scholar
92. Jaillet, L., Cortés, J. and Siméon, T., “Sampling-based path planning on configuration-space costmaps,” IEEE Trans. Robot. 26 (4), 635–646 (2010).Google Scholar
93. Van Den Berg, J., Abbeel, P. and Goldberg, K., “Lqg-mp: Optimized path planning for robots with motion uncertainty and imperfect state information,” Int. J. Robot. Res. 30 (7), 895–913 (2011).CrossRefGoogle Scholar
94. Garrido, S., Malfaz, M. and Blanco, D., “Application of the fast marching method for outdoor motion planning in robotics,” Robot. Auton. Syst. 61 (2), 106–114 (2013).Google Scholar
95. Yao, M. and Zhao, M., “Unmanned aerial vehicle dynamic path planning in an uncertain environment,” Robotica 33 (03), 611–621 (2015).Google Scholar
96. Donald, B., Xavier, P., Canny, J. and Reif, J., “Kinodynamic motion planning,” J. ACM 40 (5), 1048–1066 (1993).Google Scholar
97. LaValle, S. M. and Kuffner, J. J., “Randomized kinodynamic planning,” Int. J. Robot. Res. 20 (5), 378–400 (2001).CrossRefGoogle Scholar
98. Hsu, D., Kindel, R., Latombe, J.-C. and Rock, S., “Randomized kinodynamic motion planning with moving obstacles,” Int. J. Robot. Res. 21 (3), 233–255 (2002).Google Scholar
99. Şahin, E., “Swarm Robotics: From Sources of Inspiration to Domains of Application. In International Workshop on Swarm Robotics (Şahin, E. and Spears, W. M., eds.)(Springer, Springer-Verlag, Berlin, Heidelberg, 2005) pp. 10–20.Google Scholar
100. Barca, J. C. and Sekercioglu, Y. A., “Swarm robotics reviewed,” Robotica 31 (3), 345–359 (2013).Google Scholar