ARTIGO TÉCNICO José Rodrigues, Dario Figueira, Carlos Neves, Isabel Ribeiro Institute for Systems and Robotics Instituto Superior Técnico (IST) Contact author: José Rodrigues . E-mail: jerasman@gmail.com
LEADER-FOLLOWING GRAPH-BASED DISTRIBUTED FORMATION CONTROL ABSTRACT This paper presents the distributed formation control of a multi-agent system using graph theory with emphasis on consensus and cooperation issues. The focal point is to achieve and maintain a formation from any initial condition, with and without a leader that the entire formation must follow. Our analysis framework is based on tools from algebraic graph theory, matrix theory and control theory. We present a brief derivation of multi-agent consensus in continuous-time and the corresponding iterative form stated in discrete-time, because while the real scenario is continuous, the implementation that we simulate is discrete. Based on the discrete-time algorithm, we propose a solution to obtain and uphold consensus when there is a leader to command the entire network. Simulation results are presented, indicating the capabilities and limitations of the algorithms.
I. INTRODUCTION This paper presents consensus based algorithms for the coordination of a networked multi-agent system that aims at achieving and preserving a formation amongst themselves.
by using graph-theoretic models to describe the local interactions in the formation, where nodes symbolize the physical entities (agents) and the edges represent virtual entities that support the information flow between the nodes.
A. Formation control
B. Graph-based models to control a formation
Networked Systems have lately been the focus of scientific attention due to the boom in computation speed and reliable communications. This provided a solid base for the development of several applications like formation flight control [1], [2], satellite clustering [3], and the control of groups of unmanned vehicles [1], [4], [5].
This paper is mainly based on the notable results that have arisen since 2001. The groundwork on stating and solving consensus problems in networked dynamic systems appeared in [15] and [16], results that were later used in [17] and [18]. The issue of reaching an agreement without computing any objective functions was initially addressed in [19] and later extended in [20], [21]. These main results, which have a well described summary in [22] by Olfati-Saber et al., are the base that supports the development in this work.
Advantages of interconnected multi agent systems over conventional systems include reduced cost, increased efficiency, performance, reconfigurability, robustness, and new capabilities. A team of smaller robots to perform the same task of a larger single robot is at a distinct advantage in case of a malfunction. In one case the team of decentralized units will adapt to the loss of a team member and continue cooperating to accomplish the given task, on the other case the single robot is surely doomed as well as its given mission. Also, a space radar based on satellite clusters [6] is estimated to cost three times less than currently available systems, increase geolocation accuracy by a factor of 500, offer two-orders-of-magnitude smaller propulsion requirement, and be able to track moving targets through formation flight. Undirected Graphs have been often picked to represent formations due to the instinctive way they describe the interconnection topology of a formation, e.g. in [6] and [7]. Moreover, directed graphs have been chosen to reflect the control structure [8], the constraint feasibility [9], the information flow [10], to quantify error propagation [11] and to reflect leader following inter-agents control specifications throughoutly scrutinized [12], [13], [14]. The problem of coordination in multi-agent systems can be characterized naturally by a finite representation of the configuration space, namely
[8]
robótica
The problem of reaching a formation based on graph theory was already solved by Fax and Murray [16]. This theory consists on given an arbitrary initial position make the agents reach a consensus on a final common point. Then, a bias value is introduced, adding the feature that the final positions of the agents will not be a common point but a formation given by a desired geometric topology. This framework, presented in Section II, consists in an introduction to the main problem discussed on this paper that consists on adding a leader to command the network and maintain the formation while performing the leader motion. In the context of this paper, a formation is defined by relative positions between vehicles in a network interconnected by inter-vehicle communications. Multi-vehicle systems are an important category of networked systems due to their commercial and military applications. There are two broad approaches to handle distributed formation control: i) representation of formations as rigid structures [7], [23] and ii) representation of formations using the vectors of relative positions of neighboring vehicles and the use of consensus-based controllers with input bias [22]. In this paper we discuss this latter approach.