Graphs and Networks for the Analysis of Autonomous Agent Systems

Abstract

Autonomous agent systems are systems in which many simple entities, called “agents”, interact with each other. The behaviour resulting from such interactions can be much more complex than that of the individual agents. A group of interacting agents can for example accomplish tasks that no single agent could.\nNature provides several examples of autonomous agent systems, such as flocks of birds and insects, schools of fish, and anthills. Progresses in robotics, electronics and telecommunications make it now also possible to design such systems in order to accomplish particular tasks, such as the surveillance or exploration of areas, or the maintenance of some environments.\nIn this thesis, we analyze two issues related to autonomous agent systems, and more precisely, to the influence of the inter-agent communication network on the system behaviour. In a first part, we consider the problem of preserving the shape of a multi-agent formation by explicitly maintaining the distances between some agents constant. We study the case of distance constraints that are unilateral, that is, constraints for which the responsibility is given to a one of the two agents concerned. This leads to the notions of persistence and constraint consistence. The second part is devoted to the consensus problems: agents have a value which they update by averaging that of other agents. Eventually, all agents may obtain a common value, in which case we say that the system reaches a consensus. One major difficulty in the study of such system is the possible dependence of the interaction and communication topology on the values of the agents. We study two paradigmatic systems in which this dependence can be taken into account, and obtain results on their convergence and on the stability of their equlibria.