Static and expanding grid coverage with ant robots: complexity results

DOI10.1016/J.TCS.2011.05.001zbMATH Open1221.68245arXiv1011.5914OpenAlexW2069083556MaRDI QIDQ638536FDOQ638536

Authors: Yaniv Altshuler, Alfred M. Bruckstein 

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: In this paper we study the strengths and limitations of collaborative teams of simple agents. In particular, we discuss the efficient use of "ant robots" for covering a connected region on the Z^{2} grid, whose area is unknown in advance, and which expands at a given rate, where $n$ is the initial size of the connected region. We show that regardless of the algorithm used, and the robots' hardware and software specifications, the minimal number of robots required in order for such coverage to be possible is Omega({sqrt{n}}). In addition, we show that when the region expands at a sufficiently slow rate, a team of Theta(sqrt{n}) robots could cover it in at most O(n^{2} ln n) time. This completion time can even be achieved by myopic robots, with no ability to directly communicate with each other, and where each robot is equipped with a memory of size O(1) bits w.r.t the size of the region (therefore, the robots cannot maintain maps of the terrain, nor plan complete paths). Regarding the coverage of non-expanding regions in the grid, we improve the current best known result of O(n^{2}) by demonstrating an algorithm that guarantees such a coverage with completion time of O(frac{1}{k} n^{1.5} + n) in the worst case, and faster for shapes of perimeter length which is shorter than O(n).

Full work available at URL: https://arxiv.org/abs/1011.5914

Recommendations

• Competitive on-line coverage of grid environments by a mobile robot
• Spanning-tree based coverage of continuous areas by a mobile robot
• Filling arbitrary connected areas by silent robots with minimum visibility range
• Exploring and triangulating a region by a swarm of robots
• Uniform Dispersal of Robots with Minimum Visibility Range

zbMATH Keywords

grid searchdecentralized systemscollaborative cleaningcollaborative searchexpanding domains

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Artificial intelligence for robotics (68T40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Real-time heuristic search
• Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomized Pursuit-Evasion with Local Visibility
• The complexity of pursuit on a graph
• On the cover time of planar graphs
• Trading Space for Time in Undirected s-t Connectivity
• Efficiently searching a graph by a smell-oriented vertex process
• From ants to a(ge)nts: a special issue on ant-robotics
• Complete distributed coverage of rectilinear environments
• Coordination in multi-agent RoboCup teams
• Distributed Algorithms for Partitioning a Swarm of Autonomous Mobile Robots
• Lion and Man: The General Case

Cited In (5)

• Markov chain analysis of self-organizing mobile nodes self-organizing mobile nodes
• Ant-sweep, a decentral strategy for cooperative cleaning in expanding domains
• A local strategy for cleaning expanding cellular domains by simple robots
• Position discovery for a system of bouncing robots
• TTLed random walks for collaborative monitoring in mobile and social networks

This page was built for publication: Static and expanding grid coverage with ant robots: complexity results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638536)