An Algorithm for
Limited Visibility Graph Searching
Ath. Kehagias and A.C. Papazoglou

We study a graph search problem in which a team of searchers
attempts to find a mobile target located in a graph. Assuming
that (a) the visibility field of the searchers is limited, (b) the
searchers have unit speed and (c) the target has infinite speed, we formulate
the Limited Visibility Graph Search (LVGS) problem and present the
LVGS algorithm, which produces a search schedule guaranteed to find
the target in the minimum possible number of steps. Our LVGS algorithm is a
“conversion” of Guibas and Lavalle's
polygonal region search algorithm .

§ INTRODUCTION

In graph search problems a team of searchers attempts to find a
mobile target located in a graph. Depending on the properties of the
searchers and target, different variants of the problem are obtained.

In the current paper we study a graph searching variant in which it is assumed
that: (a) the visibility field of the searchers is limited (i.e., from
any given position they can see only part of the graph, as described by a
visibility matrix), (b) the searchers have unit speed and (c) the
target has infinite speed[These terms will be defined precisely in a
later section.]. We formulate, under these assumptions, the Limited
Visibility Graph Search (LVGS) problem and present an LVGS algorithm which,
given the adjacency and visibility matrices, produces a search schedule
guaranteed to find the target (if this is possible) in the minimum possible
number of steps. Our LVGS algorithm is a “conversion” of the polygonal region search algorithm
presented in <cit.>.

The seminal papers for graph search problems are <cit.> and
<cit.>. The basic ideas of these two works have been elaborated
and extended in a large number of papers[It is worth emphasizing that
in this formulation of the problem a worst-case analysis is adopted, by which
the target is essentially “factored out” of
the problem; i.e., the only decision maker is the searcher. This point will be
further explained in later sections.]; excellent reviews of the relevant
literature appear in <cit.> and <cit.>. A large number
of graph search algorithms have been presented in the literature; see for
. These algorithms usually depend on path- or tree-decompositions of the graph
(and related methods) resulting in rather complicated implementation; in
addition, the majority of the above works concerns the zero-visibility
case, i.e., when the searchers can only see the vertex in which they are
located. Furthermore, the search schedules studied in the graph theoretic
literature often allow a searcher to move between non-adjacent vertices (i.e.,
not necessarily following the edges of the graph). This movement mode is
called “teleporting” and is not appropriate
for most realistic applications. Relatively little has been published
<cit.> on non-teleporting
search, i.e., where the searchers move only along the graph edges. Some
related approaches appear in the robotics literature, for example in
<cit.>, where it is
usually assumed that the target is invisible but has finite speed.

A related, but different, approach to limited visibility graph searching can
be obtained in the context of pursuit games in graphs[In this
formulation we are dealing with a game in which both the pursuers and
the evader are active decision makers. ]. These involve one or more
pursuers (i.e., searchers) who try to locate and capture an
evader (i.e., target); all agents are assumed to move along the edges
of the graph (and usually, but not always, with unit speed). The
“classic” version of this problem is the
Cops and Robbers Game (CR) first introduced in
<cit.>, in which it is assumed that the cops
(searchers) are always aware of the robber's (target's) location; so this is a
complete visibility problem. Many CR variants have been considered,
obtained by varying the abilities and restrictions placed on both the cops and
the robber. There is a large literature on the Cops and visibile
Robber problem, mainly concentrating on its theoretical aspects. An excellent
and recent review of the available work appears in the book
<cit.>. Algorithmic aspects of the problem are studied in
<cit.> and <cit.>.

The variant of an invisible or partially visible robber is quite
close to the previously mentioned LVGS problem. The cops (resp. the
robber) play a role similar to that of the searchers (resp. target); note,
however, the distinction between seeing and capturing the
robber. Relatively little work has been done on this problem. The first
formulation appears in <cit.>. Further progress was achieved in the
Master's theses <cit.> and, recently, in
<cit.> (for the zero-visibility case) and in
<cit.> (for the general case, which includes zero- and
complete-visibility as special cases). A somewhat different approach to the
invisible robber appears in <cit.> and a related
computational approach is presented in <cit.>.

The approach we follow in the current paper is rather different from all of
the above. As already mentioned, our formulation and solution of the problem
are based on the ideas of <cit.>, which studies search
of a continuous polygonal environment. This approach and
generalizations to various geometric environments is presented more
extensively in the excellent book <cit.>.

In contrast to the previously mentioned treatments of graph search and
pursuit, our LVGS algorithm is relatively simple to implement, produces
non-teleporting search schedules and can be applied not only to
zero-visibility but to arbitrary visibility specifications. On the
other hand, while the algorithm can be applied to any number $K$ of searchers,
the computational burden increases quickly with $K$. In short, the main
usefulness of the LVGS algorithm is in solving the graph search problem under
the following conditions.

* One searcher is attempting to locate the target in a graph.

* Both searcher and target move only along the edges of the graph; the
searcher moves with unit speed while the target moves with infinite speed.

* The visibility of the target is determined by the visibility
matrix $B$.

The paper is organized as follows. In Section <ref> we introduce
preliminary definitions and notations. In Section <ref> we formulate the
LVGS problem and present the LVGS algorithm. Section <ref> is devoted
to the evaluation of the algorithm by numerical experiments. Finally, in
Section <ref>  we summarize our work and propose directions for further research.

§ PRELIMINARIES

We use the following set theoretic notation.

* Given a set $U$, the cardinality of $U$ is denoted by $\left\vert
U\right\vert $ and defined to be the number of elements of $U$. So, if
$U=\left\{  u_{1},...,u_{N}\right\}  $ then $\left\vert U\right\vert =N$.

* Given sets $U,W$ we define the set difference $U\backslash W$ by

\[
U\backslash W=\left\{  u:u\in U\text{ and }u\not \in W\right\}  .
\]

* Given a reference set $U=\left\{  u_{1},...,u_{N}\right\}  $, any set
$W\subseteq U$ can be described by its indicator vector $\mathbf{w}%
=\left[  w_{1},w_{2},...,w_{N}\right]  $ where

