Agents safely explore networks with hidden dangers and changing links
Safe Exploration of Arbitrary Dynamic Dangerous Networks
Distributed, Parallel, and Cluster Computing
Summary
Sometimes teams of agents need to visit all parts of a network that changes over time, but some areas are dangerous traps. The paper studies how agents can explore every safe spot without any one of them getting stuck forever. The authors show that teams of agents, even without knowing the network, can keep exploring safely or finish exploring if they have unique IDs and remember what they find. They also prove it’s impossible to perfectly mark the entrances leading to danger.
What this means in practice
- •For network administrators: Design network monitoring strategies that safely explore dynamic systems with unseen harmful nodes without risking all monitoring agents.
- •For robotics operators: Plan multi-robot missions that explore changing environments with unknown traps while ensuring some robots survive to complete the task.
Authors
Caterina Feletti, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro
Abstract
Given a team of agents on the nodes of a graph-based network, the exploration problem requires each node to be visited by at least one agent. In the classical distributed setting of static networks, agents do not know the topology of the network; in the more recently investigated setting of dynamic networks, they may have prior knowledge about the graph class (e.g., trees, tori, rings) or other parameters (e.g., number of nodes). Gotoh et al. (2021) are the first to study the exploration problem of arbitrary dynamic networks, under the necessary minimal assumption that any two nodes will be connected by a temporal path infinitely often (temporal connectivity assumption). In this paper, we extend their study of exploration under temporal connectivity by considering dangerous dynamic networks, i.e., containing possibly one or more black holes. Whenever an agent enters a black hole, it will be trapped forever. The safe exploration problem requires a team to explore all the safe nodes, ensuring that at least one agent will never be trapped in a black hole. We first prove that, given the necessary (and sufficient) number of agents, a team of oblivious agents can perpetually explore the safe nodes without any prior knowledge of the network or the team, without agent or node IDs, under semi-synchronous schedulers. Then, we provide an algorithm that enables agents to safely explore the network and terminate. In this case, agents are equipped with unique IDs and persistent memory, and they know the number of safe nodes. Yet, in both cases, we prove that it is impossible for a team of agents on dynamic networks to correctly mark only the ports leading to black holes.