An Alignment Strategy for Evolution of Multi-Agent Systems

Formation control of MAS has numerous applications such as air traffic control, formation flight, gaming, transportation engineering, surveillance, terrain mapping, and data mining [1]. Common tools for formation control include leader follower [2‐4], virtual structures [5‐7], artificial potential functions [8,9], behavioral based methods [10,11], and partial differential equation based [12‐15] methods. More recently the authors proposed continuum based techniques [16‐24], for evolution of MAS. In Refs. [16‐19], an approach using homogenous transformation of an MAS under no communication was given. It was extended in Refs. [17‐24 ]t o include homogenous transformation of an MAS under local interagent communication where leaders move independently, with the followers updating their positions based on the positions of several nearby agents. Homogenous transformation of an MAS under local interagent communication has the unique feature that both bulk motion of the MAS and interagent distances can be simultaneously controlled. Most available approaches to formation control that rely on peer-to-peer communication usually require the followers to know the exact absolute or relative positions of adjacent agents. Consequently, sensors with high accuracy may be necessary for obtaining the exact positions of the agents. Moreover, even when accurate measurements are possible there could be communication delays in receiving such position information. If properly designed feedback control strategies are not employed it is likely that robustness against such position uncertainty and communication delays will be lacking. In this paper, we develop an alignment framework for MAS evolution, where every follower agent updates its position based only on its perception of the positions of some local agents, and not their exact positions, thus avoiding having to deal with communication delays and inaccurate measurements. We start by letting the leaders be located at the end points of some finite number of segments, called leading segments, with end points lying on the boundary of a convex domain. The followers are taken to be initially located at the points of intersection of the leading segments. The MAS then evolves from this initial configuration with every follower agent aligning itself with a few chosen adjacent agents to reach the point of intersection of the leading segments, passing through the adjacent agents. We note that the follower agents do not need the exact positions of their adjacent agents to be aligned with them. Although in developing the necessary theory for the alignment technique exact positions of the agents are used, alignment only requires the direction information and not the exact locations. The key idea for this paradigm comes from the hypothesis that natural biological swarms do not perform peer-to-peer communication to sustain their group behavior as a collective. The group evolution is more likely based on what each individual agent perceives of its nearby agents behavior to control its own motion. The paper is organized into six sections: Sec. 1 is the introduction. Section 2 formally presents the initial distribution of the agents followed by the basic alignment strategy in Sec. 3. Section 4 incorporates simple kinematics for agents to develop convergence criteria. Simulations to illustrate the efficacy of the strategy are in Sec. 5 followed by conclusions and future work in Sec. 6.