**Decentralized Formation Control of Multi-agent Robot Systems based on Formation Graphs**

**Eduardo G. Hernandez-Martinez**

*Universidad Iberoamericana*

01219 México D.F., MEXICO

**Eduardo Aranda-Bricaire**

*CINVESTAV-IPN, AP 14-740*

7000 Mexico DF, MEXICO

**Abstract**:

Formation control is an important issue of motion coordination of Multi-agent Robots Systems. The goal is to coordinate a group of agents to achieve a desired formation pattern. The control strategies are decentralized because every robot does not possess information about the positions and goals of all the other robots. Based on the formation graphs properties and the local potential functions approach, we obtain a formal result about global convergence to the desired pattern for any formation graph. Also, we characterize the topologies of the formation graphs where the centroid of positions remains stationary. Finally, the control approach is extended to the case of unicycle-type robots.

**Keywords**:

Mobile robots, Decentralized control, Formation control, Graph theory, Unicycles.

**CITE THIS PAPER AS**: Eduardo G. HERNANDEZ-MARTINEZ, Eduardo ARANDA-BRICAIRE, **Decentralized Formation Control of Multi-agent Robot Systems based on Formation Graphs**, *Studies in Informatics and Control*, ISSN 1220-1766, vol. 21 (1), pp. 7-16, 2012.

**1. Introduction**

The term Multi-agent robots systems (MARS) means groups of autonomous robots coordinated to achieve cooperative tasks. Formation control is an important issue of motion coordination of MARS, specifically applied to groups of mobile wheeled robots. Applications include toxic residues cleaning,transportation and manipulation of large objects, exploration, searching and rescue tasks and simulation of biological entities behaviors [1]. The goal is to guarantee the convergence of the agents or robots to a particular formation pattern. The problem is complex because it is assumed that every robot does not possess global information. Therefore, the control strategies are decentralized and the main intention is to achieve desired global behaviors through local interactions [2].

Some advantages of decentralized approaches are greater autonomy for the robots, less computational load in control implementations and its applicability to large scale groups [3]. Decentralized formation control strategies includes behavior-based [4], [5], [6] swarms stability [7], virtual structures [3] and Local Potential Functions (LPF) [8], [9]. The LPF method consists of applying the negative gradient of a potential function as control inputs of agents. The LPF’s are designed according to the desired inter-agent distances and steer all agents to the desired formation. Formation Graphs (FG), are an important tool to guarantee convergence to the desired pattern [10],[11], [12]. The application of different FG’s to the same group of robots produces different dynamic behaviors of the group in the closed-loop system. For example, [13] analyze the convergence of the complete FG, where every robot measures the position of the rest of the group. The cyclic pursuit FG is studied in [2] where every robot pursues the next robot and the last robot pursues the first one making a closed-chain configuration. A FG with bidirectional communication in the cyclic pursuit is analyzed in [14]. An analysis of convergence of all undirected FG’s is presented in [10] where the communication between pair of robots is bidirectional. The convergence of some leader-followers schemes is analyzed in [15] for the case of the FG centered on a virtual leader and [16] for the open-chain or convoy configuration. Another approaches of leader-followers schemes are found in [8], [17], [18]. Although the LPF and FG approaches are used commonly in the literature, there does not exist a general result about the convergence of the closed-loop system using an arbitrary formation graph. Inspired in [2], we analyze the convergence to the desired formation for any FG based on the Laplacian matrix of the FG and the Gershgorin circles Theorem [19]. Also, we analyze the conditions of the FG such that the centroid of positions remains constant for all time. To the best of our knowledge, the unique similar result is exposed in [2] for the cyclic pursuit FG only. The results originally were presented in [20] and selected for publication in this journal.

The paper is organized as follows. Section 2 introduces the problem statement and defines the notion of FG. Section 3 describes the formation control strategy based on LPF for the case of point-robots and the main result about the convergence to the desired formation. The analysis of the centroid of positions is given in Section 4. The approach is extended to the case of unicycle-type robots in Section 5, together with some numerical simulations. Finally, concluding remarks are offered in Section 6.

**References**:

