Sage Journals: Discover world-class research

Abstract

We consider a scenario of deploying multiple robots to capture all intruders in a cluttered workspace with many obstacles. Here, we say that a robot captures an intruder in the case where the intruder is within the maximum range of a weapon on the robot. All robots use the Voronoi diagram as the topological map of the workspace. Due to obstacles, intruders are confined to move along a passage between obstacles. Suppose the weapons on every robot are powerful enough to cover a passage in the workspace. Then, we can consider a simplified scenario such that robots and intruders are restricted to stay on the Voronoi diagram. We assume that a robot can detect the position of any intruder using the information network. This article presents an intruder capturing strategy that is robust to time delay in data transfer using the network. Our strategy does not require the localization of a node or a robot. Based on this strategy, we provide an upper bound for the minimum number of robots required to capture all intruders on a general graph, which leads to a result of the Voronoi diagram. Lastly, we provide MATLAB (version 7.10.0 R2010a) simulations to verify the effectiveness of our capturing strategy.

Keywords

Voronoi diagram graph theory graph searching graph clear visible intruder information network capturing intruder

Introduction

Monitoring and securing of large complex environments are important tasks in military scenarios. We consider a scenario of deploying multiple robots to capture all intruders in the workspace. Here, we say that a robot captures an intruder in the case where the intruder is within the maximum range of a weapon on the robot.

Suppose that an information (sensor) network is embedded in the workspace. Such an information network becomes feasible due to the research advances in ad hoc networking.^1

–8 In this workspace, each information node can detect a nearby intruder and let a robot access the position of the intruder in real time.

Voronoi diagrams have been widely used for topological maps in robotics.^9

–15 Choset and Burdick¹⁶ argued that a Voronoi vertex whose degree is bigger than three is not “stable.” For example, suppose that there exists a circle that is tangential to four obstacles. If we slightly perturb the position of one obstacle, then the circle is not tangential to four obstacles anymore.¹⁶ Hence, Choset and Burdick¹⁶ assumed that all Voronoi vertices have degree three. This assumption is called the equidistant surface transversality assumption. This article also assumes that all Voronoi vertices have degree three.

In our article, we consider a workspace such that information nodes are deployed along a Voronoi diagram in the workspace. The exploration and networking strategy in the study by Kim¹⁵ can be applied to build the information network along the Voronoi diagram. Information nodes are deployed to cover the entire workspace.

All robots use the Voronoi diagram as the topological map of the workspace. A robot can use the control law introduced in the study by Kim et al.⁹ to move along a Voronoi edge. Due to obstacles, intruders are confined to move along a passage between obstacles. Suppose the weapons on every robot are powerful enough to cover a passage in the workspace. Then, we can consider a simplified scenario such that robots and intruders are restricted to stay on the Voronoi diagram.

Traditionally, search and pursuit-evasion problems have been addressed using two approaches.¹⁷ The first approach is to design strategies that maximize searcher performance against a worst-case intruder. In such settings, a worst-case intruder is characterized by unbounded speed, complete awareness of searcher location and intent, and full knowledge of the search environment. The second approach uses probabilistic formulations addressing false alarms in intruder detection. This approach considers optimization of maximal probability of detection or minimal time until an intruder is detected. The assumption of knowledge about an intruder’s behavior model allows incorporating probabilistic uncertainty in an intruder’s position.

This article takes the first approach that maximizes searcher performance against a worst-case intruder. More specifically, we study the minimum number of robots (searchers) required to capture worst-case intruders on the topological map of the workspace. Many articles exist on capturing worst-case intruders on graphs.^{15,18

–31} Parsons¹⁸ defined the graph searching problem initially. In this problem, searchers and worst-case intruders move along edges of a graph. We introduce several definitions used in this problem. An edge is cleared in the case where it does not contain an intruder. An edge is contaminated in the case where it contains an intruder. A monotone strategy is an intruder capturing strategy satisfying that once an edge is cleared, then the edge is not contaminated again.

