Formation control of multiple unmanned vehicles based on graph theory: A Comprehensive Review

Hai Do; Hoa Nguyen; Cuong Nguyen; Mui Nguyen; Minh Nguyen

doi:10.4108/eetmca.v7i3.2416

Authors

Hai Do Thai Nguyen University of Technology, Thai Nguyen, Viet Nam
Hoa Nguyen Thai Nguyen University of Technology, Thai Nguyen, Viet Nam
Cuong Nguyen Thai Nguyen University of Information and Technology, Thai Nguyen, Viet Nam
Mui Nguyen Thai Nguyen University of Technology, Thai Nguyen, Viet Nam
Minh Nguyen Thai Nguyen University of Technology, Thai Nguyen, Viet Nam

DOI:

https://doi.org/10.4108/eetmca.v7i3.2416

Keywords:

Graph theory, Rigid graph theory, Formation control, Multiple unmanned vehicles, Formation stability

Abstract

In recent years, formation control for multiple unmanned vehicles becomes an active research topic that has received a lot of attention from scientists due to its superior advantages compared with other conventional systems. Algebraic graph and graph rigidity theories are the two main mathematical backgrounds of the formation control theory. The graph theory is used to describe the interconnections among vehicles in formation while rigid graph theory - an important subset of graph theory - ensured that the inter-vehicle distance constraints of the desired formation are enforced via the graph rigidity. This paper provides a comprehensive review of graph theory supporting formation control for groups of unmanned aerial vehicles (UAV) or swarm UAVs. The background of the theory and the recent developments of graph-theory-based formation control are reviewed. We provide a cohesive overview of the formation control and coordination of multiple vehicles. Finally, some challenges and future potential directions in formation control are discussed.

Metrics

Metrics Loading ...

References

Hai T. Do, Hoang T. Hua, Minh T. Nguyen, Cuong V. Nguyen, Hoa TT. Nguyen, Hoa T. Nguyen, Nga TT. Nguyen. Formation control algorithms for multiple-UAVs: A comprehensive survey. EAI Endorsed Transactions on Industrial Networks and Intelligent Systems. 2021; 8(27), e3.

Duong TQ, Kim KJ, Kaleem Z, Bui MP, Vo NS. UAV caching in 6G networks: A Survey on models, techniques, and applications. Physical Communication. 2022 Apr 1;51:101532.

Hoa TT. Nguyen, Toan V Quyen, Cuong V Nguyen, Anh M Le, Hoa T Tran, Minh T Nguyen. Control algorithms for UAVs: A comprehensive survey. EAI Endorsed Transactions on Industrial Networks and Intelligent Systems. 2020; 7(23).

Nguyen MT, Boveiri HR. Energy-efficient sensing in robotic networks. Elsevier Measurement. 2020 Jul 1;158:107708.

Barnes, J.E. Military Refines a “Constant Stare against our Enemy”. Los Angeles Times. 2 November 2009; p. 1.

d’Oliveira, F.A., de Melo, F.C.L., Devezas, T.C. High-altitude platforms—Present situation and technology trends. J. Aerosp. Technol. Manag. 2016; 8, 249–262.

Nguyen MT, Teague KA. Compressive and cooperative sensing in distributed mobile sensor networks. In MILCOM 2015 IEEE Military Communications Conference, 2015 Oct 26 (pp. 1033-1038). IEEE.

Silvagni, M., Tonoli, A., Zenerino, E., Chiaberge, M. Multipurpose UAV for search and rescue operations in mountain avalanche events. Geomat. Nat. Hazards Risk. 2017; 8, 18–33.

Niethammer, U., James, M., Rothmund, S., Travelletti, J., Joswig, M. UAV based remote sensing of the Super-Sauze landslide: Evaluation and results. Eng. Geol. 2012; 128, 2–11.

Nguyen MT, Truong LH, Le TT. Video surveillance processing algorithms utilizing artificial intelligent (AI) for unmanned autonomous vehicles (UAVs). MethodsX. 2021 Jan 1;8:101472.

