Sage Journals: Discover world-class research

Abstract

In this article, we consider the problem of using multiple robots (searchers) to capture intruders in an environment. Assume that a robot can access the position of an intruder in real time, that is, an intruder is visible by a robot. We simplify the environment so that robots and worst-case intruders move along a weighted graph, which is a topological map of the environment. 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 weight of an edge or a vertex in a weighted graph is a cost describing the clearing requirement of the edge or the vertex. This article provides non-monotone search algorithms to capture every visible intruder. Our algorithms are easy to implement, thus are suitable for practical robot applications. Based on the non-monotone search algorithms, we derive the minimum number of robots required to clear a weighted tree graph. Considering a general weighted graph, we derive bounds for the number of robots required. Finally, we present switching algorithms to improve the time efficiency of capturing intruders while not increasing the number of robots. We verify the effectiveness of our approach using MATLAB simulations.

Keywords

Weighted graph search graph clear visible intruder non-monotone search algorithm sensor network intruder capture operations research

Introduction

Monitoring and securing of an environment is an important task in sensor networks. Sensor network becomes feasible due to the development of small sensor nodes, such as the Berkeley MOTES.¹ Research advances in sensor networks^2,3 demonstrated that small sensor nodes can be positioned to monitor the entire environments while detecting intruders.

Consider the case where the sensor network is completely built in an environment (The exploration and networking strategy in the study by Kim^4,5 can be applied to build the sensor network in an unknown environment.). The network can operate for many purposes, such as detecting intruders. Deployed sensor nodes form a network enabling robots (searchers) to exchange information with other robots or nodes. Moreover, sensor networks enable a robot to access every intruder’s location in real time. For instance, in the case where a sensor node n detects an adjacent intruder, this detection event can be relayed to all robots sharing the network so that every robot can perceive that n detected an intruder. Thus, an intruder is visible by a robot assisted by the sensor network.

Traditionally, intruder capture problems were handled utilizing two approaches. The first approach uses probabilistic formulations addressing average-case behaviors.^6

–12 The probabilistic approaches is the focus of the theory of search, which has a long-standing legacy in the field of operations research (OR).¹³ Measures of interest can include expected time until capturing an evader. The assumption about knowledge about the evader’s behavior allows incorporating probabilistic uncertainty in target locations, their behaviors, and/or sensor observations. Suppose the evader maneuvers in a manner which is independent of the pursuer’s motion. For example, assume that the evader performs a random walk. In this case, it is possible to capture the evader even with a stationary pursuer, since the evader will meet the pursuer in the end. The main question here is the design of an optimal strategy to capture the randomly walking evader as quickly as possible. This is the focus of probabilistic search.⁷

The second approach is on developing strategies which maximize search performance to capture a worst-case intruder.⁷ A worst-case evader is characterized by unbounded speed, complete awareness of searcher’s position and intent, and full knowledge of the search environment. An intruder with unbounded speed represents a worst-case scenario for a robot capturing an intruder. This article handles a worst-case scenario where an intrude can move much faster than a robot. For instance, a robot can be a ground robot which moves slowly on the ground. On the other hand, an intruder is a fast moving car.

The strategies which maximize search performance to capture a worst-case intruder guarantee the success of the search, defined, for instance, by capture of the evader in finite time. We acknowledge that the powerful adversary model may provide solutions that are too conservative in practical applications.⁷ However, this article shows that the presence of the sensor network can decrease the number of required robots considerably.

This article is based on the second approach which maximizes search performance against a worst-case intruder. More specifically, this article presents the minimum number of robots (searchers) required to capture worst-case intruders on the topological map of the workspace. This article considers a simplified environment where robots and worst-case intruders move along a weighted graph, which is a topological map of the environment. The weight of an edge or a vertex in a weighted graph is a cost describing the clearing requirement of the edge or the vertex.

Many papers exist on capturing worst-case intruders on graphs.^{7,14

–30} Parsons¹⁴ defined the graph searching problem initially. In this problem, searchers and worst-case intruders move along edges of a graph. Considering a finite workspace, a topological map (graph) representing the workspace is also finite. We introduce several definitions used in this article. 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. A non-monotone strategy is an intruder capturing strategy which is not monotone.

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.^29,30 In this game,^29,30 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 the vertices of the graph. A robber is captured when a cop lands on the vertex occupied by the robber, and the robber 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. Richerby and Thilikos³⁰ 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) ⌋ + 1))$ . Here, r denotes the number of intruders. $p w (G)$ and $t w (G)$ represent pathwidth and treewidth of G, respectively. See that this upper bound depends on the number of intruders. Also, deriving $p w (G)$ and $t w (G)$ is NP-hard.³¹