There are many variants of the graph searching problem originated from the study by Parsons.¹⁸ A closely related work to ours is the helicopter cops and robbers game.^30,31 In this game,^30,31 an intruder is visible, since the cops have complete knowledge of robbers’ positions as if the cops are using helicopters. Furthermore, the cops can be placed on or removed from vertices of the graph. A robber is captured when a cop lands on the vertex occupied by the robber and it cannot make any move to escape. Seymour and Thomas³⁰ proved that if k cops can catch a visible intruder, then there is a monotone search strategy using k cops. Douglas³¹ provided an upper bound for the minimum number of searchers to clear a graph G using a monotone strategy as $min (1 + pw (G), (1 tw (G)) (⌊ log (r) ⌋))$ . Here, r denotes the number of intruders. pw(G) and tw(G) represent pathwidth and treewidth of G, respectively. The upper bound depends on the number of intruders. Also, deriving pw(G) and tw(G) is Non-deterministic Polynomial (NP-hard).³³ This implies that the numerical calculation of these values is very hard.

In this article, we assume that a robot utilizes the information network to detect intruders, similar to a cop using a helicopter in the studies by Seymour and Thomas³⁰ and Richerby and Thilikos.³¹ However, a robot moves along edges of a graph continuously, which is distinct from the studies by Seymour and Thomas³⁰ and Richerby and Thilikos,³¹ and is suitable for mobile robots. Also, our searching strategy is not a monotone, which is distinct from the studies by Seymour and Thomas³⁰ and Richerby and Thilikos.³¹

The intruder capturing strategy in the study by Kim¹⁵ used information networks as the basis to capture intruders. The strategy in the study by Kim¹⁵ showed that the minimum number of searchers required to clear a graph G is equal to or less than MinGuard(G) + 1, where MinGuard(G) is the minimum number of searchers (guards) to block all cycles in G. The intruder capturing strategy in this article is inspired by the strategy in the study by Kim.¹⁵

Kim¹⁵ did not consider the localization problem of both a robot and a node. In other words, Kim¹⁵ simply assumed that all nodes and robots are localized in global coordinate systems. As far as we know, no article on graph searching problems has considered localization of a searcher. In this article, we consider an environment where Global Positioning Systems (GPS) signal cannot reach. Considering this environment, localization of distributed nodes is not trivial. (There are many articles on localization of distributed sensor nodes.^34

–40 The classic methods for the localization of distributed sensor nodes are time of arrival, time difference of arrival, angle of arrival, and received signal strength.) Our intruder capturing strategy does not require the localization of a node or a robot. To enable this, each information node is given a special functionality, which will be presented in the section “Information network structure.” As a robot visits an information node, the task of the node is to recommend a preferred direction of movement for the robot. In other words, an information node functions as a “signpost” for the robot.

Suppose that a node detects a nearby intruder. Then, the node broadcasts this detection event to a robot using the information network. As we use the information network, it is inevitable that time delay in data transfer occurs. This article presents an intruder capturing strategy that is robust to time delay in data transfer using the network. As far as we know, our intruder capturing strategy is unique in robustness to time delay in data transfer. (Using the same argument as presented in this article, we can prove that the strategy in the study by Kim¹⁵ is robust to time delay using the network. However, Kim¹⁵ did not discuss its robustness to time delay.)

Based on the strategy, we provide an upper bound for the minimum number of robots required to capture all intruders on a general graph, which leads to a result of the Voronoi diagram. We show that, under the transversality assumption, the upper bound for the minimum number of robots required to clear the Voronoi diagram can be calculated in polynomial time. Finally, we provide MATLAB simulations to verify the effectiveness of our capturing strategy.

The article is organized as follows. Section “Preliminaries and background” provides preliminaries and background information. Section “Information network structure” introduces the information network structure considered in our article. Section “Capturing intruders based on the Voronoi diagram assisted by the information network” discusses capturing intruders based on the Voronoi diagram assisted by the information network. Section “MATLAB simulations” provides MATLAB simulations to verify our results. Section “Conclusions” provides conclusions.

Preliminaries and background

This section provides background information and previous works that are used to provide the new contributions.

Graph theory

We review some general notions in graph theory.³² An undirected graph G is defined by a set $G = (N (G), E (G))$ , where N(G) denotes the set of nodes and E(G) is a set of unordered pairs of nodes. Note that multiple edges between node pairs are allowed.

