Technical Report PHD-2013-10

Title: Mathematical Analysis of Emergent Behavior in Multi-Agent Systems
Authors: Yotam Elor
Supervisors: Alfred M. Bruckstein
Abstract: Swarm robotics is a new approach to the coordination of a large number of relatively simple mobile robotic agents. The approach takes its inspiration from the system-level functioning of social insects which demonstrate three desired characteristics for multi-robot systems: robustness, flexibility and scalability. By design, a single agent is cheap, simple and has low capabilities, hence, cannot accomplish the task by itself. Therefore, the agents must cooperate to achieve their goals. On the one hand, the tasks are of global nature, hence, requires tight cooperation between all agents. On the other hand, the cheap agents have limited communication abilities. Clearly, achieving large scale cooperation between agents having very limited communication capabilities is challenging. In this work we propose and analyse distributed algorithms for coordinating large groups of agents in order to perform specific tasks. We design (local) agent behaviors and (local) inter-agent interactions and prove that the group indeed presents the desired (global) behavior. Our algorithms are based on the notion that even a simple single agent behavior and simple inter-agent interactions may lead to a complex behavior of the swarm. The process of complex group behaviors resulting from many simple interactions is sometimes called “emergence” and the resulting group's behavior is called “emergent behavior”. In this thesis, we propose distributed algorithms that employ emergent behavior to solve three multi-agent tasks: uniform deployment over a ring, cooperative localization and gradient ascent. In the uniform deployment scenario, the agents populate a ring graph and can freely travel between adjacent nodes. The agent's goal is to distribute evenly over the ring. Localization is the task of estimating the robot's self location in space, and gradient ascent is the problem of controlling a group of robots in order to climb the gradient of a scalar field defined over a d-dimensional space.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2013
To the main CS technical reports page

Computer science department, Technion