There are many articles on clearing a weighted graph.^{16,19,32
–34} The weight of an edge or a vertex in a weighted graph is a cost describing the clearing requirement of the edge or the vertex. The problem is to find a strategy to clear a weighted graph with the lowest cost, that is, the minimum number of searchers to execute it. This problem is NP-hard. Kolling and Carpin¹⁶ provided an upper bound for the minimum number of searchers by presenting a monotone search strategy to clear a weighted graph.

We consider a searcher that moves along a weighted graph continuously, which is adequate for mobile robot applications. This distinguishes our article from other articles^29,30 on graph searching, which assumed that a searcher (on a helicopter) can land on a vertex where a visible intruder exists.

The problem tackled in this article is distinct from that in Kolling and Carpin,¹⁶ since we consider a visible intruder. This article assumes that an intruder is visible by a robot. As far as we know, no paper on clearing a weighted graph considered a visible intruder. Since this article considers a visible intruder, the number of searchers required to clear a weighted graph can reduce considerably compared to the case where an intruder is not visible.

We introduce non-monotone algorithms to clear a weighted graph. Our algorithms are easy to implement, thus are suitable for practical robot applications. Since our algorithms are not monotone, the number of searchers required to capture all intruders does not increase as the number of intruders increases. Based on the non-monotone searching algorithms, we derive the minimum number of searchers required to clear a weighted tree graph. We further show that the upper bound for the minimum number of robots required to clear a weighted graph can be calculated by solving the weighted feedback vertex set problem (WFVP). Vineet et al.³⁵ considered the WFVP for undirected graphs and showed that a generalized local ratio strategy leads to an efficient approximation with the performance guarantee of twice the optimal.

Considering some special graphs, the WFVP can be solved in polynomial time or in linear time. This implies that the upper bound for the minimum number of robots required to clear a weighted graph can be calculated in polynomial time or in linear time. In the case where the weighted graph is a diamond graph in the study by Carrabs et al.,³⁶ we can solve the WFVP in linear time.³⁶ Also, we can solve the WFVP in polynomial time in the case where the graph is an interval graph,³⁷ co-comparability graph,³⁸ permutation graph,³⁹ or convex bipartite graph.³⁸

We further present switching algorithms to improve the time efficiency of capturing intruders while not increasing the number of searchers (robots). We verify the effectiveness of our approach using MATLAB simulations.

The second section presents preliminary information of this article. In the third section, we present non-monotone search algorithms to capture visible intruders. The fourth section presents switching algorithms to improve the time efficiency of capturing intruders while not increasing the number of robots. The fifth section provides MATLAB simulations to verify the effectiveness of our approach. The last section provides conclusions.

Preliminary information

This section presents preliminary information of this article.

Graph theory

We review some general notions in graph theory⁴⁰ An undirected graph G is defined by a set G = (V(G), E(G)), where V(G) denotes the vertex set and E(G) is a set of unordered pairs of vertices where multiple edges between vertex pairs are allowed.

A vertex v is said to be adjacent to another vertex w if the graph contains an edge {v, w}. In this case, v is a neighbor to w. A walk is a sequence of vertices and edges v ₁, $v_{1}, {v_{1}, v_{2}}, v_{2},..., {v_{n - 1}, v_{n}}, v_{n}$ . A graph G is connected if there is a walk between every pair of distinct vertices. A walk is closed in the case where it starts and ends at the same vertex. A cycle is a closed walk with no repetitions of vertices and edges allowed, other than the repetition of the starting and ending vertex. The subgraph of G induced by a set of vertices $S \subset V (G)$ is the graph (S, E_S ) where $E_{S} = {{x, y} \in E (G) : x, y \in S}$ .

Let T denote a tree graph, which is a graph without any cycle. Suppose n is a vertex of T. Then, we define a branch of T at n as the maximal subtree of T, denoted by T′, if n has degree 1 in T′. For instance, a branch of T at u is depicted with bold line segments in Figure 1.

Figure 1.

A branch of T at u is depicted with bold line segments.

