Static and expanding grid coverage with ant robots: complexity results

DOI10.1016/J.TCS.2011.05.001MaRDI QIDQ638536zbMATH OpenOpenAlexFDO

Authors Yaniv Altshuler, Alfred M. Bruckstein

Publication date 12 September 2011

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

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

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)

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

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

Cites work

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

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)