A walk is an alternating sequence of nodes and edges in a graph such that each node belongs to the edge immediately before and after it in the sequence. A graph G is connected if there is a walk between every pair of distinct nodes. The subgraph of G induced by a set of nodes $S \subset N (G)$ is the graph $(S, E_{S})$ , where $E_{S} = {(x, y) \in E (G) : x, y \in S}$ .

A cycle is a graph consists of vertices connected in a closed chain. A tree is a connected graph without cycles. Suppose n is a node of a tree graph T. Then, we define a branch of T at n as the maximal subtree of T, denoted by T′ if n has degree one in T′.

A feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. Finding a minimum feedback vertex set in a graph is an NP-complete problem.^41,42 However, finding a minimum feedback vertex set in a graph of maximum degree three can be solved in polynomial time.^41,42

The workspace and its Voronoi diagram

Consider a connected and compact workspace W ⊂ R² whose boundary, ∂W, is a simple closed curve that is continuous and has no self-intersection. Let $O_{1}, O_{2}, ..., O_{M - 1}$ be M − 1 disjoint and compact obstacles in W. We introduce O_M as a “virtual” obstacle that bounds the workspace, that is, $\partial W \subset \partial O_{M}$ and $W \cap O_{M} = \partial W$ .

Obeying the conventions established in the literature on Voronoi diagrams,^10,43 let V_i be the Voronoi cell of O_i and ∂V_i be the boundary of the Voronoi cell V_i. A Voronoi edge is a common boundary edge shared by two Voronoi cells. A Voronoi vertex is a node where at least three Voronoi edges meet.

The following assumptions, which were also used in our previous articles,^4,9 are made about the workspace.

Assumption 1

The boundary ∂V_i of every Voronoi cell V_i is a simple closed curve.

Assumption 2

\cup_{i = 1}^{M} (V_{i} \cup \partial V_{i}) = W

Since ∂V_i is a simple closed curve for each O_i, Voronoi cells correspond to faces of the Voronoi diagram. In the weak dual graph of the Voronoi diagram, each Voronoi cell V_i will be represented by a node n_i. And each Voronoi edge shared by ∂V_i and ∂V_j corresponds to an edge $(n_{i}, n_{j})$ that connects n_i and n_j.

Cooperative exploration and networking strategy in¹⁵

In our article, we consider a workspace such that information nodes are deployed along the Voronoi diagram in the workspace. The networking strategy in the study by Kim¹⁵ can be applied to build the information network along the Voronoi diagram. In this section, we briefly introduce the networking strategy in the study by Kim.¹⁵

Using the networking strategy described in the study by Kim,¹⁵ multiple robots explore an unknown workspace while deploying information nodes at Voronoi vertices. Moreover, information nodes are deployed along long Voronoi edges in order to relay data from one node to another node out of the maximum sensing range. Information nodes are deployed to satisfy that the sensor footprints cover $W \ \cup_{i = 1}^{M} O_{i}$ entirely.

Suppose N robots are deployed in an unknown workspace to build the information network. A robot, say R_i where i ≤ N, can use the control law introduced in the study by Kim et al.⁹ to move along a Voronoi edge.

While R_i explores the workspace using the networking strategy in the study by Kim,¹⁵ the Voronoi information graph G_v is constructed. (The Voronoi information graph is called the combined graph in the study by Kim.¹⁵) Every node in $N (G_{v})$ represents a deployed information node. Every edge, say $(v_{1}, v_{2}) \in E (G_{v})$ , represents a Voronoi edge whose two endnodes correspond to two information nodes n₁ and n₂, respectively. Here, n₁ and n₂ indicate two information nodes corresponding to $v_{1} \in N (G_{v})$ and $v_{2} \in N (G_{v})$ , respectively.

At each Voronoi vertex, if every edge adjacent to this vertex has been visited by any robot, then the vertex is considered as explored, otherwise unexplored. We say that a robot R_i explores a Voronoi edge when the edge has not been traversed by any other robot before R_i traverses the edge. An unexplored vertex corresponds to a node $v \in N (G_{v})$ storing an unexplored edge emanating from the node.

In the case where a robot meets an unexplored vertex, it simply moves along an unexplored edge emanating from the node. Consider the case where a robot, say R_i, meets an explored vertex. Then, the robot searches for an unexplored edge using G_v.