Honkavaara, E., Saari, H., Kaivosoja, J., Pölönen, I., Hakala, T., Litkey, P., Mäkynen, J., Pesonen, L. Processing and assessment of spectrometric, stereoscopic imagery collected using a lightweight UAV spectral camera for precision agriculture. Remote Sens. 2013; 5, 5006–5039.

Hugenholtz, C.H., Whitehead, K., Brown, O.W., Barchyn, T.E., Moorman, B.J., LeClair, A., Riddell, K., Hamilton, T. Geomorphological mapping with a small unmanned aircraft system (sUAS): Feature detection and accuracy assessment of a photogrammetrically-derived digital terrain model. Geomorphology. 2013; 194, 16–24.

Nguyen MT, Tran HT, Nguyen CV, Ala G, Viola F, Colak I. A Novel Framework of Hybrid Harvesting Mechanisms for Remote Sensing Devices. In2022 IEEE 21st Mediterranean Electrotechnical Conference (MELECON) 2022 Jun 14 (pp. 1007-1012). IEEE.

Gheisari, M., Irizarry, J., Walker, B.N. UAS4SAFETY: The potential of unmanned aerial systems for construction safety applications. In Proceedings of the Construction Research Congress 2014: Construction in a Global Network, Atlanta, GA, USA, 19–21. May 2014; pp. 1801–1810.

Sankarasrinivasan, S., Balasubramanian, E., Karthik, K., Chandrasekar, U., Gupta, R. Health monitoring of civil structures with integrated UAV and image processing system. Procedia Comput. Sci. 2015; 54, 508–515.

Pham AQ, La HM, La KT, Nguyen MT. A magnetic wheeled robot for steel bridge inspection. In International Conference on Engineering Research and Applications 2019 Dec 1 (pp. 11-17). Springer, Cham.

Bretschneider, T.R., Shetti, K. UAV based gas pipeline leak detection. In Proceedings of the ARCS 2015, Porto, Portugal. 24–27 March 2015.

Muchiri, N., Kimathi, S. A review of applications and potential applications of UAV. In Proceedings of the 2016 Sustainable Research and Innovation Conference, Nairobi, Kenya. 4–6 May 2016; pp. 280–283.

Mathur, P., Nielsen, R.H., Prasad, N.R., Prasad, R. Data collection using miniature aerial vehicles in wireless sensor networks. IET Wirel. Sens. Syst. 2016; 6, 17–25.

Khanal, S., Fulton, J., Shearer, S. An overview of current and potential applications of thermal remote sensing in precision agriculture. Comput. Electron. Agric. 2017; 139, 22–32.

Howell, C.T., III, Jones, F., Thorson, T., Grube, R., Mellanson, C., Joyce, L., Coggin, J., Kennedy, J. The First Government Sanctioned Delivery of Medical Supplies by Remotely Controlled Unmanned Aerial System (UAS). In Proceedings of the Xponential 2016, New Orleans, LA, USA. 2–5 May 2016.

Do HT, Truong LH, Nguyen MT, Chien CF, Tran HT, Hua HT, Nguyen CV, Nguyen HT, Nguyen NT. Energy-Efficient Unmanned Aerial Vehicle (UAV) Surveillance Utilizing Artificial Intelligence (AI). Wireless Communications and Mobile Computing. 2021 Oct 13;2021.

Wang, Xiangke, Zhiwen Zeng, and Yirui Cong. Multi-agent distributed coordination control: Developments and directions via graph viewpoint. Neurocomputing 199. 2016; 204-218.

T. Balch and R. C. Arkin. Behavior-based formation control for multirobot teams. IEEE transactions on robotics and automation. 1998; vol. 14, no. 6, pp. 926–939.

Michaud, François, and Monica Nicolescu. Behavior-based systems. Springer handbook of UAVsics. Springer, Cham. 2016; pp.307-328.

Lee, Giroung, and Dongkyoung Chwa. Decentralized behavior-based formation control of multiple UAV considering obstacle avoidance. Intelligent Service UAVsics. 2018; 11(1), pp. 127-138.