\[
\forall n\in\left\{  1,...,N\right\}  :w_{n}=\left\{
\begin{array}
1 & \text{iff }u_{n}\in W,\\
0 & \text{iff }u_{n}\not \in W.
\end{array}
\right.
\]

We use the following graph theoretic definitions and notation.

* A graph is a pair $G=\left(  V,E\right)  $, where the
vertex set is $V=\left\{  x_{1},x_{2},...,x_{N}\right\}  $ and the
edge set $\ $is

\[
E\subseteq\left\{  \left\{  x,y\right\}  :x,y\in V\text{, }x\neq y\right\}  ;
\]

a directed graph is a pair $G=\left(  V,E\right)  $, where the
vertex set is $V=\left\{  1,2,...,N\right\}  $ and the edge set
$\ $is

\[
E\subseteq\left\{  \left(  x,y\right)  :x,y\in V\text{, }x\neq y\right\}  .
\]

In both of the above cases we usually (but not always) take the node set to
be $V=\left\{  1,2,...,N\right\}  $.

* For graph $G=\left(  V,E\right)  $ and vertex $x\in V$:

\begin{align*}
\text{the \emph{neighborhood} of }x\text{ is}  &  :N\left(  x\right)
=\left\{  y:\left\{  x,y\right\}  \in E\right\}  ,\\
\text{the \emph{closed neighborhood} of }x\text{ is}  &  :N\left[  x\right]
=N\left(  x\right)  \cup\left\{  x\right\}  .
\end{align*}

* For graph $G=\left(  V,E\right)  $ with $\left\vert V\right\vert
=N$, the adjacency matrix of $G$ is an $N\times N$ matrix $A$ defined

\[
\forall x,y\in V:A_{xy}=\left\{
\begin{array}
1 & \text{iff }\left\{  x,y\right\}  \in E,\\
0 & \text{iff }\left\{  x,y\right\}  \not \in E.
\end{array}
\right.
\]

For directed graph $G=\left(  V,E\right)  $ with $\left\vert
V\right\vert =N$, the adjacency matrix of $G$ is an $N\times N$ matrix
$A$ defined by

\[
\forall x,y\in V:A_{xy}=\left\{
\begin{array}
1 & \text{iff }\left(  x,y\right)  \in E,\\
0 & \text{iff }\left(  x,y\right)  \not \in E.
\end{array}
\right.
\]

A graph $G=\left(  V,E\right)  $ is uniqely specified by its adjacency matrix;
hence in what follows we will sometimes say “the graph
$A$”. The same is true of a directed graph.

* For graph $G=\left(  V,E\right)  $ with $\left\vert V\right\vert
=N$, a visibility matrix for $G$ is an $N\times N$ matrix $B$ defined

\[
\forall x,y\in V:B_{xy}=\left\{
\begin{array}
1 & \text{iff }y\text{ can be seen from }x,\\
0 & \text{iff }y\text{ cannot be seen from }x.
\end{array}
\right.
\]

§ THE LVGS PROBLEM AND ALGORITHM

We start with an informal description of the LVGS problem.

* We are given: the graph $G=\left(  V,E\right)  $, specified by its
adjacency matrix $A$, and a visibility matrix $B$ for $G$.

* At time $t=0$ we place each of $K$ searchers at a graph vertex (a vertex
can contain any number of searchers). It is also assumed that a target is
located at some unknown graph vertex.

* At discrete time steps $t\in\left\{  1,2,\ldots\right\}  $ we can move
each searcher to a vertex neighboring his current position.

* The following assumptions are made for each time step $t\in\left\{
0,1,2,\ldots\right\}  .$

* The visibility matrix $B$ is similar to the adjacency matrix $A$. Just
like an agent located at vertex $x$ can move to vertex $y$ iff
$A_{xy}=1$, similarly, an agent located at vertex $x$, can see vertex
$y$ (and its contents) iff $B_{xy}=1$.

* The target will always move to a vertex $z$ which is not seen by any
searcher, provided there is a path from his current vertex to $z$
which does not pass through a  searcher-visible vertex.

* The process ends when the target is in a vertex which can be observed by
the searchers (the target is observed, the graph is “cleared”).

* Our goal is to clear the graph in the shortest possible number of steps.

To provide a precise mathematical formulation of the above
description, we introduce the following.

For each $t\in\left\{  1,2,\ldots\right\}  $ we
define the position vector by

\[
\mathbf{x}(t)=[x_{1}(t),\ldots,x_{K}(t)],
\]

where $x_{k}(t)\in V$ is the position of the $k$-th searcher at time $t$. For
all $t\geq1$, we have $\mathbf{x}(t)\in\mathbf{X}=V^{K}$.

We also introduce the null position vector $\lambda$; hence
we write $\mathbf{x}(0)=\lambda$ to indicate that, at $t=0$, no searchers have
been placed on the graph.

If a vertex may contain the target, the
vertex is called dirty, otherwise it is called clear.

When a vertex $x$ is seen by a searcher it is cleared; it remains clear
as long as there is no “free” (i.e.,
invisible to the searchers) path from $x$ to a dirty vertex. If, at some time,
a path from a clear vertex $x$ to a dirty vertex $y$ becomes invisible to the
searchers, then $x$ becomes dirty again (is recontaminated). We will
denote the set of all dirty (resp. clear) vertices at time $t$ by $D\left(
t\right)  $ (resp. by $C\left(  t\right)  $). We can describe sets by their
indicator vectors; we will denote the indicator vector of $D\left(
t\right)  $ by

\[
\mathbf{d}\left(  t\right)  =[d_{1}\left(  t\right)  ,d_{2}\left(  t\right)
,...,d_{N}\left(  t\right)  ].
\]

More precisely, we have the following.

For each $t\in\left\{  0,1,2,\ldots\right\}  $ we
define the contamination vector by

\[
\mathbf{d}\left(  t\right)  =[d_{1}\left(  t\right)  ,d_{2}\left(  t\right)
,...,d_{N}\left(  t\right)  ]
\]

\[
\forall t,n:d_{n}\left(  t\right)  =\left\{
\begin{array}
1 & \text{iff vertex }n\text{ is dirty at time }t\text{,}\\
0 & \text{iff vertex }n\text{ is clear at time }t\text{.}%
\end{array}
\right.
\]

We set $\mathbf{d}\left(  0\right)  =\left[  1,...,1\right]  $, i.e., at $t=0$
all vertices are dirty.

Next we define the state vector, which contains all the
information relevant to the graph search.

For each $t\in\left\{  0,1,2,\ldots\right\}  $ we
define the state vector by

\[
\mathbf{z}(t)=\left[  x_{1}(t),...,x_{K}(t),d_{1}(t),...,d_{N}(t)\right]
=\left[  \mathbf{x,d}\right]  .
\]

For all $t\geq1$, we have $\mathbf{x}(t)\in V^{K}\times\left\{  0,1\right\}
^{N}$. Taking in account $t=0$, the state space (set of all possible
states) is

\[
\mathbf{Z}=\left(  V^{K}\times\left\{  0,1\right\}  ^{N}\right)  \cup\left\{
\left[  \lambda,1,...,1\right]  \right\}  .
\]

It is assumed that, at every time $t$, the “search
planner” knows $\mathbf{z}(t)$; i.e., he knows the location
of all searchers and the possible locations of the target.

The clear states are the elements of
$\mathbf{Z}$ which have the form

\[
\mathbf{z}=\left[  \mathbf{x,}\left[  0,...,0\right]  \right]  ,
\]

and the set of all clear states will be denoted by $\mathbf{Z}_{C}$. The set
of all dirty states is

\[
\mathbf{Z}_{D}=\mathbf{Z}\backslash\mathbf{Z}_{C}%
\]

and the dirty states are the elements of $\mathbf{Z}_{D}$.

The control vector is

\[
\mathbf{u}(t)=[u_{1}(t),\ldots,u_{K}(t)]
\]

where $u_{k}(t)$ denotes the position to which the $k$-th searcher will be
moved at time $t+1$ (so at $t+1$ the $k$-th searcher will be located at
$x_{k}(t+1)=u_{k}(t)$). Of course moves must be legal, i.e.,

\begin{equation}
\forall t,k:\left\{  x_{k}(t),u_{k}(t)\right\}  \in{E}. \label{eq0301}%
\end{equation}

To specify the “search evolution equation
” we first define star-multiplication $\ast$ as follows.

Given the $L\times M$ matrix $P$ and the $M\times
N$ matrix $Q$ we define the $L\times N$ matrix $P\ast Q$ as follows

\[
\forall l\in\{1,2,\ldots,L\},n\in\{1,2,\ldots,N\}:\left(  P\ast Q\right)
\]

When the target's speed is equal to $s$ (i.e., at every time step he can
traverse $s$ edges) and assuming that no searchers exist in the graph, we
have the following equation for the evolution of the dirty
set[If the target is arbitrarily fast, then it suffices to
set $s=N$, the number of vertices in the graph.]

\[
\mathbf{d}(t+1)=\mathbf{d}(t)\ast A\underset{s\text{ times}}{\ast\cdots\ast}A
\]

Now suppose a single searcher is placed at vertex $u_{1}$ . The searcher
blocks certain paths which, if taken by the target, would result in his being
observed. In particular, the target will not move into any vertex which
belongs to the visibility field of the searcher; similarly, the target will
not move out of any vertex in the visibility field. Similar rules hold in case
$K$ searchers are located in the graph.

To model this situation, we introduce the modified adjacency matrix
$\overline{A}\left(  \mathbf{u}\right)  $. It describes the vertices into
which the target can move without being observed by searchers located at
positions $\mathbf{u}=\left[  u_{1},...,u_{K}\right]  $. In other words,
$\overline{A}\left(  \mathbf{u}\right)  $ is the adjacency matrix of the graph
$\overline{G}\left(  \mathbf{u}\right)  $ obtained by removing from the graph
$G$ the vertices which lie in the visibility region of the searchers (and all
their incident edges).

The modified adjacency matrix $\overline
{A}\left(  \mathbf{u}\right)  $, where $\mathbf{u=}\left[  u_{1}%
,...,u_{K}\right]  $, is defined as follows

\[
\forall x,y:\overline{A}_{xy}\left(  \mathbf{u}\right)  =\left\{
\begin{array}
A_{xy}\text{ } & \text{iff: }\forall k\in\left\{  1,2,...,K\right\}  :\left\{
x,y\right\}  \cap N\left[  u_{k}\right]  =\emptyset\text{,}\\
0 & \text{otherwise.}%
\end{array}
\right.
\]

Putting all of the above pieces together we can write an equation which
specifies the next state of the graph search, given the current state and control.

The graph search evolution equation (or
simply the evolution equation) is

\begin{align}
\mathbf{x}(t+1)  &  =\mathbf{u}(t),\label{eq0302}\\
\mathbf{d}(t+1)  &  =\mathbf{d}(t)\ast\overline{A}(\mathbf{u}(t))\underset
{s\text{ times}}{\ast\cdots\ast}\overline{A}(\mathbf{u}(t)). \label{eq0303}%
\end{align}

Now we are ready to formally define a preliminary version of
the LVGS problem as follows.

(Preliminary LVGS Problem) Given $A$ and $B$ choose,
subject to (<ref>)-(<ref>), the minimum $T$ and respective
$\mathbf{u}(0),...,\mathbf{u}(T-1)$ such that $\left[  \mathbf{x}(T),\mathbf{d}(T)\right]
\in \mathbf{Z}_{C}$.

This problem can be solved by graph theoretic methods. Consider the directed
graph $G^{\prime}=\left(  V^{\prime},E^{\prime}\right)  $ where the vertices
are the previously defined states (i.e., $V^{\prime}=\mathbf{Z}$) and the
edges correspond to valid state (i.e., an edge $\left(  \mathbf{z}%
_{1},\mathbf{z}_{2}\right)  $ denotes that we can make a transition from
$\mathbf{z}_{1}=\left(  \mathbf{x}_{1},\mathbf{d}_{1}\right)  $ to
$\mathbf{z}_{2}=\left(  \mathbf{x}_{2},\mathbf{d}_{2}\right)  $). Then we can
solve the LVGS problem by finding a shortest path from the vertex $\left(
\lambda,\left[  1,...,1\right]  \right)  $ to some vertex of the form
$\left(  \mathbf{x},\left[  0,...,0\right]  \right)  \in\mathbf{Z}_{C}$, which
can be solved by, e.g., Dijkstra's algorithm.

However, in the above formulation the size of $\mathbf{Z}$ is $\left\vert
\mathbf{Z}\right\vert =\left\vert V\right\vert \cdot2^{\left\vert V\right\vert
}+1$ which grows exponentially. For instance, when the original $G$ has
$\left\vert V\right\vert =10$ vertices and we employ a single searcher
($K=1$), then $\left\vert \mathbf{Z}\right\vert =10\cdot2^{10}+1=\allowbreak
10\,241$; with $\left\vert V\right\vert =20$ vertices and a single searcher we
have $\left\vert \mathbf{Z}\right\vert =20\cdot2^{20}+1=\allowbreak

Consequently, in what follows we will introduce a different approach (inspired
from <cit.>) which can achieve the same goal (reaching
an all-clear state) using a much smaller directed graph $G_{I}$, the
“information state graph”; $G_{I}$
describes how the contamination of $G$ (i.e., the possible locations of the
target) changes as the searcher moves in $G$.

To describe the structure of $G_{I}$, we consider the evolution of
contamination as the searchers move through $G$. For the sake of simplicity we
will consider the case of a single searcher (the extension to the case of many
searchers is straightforward). Supposing that the searcher is located on some
vertex $x$, then

* we have a visible component, defined to be the subgraph induced
by the vertices which are visible to the searcher;

* unless the search problem is trivial, we will also have some
invisible components, defined to be the connected components of the
graph obtained by removing the visible component; by this definition, the
vertices of the invisible components cannot be seen by the searcher.

Hence, given $A$ and $B$, and for every $x\in V$, we have a
visible component and one or more invisible components
[Strictly speaking, the components are subgraphs of $G$ but, since
$G$ is given, they are fully specified by their vertex sets. Hence
“components” will also be used to refer to
the corresponding vertex sets.]. By definition, the vertices in the searcher's
visible component are clear. On the other hand, some of the vertices of the
invisible components may be contaminated. Suppose that at some time the
searcher is located at vertex $x$, resulting at the partition of $V$ into $M$
invisible components (we can omit the visible component, since it will always
be clear); the contamination of the components is encoded by a vector
$\widehat{\mathbf{d}}=\left[  \widehat{d}_{1},...,\widehat{d}_{M}\right]  $,
where $\widehat{d}_{m}$ equals $0$ (resp. $1$) iff the $m$-th component is
clear (resp. dirty).[Note that the size of $\widehat{\mathbf{d}}$ is
not fixed since, for different searcher positions, we will have a different
number of visibility components.] The pair $\widehat{\mathbf{z}}%
=(x,\widehat{\mathbf{d}})$ will be called the information state and
gives us all the needed information about the current state of the search.

Let us clarify the above ideas with an example.
Consider the tree of Figure <ref>. Assume a single searcher with a
visibility range of $L=1$ (i.e., he can see all the vertices which are at
distance at most one from his current position). Consequently, the visibility
matrix is

\[
\begin{array}
1 & 1 & 1 & 0 & 0 & 0 & 0\\
1 & 1 & 0 & 1 & 1 & 0 & 0\\
1 & 0 & 1 & 0 & 0 & 1 & 1\\
0 & 1 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 1
\end{array}
\right]
\]

Assume the searcher is located on vertex $1$; then he can see vertices $1,2$
and $3$. Hence, as can be seen in Figure <ref>, the visible component
is $V_{1}=\left\{  1,2,3\right\}  $ and the invisible components are
$V_{2}=\left\{  4\right\}  $,$\ V_{3}=\left\{  5\right\}  $, $V_{4}=\left\{
6\right\}  $, and $V_{5}=\left\{  7\right\}  $.

figureA graph  to be searched.

figureVisible and invisible components of the graph when the searcher is at vertex 4
and has straight line visibility (he  can see vertices 1, 2 and 3).

Now suppose the searcher performs the following search schedule:
(2)=1\rightarrow$ $\mathbf{u}(3)=3$. Then we have the following evolution of
clear and contaminated components (in the third column, the visible component
verices are listed in italics).

\begin{align*}
\begin{tabular}
Time & Pursuer Location & Visibility Components & Contamination Vector &
Information state\\\hline
$0$ & $\lambda$ & $\left\{  1,2,...,7\right\}  $ & $\left(  1\right)  $ &
$\left(  \lambda,\left(  1\right)  \right)  $\\\hline
$1$ & $1$ & $\left\{  \emph{1,2,3}\right\}  ,\left\{  4\right\}  ,\left\{
5\right\}  ,\left\{  6\right\}  ,\left\{  7\right\}  $ & $\left(
1,1,1,1\right)  $ & $\left(  1,\left(  1,1,1,1\right)  \right)  $\\\hline
$2$ & $2$ & $\left\{  \emph{1,2,4,5}\right\}  ,\left\{  3,6,7\right\}  $ &
$\left(  1\right)  $ & $\left(  2,\left(  1\right)  \right)  $\\\hline
$3$ & $1$ & $\left\{  \emph{1,2,3}\right\}  ,\left\{  4\right\}  ,\left\{
5\right\}  ,\left\{  6\right\}  ,\left\{  7\right\}  $ & $\left(
0,0,1,1\right)  $ & $\left(  1,\left(  0,0,1,1\right)  \right)  $\\\hline
$4$ & $3$ & $\left\{  \emph{1,3,6,7}\right\}  ,\left\{  2,4,5\right\}  $ &
$\left(  0\right)  $ & $\left(  3,\left(  0\right)  \right)  $\\\hline
\end{tabular}
\ \ \ \ \ \ \\
&  \text{Table 1. Visibility components, contamination vectors and information
states for a walk through }\\
&  \text{the binary tree of depth 2, with visibility range }L=1\text{.}%
\end{align*}

The entries in the above table can be explained as follows.

* At $t=0$ the searcher is outside the graph. The single invisible
component contains all graph vertices.

* At $t=1$ the searcher moves to vertex $1$ and sees vertices $2,3$. All
of these form a single clear component; each of vertices $4,5,6,7$ forms a
separate component which is contaminated (may contain the target); hence the
contamination vector is $\left(  1,1,1,1\right)  $.

* At $t=2$ the searcher moves to vertex $2$. Now he sees vertices
$1,2,4,5$, all of which form a single clear component and the vertices $3,6,7$
forms a single contaminated component. Note that vertices $4$ and $5$ have
been cleared and vertex $3$ has been recontaminated. Hence the contamination
vector is $\left(  1\right)  $.

* At $t=3$ the searcher moves back to vertex $1$. The components are the
same as at time $t=1$, but now they are in a different contamination state,
namely, $\left(  0,0,1,1\right)  $. This is so because vertices $4$ and $5$
were previously clear and, though no longer directly visible, cannot be
recontaminated because the target cannot move from $6$ or $7$ to $4$ or $5$
without passing through the currently visible component $\left\{
1,2,3\right\}  $.

* Finally, at $t=4$ the searcher moves to vertex $3$. The components now
are $\left\{  1,3,6,7\right\}  $ (which is visible) and $\left\{
2,4,5\right\}  $ (which was clear and cannot be recontaminated). Hence the
contamination vector is $\left(  0\right)  $ and the graph has been cleared.

Note how the number of components and the vertices they include
change during the search; also note that the same components can, at different
times, be clear or contaminated depending on the search history.

The previous example employed “distance-based visibility”. Now we present an example with
“straight-line visibility”. Consider the
graph of Figure <ref> in which each vertex is supposed to be actually
located in the position indicated in the figure. Assume a single searcher with
straight-line visibility (i.e., he can see all the vertices which lie in a
straight-line path passing from his current vertex). Consequently, the
visibility matrix is

\[
\begin{array}
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1
\end{array}
\right]
\]

Assume the searcher is at vertex 4; then he can see vertices 3, 4, 5, 7, 8 and
9. Hence, as can be seen in Figure <ref>, the visible component is
$V_{1}=\left\{  3,4,5,7,8,9\right\}  $ and the invisible components are
$V_{2}=\left\{  1,2\right\}  $,$\ V_{3}=\left\{  6\right\}  $, $V_{4}=\left\{
10\right\}  $, and $V_{5}=\left\{  11,12\right\}  $.

figureA graph to be searched.

figureVisible and invisible components of the graph when the searcher is at vertex 4
(he  can see vertices 3, 4, 5, 7, 8 and 9).

Now suppose the searcher performs the following search schedule:
(2)=3\rightarrow$ $\mathbf{u}(3)=4$, $\mathbf{u}(4)=9\rightarrow
\mathbf{u}(5)=4\rightarrow\mathbf{u}(6)=5$.  Then we have the following
evolution of clear and contaminated components (in the third column, the
visible component verices are listed in italics).

\begin{align*}
\begin{tabular}
Time & Pursuer Location & Visibility Components & Contamination Vector &
Information state\\\hline
$0$ & $\lambda$ & $\left\{  1,2,...,12\right\}  $ & $\left(  1\right)  $ &
$\left(  \lambda,\left(  1\right)  \right)  $\\\hline
$1$ & $1$ & $\left\{  \emph{1,2}\right\}  ,\left\{  3,4,...,12\right\}  $ &
$\left(  1\right)  $ & $\left(  1,\left(  1\right)  \right)  $\\\hline
$2$ & $2$ & $\left\{  \emph{1,2,3}\right\}  ,\left\{  4,5,...,12\right\}  $ &
$\left(  1\right)  $ & $\left(  2,\left(  1\right)  \right)  $\\\hline
$3$ & $3$ & $\left\{  1\right\}  ,\left\{  \emph{2,3,4,9}\right\}  ,\left\{
5,6,7,8\right\}  ,\left\{  10\right\}  ,\left\{  11,2\right\}  $ & $\left(
0,1,1,1\right)  $ & $\left(  3,\left(  0,1,1,1\right)  \right)  $\\\hline
$4$ & $4$ & $\left\{  1,2\right\}  ,\left\{  \emph{3,4,5,7,8,9}\right\}
,\left\{  6\right\}  ,\left\{  10\right\}  ,\left\{  11,12\right\}  $ &
$\left(  0,1,1,1\right)  $ & $\left(  4,\left(  0,1,1,1\right)  \right)
$5$ & $9$ & $\left\{  1,2\right\}  ,\left\{  \emph{3,4,9,10,11,12}\right\}
,\left\{  5,6,7,8\right\}  $ & $\left(  0,1\right)  $ & $\left(  9,\left(
0,1\right)  \right)  $\\\hline
$6$ & $4$ & $\left\{  1,2\right\}  ,\left\{  \emph{3,4,5,7,8,9}\right\}
,\left\{  6\right\}  ,\left\{  10\right\}  ,\left\{  11,12\right\}  $ &
$\left(  0,1,0,0\right)  $ & $\left(  4,\left(  0,1,0,0\right)  \right)
$7$ & $5$ & $\left\{  1,2,3\right\}  ,\left\{  \emph{4,5,6,7,8}\right\}
,\left\{  9,10,11,12\right\}  $ & $\left(  0,0\right)  $ & $\left(  5,\left(
0,0\right)  \right)  $\\\hline
\end{tabular}
\ \ \ \ \ \ \\
&  \text{Table 2. Visibility components, contamination vectors and information
states for a walk through }\\
&  \text{the graph with straight line visibility.}%
\end{align*}

The reader can check that the search schedule clears the graph, which is also
seen by the final information state $\left(  5,\left(  0,0\right)  \right)  $.

We denote by $\widehat{\mathbf{Z}}$ the set of all information states
$(x,\widehat{\mathbf{d}})$ and by $\widehat{\mathbf{Z}}_{C}$ the set of all
clear information states $(x,\left[  0,...,0\right]  )$. There exists a
state transition function $F:\widehat{\mathbf{Z}}_{C}\times
V\rightarrow\widehat{\mathbf{Z}}_{C}$ which maps the current information state
and searcher move to the next information state:

\begin{equation}
\widehat{\mathbf{z}}\left(  t+1\right)  =F\left(  \widehat{\mathbf{z}}\left(
t\right)  ,u\left(  t\right)  \right)  . \label{eq0304}%
\end{equation}

While it is difficult to give a general description for $\widehat{\mathbf{Z}}$
and $F$,  they can be easily constructed algorithmically for a given graph
$G$. The information graph $G_{I}=\left(  V_{I},E_{I}\right)  $, has
$V_{I}=\widehat{\mathbf{Z}}$ and $E_{I}$ consists of the state transitions
which are described by the state transition function $F$.

In Figure <ref>.a we present the
information graph corresponding to the graph of Example <ref>, with
visibility range $L=1$. The information graph has $\left\vert V_{I}\right\vert
=36$ vertices; compare this to the  previously mentioned $V^{\prime
}$ which has $\left\vert V^{\prime}\right\vert =\left\vert V\right\vert
\cdot2^{\left\vert V\right\vert }+1=7\cdot2^{7}+1=\allowbreak897$ vertices.
In this case, since the information graph is of low complexity, it
is easy to check by inspection that the shortest clearing presented in Table
1 also appears in the information graph.

In Figure <ref>.b we see the information graph corresponding to
Example <ref>. The information graph has $\left\vert V_{I}%
\right\vert =76$ vertices; compare this to the  previously mentioned
$V^{\prime}$ which has $\left\vert V^{\prime}\right\vert =\left\vert
V\right\vert \cdot2^{\left\vert V\right\vert }=12\cdot2^{12}+1=\allowbreak
49\,153$ vertices.

figure(a) The information digraph for Example <ref>,  with visibility range $L=1$;
(b) The information digraph for Example <ref>,  with straight-line visibility.

Now we can formulate the LVGS problem as follows.

(Main LVGS Problem) Given $A$ and $B$ choose, subject to
(<ref>), the minimum $T$ and respective $u(0),...,u(T-1)$ such that
$\left[  x(T),\widehat{\mathbf{d}}(T)\right]  \in \widehat{\mathbf{Z}}_{C}$.

The problem reduces to finding, in the graph $G_{I}$, a shortest path from the
unique all-dirty state $\left(  \lambda,\left[  1\right]  \right)  $ (i.e.,
when the searcher has not yet been placed in the graph and there is a single
invisible and dirty component) to some all-clear state $\left(  \mathbf{x,}%
\left[  0,...,0\right]  \right)  \in\mathbf{Z}_{C}$. Note that we also have to
construct the information graph $G_{I}$ and the transition function
$F$. The following LVGS algorithm constructs the graph and finds a shortest
path. The pseudocode is rather self-explanatory; here are a few clarifications.

* Lines 3-7: for each vertex in $G$, a group of vertices is added to
$G_{I}$, each corresponding to a different possible information state.

* Lines 8-15: edges are added to $G_{I}$ by following the searcher's
possible transitions between adjacent $G_{I}$ vertices, by the routine
newInfoState.[Actually we have two versions of this
routine: (a) the first version corresponds to sequential moves (i.e., first
the searcher moves with unit speed and the the target moves with unbounded
speed); (b) the second version implements concurrent moves by both searcher
and target and is somewhat more complicated (details are omitted, in the
interest of simplicity).]

* Lines 6-20: using Dijkstra's algorithm, we find a shortest path between
the all-dirty vertex and every all-clear vertex of $G_{I}$.[For very
large $G_{I}$ we can instead use a depth-first search starting at $\left(
\lambda,\left(  1\right)  \right)  $; this will find a clearing search
schedule, though not the shortest one.]

* Lines 21-22: the algorithm returns the overall shortest path.

This concludes our formulation and proposed solution of the LVGS problem. It
is worth emphasizing that, in both formulation and solution, the only decision
maker is the searcher; the target has been “factored
out” of the problem. This is achieved by adopting a worst
case analysis, namely that every possible contamination is actually

The LVGS Algorithm

[1]
LVGS$A$, $B$
Let $G=(V,E)$ be the graph with adjacecny matrix $A$
$i\in V$  Build vertex set $V_I$ of $G_I=(V_I,E_I)$
every possible $\mathbf{c}(i)$  $\mathbf{c}(i)$: contamination state of \(i\)
add vertex $(i,\mathbf{c}(i))$ to $V_I$
$i\in V$  Build edge set $E_I$ of $G_I=(V_I,E_I)$
$j\in N[i]$
every possible $\mathbf{c}(i)$
calculate $\mathbf{c}(j)=\mathbf{newInfoState}(A,B)$ Using algorithm newInfoState
add edge $(i,\mathbf{c}(i))\rightarrow(j,\mathbf{c}(j))$ to $E_I$
Let $u=(\lambda,[1,...,1])$, the all dirty state of $V_I$
Let $V_I^c$ be the set of clear states of $V_I$
$v\in V^c_I$
$(\text{BestCost}(v),\text{BestPath}(v))=\mathbf{Dijkstra}(G_I,u,v)$ Using Dijkstra's algorithm

Let $\widehat{v}=\arg \min_{v\in V^c_I}\text{BestCost}(v)$
return $(\text{BestCost}(\widehat{v}),\text{BestPath}(\widehat{v}))$

§ EXPERIMENTS

In this section we give examples of the application of our algorithm to
various graph families. We only present examples for “distance-based visibility”, i.e., the visibility matrix
determined by the visibility range parameter $L$. Specifically, when
the cop is located at vertex $x$, he can see the vertices $y$ which are within
$L$ edges of $x$, i.e.,

\[
\begin{array}
1 & \text{iff }d\left(  x,y\right)  \leq L,\\
0 & \text{otherwise.}%
\end{array}
\right.
\]

§.§ Paths

We first apply the LVGS algorithm to paths. This serves as a “reality check” since, clearly, a single searcher can clear a
path by sweeping from one end to the other. In all our experiments the
LVGS algorithm produced a clearing schedule of minimum length (minimum number
of steps) which is given by the following formula: with path length $N$ and
visibility range $L$, the number of required steps is

\[
T_{\min}=\max\left(  N-\left(  2L+1\right)  ,0\right)  .
\]

§.§ Complete Binary Trees

The next family of graphs we examine are complete binary trees. In Table
<ref> we see the results for trees of depth $D\in\left\{
1,...,4\right\}  $ and visibility range $L=\left\{  1,...,5\right\}  $. Listed
in every cell is the length of an optimal search trajectory and computation
time (in seconds). Note that, for $D=4$ and visibility range $L=1,$ the cell
contains $\mathbf{\infty}$, which means that the searcher cannot clear the
graph. Also note that computation times increase significantly with tree
depth, even for high visibility range. E.g., for $D=4$ and visibility range
$L=3$ the cell contains n/a; this means that the algorithm did not
terminate after running for 5 hours. The reason for the high execution times
is that trees of higher depth must be partitioned into many components. For
example, in the complete binary tree of depth $4$ with visibility range $L=3$
the searcher from vertex 1 can see the entire tree except for the leaves.
Since every leaf is a different component, we have 16 invisible components
which contribute to $G_{I}$ $2^{16}=65536$ vertices. This is a case in which
the computational burden of finding a shortest clearing path in $G_{I}$ is
unmanageable. [However, substituting a depth first search for
Dijktra's algorithm yields a (non-optimal) clearing path in a few seconds.]

26emTree Depth     5|c|Visibility Range $L$
1     2     3     4     5

1         0     0     0     0     0

2         2     0     0     0     0

3         8     2     0     0     0

4         $\infty$     8     n/a     0     0

26emTree Depth     5|c|Visibility Range $L$
1     2     3     4     5

1     0.48      0.05      0.02      0.02      0.04

2     3.52      0.15      0.09      0.01      0.01

3     31.14      82.22      0.65      0.61      0.41

4     228.65      3063.17      $>$ 18300.00      7.13      8.23

tableComplete binary trees: optimal length of clearing search schedule and
computation times in seconds.

§.§ Grids

The next type of graph we look into are grids. In Table <ref> we
see search schedule lengths and computation times for $M\times N$ grids with
$M,N\in\left\{  2,...,6\right\}  $. Apparently grids are actually easier to
handle than trees.

25emGrid Size     4|c|Visibility Range
1     2     3     4

2x2     $\infty$     0     0     0

2x3     $\infty$     0     0     0

2x4     $\infty$     1     0     0

2x5     $\infty$     2     0     0

2x6     $\infty$     3     1     0

3x3     $\infty$     0     0     0

3x4     $\infty$     1     0     0

3x5     $\infty$     2     0     0

3x6     $\infty$     3     1     0

4x4     $\infty$     $\infty$     1     0

4x5     $\infty$     $\infty$     1     0

4x6     $\infty$     $\infty$     3     1

5x5     $\infty$     $\infty$     2     0

5x6     $\infty$     $\infty$     3     1

6x6     $\infty$     $\infty$     $\infty$     3

25emGrid Size     4|c|Visibility Range $L$
1     2     3     4

2x2     0.81        0.03         0.02        0.01

2x3     1.31      0.05      0.02      0.01

2x4     2.01      0.91      0.04      0.01

2x5     3.70      2.45      0.12      0.05

2x6     6.05      5.17      2.48      0.14

3x3     3.21        0.11         0.04        0.01

3x4     6.32      6.19      0.18      0.05

3x5     10.40      17.66      0.48      0.22

3x6     15.89      55.65      59.82      1.38

4x4     7.12        15.49         8.41        0.18

4x5     14.01      46.19      28.38      0.76

4x6     19.81      67.20      86.95      35.32

5x5     15.89        55.65        59.82        1.38

5x6     41.52      139.59      182.42      110.65

6x6     32.36        90.70      204.52      159.80

table$M\times N$ grids: optimal length of clearing search schedule and computation times in seconds.

§.§ Randomly Generated Trees

In this section we apply the LVGS algorithm to trees in which children are
generated probabilistically. Specifically, we start with a complete binary
tree of depth one (one root with two children) and every vertex (except the
root) can have $n\in\left\{  0,1,2\right\}  $ children with probability
$p_{n}$ where $\left[  p_{0},p_{1},p_{2}\right]  =[\frac{1}{3},\frac{1}%
{3},\frac{1}{3}]$. We continue adding children to every leaf until the tree
reaches a maximum depth value $D_{\max}$. Hence a family of random binary
trees is fully described by the parameters $\mathbf{p}=[\frac{1}{3},\frac
{1}{3},\frac{1}{3}]$ and $D_{\max}$. In Table <ref> we present,
for visibility range $L\in\{1,...,4\}$ and maximum depth $D_{\max}=5$, some
statistics averaged over $100$ randomly generated trees.

28emmax depth = 5     4|c|Visibility Range $L$
1     2     3     4

Number of Cleared Graphs     81/100     100/100     100/100     100/100

Average Clearing Length     5.32     3.19     1.32     0.36

Maximum Clearing Length     14     14     6     2

Average Calculation Time     11.99      22.75      31.62      18.90

Maximum Calculation Time     111.98      327.14      954.32     972.77

tableStatistics for 100 randomly generated trees with  $D_{max}=5$.

In Table <ref> we present similar results for 100
trees with maximum depth $D_{\max}=6$, and for visibility range $L\in
\{1,...,4\}$.

28em max depth = 6     4|c|Visibility Range $L$
1     2     3     4

Number of Cleared Graphs     72/100     99/100     100/100     100/100

Average Clearing Length     4.58     3.9     1.99     0.78

Maximum Clearing Length     19     16     12     6

Average Calculation Time     19.82       62.47      83.91      100.37

Maximum Calculation Time      303.04       1921.38      2467.45      4867.91

tableStatistics for 100 randomly generated trees with $D_{max}=6$.

§.§ Grids with Randomly Deleted Edges

In this section we use graphs which are created by deleting edges from a full
grid; for brevity, these will be referred as “deleted
grids”. The specific method by which the edges are deleted is
the following. We start  with a full grid and, for every edge $e$ of the grid:

* If removal of $e$ would result in a disconnected graph, leave $e$ in place.

* Otherwise remove $e$ with probability $p\in\left[  0,1\right]  $ (a parameter).

The above procedure results in a deleted grid; higher $p$ values
reult in sparser graphs but, by construction, the resulting graph is always
connected. Results for $N\times N$ deleted grids are presented in the
following Tables <ref>,<ref> and <ref>.

\( \mathbf{p} = \mathbf{1/2}\)     4|c|Visibility Range $L$
grid size = 3x3     1     2     3     4

Number of Cleared Graphs     73/100     95/100     99/100     100/100

Average Clearing Length     4.84     1.98     0.45     0

Maximum Clearing Length     6     4     2     0

Minimum Clearing Length     2     0     0     0

Average Calculation Time     3.79      2.28      0.63      0.08

Maximum Calculation Time     8.62      5.87      2.38      0.23

Minimum Calculation Time     1.68      0.18      0.07      0.01

tableStatistics for 100 $3\times 3$ deleted grids.

\( \mathbf{p} = \mathbf{1/2}\)     4|c|Visibility Range $L$
grid size = 4x4     1     2     3     4

Number of Cleared Graphs     44/100     91/100     96/100     99/100

Average Clearing Length     10.57     6.79     3.97     1.86

Maximum Clearing Length     13     10     8     6

Minimum Clearing Length     9     4     1     0

Average Calculation Time     15.44      22.13      17.68      8.92

Maximum Calculation Time     42.02      62.15      46.21      21.42

Minimum Calculation Time     6.80      8.82      8.72      0.40

tableStatistics for 100 $4\times 4$ deleted grids.

\( \mathbf{p} = \mathbf{1/2}\)     4|c|Visibility Range $L$
grid size = 5x5     1     2     3     4

Number of Cleared Graphs     6/100     67/100     90/100     95/100

Average Clearing Length     17.67     12.97     8.81     5.73

Maximum Clearing Length     21     18     14     12

Minimum Clearing Length     16     8     4     1

Average Calculation Time     43.33      99.51      118.8      100.1

Maximum Calculation Time     118.19      282.3      438.73     378.94

Minimum Calculation Time     18.30      37.70      43.56      41.53

tableStatistics for 100 $5\times 5$ deleted grids.

§ CONCLUSION

We have formulated a graph search problem, with searchers looking for a mobile
target under the following assumptions: (a) the visibility field of the
searchers is limited, (b) movement is along the graph edges, (c) the searchers
have unit speed and (d) the target has infinite speed.

To solve the problem we have presented the LVGS algorithm, which is a
conversion the polygonal region search algorithm of
<cit.>. This algorithm is guaranteed to always find a
solution if one exists. Furthermore, the LVGS algorithm can acommodate every
kind of visibility conditions (0-visibility, distance-based visibility of
arbitrary range and straight line visibility) using the visibility matrix.
While the problem formulation can acommodate an arbitrary number of searchers
and arbitrary searcher and target speed, the LVGS algorithm is particularly
suited for problems involving a single searcher, movement along the edges of
the graph, unit speed for the searcher and infinite speed for the target.

We conclude this paper by listing some research directions which we intend to
pursue in the future.

* The polygonal region search algorithm of <cit.> is
complex to implement and can be computationally impractical for complicated
regions. An alternative strategy to handle polygonal regions is to first
approximate them by discretization and then study the search problem on a
graph equivalent to the discretized region. We believe it will be interesting
to compare the performance of this approach combined with our LVGS algorithm
to that of the original polygonal region algorithm.

* In the Introduction we have briefly mentioned the connection of graph
search to pursuit in graphs, especially to the problemof the cops and
invisible (or partially visible) robber. We believe that this connection
merits further study and that the LVGS algorithm could provide solutions
competitive to the ones obtained by combinatorial arguments

Alspach2006B. Alspach, Searching and sweeping graphs: a brief
survey, Matematiche (Catania) 59 (2006) 5–37.

Barriere2002L. Barrière, P. Flocchini, P. Fraigniaud, N.
Santoro, Capture of an intruder by mobile agents, in: Proceedings of the
fourteenth annual ACM symposium on Parallel algorithms and architectures
(SPAA 2002), ACM Press, 2002, pp. 200–209.

Barriere2003L. Barriere, P. Fraigniaud, N. Santoro, D. Thilikos,
“Searching is not jumping”, in:
Graph-Theoretic Concepts in Computer Science, Lecture Notes in
Computer Science, vol. 2880, 2003, pp. 34–45.

Berarducci1993A. Berarducci and B. Intrigila. “On
the cop number of a graph.” Advances in Applied
Mathematics, 14.4 (1993): 389-403.

Breisch1967R. Breisch, “An intuitive approach to
speleotopology”. Southwestern Cavers, 6.5 (1967): 72-78.

Dendris1997N.D. Dendris, L.M. Kirousis, D.M. Thilikos,
target-search games on graphs and related parameters, Theoret. Comput.
Sci. 172 (1997) 233–254.

Hollinger2011T.H. Chung, G.A. Hollinger and V. Isler.
“Search and pursuit-evasion in mobile
robotics.” Autonomous Robots 31.4 (2011): 299.

Clarke2019N. E. Clarke, D. Cox, C. Duffy, D. Dyer, S. L.
Fitzpatrick, M. E. Messinger (2019). Limited visibility Cops and Robber.
Discrete Applied Mathematics.

Deren2011D. Dereniowski. “Connected searching of
weighted trees.” Theoretical Computer Science, 412.41
(2011): 5700-5713.

Deren2012D. Dereniowski “From pathwidth to
connected pathwidth.” SIAM Journal on Discrete
Mathematics, 26.4 (2012): 1709-1732.

Deren2013D. Dereniowski et al. “Zero-visibility
cops and robber game on a graph.” Frontiers in
Algorithmics and Algorithmic Aspects in Information and Management. Springer,
Berlin, Heidelberg, 2013. 175-186.

Deren2015D. Dereniowski et al. “The complexity of
zero-visibility cops and robber.” Theoretical Computer
Science, 607 (2015): 135-148.

Deren2015bD. Dereniowski et al. “Zero-visibility
cops and robber and the pathwidth of a graph.” Journal
of Combinatorial Optimization, 29.3 (2015): 541-564.

Fomin2008F. V. Fomin and D. M. Thilikos, An annotated bibliography
on guaranteed graph searching.

Guibas1997L. J. Guibas, J. C. Latombe, S. M. LaValle, D. Lin and R.
Motwani (1997, August). “Visibility-based pursuit-evasion in
a polygonal environment”. In Workshop on Algorithms and
Data Structures (pp. 17-30). Springer, Berlin, Heidelberg.

Guibas1999L. J. Guibas, J. C. Latombe, S. M. , D. Lin, R. Motwani,
(1999). “A visibility-based pursuit-evasion
problem”. International Journal of Computational
Geometry & Applications, 9(04n05), 471-493.

Hahn2006G. Hahn and G. MacGillivray. “A note on
k-cop, l-robber games on graphs.” Discrete
Mathematics, 306.19-20 (2006): 2492-2497.

Hollinger2009G. Hollinger, S. Singh, J. Djugash, and Ath. Kehagias.
“Efficient Multi-robot Search for a Moving
Target”. The International Journal of Robotics
Research, 28.2 (2009): 201-219.

Hollinger2010G. Hollinger, Ath. Kehagias and S. Singh.
“GSST: anytime guaranteed search”.
Autonomous Robots, 29.1 (2010): 99-118.

Hollinger2010bG. Hollinger, S. Singh and Ath. Kehagias.
“Improving the Efficiency of Clearing with Multi-agent
Teams”. The International Journal of Robotics
Research, 29.8 (2010): 1088-1105.

Jeliazkova2006D. Jeliazkova , Aspects of the Cops and Robber
Game Played with Incomplete Information, Master's thesis, Acadia University (2006).

Kehagias2009Ath. Kehagias, G. Hollinger, and S. Singh.
“A graph search algorithm for indoor
pursuit/evasion.” Mathematical and Computer
Modelling, 50.9-10 (2009): 1305-1317.

Kehagias2012Ath. Kehagias, D. Mitsche and P. Pralat.
“Cops and invisible robbers: The cost of
drunkenness.” Theoretical Computer Science, 481
(2013): 100-120.

Kehagias2014Ath. Kehagias, D. Mitsche and P. Prałat.
“The role of visibility in pursuit/evasion
games.” Robotics, 3.4 (2014): 371-399.

Kiroussis1986L.M. Kirousis, C.H. Papadimitriou, “Searching and pebbling”, Theoret. Comput. Sci., 47
(1986) 205–218.[26]

Lavalle2006S. M. LaValle, Planning algorithms. Cambridge
University Press, 2006.

Nowakowski1983R. Nowakowski, and P. Winkler. “Vertex-to-vertex pursuit in a graph.” Discrete
Mathematics, 43.2-3 (1983): 235-239.

NowakowskiBookR. Nowakowski and A. Bonato. The game of cops
and robbers on graphs. American Mathematical Soc., 2011.

Parsons1978T.D. Parsons. “Pursuit-evasion in a
graph.” Theory and applications of graphs. Springer,
Berlin, Heidelberg, 1978. 426-441.

Quilliot1985A. Quilliot, “A short note about
pursuit games played on a graph with a given genus”, J.
Comb. Theory Ser. B, 38 (1985) 89-92.

Sarmiento2004A. Sarmiento, R. Murrieta-Cid, and S. Hutchinson.
“A multi-robot strategy for rapidly searching a polygonal
environment.” Ibero-American Conference on Artificial
Intelligence. Springer, Berlin, Heidelberg, 2004.

Seymour1993P.D. Seymour, R. Thomas, “Graph
searching and a min-max theorem for tree-width”, J.
Comb. Theory, Ser. B, 58 (1993) 22–33.

Tang2004Tang, A. Cops and robber with bounded visibility.
Master's thesis, Dalhousie University (2004).

Tosic1985R. Tosic, “Inductive classes of
graphs”. In: Proceedings of the Sixth Yugoslav Seminar
on Graph Theory, pp. 233–237. University of Novi Sad (1985)

Yang2007B. Yang, “Strong-mixed searching and
pathwidth”, J. Comb. Optim., 13 (2007) 47–59.