Anonymous graph exploration with binoculars

DOI10.1007/978-3-662-48653-5_8MaRDI QIDQ1664135zbMATH OpenOpenAlexFDO

Authors J. Chalopin, Emmanuel Godard, Antoine Naudin

Publication date 24 August 2018

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

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We investigate the exploration of networks by a mobile agent. It is long known that, without global information about the graph, it is not possible to make the agent halts after the exploration except if the graph is a tree. We therefore endow the agent with binoculars, a sensing device that can show the local structure of the environment at a constant distance of the agent current location. We show that, with binoculars, it is possible to explore and halt in a large class of non-tree networks. We give a complete characterization of the class of networks that can be explored using binoculars using standard notions of discrete topology. Our characterization is constructive, we present an Exploration algorithm that is universal; this algorithm explores any network explorable with binoculars, and never halts in non-explorable networks.

Recommendations

• Edge exploration of anonymous graph by mobile agent with external help
• Explorable families of graphs
• Deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports
• Deterministic network exploration by anonymous silent agents with local traffic reports
• Efficient exploration of anonymous undirected graphs

Cited in

(4)

• Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane
• Explorable families of graphs
• Verification of agent navigation in partially-known environments
• Memory Efficient Anonymous Graph Exploration

This page was built for publication: Anonymous graph exploration with binoculars

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