Ph.D Thesis

Ph.D StudentElor Yotam
SubjectMathematical Analysis of Emergent Behavior in Multi-
Agent Systems
DepartmentDepartment of Computer Science
Supervisor PROF. Alfred Bruckstein
Full Thesis textFull thesis text - English Version


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 analyze 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.