In the case where R_i meets an explored vertex, R_i searches for the nearest unexplored edge $E_{R_{i}}$ using G_v. $E_{R_{i}}$ is relayed (broadcasted) across the information network to all other robots sharing the network. If another robot R_j (for any j ≠ i) visits one end point of $E_{R_{i}}$ , then R_j ignores the point. In this way, $E_{R_{i}}$ is “reserved” for R_i until it is reached by R_i. Once R_i reaches one end point of $E_{R_{i}}$ , it moves along $E_{R_{i}}$ .

Information network structure

Figure 1 depicts the information network built using the exploration and networking strategy in the study by Kim.¹⁵ The obstacle boundaries are shown as thick red curves. Deployed information nodes are marked with large green dots. By removing all edges intersecting an obstacle boundary in Figure 1, we derive G_v for the environment in Figure 1.

Figure 1.

The information network built using the exploration and networking strategy in the study by Kim.¹⁵

In this article, we present an intruder capturing strategy that does not require the localization of a node or a robot. As a robot visits an information node, the task of the node is to recommend a preferred direction of movement for the robot. In other words, an information node functions as a signpost for the robot. To enable this, we introduce a new concept as follows. The angle of an edge e at a node n is the angle of the line tangential to e at n measured clockwise from the north direction. An illustration of the angle of an edge e at each end point of e is shown in Figure 2.

Figure 2.

The angle of an edge e at each end point of e.

We assume that every information node has the following functionality: an information node stores the angle of every edge adjacent to the node. This assumption is called the angle assumption.

In the case where information nodes are deployed using the networking strategy in the study by Kim,¹⁵ each node does not have the above functionality. To provide a node with the above functionality, we modify the networking strategy in the work by Kim¹⁵ to algorithm 1. Lemma 1 shows that every node deployed using algorithm 1 has the above functionality. The features of algorithm 1 distinct from the networking strategy in the work by Kim¹⁵ are marked with bold sentences.

Algorithm 1.

Networking strategy to satisfy the angle assumption.

repeat

if a robot R_i cannot detect any information node then

R_i drops an information node at the position;

end if

Suppose R_i meets a Voronoi vertex v after traversing a Voronoi edge $(v_{prev}, v)$ ;

The information node at v_prev stores the angle of $(v_{prev}, v)$ ;

The information node at v stores the angle of $(v_{prev}, v)$ ;

if there is no information node at v then

R_i drops an information node at v;

end if

if v corresponds to one end point of $E_{R_{i}}$ then

R_i moves along $E_{R_{i}}$ ;

else if there is an unexplored edge, say E, emanating from v, and E has not been reserved by any robot then

R_i moves along the edge E;

else

R_i searches for the nearest unexplored edge $E_{R_{i}}$ , which has not been reserved by any other robot;

R_i broadcasts $E_{R_{i}}$ followed by moving along the shortest path to reach one end point of $E_{R_{i}}$ ;

end if

until there is no unexplored edge in the workspace;

Lemma 1

As a result of algorithm 1, every information node stores the angle of every Voronoi edge adjacent to the node.

Proof

We prove by contradiction. Suppose that algorithm 1 ends and that a node n does not store the angle of an adjacent Voronoi edge, say e. e must be traversed by a robot, since there exists no unexplored edge after algorithm 1 ends. Every end point of e stores the angle of e using algorithm 1. This is a contradiction to the statement that n does not store the angle of e. Thus, every information node stores the angle of every Voronoi edge adjacent to the node. □

To make algorithm 1 feasible, each information node must be equipped with a sensor to measure the angle of an adjacent edge. For example, we can consider the case where each node is equipped with 360° scanning camera. (A camera is useful for detecting intruders. Using a camera, a node can detect and identify a nearby intruder.) Consider the case where an information node, say i, measures the angle of an adjacent edge e. Suppose that a robot moves along e and that the robot is sufficiently close to i. Since i is equipped with a camera, i can measure the bearing of the robot close to i. Then, the bearing of the robot can be used to estimate the angle of e.

Capturing intruders based on the Voronoi diagram assisted by the information network

