Technical Report PHD-2017-12

Title: Gathering and Guidance of Multi-Agent Systems
Authors: Rotem Manor
Supervisors: Alfred M. Bruckstein
PDFCurrently accessibly only within the Technion network
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 neighbors. 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 neighboring 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 neighbor” policy, preform the task of gathering to a point within a finite time or a finite expected number of time steps. In continuous time, preforming 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 R 2 -plane within a finite expected number of time-steps, implementing a randomized visibility preserving motion law. In addition, we analyse 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.

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 2017
To the main CS technical reports page

Computer science department, Technion