S. Kim and Y. Kim. Three dimensional optimum controller for multiple UAV formation flight using behaviorbased decentralized approach. in 2007 International Conference on Control, Automation and Systems, pp. 2007; 1387– 1392, IEEE.

V. Roldão, R. Cunha, D. Cabecinhas, C. Silvestre, and P. Oliveira. A leader-following trajectory generator with application to quadrotor formation flight. Robotics and Autonomous Systems. 2014; vol. 62, no. 10, pp. 1597–1609.

N. Sorensen and W. Ren. A unified formation control scheme with a single or multiple leaders. in 2007 American Control Conference. 2007; pp. 5412–5418, IEEE

R. Olfati-Saber. Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions on automatic control. 2006; vol. 51, no. 3, pp. 401–420.

N. Sorensen and W. Ren. A unified formation control scheme with a single or multiple leaders. 2007 American Control Conference. 2007; pp. 5412–5418, IEEE.

Nguyen MT, La HM, Teague KA. Collaborative and compressed mobile sensing for data collection in distributed robotic networks. IEEE Transactions on Control of Network Systems. 2017 Sep 19;5(4):1729-40.

A. Askari, M. Mortazavi, and H. Talebi. UAV formation control via the virtual structure approach. Journal of Aerospace Engineering. 2015; vol. 28, no. 1, p. 04014047.

C. K. Peterson and J. Barton.Virtual structure formations of cooperating UAVs using wind-compensation command generation and generalized velocity obstacles. in 2015 IEEE Aerospace Conference. 2015; pp. 1–7, IEEE.

D. Zhou, Z. Wang, and M. Schwager. Agile coordination and assistive collision avoidance for quadrotor swarms using virtual structures. IEEE Transactions on UAVsics. , 2018; vol. 34, no. 4, pp. 916–923.

B. D. O. Anderson, C. Yu, B. Fidan, J. M. Hendrickx, Rigid graph control architecture for autonomous formation, IEEE Control System Magazine. 2008; 28 (6), 48–63.

Falconi, R., Sabattini, L., Secchi, C., Fantuzzi, C., & Melchiorri, C. A graphbased collisionfree distributed formation control strategy. IFAC Proceedings Volumes. 2011; 44(1), 6011–6016.

Fax, J. A., & Murray, R. M. Information flow and cooperative control of vehicle formations. IEEE Transactions on Automatic Control. 2004; 49(9), 1465–1476.

Y. Zhao, L. Jiao, R. Zhou, and J. Zhang, UAV formation control with obstacle avoidance using improved artificial potential fields. in 2017 36th Chinese Control Conference (CCC). 2017; pp. 6219–6224, IEEE.

Minh T. Nguyen, Truong LH, Tran TT, Chien CF. Artificial intelligence based data processing algorithm for video surveillance to empower industry 3.5. Computers & Industrial Engineering. 2020 Oct 1;148:106671.

Y. Chen, J. Yu, X. Su, and G. Luo, Path planning for multi-UAV formation,” Journal of Intelligent & Robotic Systems. 2015; vol. 77, no. 1, pp. 229–246.

Y.-B. Chen, G.-C. Luo, Y.-S. Mei, J.-Q. Yu, and X.-L. Su, UAV path planning using artificial potential field method updated by optimal control theory, Int. J. Syst. Sci.. 2016; vol. 47, no. 6, pp. 1407–1420.

Tran HT, Tran DL, Nguyen VQ, Do HT, Nguyen MT. A Novel Framework of Modelling, Control, and Simulation for Autonomous Quadrotor UAVs Utilizing Arduino Mega. Wireless Communications and Mobile Computing. 2022 Aug 19;2022.

Chu, X., Peng, Z., Wen, G., & Rahmani, A. Decentralised consensus-based formation tracking of multiple differential drive robots. International Journal of Control. 2017;90, 2461–2470.

Wen, G., Zhang, H.-T., Yu, W., Zuo, Z., & Zhao, Y. Coordination tracking of multi-agent dynamical systems with general linear node dynamics. International Journal of Robust and Nonlinear Control. 2017; 27(9), 1526–1546.