Suppose that the information network is built along the Voronoi diagram of the workspace using algorithm 1. All robots use the Voronoi diagram as the topological map of the workspace. Due to obstacles, intruders are confined to move along a passage between obstacles. Suppose the weapons on every robot are powerful enough to cover a passage in the workspace. Then, we can consider a simplified scenario such that robots and intruders are restricted to stay on the Voronoi diagram.

Before tackling capturing intruders in the Voronoi diagram, we study capturing intruders in a topological map of a workspace assisted by the information network.

Definitions and assumptions

Let G denotes a topological map of a workspace. Suppose that each node in G is associated to an information node in the workspace. Let us consider an environment where robots and intruders are restricted to stay on G.

We introduce a guard, whose role is to guard a node in G. Only one robot, say free robot, moves along edges of G continuously.

The free robot utilizes the information network to detect intruders. The free robot obtains the position of any intruder whenever the robot visits a node in G. This is feasible, since information nodes are deployed to cover the entire workspace.

Obeying the conventions established in the literature on capturing intruders on graphs,^19,26

–29 we assume that an intruder has full knowledge of the environment, searching strategies, and positions of both the free robot and guards. In addition, an intruder moves along edges of G at unbounded speed to avoid both the free robot and guards.

An intruder is captured if (1) it is on an edge whose one end point is guarded while the free robot moves through the edge from the opposite end point or (2) it is on an edge one end point of which has degree one while the free robot moves through the edge starting from the opposite end point. The minimum number of robots to capture all intruders on G is denoted as s_I(G) where I indicates the information network.

Capturing intruders on a general graph

In this subsection, we derive an upper bound for s_I(G) for G. Lemma 2 provides the capturing strategy to derive the bound.

Lemma 2

Suppose that one free robot and one intruder move along a tree graph T. Then, the robot can capture the intruder in finite time using the following strategy:

Whenever the robot meets a node, it obtains the branch containing the intruder. Then, it moves through the edge contained in the branch until it meets another node. Iterate this until the intruder is captured.

Lemma 3 shows that the capturing strategy in lemma 2 is robust to time delay in data transfer using the information network.

Lemma 3

Using the capturing strategy in lemma 2, the intruder is captured in finite time regardless of time delay in data transfer using the information network.

Proof

Suppose that the free robot is at a node n. Suppose that an intruder at a branch, say b, is detected at time step t₁ and that the detection event is broadcasted to the free robot at time step t₂. According to the definition of a branch, n is the only node connecting b with T\b. Blocked by the free robot at n, the intruder cannot escape from b between two time steps t₁ and t₂. Thus, as the robot chooses b and moves through the edge contained in b, the intruder cannot escape from b. As we iterate this, the intruder is captured in finite time. □

To make lemma 2 feasible, the free robot must be able to choose the branch containing the intruder and move through the edge contained in the branch until it meets another node. Suppose that the robot is located at a node n and that a node n_a is adjacent to n in the branch containing the intruder. We assume that an information node is not localized and that the robot cannot access the position of a node.

Suppose that the free robot visits n and that the next node to visit is n_a. Using the angle assumption, n stores the angle of one edge leading to n_a. Hence, n recommends the moving direction for the robot. By simply following the edge corresponding to the recommended direction, the robot can visit n_a.

Since an intruder can move at unbounded speed, an intruder can escape from the free robot using a cycle in a general graph G. To block escape of an intruder, we deploy guards at nodes in G. If a guard is deployed at a node, then the node becomes unavailable to intruders. Hence, once a guard is deployed at a node, we mark the node as guarded. We say that a cycle C is blocked if any node in N(C) is guarded.

We define $N_{min} (G)$ as the minimum number of guarded nodes to block all cycles contained in G. By definition, $N_{min} (G)$ is the cardinality of a minimum feedback vertex set of G. Thus, finding $N_{min} (G)$ is an NP-complete problem, as discussed in section “Graph theory.”

In our problem of searching for $N_{min} (G)$ , the universal set U corresponds to the set of all cycles that are contained in G. Let a node in G be identified by n_i where $i \leq | N (G) |$ . We build a family of subsets $S = {S_{1}, S_{2},..., S_{| N (G) |}}$ of U. Here, S_i is the set of cycles satisfying that every cycle in S_i has n_i in it. Hence, every cycle in S_i is blocked by deploying a guard at $n_{i} \in N (G)$ . P ⊂ S is selected so that it contains all cycles in U while minimizing |P|. Then, $N_{min} (G)$ corresponds to |P|. For this problem, approximation algorithms returning near-optimal solutions exist.⁴⁴