Given G, splitting of a vertex v is an operation . Here, $V^{'} = (V \ {v}) \cup {v^{1},... v^{deg (v)}}$ and $E^{'} = (E \ (\cup_{u \in N_{v}} {u, v}) \cup_{u \in N_{v}} {u, ν (u)}$ where N_v denotes a neighboring vertex set of v and $ν : N_{v} \to {v^{1},... v^{deg (v)}}$ is a bijection (This operation is not well-defined in the case where self-loop is attached to the split vertex v. When there is a self-loop at v, we replace the self-looping edge {v, v} by two edges {v, n} and{n, v}, where n is a new degree 2 vertex. Thereafter, we implement a vertex splitting at v.). Figure 2 illustrates splitting of v. In this figure, v is split into two new vertices v ¹ and v ².

Figure 2.

Splitting of a vertex v.

Given an undirected and vertex weighted graph G, the weighted feedback vertex problem (WFVP) consists in finding a subset $F \subset V (G)$ of vertices of minimum weight such that each cycle in G contains at least one vertex in F .³⁶ The WFVP on general graphs is known to be NP-hard.³⁶

Problem description

We introduce the problem considered in this article. Consider the case where one or more robots are used to capture possible intruders in a given environment. Also, sensor nodes are positioned in the environment such that a robot can access the position of an intruder in real time. This environment was also considered in the study by Kim.^4,5 Where to deploy sensor nodes to cover the entire environment was considered in the study by Kim^4,5 and is not within the scope of this article.

We consider a robot which is equipped with finite range weapons to capture (destroy) a nearby intruder. We say that an intruder is captured in the case where it is inside the maximum range of weapons of a robot. Even a very fast intruder (intruder with unbounded speed) is captured by a robot once the intruder is inside the maximum range of weapons of the robot. In Figure 3, a circle illustrates the maximum weapon range of a robot. The center of a circle represents the position of the robot associated to the circle.

Figure 3.

A circle illustrates the maximum weapon range of a robot. The center of a circle represents the position of the robot associated to the circle.

We summarize the assumptions in this article as follows.

A1: A robot has full knowledge of the search environment.

A2: Sensor nodes are positioned in the environment such that a robot can access the position of an intruder in real time. In other words, an intruder is visible.

A3: A robot is equipped with finite range weapons to capture (destroy) a nearby intruder which is inside the maximum range of weapons of the robot.

We propose a capture strategy based on the above assumptions. Using assumption (A1), we deploy guard robots at intersections in the workspace to block the escape of an intruder with unbounded speed. Using A3, a robot is equipped with finite range weapons to capture a nearby intruder. Even a very fast intruder (intruder with unbounded speed) is captured by a robot once the intruder is inside the maximum range of weapons of the robot. Considering the finite range, we make multiple robots (driving robots) form a dense formation so that they can drive an intruder until it is captured.

Using A2, an intruder is visible to the driving robots. The driving robots select one intruder as a target and chase the target while maintaining a dense formation. The robots form a dense formation so that the target cannot move through the formation without being caught. Since an intruder cannot move through the formation without being caught, we say that the driving robots sweep a passage.

See Figure 3 for an illustration of the case where six robots sweep a passage. In this figure, a circle illustrates the maximum weapon range of a robot. Only one robot cannot sweep this passage, since this passage is much wider than the weapon range of a robot. Similarly, multiple robots may be needed to guard an intersection.

As a topological map of an environment, we introduce a weighted graph G_l . Each vertex in G_l is associated to an intersection, and each edge in G_l is associated to a passage in the environment. Each vertex and edge in G_l has its weight. The weight of an edge or a vertex in G_l is a cost describing the clearing requirement of the edge or the vertex. To clear an edge e, at least w(e) robots must move along e as one group.

Figure 3 illustrates G_l . In Figure 3, vertices in V(G_l ) are depicted with dots at the center of intersections. In this figure, edges in E(G_l ) are depicted with dotted line segments. In this figure, one group of six robots sweeps a passage while maintaining a dense formation. Thus, w(e) = 6 for the edge $e \in E (G_{l})$ in Figure 3. Also, to clear a vertex v, at least w(v) robots must be located at v. How to set weights in G_l is presented in the literature^16,33,41 and is not within the scope of this article.

We introduce non-monotone algorithms to clear G_l , considering both the number of robots required and the time efficiency. Based on the algorithms, we derive bounds for the minimum number of robots required to capture all intruders.

Non-monotone searching algorithms

In this section, we introduce non-monotone searching algorithms to capture visible intruders. Based on the searching algorithms, we derive bounds for the number of robots required to capture all intruders.

We first introduce definitions before presenting the strategy. We say that G_l is cleared in the case where no intruder is in G_l . G_l is contaminated in the case where at least one intruder is in G_l . Let us denote the minimum number of robots to capture all visible intruders in G_l as s_l (G_l ).

We introduce a driving robot, whose role is to chase an intruder in G_l . We further introduce a guard, whose role is to guard a vertex in G_l . We say that a vertex v is guarded in the case where at least w(v) guards are deployed to guard v. In the case where v is guarded, no intruder can pass through v without being captured.

We define H as

H = MAX (max_{\forall e \in E (G_{l})} w (e), max_{\forall v \in V (G_{l})} w (v)) .

Here, MAX(α, β) indicates the larger one between α and β. H in equation (1) indicates the maximum weight in the graph. H driving robots move as one group and move along G_l to capture intruders. H is a lower bound for s_l (G_l ), as presented in the next lemma.

Lemma 1

$s_{l} (G_{l}) \geq H .$

Proof

Recall that $H = MAX ({max}_{\forall e \in E (G_{l})} w (e), {max}_{\forall v \in V (G_{l})} w (v))$ . Consider the case where we have less than H robots. In this case, a vertex or edge, whose weight is H, cannot be cleared. We proved that s_l (G_l ) ≥ H is required.

We first introduce a search algorithm to capture one intruder in the case where G_l is a tree graph, say T. Algorithm 1 provides the searching strategy using H driving robots. To capture the intruder, H driving robots move as one group. This coordinated strategy will be extended to a strategy of capturing multiple intruders contained in a general graph, later in Algorithm 2.

Algorithm 1
Clear strategy using one group of H driving robots (G_l is a tree T)

Algorithm 2.
Capturing all intruders.

Considering a tree graph, we have the following theorem.

Theorem 1

Consider the case where G_l is a tree graph s_l (G_l ) = H.

Proof

Lemma 1 proved that s_l (G_l ) ≥ H. We also prove that s_l (G_l ) ≤ H. Algorithm 3 provides a searching strategy using H driving robots. Since this algorithm works to capture every intruder in a tree graph, s_l (G_l ) ≤ H.

Algorithm 3.
$g_{f}$ .CAPTURE( $T A R G E T$ ).

Suppose that H = 6 and that one edge, say e ₁, requires w(e ₁) = 2 robots to sweep the edge. Recall that the driving robots form a dense formation so that an intruder cannot move through the formation without being caught. Suppose that the driving robots sweep a passage where only two robots are needed to clear the passage. In this case, the driving robots form a denser formation (decrease the relative distance between each other) to sweep the passage. Formation change of the driving robots is not within the scope of this article. The control laws in the study by Alonso-Mora et al.⁴² can be used for formation control considering obstacles. See Figure 4 for an illustration of the case where six robots sweep a passage which requires only two robots for sweeping the passage. In Figure 4, a circle illustrates the maximum weapon range of a robot.

Figure 4.
A circle illustrates the maximum weapon range of a robot. The center of a circle represents the position of the robot associated to the circle. Six robots sweep a passage which requires only two robots for sweeping the passage.

Next, let us consider G_l which is not a tree. Recall that we consider a worst-case intruder. Hence, an intruder can move at unbounded speed to avoid both the driving robots and guards. To block escape of an intruder, we guard vertices in G_l . We say that a cycle C is blocked if any vertex in V(C) is guarded.

We define N_g as the minimum number of guards to block all cycles in G_l . Computational method to derive N_g corresponds to the WFVP in the study by Carrabs et al.³⁶ The WFVP for a general graph is known to be NP-hard in computer science.³⁶ In the case where G_l is a general graph, approximation algorithms returning near-optimal solutions exist.⁴³

Considering some special graphs, N_g can be derived in polynomial time or in linear time. In the case where G_l is a diamond graph in the study by Carrabs et al.,³⁶ we can derive N_g in linear time.³⁶ Also, we can derive N_g in polynomial time in the case where G_l is an interval graph,³⁷ co-comparability graph,³⁸ permutation graph,³⁹ or convex bipartite graph.³⁸

Suppose N_g guards are deployed to block all cycles in G_l . H driving robots capture every intruder one by one using Algorithm 2. Algorithm 2 describes our searching strategy considering the case where there are many intruders. Let g_f denote one group of H driving robots. Among all intruders that are detected using sensor networks, g_f selects one as TARGET. Then, g_f chases TARGET until TARGET is captured. While g_f chases TARGET, g_f keeps sweeping edges to avoid the escape of. Since all cycles in G_l are blocked, any targeted intruder cannot escape from g_f . In this way, we can decrease the number of intruders until all intruders are captured.

There may be a case where an intruder, say $i n$ , enters the workspace while driving robots are capturing other intruders. As time goes on, $i n$ will be set as TARGET, and TARGET will be captured by driving robots.

Since we need H driving robots and N_g guards to capture all intruders on G_l , s_l (G_l ) ≤ H+ N_g follows. Moreover, we have s_l (G_l ) ≥ H using Lemma 1. Therefore, we have the following theorem.

Theorem 2

$H \leq s_{l} (G_{l}) \leq H + N_{g} .$

In the case where $H ≫ N_{g}$ , Theorem 2 provides tight bounds for the number of robots required to clear G_l . For instance, in the case where G_l is a sparse graph with large edge weights, it is probable that $H ≫ N_{g}$ .

The switching search algorithms

In Algorithm 2, only driving robots move, while other robots guard their designated locations. Considering the efficiency of capturing intruders, it is desirable to make a guard move if necessary. We present switching algorithms to make a guard move to capture intruders if the movement of the guard does not allow an intruder to escape.

Before presenting our switching algorithms (see Algorithm 4), we need to introduce a new graph G_T representing the available set of points for an intruder.

Algorithm 4.
Time-efficient capturing strategy using $N_{g} + H$ robots.

Suppose we deploy N_g guards to block all cycles in G_l . Since all cycles in G_l are blocked, an intruder cannot escape from the driving robots.

By splitting guarded vertices in G_l , we obtain G_T . G_T is composed of several disjoint tree graphs, since all cycles in G_l are blocked. In other words, G_T = {T ₁,…,T_L } where T_i denotes the ith tree graph. A robot is adjacent to a tree graph T_i if the robot guards a vertex of T_i .

In the case where N_g is zero, there is no cycle to block in G_l . This implies that G_l is a tree. Thus, G_T = {T ₁}, where T ₁ is identical to G_l .

Figure 5 illustrates G_l with corresponding G_T . In this figure, v ₁ and v ₂ in G_l are guarded to block all cycles in G_l . By splitting v ₁ and v ₂ in G_l , we obtain G_T . G_T is composed of two disjoint tree graphs T ₁ and T ₂, since all cycles in G_l are blocked. N_g = w(v ₁) + w(v ₂) = 3, since w(v ₁) = 1 and w(v ₂) = 2.

Figure 5.
An illustration of G_l with corresponding G_T . N_g = w(v ₁) + w(v ₂) = 3, since w(v ₁) = 1 and w(v ₂) = 2.

Considering the G_l in Figure 5, we need to split at least two vertices in G_l to remove all cycles in G_l . Figure 6 illustrates G_l with corresponding G_T . In Figure 6, v ₁ and v ₃ in G_l are guarded to block all cycles in G_l . By splitting v ₁ and v ₃ in G_l , we obtain two disjoint tree graphs G_T . N_g = w(v ₁) + w(v ₃) = 4, since w(v ₁) = 1 and w(v ₃) = 3. N_g in Figure 6 is larger than N_g in Figure 5. Thus, splitting two vertices as in Figure 5 is more desirable than splitting two vertices as in Figure 6.

Figure 6.
In this figure, v ₁ and v ₃ in G_l are guarded to block all cycles in G_l . N_g = w(v ₁) + w(v ₃) = 4, since w(v ₁) = 1 and w(v ₃) = 3.

The idea of our switching algorithms (see Algorithm 4) is as follows. As time goes on, the number of cleared trees increases. The guards which are not adjacent to any contaminated tree do not have to guard their designated locations anymore. In this case, we can let guards maneuver to improve the time efficiency of graph clear operation considerably.

Algorithm 4 requires H + N_g robots to capture all intruders. Note that the number of robots required to capture intruders using Algorithm 4 is equal to that required using Algorithm 2. Algorithm 4 was developed to improve the time efficiency of capturing intruders compared to Algorithm 2. Algorithm 4 lets a guarding robot move to capture intruders if the movement of the guard does not allow an intruder to escape.

Algorithm 4 is time efficient, since every tree graph in TreeSet can be cleared simultaneously using Algorithm 5. See line 28 in Algorithm 4. For example, assume that there are n tree graphs in TreeSet. Correspondingly, n groups of robots are selected to clear n tree graphs, respectively. n groups can run Algorithm 5 simultaneously to clear n tree graphs. In this way, time efficiency of Algorithm 4 increases significantly compared to the case where only H driving robots maneuver.

Algorithm 5.
Simultaneous clearing of every tree in $T r e e S e t$ .

Algorithm 4 is designed not to make a robot idle. Suppose that T_i is in TreeSet and that g_i is selected to clear T_i . Suppose that there are only a few intruders in T_i and that T_i is cleared before all trees in TreeSet are cleared. In this case, g_i must not be idle. Therefore, once g_i finishes clearing T_i , g_i begins to clear another contaminated tree in TreeSet. This process is presented in lines 5–8 of Algorithm 5.

Lemma 2

Consider the intruder capturing strategy using Algorithm 4. Suppose we choose n groups of robots (g ₁,g ₂,…,g_n ) to clear every tree graph (T ₁,T ₂,…,T_n ) in TreeSet. The role of g_i , ith group of robots, is to capture intruders in T_i where i ≤ n. Using Algorithm 5, g_i , $\forall i \leq n$ , clears T_i in finite time.

Proof

Suppose we choose n groups of robots (g ₁,g ₂,…,g_n ) to clear every tree graph (T ₁,T ₂,…,T_n ) in TreeSet. The role of g_i , ith group of robots, is to capture intruders in T_i where i ≤ n. The location of each robot in g_i , $\forall i \leq n$ , is not adjacent to T_i or to any tree in TreeSet. See line 16 in Algorithm 4. Thus, even if every robot in g_i leaves its location to clear T_i using Algorithm 5, no intruder can sneak into T_i or into any tree in TreeSet. According to Algorithm 6, g_i captures every intruder in T_i one by one. Thus, T_i is cleared in finite time.

Algorithm 6.
$g_{i}$ .CLEAR( $T_{k}$ )

Lemma 3

Consider the intruder capturing strategy using Algorithm 4. Once a tree graph is cleared, no intruder can sneak into the tree graph again.

Proof

Suppose we choose one group of robots, say g_u , to capture all intruders in one contaminated tree graph, say $T_{u} \in G_{T}$ . In Algorithm 4, both S_f and S_g are initialized as the set of robots, which are not adjacent to any contaminated tree. See lines 7 and 9 in Algorithm 4. Thus, the position of each robot in g_u is not adjacent to any contaminated tree. This implies that guards adjacent to a contaminated tree do not move at all. Thus, as every robot in g_u leaves its position to clear T_u , no intruder can sneak into any cleared tree graph.

Thus, once a tree graph is cleared, no intruder can sneak into the tree graph again.

Theorem 3

Using Algorithm 4, all intruders are captured in finite time.

Proof

Suppose we choose one group of robots, say g_i , to capture all intruders in one contaminated tree graph, say $T_{i} \in G_{T}$ . According to Lemma 2, g_i captures every intruder in T_i one by one. Moreover, according to Lemma 3, once T_i is cleared, no intruder can sneak into T_i again.

Suppose that there is at least one contaminated tree as i in Algorithm 4 is set to 1. We prove that as i in Algorithm 4 changes from 1 to L + 1, TreeSet contains at least one contaminated tree. This further indicates that the number of cleared trees increases, since every tree in TreeSet is cleared simultaneously using Algorithm 5.

We prove that as i in Algorithm 4 increases from 1 to L + 1, TreeSet contains at least one contaminated tree. Suppose that i in Algorithm 4 has been increasing from 1 to l. Suppose that T_l is contaminated and that TreeSet has been empty until i reaches l. Whenever TreeSet is empty, S contains S_f , additional H driving robots which are not adjacent to any tree graph in G_T . See line 7 in Algorithm 4. Driving robots in S_f are not adjacent to any tree graph in $G_{T} \ ({T_{l}})$ . Hence, T_l is added to TreeSet. We proved that as i in Algorithm 4 increases to L + 1, TreeSet contains T_l which is contaminated.

Recall that we have $s_{I} (G_{l}) \geq H$ using Lemma 1. Since Algorithm 4 requires H + N_g robots to capture all intruders, we obtain the following theorem using lemma 1.

Theorem 4

The number of robots required to clear G_l is between H and H + N_g .

MATLAB simulations

We provide MATLAB simulations to verify the effectiveness of our approach. This article considers a simplified environment where robots and worst-case intruders move along a weighted graph, which is a topological map of the environment. As a topological map of the environment, this article utilizes the Voronoi diagram in the study by Kim et al.⁴⁴ In robotics, Voronoi diagrams have been widely utilized as topological maps.^44
–46 In the Voronoi diagram, a Voronoi edge is the set of points which are equidistant from the two closest obstacles. A Voronoi vertex is a point where more than two Voronoi edges meet. See Kim et al.⁴⁴ for the definition of the Voronoi diagram.

Simple obstacle environments

We first consider simple obstacle environments. The obstacle boundaries are shown in thick red curves in Figure 7. We build the Voronoi edge (green circles in Figure 7) using the exploration algorithms in the study by Kim et al.⁴⁴

Figure 7.
We build the Voronoi edge (green circles) using the exploration algorithms in the study by Kim et al.⁴⁴

Figure 8 shows the weight of each Voronoi edge. Each Voronoi edge has its associated number as depicted in Figure 7. We first present several concepts before presenting how we set the weight of every edge e in Figure 8. Let O indicate an obstacle boundary. $c \in O$ is a point on an obstacle boundary O, and $p \in e$ is a point on an edge e. In Figure 7, $p \in e$ is depicted with green circles, and $c \in O$ is a point on thick red curves. Considering an arbitrary real number d, $⌈ d ⌉$ indicates the ceil operator to return an integer i satisfying that d ≤ i < d + 1.

Figure 8.
The weight of each Voronoi edge, considering the scenario in Figure 7.

In Figure 8, the weight of an edge e is set as follows.

$w (e) = ⌈ max_{c \in O, p \in e} ∥ c - p ∥ ⌉$
2

Here, $∥ c - p ∥$ is an L ₂ (Euclidean) norm. $∥ c - p ∥$ is the relative distance between c and p. ${max}_{c \in O, p \in e} ∥ c - p ∥$ in w(e) is the maximum distance between an obstacle boundary and the edge e. As the weight of an edge increases, the passage associated to the edge gets wider. This is reasonable, since we need more robots to sweep a passage as the passage gets wider. Also, we set the weight of a Voronoi vertex as one.

Considering the Voronoi diagram in Figures 7 and 8, we have H = 5, and N_g = 2. In Figure 7, a guarded vertex is marked with blue color. We can let H = 5 robots move to capture a visible intruder one by one, while two robots guard two vertices with blue color. In total, we use N_g + H = 7 robots to capture every intruder. Since H = 5 robots cannot clear the Voronoi diagram due to a cycle in the graph, we need at least 6 robots to clear the graph.

We next verify the effectiveness of our intruder capturing algorithms. We generate one worst-case intruder in the Voronoi diagram G_l in Figure 7. Since all cycles are blocked, the intruder is constrained to stay in a tree, say T_i . g_f moves along T_i and visit vertices sequentially to capture the intruder. On the other hand, the intruder moves along T_i with unbounded speed to escape from g_f . Whenever g_f visits a Voronoi vertex, the intruder moves along T_i with unbounded speed to maximize its distance from g_f . Since T_i is a tree, the intruder must be captured in finite time. The total traversal distance of g_f until capturing this intruder is 38 distance units.

Complicated obstacle environments

We next consider complicated obstacle environments. The obstacle boundaries are shown in thick red curves in Figure 9. We build the Voronoi edge (green circles in Figure 9) using BE algorithms in the study by Kim et al.⁴⁴

Figure 9.
We consider complicated obstacle environments. We build the Voronoi edge (green circles) using BE algorithms in the study by Kim et al.⁴⁴

Figure 10 shows the weight of each Voronoi edge. Each Voronoi edge has its associated number as depicted in Figure 9. The weight of a Voronoi edge is set using equation (2). Also, we set the weight of a Voronoi vertex as one.

Figure 10.
The weight of each Voronoi edge, considering the scenario in Figure 9.

Considering the Voronoi diagram in Figures 9 and 10, we have H = 8, and N_g = 3. In Figure 9, a guarded vertex is marked with blue color. We can let H = 8 robots move to capture a visible intruder one by one, while three robots guard three vertices with blue color.

In total, we use N_g + H = 11 robots to capture every intruder. Since H = 8 robots cannot clear the Voronoi diagram due to a cycle in the graph, we need at least 9 robots to clear the graph.

We next verify the effectiveness of our intruder capturing algorithms. We generate one worst-case intruder in the Voronoi diagram G_l in Figure 9. Since all cycles are blocked, the intruder is constrained to stay in a tree, say T_i . g_f moves along T_i and visit vertices sequentially to capture the intruder. Whenever g_f visits a Voronoi vertex, the intruder moves along T_i with unbounded speed to maximize its distance from g_f . The total traversal distance of g_f until capturing this intruder is 73 distance units.

Conclusions

Consider a team of robots deployed to capture worst-case intruders in an environment. We simplify the scenario such that robots and intruders move along a topological map of the environment, represented by a weighted graph G_l . We introduce weighted graph searching algorithms to capture every visible intruder. We then derive the minimum number of robots required to clear a weighted tree graph. Considering a general weighted graph, we derive bounds for the number of robots required. Finally, we present switching algorithms to improve the time efficiency of capturing intruders while not increasing the number of robots.

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) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by Cooperative RnD between Industry, Academy, and Research Institute funded Korea Ministry of SMEs and Startups in 2019 [Grant No. S2658135].

