How many oblivious robots can explore a line

DOI10.1016/J.IPL.2011.07.018MaRDI QIDQ1944194zbMATH OpenOpenAlexFDO

Authors P. Flocchini, David Ilcinkas, Andrzej Pelc, N. Santoro

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.07.018

zbMATH Keywords

asynchronousdistributed computingline explorationmobile robotsoblivious

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Artificial intelligence for robotics (68T40) Distributed algorithms (68W15) Automated systems (robots, etc.) in control theory (93C85)

Recommendations

• Network exploration by silent and oblivious robots
• Computing without communicating: ring exploration by asynchronous oblivious robots
• Remembering without memory: tree exploration by asynchronous oblivious robots
• Optimal torus exploration by oblivious robots
• Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots

Cites work

• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
• Gathering asynchronous oblivious mobile robots in a ring
• scientific article; zbMATH DE number 2038783 (Why is no real title available?)
• scientific article; zbMATH DE number 1775412 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Map construction of unknown graphs by multiple agents
• Network exploration by silent and oblivious robots
• Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
• Remembering without memory: tree exploration by asynchronous oblivious robots
• Structural Information and Communication Complexity
• Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring

Cited in

(12)

• Search on a line with faulty robots
• The ANTS problem
• Universal systems of oblivious mobile robots
• Network exploration by silent and oblivious robots
• Optimal probabilistic ring exploration by semi-synchronous oblivious robots
• Exploring graphs with time constraints by unreliable collections of mobile robots
• A unified approach for gathering and exclusive searching on rings under weak assumptions
• Optimal exclusive perpetual grid exploration by luminous myopic opaque robots with common chirality
• Perpetual torus exploration by myopic luminous robots
• Perpetual torus exploration by myopic luminous robots
• Infinite grid exploration with synchronous myopic robots without chirality
• Optimal asynchronous perpetual finite grid exploration

This page was built for publication: How many oblivious robots can explore a line

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