How many oblivious robots can explore a line

DOI10.1016/j.ipl.2011.07.018zbMath1260.68398MaRDI QIDQ1944194

Andrzej Pelc, Nicola Santoro, David Ilcinkas, Paola Flocchini

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

distributed computing; mobile robots; asynchronous; oblivious; line exploration

Mathematics Subject Classification ID

93C85: Automated systems (robots, etc.) in control theory

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

68T40: Artificial intelligence for robotics

68W15: Distributed algorithms

Related Items

Self-stabilizing robots in highly dynamic environments, 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, Optimal probabilistic ring exploration by semi-synchronous oblivious robots, A unified approach for gathering and exclusive searching on rings under weak assumptions, Search on a line with faulty robots, The ANTS problem, Universal Systems of Oblivious Mobile Robots

Cites Work

• Unnamed Item
• Unnamed Item
• Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
• Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
• Remembering without memory: tree exploration by asynchronous oblivious robots
• Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
• \((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
• Map construction of unknown graphs by multiple agents
• Gathering asynchronous oblivious mobile robots in a ring
• Network Exploration by Silent and Oblivious Robots
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Structural Information and Communication Complexity
• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
• LATIN 2004: Theoretical Informatics