- ARAI, T., E. PAGELLO, L. E. PARKER,
**Guest Editorial Advances in Multirobot Systems**, IEEE Transactions on Robotics and Automation, vol. 18(5), 2002, pp. 655-661. - LIN, Z., M. BROUCKE, B. FRANCIS,
**Local Control Strategies for Groups of Mobile Autonomous Agents**, IEEE Transactions on Automatic Control, vol. 49(4), 2004, pp. 622-629. - DO, K.,
**Formation Tracking Control of Unicycle-type Mobile Robots**, IEEE International Conference on Robotics and Automation, 2007, pp. 2391-2396. - BALCH, T., R. ARKIN,
**Behaviour-based Formation Control for Multirobot Teams**, IEEE Transactions on Robotics and Automation, vol. 14(3), 1998, pp. 926-939. - FREDSLUND, J., M. MATARIC,
**General Algorithm for Robot Formations using Local Sensing and Minimal Communication**, IEEE Transactions on Robotics and Automation, vol. 18(5), 2002, pp. 837-846. - SUSNEA I., G. VASILIU, A. FILIPESCU, A. RADASCHIN,
**Virtual Pheromones for Real-Time Control of Autonomous Mobile Robots,**Studies in Informatics and Control, vol. 18(3), 2009, pp. 233-240. - SPEARS, W., D. SPEARS, J. HAMANN, R. HEIL,
**Physics-based Control of Swarms of Vehicles**, Autonomous Robots, vol. 17, 2004, pp. 137-162. - LEONARD, N., E. FIORELLI,
**Virtual Leaders, Artificial Potentials and Coordinated Control of Groups**, IEEE Conference on Decision and Control, 2001, pp. 2968-2973. - YAMAGUCHI, H.,
**A Distributed Motion Coordination Strategy for Multiple Nonholonomic Mobile Robots in Cooperative Hunting Operations**, Robotics and Autonomous Systems, vol. 43, 2003, pp. 257-282. - DIMAROGONAS, D., K. KYRIAKOPOULOS,
**Distributed Cooperative Control and Collision Avoidance for**, IEEE Conference on Decision and Control, 2006, pp. 721-726. - DESAI, J.,
**A Graph Theoretic Approach for Modelling Mobile Robot Team Formations**, Journal of Robotic Systems, vol. 19(11), 2002, pp. 511-525. - MUHAMMAD, A., M. EGERSTEDT,
**Connectivity Graphs as Models of Local Interactions**, IEEE Conference on Decision and Control, 2004, pp. 124-129. - DO, K.,
**Formation Control of Mobile Agents using Local Potential Functions**, American Control Conference, 2006, pp. 2148-2153. - HERNANDEZ-MARTINEZ, E., E. ARANDA-BRICAIRE,
**Non-collision Conditions in Multi-agent Robots Formation using Local Potential Functions**, IEEE International Conference on Robotics and Automation, 2008, pp. 3776-3781. - HERNANDEZ-MARTINEZ, E., E. ARANDA-BRICAIRE,
**Non-collision Conditions in Formation Control using a Virtual Leader Strategy**, XIII CLCA and VI CAC, 2008, pp. 798-803. - HERNANDEZ-MARTINEZ, E., E. ARANDA-BRICAIRE,
**Marching Control of Unicycles based on the Leader-followers Scheme**, 35th Annual Conference of the IEEE Industrial Electronics Society (IECON), 2009, pp. 2285-2290. - DESAI, J., J. OSTROWSKI, KUMAR, V.,
**Modelling and Control of Formations of Nonholonomic Mobile Robots**, IEEE Transactions on Robotics and Automation, vol. 6(17), 2001, pp. 905-908. - TANNER, H., V. KUMAR, G. PAPPAS,
**Leader-to-formation Stability**, IEEE Transactions on Robotics and Automation, vol. 20(3), 2004, pp. 443-455. - BELL, H.,
**Gerschgorin’s Theorem and the Zeros of Polynomials**, American Mathematics, vol. 1(3), 1972, pp. 292-295. - HERNANDEZ-MARTINEZ, E., E. ARANDA-BRICAIRE,
**Decentralized Formation Control of Multi-agent Robots Systems based on Formation Graphs**, XIV CLCA and XIX ACCA, 2010. - BROCKETT, R., R. MILLMAN, H. J. SUSSMANN,
**Asymptotic Stability and Feedback Stabilization**, Birkhäuser, Massachusetts, 1983.