Shoja, S., Baradarannia, M., Hashemzadeh, F., Badamchizadeh, M., & Bagheri, P. Surrounding control of nonlinear multi-agent systems with non-identical agents. ISA Transactions. 2017; 70, 219–227.

Soni, A., & Hu, H. Formation control for a fleet of autonomous ground vehicles: A survey. Robotics. 2018; 7(4), 67.

Dong, W., & Guo, Y. (2007). Formation control of nonholonomic mobile robots using graph theoretical methods. In Cooperative Systems (pp. 369-386). Springer, Berlin, Heidelberg.

J. A. Fax and R. M. Murray, Information flow and cooperative control of vehicle formations, in IEEE Transactions on Automatic Control. Sept. 2004; vol. 49, no. 9, pp. 1465-1476. doi: 10.1109/TAC.2004.834433.

Pirani, M., & Sundaram, S. Spectral properties of the grounded Laplacian matrix with applications to consensus in the presence of stubborn agents. In 2014 American Control Conference. 2014, June; (pp. 2160-2165). IEEE.

Lin, Zhiyun; Francis, Bruce; Maggiore, Manfredi. Necessary and sufficient graphical conditions for formation control of unicycles. IEEE Transactions on automatic control, 2005, 50.1: 121-127.

Zelazo, Daniel. Graph-theoretic methods for the analysis and synthesis of networked dynamic systems. University of Washington. 2009.

Jin, Z., & Murray, R. M. Double-graph control strategy of multi-vehicle formations. In IEEE conference on decision and control (cdc). 2004); 2 pp. 1988–1994, doi:10.1109/CDC.2004.1430340.

Ren, W., & Beard, R. W. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Transactions on Automatic Control. 2005; 50(5), 655–661.

Dong, W., & Guo, Y. Formation control of nonholonomic mobile robots using graph theoretical methods. In D. Grundel, R. Murphey, P. Pardalos, & O. Prokopyev (Eds.), Cooperative systems control and optimization. 2007; 588 (pp. 369–386). Springer Berlin Heidelberg.

Pereira, G. A. S., Kumar, V., & Campos, M. F. M. Closed loop motion planning of cooperating mobile robots using graph connectivity. Robotics and Autonomous

Systems. 2008; 56(4), 373–384.

Falconi, R., Sabattini, L., Secchi, C., Fantuzzi, C., & Melchiorri, C. A graphbased collisionfree distributed formation control strategy. IFAC Proceedings Volumes, 2011; 44(1), 6011–6016.

Li, D., Ge, S. S., He, W., Ma, G., & Xie, L. (2019). Multilayer formation control of multi-agent systems. Automatica, 2019; 109.

Hendrickx, J. M., Anderson, B. D., Delvenne, J. C., & Blondel, V. D. Directed graphs for the analysis of rigidity and persistence in autonomous agent systems. International Journal of Robust and Nonlinear Control: IFAC‐Affiliated Journal.2007; 17(10‐11), 960-981.

B.D.O. Anderson, C. Yu, B. Fidan, and J.M. Hendrickx, Rigid graph control architectures for autonomous formations, IEEE Contr. Syst. Mag. 2008; vol. 28, no. 6, pp. 48–63.

De Queiroz, Marcio, Xiaoyu Cai, and Matthew Feemster. Formation control of multi-agent systems: a graph rigidity approach. John Wiley & Sons, 2019.

S. Zhao, D. Zelazo, Bearing rigidity and almost global bearing-only formation stabilization, arXiv preprint arXiv:1408.6552.

S. Mou, A. Morse, B. Anderson, Toward robust control of minimally rigid undirected formations, in: Decision and Control (CDC). IEEE 53rd Annual Conference on, IEEE. 2014; pp. 643–647

Z. Sun, S. Mou, B. D. Anderson, A. Morse, Formation movements in minimally rigid formation control with mismatched mutual distances, in: Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on, IEEE, 2014; pp. 6161–6166.

