Remembering without memory: tree exploration by asynchronous oblivious robots

DOI10.1016/j.tcs.2010.01.007zbMath1191.68712OpenAlexW3023452807MaRDI QIDQ962164

Paola Flocchini, Nicola Santoro, David Ilcinkas, Andrzej Pelc

Publication date: 6 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.01.007

zbMATH Keywords

treeasynchronousmobile agentexplorationrobotoblivious

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Agent technology and artificial intelligence (68T42)

Related Items (26)

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane ⋮ Ring exploration with myopic luminous robots ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ The ANTS problem ⋮ Optimal probabilistic ring exploration by semi-synchronous oblivious robots ⋮ 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 ⋮ How many oblivious robots can explore a line ⋮ Optimal torus exploration by oblivious robots ⋮ Computing on rings by oblivious robots: a unified approach for different tasks ⋮ LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS ⋮ A unified approach for gathering and exclusive searching on rings under weak assumptions ⋮ Gathering on rings under the look-compute-move model ⋮ Of robot ants and elephants: a computational comparison ⋮ Network Exploration by Silent and Oblivious Robots ⋮ Self-stabilizing robots in highly dynamic environments ⋮ Synchronous robots vs asynchronous lights-enhanced robots on graphs ⋮ Exploration of High-Dimensional Grids by Finite Automata ⋮ Universal Systems of Oblivious Mobile Robots ⋮ Anonymous meeting in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gathering of asynchronous robots with limited visibility
• Optimal graph exploration without good maps
• Local spreading algorithms for autonomous robot systems
• Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
• \((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
• Impossibility of gathering by a set of autonomous mobile robots
• Computing without communicating: ring exploration by asynchronous oblivious robots
• Gathering asynchronous oblivious mobile robots in a ring
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• Exploring an unknown graph
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
• Algorithms – ESA 2005
• LATIN 2004: Theoretical Informatics
• LATIN 2004: Theoretical Informatics

This page was built for publication: Remembering without memory: tree exploration by asynchronous oblivious robots