ORCID iD

Jonghoek Kim

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 fifth international conference on mobile systems, applications and services (MobiSys 07), San Juan, Puerto Rico, 11–13 June 2007, pp. 85–98. ACM.

Liu

Xie

. Automatic and robust breadcrumb system deployment for indoor firefighter applications. In: Proceedings of the eighth international conference on mobile systems, applications, and services (MobiSys 10), San Francisco, California, USA, 15–18 June 2010, pp. 21–34. ACM.

Kim

. Cooperative exploration and networking while preserving collision avoidance. IEEE Trans Cybern 2016; 47: 1–11.

Kim

. Capturing intruders based on Voronoi diagrams assisted by information networks. Int J Adv Robot Syst 2017; 14: 1–8.

Ong

SCW

Png

Hsu

. Planning under uncertainty for robotic tasks with mixed observability. Int J Robot Res 2010; 29(8): 1053–1068.

Chung

Hollinger

Isler

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

Sato

Royset

. Path optimization for the resource-constrained searcher. Nav. Res.Logist. 2010; 57(5): 422–440.

Hohzaki

. Discrete search allocation game with false contacts. Nav. Res. Logist. 2007; 54(1): 46–58.

10.

Kress

Lin

Szechtman

. Optimal discrete search with imperfect specificity. Math Method Oper Res 2008; 68(3): 539–549.

