Multi-agent Consensus Using Generalized Cyclic Pursuit Strategies

Abstract

One of the main focus of research on multi-agent systems is that of coordination in a group of agents to solve problems that are beyond the capability of a single agent. Each agent in the multi-agent system has limited capacity and/or knowledge which makes coordination a challenging task. Applications of multi-agent systems in space and ocean exploration, military surveillance and rescue missions, require the agents to achieve some consensus in their motion. The consensus has to be achieved and maintained without a centralized controller. Multi-agent system research borrows ideas from the biological world where such motion consensus strategies can be found in the flocking of birds, schooling of fishes, and colony of ants. One such classes of strategies are the cyclic pursuit strategies which mimic the behavior of dogs, birds, ants, or beetles, where one agent pursues another in a cyclic manner, and are commonly referred to as the `bugs' problem, In the literature, cyclic pursuit laws have been applied to a swarm of homogenous agents, where there exists a predefined cyclic connection between agents and each agent follows its predecessor. At equilibrium, the agents reach consensus in relative positions. Equilibrium formation, convergence, rate of convergence, and stability are some of the aspects that have been studied under cyclic pursuit. In this thesis, the notion of cyclic pursuit has been generalized. In cyclic pursuit, usually agents are homogenous in the sense of having identical speeds and controller gains where an agent has an unique predecessor whom it follows. This is defined as the basic cyclic pursuit (BCP) and the sequence of connection among the agents is defined as the Pursuit sequence (PS). We first generalize this system by assuming heterogeneous speed and controller gains. Then, we consider a strategy where an agent can follow a weighted centroid of a group of other agents instead of a single agent. This is called centroidal cyclic pursuit (CCP). In CCP, the set of weights used by the agents are assumed to be the same. We generalize this further by considering the set of weights adopted by each agent to be different. This defines a generalized centroidal cyclic pursuit (GCCP). The behavior of the agents under BCP, CCP and GCCP are studied in this thesis. We show that a group of holonomic agents, under the cyclic pursuit laws ¡ BCP, CCP and GCCP ¡ can be represented as a linear system. The stability of this system is shown to depend on the gains of the agents. A stable system leads to a rendezvous of the agents. The point of rendezvous, also called the reachable point, is a function of the gains. In this thesis, the conditions for stability of the heterogeneous system of agents in cyclic pursuit are obtained. Also, the reachable point is obtained as a function of the controller gains. The reachable set, which is a region in space where rendezvous can occur, given the initial positions of the agents, are determined and a procedure is proposed for calculating the gains of the agents for rendezvous to occur at any desired point within the reachable set. Invariance properties of stability, reachable point and reachable set, with respect to the pursuit sequence and the weights are shown to exist for these linear cyclic pursuit laws. When the linear system is unstable, the agents are shown to exhibit directed motion. We obtain the conditions under which such directed motion is possible. The straight line asymptote to which the agents converge is characterized by the gains and the pursuit sequence of the agents. The straight lines asymptote always passes through a point, called the asymptote point, for given initial positions and gains of the agents. This invariance property of the asymptote point with respect to the pursuit sequence and the weights are proved. For non-homonymic agents, cyclic pursuit strategies give rise to a system of nonlinear state equations. It is shown that the system at equilibrium converges to a rigid polygonal formation that rotates in space. The agents move in concentric circles at equilibrium. The formation at equilibrium and the conditions for equilibrium are obtained for heterogeneous speeds and controller gains. The application of cyclic pursuit strategies to autonomous vehicles requires the satisfaction of some realistic restrictions like maximum speed limits, maximum latex limits, etc. The performances of the strategies with these limitations are discussed. It is also observed that the cyclic pursuit strategies can also be used to model some behavior of biological organisms such as schools of fishes.