Computing without communicating: ring exploration by asynchronous oblivious robots

DOI10.1007/s00453-011-9611-5zbMath1272.68399OpenAlexW2020796742MaRDI QIDQ2392925

Andrzej Pelc, David Ilcinkas, Nicola Santoro, Paola Flocchini

Publication date: 5 August 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9611-5

zbMATH Keywords

ringmobile robotsasynchronousexplorationoblivious

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Artificial intelligence for robotics (68T40)

Related Items (26)

Formal verification of mobile robot protocols ⋮ Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane ⋮ Search by a metamorphic robotic system in a finite 2D square grid ⋮ Ring exploration with myopic luminous robots ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ Model Checking of Robot Gathering ⋮ Leader Election and Shape Formation with Self-organizing Programmable Matter ⋮ Explore and repair graphs with black holes using mobile entities ⋮ Ring exploration of myopic luminous robots with visibility more than one ⋮ Grid exploration by a swarm of autonomous robots with minimum repetitions ⋮ Optimal exclusive perpetual grid exploration by luminous myopic opaque robots with common chirality ⋮ Perpetual torus exploration by myopic luminous robots ⋮ Gathering of robots on anonymous grids and trees without multiplicity detection ⋮ Perpetual torus exploration by myopic luminous robots ⋮ Gathering Asynchronous and Oblivious Robots on Basic Graph Topologies Under the Look-Compute-Move Model ⋮ Optimal torus exploration by oblivious robots ⋮ Parameterized verification of algorithms for oblivious robots on a ring ⋮ Computing on rings by oblivious robots: a unified approach for different tasks ⋮ A unified approach for gathering and exclusive searching on rings under weak assumptions ⋮ Remembering without memory: tree exploration by asynchronous oblivious robots ⋮ Gathering on rings under the look-compute-move model ⋮ On the self-stabilization of mobile oblivious robots in uniform rings ⋮ Synchronous robots vs asynchronous lights-enhanced robots on graphs ⋮ Universal Systems of Oblivious Mobile Robots ⋮ Election in fully anonymous shared memory systems: tight space bounds and algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal graph exploration without good maps
• 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
• Gathering few fat mobile robots in the plane
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• Piecemeal graph exploration by a mobile robot.
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Theoretical aspects of distributed computing in sensor networks.
• Impossibility of gathering by a set of autonomous mobile robots
• Computing without communicating: ring exploration by asynchronous oblivious robots
• Map construction of unknown graphs by multiple agents
• Gathering asynchronous oblivious mobile robots in a ring
• Network Exploration by Silent and Oblivious Robots
• Tree exploration with logarithmic memory
• Optimal Probabilistic Ring Exploration by Semi-synchronous Oblivious Robots
• Collective tree exploration
• Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
• Optimal Deterministic Ring Exploration with Oblivious Asynchronous Robots
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Exploring an unknown graph
• Tree exploration with little memory
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• Structural Information and Communication Complexity
• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
• Computing by Mobile Robotic Sensors
• Searching for a Black Hole in Synchronous Tree Networks
• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
• Algorithms – ESA 2005

This page was built for publication: Computing without communicating: ring exploration by asynchronous oblivious robots