11.

Hollinger

Singh

Djugash

. Efficient multi-robot search for a moving target. Int J Robot Res 2009; 28(2): 201–219.

12.

Bourgault

Furukawa

Durrant-Whyte

. Optimal search for a lost target in a Bayesian world. Field Service Robot 2006; 24: 209–222.

13.

McCue

. U-boats in the bay of biscay: an essay in operations analysis. Washington, DC: National Defense University Press, 1990.

14.

Parsons

. Pursuit-evasion in a graph. In: Theory and applications of graphs. Lecture notes in mathematics. Berlin, Heidelberg: Springer-Verlag 1978, Vol. 642, pp. 426–441.

15.

Megiddo

Hakimi

Garey

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

16.

Kolling

Carpin

. The graph-clear problem: definition, theoretical properties and its connections to multirobot aided surveillance. In: Proceeding of the 2007 IEEE/RSJ international conference on intelligent robots and systems, San Diego, CA, USA, 29 October–2 November 2007, pp. 1003–1008.

17.

Lapaugh

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

18.

Fomin

Fraigniaud

Nisse

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

19.

Barriére

Barri Ere

Flocchini

. Capture of an intruder by mobile agents. In: Proceeding of the 14th annual ACM symposium on parallel algorithms and architectures, Winnipeg, Manitoba, Canada, 10–13 August 2002, pp. 200–209.

