טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentManor Rotem
SubjectGathering and Guidance of Multi-Agent Systems
DepartmentDepartment of Autonomous Systems and Robotics
Supervisor Professor Alfred Bruckstein


Abstract

This work describes results on distributed systems comprising mobile agents that are identical and anonymous, oblivious and interact solely by adjusting their motion according to the relative location of their neighbours. The agents are assumed capable of sensing the presence of other agents within a given sensing range and able to implement rules of motion based on full or partial information on the geometric constellation of their neighbouring agents. Eight different problems that cover assumptions of finite versus infinite sensing range, direction and distance versus direction only sensing and discrete versus continuous motion, are first surveyed in the context of geometric consensus, clustering or gathering tasks.

We consider a group of mobile robotic agents, identical and indistinguishable, having no memory (oblivious) and no common frame of reference (neither absolute location nor a common orientation). Furthermore, these agents are assumed to posses only rudimentary sensing and computational capabilities (limited visibility and basic geometric sorting). We prove that, such robots, implementing a ”Chase the farthest neighbour” policy, perform the task of gathering to a point within a finite time or a finite expected number of time steps. In continuous time, performing such a gathering task is rather straightforward, while in the discrete time, we prove that a randomized semi-synchronized timing model leads to gathering within a finite expected number of time-steps.


Furthermore, we analyze a gathering process for a group of mobile robotic agents, identical and indistinguishable, with no memory and no common frame of reference, assuming these agents have bearing only sensing within a limited visibility range. We prove that such robots can gather to a small disk in the R2-plane within a finite expected number of time-steps, implementing a randomized visibility preserving motion law. In addition, we analyze the dynamics of the cluster of agents after gathering, and show that the agent cluster performs a “random-walk” in the plane.


We suggest a control mechanism for leading a team of such agents (with bearing only sensing within a limited visibility range) in desired directions. Here the agents are assumed to have a compass, i.e. a common North direction, and may receive a direction-control broadcast with some given probability. We prove that, under the suggested control mechanism, the swarm of agents gathers to a small disk in the plane and moves in the desired direction with an expected velocity dependent on the probability of receiving the control signal.