Suppose $N_{min} (G)$ nodes of G are guarded to block all cycles contained in G. Since all cycles in G are blocked, no cycle is available to an intruder, that is, available set of points for an intruder is a tree. Thus, an intruder cannot escape from the free robot using lemma 2. Furthermore, the free robot can capture all intruders by chasing one intruder at a time. Since we need one free robot and $N_{min} (G)$ guards to capture all intruders on G, $s_{I} (G) \leq 1 + N_{min} (G)$ .

Lemma 4

For a general graph G, $s_{I} (G) \leq 1 + N_{min} (G)$ .

For a general graph G, algorithm 2 describes our graph searching strategy using one free robot and $N_{min} (G)$ guards.

Algorithm 2.

Capturing all intruders on a general graph G.

guard $N_{min} (G)$ nodes of G to block all cycles in G;

r_f ← one free robot which maneuvers to capture intruders;

repeat

r_f chooses one intruder as TARGET;

T ⊂ G ← the tree which is available to TARGET;

if r_f is not on T then

r_f moves along G to reach a node in T;

end if

repeat

r_f meets a node in T and chooses the branch of T containing TARGET;

r_f moves through the edge contained in the branch until it meets another node;

until r_f captures TARGET, and TARGET is removed from the list of intruders;

until all intruders on G are captured;

Capturing intruders on the Voronoi diagrams

We consider capturing intruders in the topological map of a workspace, represented by the Voronoi diagram defined in section “The workspace and its Voronoi diagram.” We compute $N_{min} (D)$ , that is, the minimum number of guards needed to block all cycles on the Voronoi diagram D so that we capture any number of intruders.

Note that finding a minimum feedback vertex set in a graph of maximum degree three can be solved in polynomial time.^41,42 Hence, under the transversality assumption, $N_{min} (D)$ can be solved in polynomial time.

MATLAB simulations

Since we suppose the weapons on every robot are powerful enough to cover a passage in the workspace, we can simplify a scenario such that a searcher and an intruder move along Voronoi edges.

Figure 3 shows the Voronoi diagram D as well as obstacle environments. Thick red curves indicate obstacle boundaries. We use the exploration strategy in the study by Kim et al.⁹ to build D. See that D contains four cycles and that no Voronoi edge intersects an obstacle boundary. There are six vertices in D, and every vertex has degree three.

Figure 3.

The Voronoi diagram as well as obstacle environments.

In Figure 3, deployed guards are marked with large blue dots. Two guards are deployed at two vertices in D to block all cycles. Since every vertex in D has degree three, the minimum number of guards can be found in polynomial time using methods in the studies by Li and Liu⁴¹ and Ueno et al.⁴²

Once two guards are deployed to block all cycles, one free robot chases one intruder at a time to capture all intruders. Blocked by two guards, no intruder can escape from the free robot. Our algorithm robustly works against any number of worst-case intruders with infinite speed.

Conclusions

We consider a scenario of deploying multiple robots to capture intruders in a cluttered workspace with many obstacles. We consider a simplified scenario such that robots and intruders are restricted to stay on the Voronoi diagram. Assuming that one free robot can access the position of any intruder utilizing the information network, a capturing strategy is proposed so that robots capture all intruders in finite time. Our capturing strategy is simple to implement and is guaranteed to capture all intruders regardless of the number of intruders. Based on this strategy, we derive an upper bound for the minimum number of robots required to capture all intruders on a general graph, which leads to a result of the Voronoi diagram.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Culler

Estrin

Srivastava

. Overview of sensor networks. IEEE Comput Mag 2004; 37(8): 41–49.

Souryal

Geissbuehler

Miller

. Real-time deployment of multihop relays for range extension. In: Proceedings of the 5th international conference on mobile systems, applications and services (MobiSys 07) (ed E Knightly), San Juan, Puerto Rico, 11–13 June 2007, pp. 85–98. New York, NY: ACM.

Liu

Xie

