Capture of an intruder by mobile agents
Authors:
Open Access
- 10 August 2002
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 200-209
Abstract
Consider a team of mobile software agents deployed to capture a (possibly hostile) intruder in a network. All agents, including the intruder move along the network links; the intruder could be arbitrarily fast, and aware of the positions of all the agents. The problem is to design the agents' strategy for capturing the intruder. The main efficiency parameter is the size of the team. This is an instance of the well known graph-searching problem whose many variants have been extensively studied in the literature. In all existing solutions, and in all the variants of the problem, it is assumed that agents can be removed from their current location and placed in another network site arbitrarily and at any time. As a consequence, the existing optimal strategies cannot be employed in situations for which agents cannot access the network at any point, or cannot "jump" across the network, or cannot reach an arbitrary point of the network via an internal travel through insecure zones. This motivates the contiguous search problem in which agents cannot be removed from the network, and clear links must form a connected sub-network at any time, providing safety of movements. This new problem is NP-complete in general. We study it for tree networks, and we consider its more general version, the weighted case, which arises naturally when considering networks whose nodes and links are of different nature and thus require a different number of agents to be explored. We give a linear-time algorithm that computes, for any tree $T$, the minimum number of agents to capture the intruder, and the corresponding search strategy. Beside its optimality in time, our algorithm is naturally distributed: if $T$ is a processor-network, then the minimal search strategy for $T$ can be computed by $T$ in a decentralized manner, using a linear number of messages.
Keywords
This publication has 25 references indexed in Scilit:
- Mutual searchJournal of the ACM, 1999
- Monotonicity and inert fugitive search gamesElectronic Notes in Discrete Mathematics, 1999
- Bushiness and a tight worst-case upper bound on the search number of a simple polygonInformation Processing Letters, 1998
- Mixed searching and proper-path-widthTheoretical Computer Science, 1995
- Recontamination does not help to search a graphJournal of the ACM, 1993
- The vertex separation number of a graph equals its path-widthInformation Processing Letters, 1992
- Single step graph search problemInformation Processing Letters, 1991
- Monotonicity in graph searchingJournal of Algorithms, 1991
- The complexity of searching a graphJournal of the ACM, 1988
- Distributed algorithms for finding centers and medians in networksACM Transactions on Programming Languages and Systems, 1984