20.

Fomin

Thilikos

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

21.

Dereniowski

Dyer

. On minimum cost edge searching. Theory Comput Sci 2013; 495: 37–49.

22.

Lelia

Burman

Nisse

. Exclusive graph searching. Algorithmica 2017; 77(3): 942–969.

23.

Jeong-Ok

Georges

Mauro

. On a pursuit-evasion model without instantaneous movement. Austr J Combin 2016; 64(3): 392–419.

24.

Makedon

Sudborough

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

25.

Lefteris

Papadimitriou

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

26.

Lefteris

Papadimitriou

. Searching and pebbling. Theory Comput Sci 1986; 47: 205–218.

27.

Bienstock

Seymour

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

28.

Dendris

Kirousis

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

29.

Seymour

Thomas

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

30.

Richerby

Thilikos

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

31.

Bodlaender

Gilbert

Hafsteinsson

. Approximating treewidth, pathwidth, and minimum elimination tree height. J Algorithms 1991; 18:238–255.

32.

Kolling

Carpin

. Pursuit-evasion on trees by robot teams. IEEE Trans Robot 2009; 26: 32–47.

33.

Kolling

Carpin

. Extracting surveillance graphs from robot maps. In: Proceeding of intelligent robots and systems, Nice, France, 22–26 September 2008, pp. 2323–2328.