. Automatic and robust breadcrumb system deployment for indoor firefighter applications. In: Proceedings of the 8th international conference on mobile systems, applications, and services (MobiSys 10) (ed S Banerjee), San Francisco, CA, USA, 15–18 June 2010, pp. 21–34. New York, NY: ACM.

Kim

Zhang

Egerstedt

. Simultaneous cooperative exploration and networking based on Voronoi diagrams. In: Proceedings of IFAC workshop on networked robotics (ed K

Moore

), Colorado, USA, 6–8 October 2009, pp. 1–6. Elsevier Ltd.

Kim

Maxon

Egerstedt

. Intruder capturing game on a topological map assisted by information networks. In: Proceedings of IEEE conference on decision and control (ed E

Chong

), Orlando, FL, USA, 12 December–15 December 2011, pp. 6266–6271. IEEE.

Batalin

Sukhatme

. Coverage, exploration and deployment by a mobile robot and communication network. Telecommun Syst 2004; 26: 181–196.

Yoon

Kim

Y-H

. An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks. IEEE Trans Cybern 2013; 43: 1473–1483.

Pimenta

LCA

Schwager

Lindsey

. Simultaneous coverage and tracking (scat) of moving targets with robot networks. In: Proceedings of workshop on the algorithmic foundations of robotics (WAFR) (ed H

Choset

), Mexico, 7–9 December 2008, pp. 85–99. Springer-Verlag Berlin, Heidelberg.

Kim

Zhang

Egerstedt

. A provably complete exploration strategy by constructing Voronoi diagrams. Auton Robot 2010; 29(3–4): 367–380.

10.

Choset

Nagatani

. Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Trans Robot Autom 2001; 17: 125–137.

11.

Nagatani

Choset

. Toward robust sensor based exploration by constructing reduced generalized Voronoi graph. In: Proceedings of IEEE/RSJ international conference on intelligent robots and systems (ed TS

Ray

), Kyongju, Korea, 17–21 October 1999, pp. 1687–1692. IEEE.

12.

Rao

NSV

Stoltzfus

Iyengar

. A retraction method for learned navigation in unknown terrains for a circular robot. IEEE Trans Robot Autom 1991; 7: 699–707.

13.

Choset

Konukseven

Burdick

. Mobile robot navigation: issues in implementating the generalized Voronoi graph in the plane. In: Proceedings of IEEE/SICE/RSJ international conference on multisensor fusion and integration for intelligent systems (ed RR

Brooks

), Washington, DC, USA, 8–11 December 1996, pp. 241–248. IEEE.

14.

Lavalle

SM.

Planning algorithms. Cambridge University Press, 2006.

15.

Kim

. Cooperative exploration and protection of a workspace assisted by information networks. Ann Math Artif Intell 2014; 70: 203–220.

16.

Choset

Burdick

. Sensor based planning, part I: the generalized Voronoi graph. In: Proceedings of the IEEE international conference on robotics and automation (ed E

Freund

), Nagoya, Japan, 21–27 May 1995, pp. 1649–1655. IEEE.

17.

Chung

Hollinger

GA,

Isler

. Search and pursuit-evasion in mobile robotics. Auton Robot 2011; 31: 299–316.

18.

Parsons

TD.

Pursuit-evasion in a graph. In: Theory and applications of graphs (ed DR

Lick

), Michigan, USA, 11–15 May 1976, Vol. 642. Lecture Notes in Mathematics, pp. 426–441. Springer-Verlag.

19.

Megiddo

Hakimi

Garey

. The complexity of searching a graph. J ACM 1988; 35: 18–44.

20.

Kolling

Carpin

. The graph-clear problem: definition, theoretical properties and its connections to multirobot aided surveillance. In: Proceedings of the 2007 IEEE/RSJ international conference on intelligent robots and systems (ed E

Grant

), California, USA, 20 October–2 November 2007, pp. 1003–1008. IEEE.

21.

Lapaugh

. Recontamination does not help to search a graph. J ACM 1993; 40(2): 224–245.

22.

Fomin

Fraigniaud

Nisse

. Nondeterministic graph searching: from pathwidth to treewidth. Algorithmica 2009; 53(3): 358–373.

23.

Barriére

Barri Ere

Flocchini

