Technical Report CIS-2009-01

TR#:CIS-2009-01
Class:CIS
Title: Multi-A(ge)nt Graph Patrolling and Partitioning.
Authors: Yotam Elor and Alfred M. Bruckstein.
PDFCIS-2009-01.pdf
Abstract: Abstract We introduce a novel multi agent patrolling algorithm inspired by the behavior of gas filled balloons. Very low capability ant-like agents are considered with the task of patrolling an area modeled as a graph. While executing the proposed algorithm, the agents dynamically partition the graph between them using simple local interactions, every agent assuming the responsibility for patrolling his subgraph. Balanced graph partition is an emergent behavior due to the local interactions between the agents in the swarm. Extensive simulations on various graphs (environments) showed that the average time to reach a balanced partition is linear with the graph size. The simulations yielded a convincing argument for conjecturing that if the graph being patrolled contains a balanced partition, the agents will find it. However, we could not prove this. Nevertheless, we can prove that if a balanced partition is reached, the maximum time lag between two successive visits to any vertex using the proposed strategy is at most twice the optimal so the patrol quality is at least half the optimal.
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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2009/CIS/CIS-2009-01), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 2009
To the main CS technical reports page

Computer science department, Technion
admin