34.

Richard

Tovey

Koenig

. Algorithms and complexity results for graph-based pursuit evasion. Auton Robot 2011; 31: 317.

35.

Vineet

Berman

Fujito

. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In: Proceedings of the sixth international symposium on algorithms and computation, Australia, 4–6 December 1995, pp. 142–151.

36.

Carrabs

Cerulli

Gentili

. A linear time algorithm for the minimum weighted feedback vertex set on diamonds. Inform Process Lett 2005; 94: 29–35.

37.

Tang

. A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inform Process Lett 1997; 61: 107–111.

38.

Chang

Liang

. Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Inform 1997; 34: 337–346.

39.

Liang

. On the feedback vertex set problem in permutation graphs. Inf Process Lett 1994; 52: 123–129.

40.

Douglas

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

41.

Kolling

Carpin

. Surveillance strategies for target detection with sweep lines. In: Proceeding of intelligent robots and systems, St. Louis, MO, USA, 10–15 October 2009, pp. 5821–5827.

42.

Alonso-Mora

Montijano

Schwager

. Distributed multi-robot formation control among obstacles: a geometric and optimization approach with consensus. In: 2016 IEEE international conference on robotics and automation (ICRA), Stockholm, Sweden, 16–21 May 2016, pp. 5356–5363. IEEE.

43.

Vijay

. Approximation algorithms. New York, NY: Springer, 2010.

44.

Kim

Zhang

Egerstedt

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

45.

Choset

Walker

Eiamsa-Ard

. Sensor-based exploration: incremental construction of the hierarchical generalized Voronoi graph. Int J Robot Res 2000; 19(2): 126–148.

46.

Choset

Burdick

. Sensor based planning, Part I: the generalized Voronoi graph. In: Proceeding of the IEEE international conference on robotics and automation, Nagoya, Japan, 21–27 May 1995, pp. 1649–1655.

Intruder capture algorithms considering visible intruders

Abstract

Keywords

Introduction

Preliminary information

Graph theory

Problem description

Non-monotone searching algorithms

Lemma 1

Proof

Theorem 1

Proof

Theorem 2

The switching search algorithms

Lemma 2

Proof

Lemma 3

Proof

Theorem 3

Proof

Theorem 4

MATLAB simulations

Simple obstacle environments

Complicated obstacle environments

Conclusions

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References