. Capture of an intruder by mobile agents. In: Proceedings of the fourteenth annual ACM symposium on parallel algorithms and architectures (ed A

Rosenberg

), Canada, 11–13 August 2002, pp. 200–209. New York, NY: ACM.

24.

Fomin

and Thilikos

. An annotated bibliography on guaranteed graph searching. Theor Comput Sci 2008; 399: 236–245.

25.

Makedon

Sudborough

. On minimizing width in linear layouts. Discrete Appl Math 1989; 23(3): 243–265.

26.

Kirousis

Papadimitriou

. Interval graphs and searching. Discrete Math 1985; 55(2): 181–184.

27.

Kirousis

Papadimitriou

. Searching and pebbling. Theor Comput Sci 1986; 42(2): 205–218.

28.

Bienstock

Seymour

. Monotonicity in graph searching. J Algorithms 1991; 12(2): 239–245.

29.

Dendris

Kirousis

LM,

Thilikos

. Fugutive-search games on graphs and related parameters. Theor Comput Sci 1997; 172: 233–254.

30.

Seymour

Thomas

. Graph searching and a min-max theorem for tree-width. J Combin Theory Ser B 1993; 58: 22–33.

31.

Richerby

Thilikos

. Graph searching in a crime wave. SIAM J Discrete Math 2009; 23(1): 349–368.

32.

Douglas

. Introduction to graph theory. 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2001.

33.

Bodlaender

Gilbert

Hafsteinsson

. Approximating treewidth, pathwidth, and minimum elimination tree height. Lect Notes Comput Sci 1992; 570: 1–12.

34.

Howard

Mataric

MJ,

Sukhatme

. Relaxation on a mesh: a formalism for generalized localization. In: Proceedings of IEEE/RSJ international conference on intelligent robots and systems (ed N

Adachi

), Hawaii, USA, 29 October–3 November 2001, pp 1055–1060. IEEE.

35.

Mao

Fidan

Anderson

BDO

. Wireless sensor network localization techniques. Comput Netw 2007; 51: 2529–2553.

36.

Priyantha

Balakrishnan

Demaine

. Anchor-free distributed localization in sensor networks. In: Proceedings of the first international conference on embedded networked sensor system (ed I

Akyildiz

), USA, 5–7 November 2003, pp. 340–341. New York: ACM.

37.

Jiang

J-R

Lin

C-M

Lin

F-Y

. ALRD: AoA localization with RSSI differences of directional antennas for wireless sensor networks. Int J Distrib Sens Netw 2013; 2013: 529489.

38.

Han

Duong

. Localization algorithms of wireless sensor networks: a survey. Telecommun Syst 2013; 52: 2419–2436.

39.

Cheng

Zhang

. A survey of localization in wireless sensor network. Int J Distrib Sens Netw 2012: 2012; 962523.

40.

Niculescu

Nath

. Ad hoc positioning system (APS) using AOA. In: Twenty-second annual joint conference of the IEEE computer and communications (ed F

Bauer

), USA, 30 March–3 April 2003, pp. 1734–1743. IEEE.

41.

Liu

. A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph. Acta Math Sci 1999; 19(4): 375–381.

42.

Ueno

Kajitani

Gotph

. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Math 1988; 72: 355–360.

43.

Bhattacharya

Gavrilova

. Roadmap-based path planning—using the Voronoi diagram for a clearance-based shortest path. IEEE Robot Autom Mag 2008; 15: 58–66.

44.

Dutta

. Survey of approximation algorithms for set cover problem. Master’s thesis, University of North Texas, TX, 2009.

Capturing intruders based on Voronoi diagrams assisted by information networks

Abstract

Keywords

Introduction

Preliminaries and background

Graph theory

The workspace and its Voronoi diagram

Assumption 1

Assumption 2

Cooperative exploration and networking strategy in 15

Information network structure

Lemma 1

Proof

Capturing intruders based on the Voronoi diagram assisted by the information network

Definitions and assumptions

Capturing intruders on a general graph

Lemma 2

Lemma 3

Proof

Lemma 4

Capturing intruders on the Voronoi diagrams

MATLAB simulations

Conclusions

Footnotes

Declaration of conflicting interests

Funding

References

Cooperative exploration and networking strategy in¹⁵