J. Graver, B. Servatius, H. Servatius, Combinatorial Rigidity (Gradu-ate Studies in Mathematics), American Mathematical Society, New York, USA, 1994.

G. Laman, On graphs and rigidity of plane skeletal structures, Journal of Engineering Mathematical 4 (4).1970; 331–340.

R. Olfati-Saber, R. M. Murray, Graph rigidity and distributed formation stabilization of multi-vehicle systems, in: Proceedings of the IEEE Inter- national Conference on Decision and Control, Las Vegas, Nevada, USA. 2002; pp. 2965–2971.

T. Eren, B. Anderson, A.Morse, W. Whiteley, P.Belhumeur, Operations on formations of autonomous agents, Communications in Information and Systems 3 (4). 2004; 223–258.

D. Zelazo, A. Franchi, H. H. B¨ulthoff, P. R. Giordano, Decentralized rigidity maintenance control with range measurements for multi-robot systems, The International Journal of Robotics Research 34 (1). 2015; 105 – 128.

Eren, T., Whiteley, W., Anderson, B. D. O., Morse, A. S., & Belhumeur, P. N. Information structures to secure control of rigid formations with leader–follower architecture. In Proceedings of the 2005 American control conference. 2005; (pp. 2966–2971).

Mou, S., Morse, A. S., Belabbas, M. A., Sun, Z., Anderson, B. D. O. Undirected rigid formations are problematic. Automatic Control, IEEE Transactions on, in press.2016.

Sun, Z., Anderson, B. D., Deghat, M., & Ahn, H. S. Rigid formation control of double-integrator systems. International Journal of Control, 2017; 90(7), 1403-1419.

Yang Quan Chen and Zhongmin Wang. Formation control: a review and a new consideration. 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2005, pp. 3181-3186, doi: 10.1109/IROS.2005.1545539.

Shinji Harat, Tomohisa Hayakawa and Hikaru Sugatat. Stability Analysis of Linear Systems with Generalized Frequency Variables and Its Applications to Formation Control. 2007 46th IEEE Conference on Decision and Control, 2007; pp. 1459-1466, doi: 10.1109/CDC.2007.4435000

G. Lafferriere, J. Caughman and A. Williams. Graph theoretic methods in the stability of vehicle formations. Proceedings of the 2004 American Control Conference, 2004; pp. 3729-3734 vol.4, doi: 10.23919/ACC.2004.1384492.

D. V. Dimarogonas and K. H. Johansson. On the stability of distance-based formation control. 2008 47th IEEE Conference on Decision and Control, 2008; pp. 1200-1205, doi: 10.1109/CDC.2008.4739215.

Dimarogonas, Dimos V., and Karl H. Johansson. Stability analysis for multi-agent systems using the incidence matrix: Quantized communication and formation control. Automatica 46.4. 2010; 695-700.

Y. -H. Chang, C. -W. Chang, C. -L. Chen and C. -W. Tao. Fuzzy Sliding-Mode Formation Control for Multirobot Systems: Design and Implementation. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), April 2012, vol. 42, no. 2, pp. 444-457,doi: 10.1109/TSMCB.2011.2167679.

L. Moreau, Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control. Feb. 2005; vol. 50, no. 2, pp. 169-182, doi: 10.1109/TAC.2004.841888.

J. A. Fax, R. M. Murray, Information flow and cooperative control of vehicle formations. IEEE Transactions on Automatic Control. 2004; 49 (9), 1465–1476.

H. G. Tanner, G. J. Pappas and V. Kumar. Leader-to-formation stability. in IEEE Transactions on Robotics and Automation. June 2004; vol. 20, no. 3, pp. 443-455.

Z. Lin, M. Broucke, B. Francis, Local control strategies for groups of mobile autonomous agents. IEEE Transactions on Automatic Control. 2004; 49 (4), 622–629.

Wen, G., Zhang, H.-T., Yu, W., Zuo, Z., & Zhao, Y. Coordination tracking ofmulti-agent dynamical systems with general linear node dynamics. International Journal of Robust and Nonlinear Control. 2017; 27(9), 1526–1546.