Hide-and-Seek with Directional Sensing

We consider a game played between a hider, who hides a static object in one of several possible positions in a bounded planar region, and a searcher, who wishes to reach the object by querying sensors placed in the plane. The searcher is a mobile agent, and whenever it physically visits a sensor, the sensor returns a random direction, corresponding to a half-plane in which the hidden object is located. We first present a novel search heuristic and characterize bounds on the expected distance covered before reaching the object. Next, we model this game as a large-dimensional zero-sum dynamic game and we apply a recently introduced randomized sampling technique that provides a probabilistic level of security to the hider. We observe that, when the randomized sampling approach is only allowed to select a very small number of samples, the cost of the heuristic is comparable to the security level provided by the randomized procedure. However, as we allow the number of samples to increase, the randomized procedure provides a higher probabilistic security level.


Introduction
Games of hide-and-seek have been among folklore over the past several centuries. In modern times, these games find relevance in modeling problems of protecting high-valued assets or seeking out potential threats. This paper is concerned with one such game between a hider, who hides a static object among candidate points in a region, and a seeker, who wishes to reach the object by covering minimum distance, while making use of information about the object's location obtained from a few sensors deployed in the region.
A version of this problem without sensor measurements was addressed in our earlier work [BBHPD10], wherein we formalized the problem in the form of a static matrix game. We provided a randomized approach to obtain probabilistic levels of security for the hider. In this paper, we utilize the measurements from additional sensors, which effectively make this problem a dynamic game. In addition, we also analyze a novel heuristic for the seeker, and compare its performance to the randomized method.
Related Work. Search theory has received a lot of attention over the past several decades. Classic works [Sto07], [Was02] address several problems involving the search of static as well as moving objects, under various assumptions on sensing abilities of the searcher. [BP02] proposes a search-theoretic approach based on rate of return maps to develop cooperative search plans for uninhabited air vehicles to detect stationary targets.
The problem considered in this paper bears similarities to the area of acoustic source localization, which involves estimating the location of a source using time-of-arrival measurements (see [AKLV04], [BSL08]). Recently, [KSIH10] proposed protocols to route one or more unmanned aerial vehicles to collect time-ofarrival measurements from sensors deployed in an environment. [SMH03] presented an efficient approach to detect an object in a polygonal environment. One straightforward strategy to reach the object without the use of any sensor measurement is to visit every candidate point via the shortest path through all candidate points. However, the computational complexity of determining the shortest path scales exponentially with the number of candidate points [Bel62].
This material is based upon work supported in part by ARO MURI Grant number W911NF0910553, and in part by the Center of Excellence for Research DEWS, University of L'Aquila, Italy.
Contributions. We consider a game played between a hider and a searcher. A static object, such as a treasure, is placed by the hider at one of m given points, distributed independently and uniformly in a square region E ⊂ R 2 . We assume that s(m) directional sensors are deployed in E so as to minimize the maximum distance from any point in E [SD96]. Each sensor has an associated line and returns a binary information about the half-plane in which the treasure lies, without measurement error. Such a model arises when an array of microphones is used at each location [VMRL03]. The goal for a searcher, assumed to move with bounded maximum speed and to have a simple integrator dynamics, is to reach the treasure in the shortest possible time (or equivalently, by covering the shortest possible distance), from a given starting point. On the other hand, the hider's goal is to make the searcher travel as much distance as possible until the treasure is reached.
We first present a Divide-and-Search heuristic which involves: (i) moving to the sensor closest to the centroid of the sub-region that contains the treasure, (ii) updating the sub-region that contains the treasure based on the measurement received, and (iii) performing an exhaustive search through all the remaining candidate points, when no more sensor locations are present in the updated sub-region that contains the treasure. We provide a novel upper bound on the expected distance covered by the searcher and characterize the number of sensors required by this heuristic. The upper bound on the expected distance scales as log(m), which is a significant improvement as compared to following an open-loop approach of following the shortest path through the candidate points, the length of which scales as √ m.
We then model this game as a zero-sum feedback matrix game and apply the randomized approach introduced in [BBHPD10] for static matrix games, and extended in [BH11] to partial information dynamic games. The hider samples columns from a matrix, which represent different policies of the searcher, and computes a sampled security level and a policy to play the actual game. We first establish monotonicity of the security level of the game as a function of the number of policies of the searcher considered by the hider. A comparison of the security levels obtained through the randomized method with the lengths of the paths produced by the heuristic procedure reveals that if the hider becomes aware that the seeker is using the heuristic procedure she can select (deterministic) locations for the treasure that will lead to very long searches by the seeker. In contrast, the randomized approach produces search strategies that make the task of the hider more challenging, effectively forcing her to use randomized hiding strategies. However, it is important to note that the randomized approach generates policies that are optimized for a specific geometry of the points and can be fragile with respect to changes in the positions of the points away from the positions for which the game was sampled.
Organization. This paper is organized as follows. The problem formulation is presented in Section 2. Preliminary results are included in Section 3. The Divide-and-Search heuristic is presented and analyzed in Section 4. The formulation of this problem in the form of a dynamic game is presented in Section 5. Simulations of the heuristic and the randomized approach are included in Section 6.

Problem formulation
Consider a problem in which a seeker has to find a treasure that is placed at one of m given points, distributed independently and uniformly in a square region E ⊂ R 2 with area denoted by Area(E). We consider deploying s(m) directional sensors in E so that the maximum distance of any point in E from any sensor is minimized. In the following, each point will be regarded in terms of the corresponding index i ∈ P := {1, 2, ..., m} for each candidate treasure point, i ∈ S := {m + 1, ..., m + s} for each sensor point and i = 0 for the searcher initial position, that is assumed to be set at the centre of the square region.
Each sensor i has an associated straight line defined by n ′ i (p − p i ) = 0, i ∈ S, where the unit vector n i (normal to the straight line) is given and known, and p i belongs to the line; we assume that n ′ i (p j − p i ) = 0 for all i ∈ S, j ∈ P, i = j, and that the orientations of the unit vectors n i are distributed independently and uniformly in [0, 2π]. Whenever a sensor is visited, it returns a binary information about the half-plane in which the treasure lies, as shown in Figure 1. More formally, a seeker visiting a sensor point i will receive the observation y = sgn(n ′ i (p Θ − p i )) ∈ {−1, 1}, where p Θ denotes the treasure position. This will allow us to restrict the time horizon to at most m + s points T = {0, 1, 2, ..., m + s}, after which the treasure is certainly found.
We shortly introduce a bit of extra notation to better describe the strategy of the seeker. At time t ∈ T , let x (t) be current location of the pursuer, with x (0) = 0 and x (t) ∈ P ∪ S for t ≥ 1. The position x (t + 1) is decided at time t by a motion control action u (t), namely x (t + 1) = u (t); the pursuer visits the node p x(t) and gets the measurement be the sequences of visited nodes and collected observations by the seeker, respectively, up to some time k ≥ 0, with y (0) := ∅. For the sake of simplicity, we assume we can write X k+1 = X k ∪ {x (k + 1)} and Y k+1 = Y k ∪ {y (k + 1)} with a slight abuse of notation. E Θ n i Figure 1. Problem formulation. A circle denotes a candidate treasure point, a square denotes a sensor and the dot denotes the searcher. In this figure, the searcher is at a sensor and has received a measurement corresponding to the treasure Θ being at one of the circles in the shaded region.

Preliminaries
In this section, we summarize some preliminary results which we will use in the rest of the paper.
3.1. Geometric Preliminaries. The first result by [SD96] gives an upper bound on the minimum of the s distances from any point z ∈ E.
Lemma 3.1. The rectangular heuristic from [SD96] to place the s sensors satisfies min i∈{1,...,s} The next result is well-known in computational geometry. The next result provides an upper bound on the length of the shortest path through all points in a convex polygon which is contained inside E.

Lemma 3.3 (Shortest path length bound). The length of the shortest path through n points that are inside a convex polygon of area A which is contained inside E is upper bounded by
Proof of Lemma 3.3. We provide a constructive proof as follows. First, consider the minimum area-enclosing rectangle of the given convex polygon. By Proposition 3.2, this rectangle has area upper bounded by 2A. Now, let the smaller side of this rectangle have length equal to B and the larger side have length equal to H. Define, h := H/B = 2A/B 2 . Now using Lemma II.3 from [BSBH10], there exists a path that starts from the smaller side, passes through each of the n points exactly once and terminates on the opposite side of the rectangle, and has length upper bounded by where we used the fact that both B and H can be at most equal to 2 Area(E). The result now follows since the vehicle would cover a distance of at most 2 Area(E) to reach any point on the smaller side of the minimum area-enclosing rectangle of the given convex polygon.

3.2.
Randomized sampling for large zero-sum games. In [BBHPD10], we introduced the Sampled Saddle-Point (SSP) algorithm, in which players sample sub-matrices from the original M × N matrix A, solve smaller games and utilize the saddle-point policies so obtained against each other. The SSP algorithm can be summarized as follows.
Let B k×l denote the set of k × l left-stochastic (0, 1)-matrices (i.e., matrices whose entries belong to the set {0, 1} and whose columns add up to one).
Algorithm 1: Sampled Saddle-Point For P 1 : The subscript in the probability measure P emphasizes which random variables define the events that are being measured. To provide guarantees for specific policies/values, the following notions of security that refer to specific policies/values are introduced. The policy y * with valueV (A 1 ) is ǫ-secure for player The following result provides a bound on the size of the sub-matrices for the players that guarantees ǫ-security with ǫ = 0.
If one further increases n 1 to satisfy then, with probability 1 higher than 1 − β, the policy y * with valueV (A 1 ) is ǫ = 0-secure for P 1 with confidence 1 − δ.
Suppose that, due to computational limitations, player P 1 cannot satisfy the bounds in Theorem 3.4 to obtain ǫ = 0-security for a given level of confidence 1 − δ. One option to overcome this difficulty and maintain the same high level of confidence would be to accept a larger value for ǫ.
The following is an a-posteriori procedure for P 1 . Let e j denote the jth element of the canonical basis of R k1 .
If one further increases k 1 to satisfy then, with probability higher than 1 − β, the policy y * with valueV (A 1 ) is ǫ-secure for P 1 with confidence 1 − δ.

The Divide-and-Search Heuristic
We now present and analyze a novel heuristic for the searcher. This heuristic involves computing the centroid of a convex polygonal region at every iteration, and then moving to the sensor closest to the centroid. At every iteration, the polygonal region is updated using the measurement from the sensor. If no such sensor exists, then the searcher performs an exhaustive search over the remaining candidate points in the region.
Formally, the centroid Cent(Q) of a convex region Q ⊂ R 2 is defined as the unique point q in Q that minimizes Q z − q 2 dz. As per our measurement model, given an unknown treasure position Θ, any sensor x (t) ∈ S visited at time t, and a measurement y (t) = sgn(n ′ x(t) p Θ − p x(t) ), let H(x (t) , y (t)) denote the half-plane which contains the treasure.
Let K denote the number of measurements taken by the searcher. Then, the heuristic is described in Algorithm 3.

Algorithm 3: Divide-and-Search
Assumes , y (t)) end for Move on the shortest path through all targets in E K . Figure 2 shows snapshots of a numerical implementation of the heuristic, with a high number of nodes. The following is a useful property of Algorithm 3.
Lemma 4.1 (Upper bound on Area(E K )). Assume that the sensors are placed using the rectangular heuristic by [SD96]. Then, at the end of Algorithm 3, where the expectation is over the distribution of the measurements obtained by the sensors.
Proof of Lemma 4.1. From Algorithm 3, it is immediate that each E t is convex. Consider the region E t−1 as shown in Figure 3. We obtain a measurement y (t) at a sensor closest to Cent(E t−1 ), as shown in Figure 3. Let l denote a line that passes through Cent(E t ) and which is perpendicular to n x(t) . Using the centroid property [BH02] that any line through the centroid of a convex region divides the region into two parts such that the area of each part is at most two-thirds of the area of the original convex region, we obtain where d t is the distance of the closest sensor to Cent(E t−1 ) and the second term is the area of the rectangular strip between the two lines. Using Lemma 3.1, where the expectation is with respect to the sensor measurements. By using this inequality recursively, and from the fact that 1 − (2/3) K < 1, we obtain (4.1).
We now present the main result of this section, which provides an upper bound on the expected distance covered by the searcher using the Divide-and-Search heuristic, and also characterizes the number of sensors required. Let D denote the distance covered by the searcher until the treasure is found.
Theorem 4.2 (Performance of Algorithm 3). Suppose that: (1) the number of candidate treasure locations m and the number of sensors s satisfy s = ⌈m/(ln(m)) 2 ⌉; (2) the sensors are located using the rectangular heuristic from [SD96].  Figure 2. The Divide-and-Search heuristic. The big solid dot is the searcher, the blue (light) circles denote target points wherein the treasure is not present, the red (dark) circles denote the candidate treasure locations, the solid red dot denotes the exact location of the treasure, the + denotes the centroid of the region E t at each iteration, the squares denote the sensors. The shortest path is illustrated by a dashed line in the final figure.
Then, the expected value of D using Algorithm 3 satisfies where the expectation is with respect to the joint distribution of the measurements and the candidate treasure locations.
Proof of Theorem 4.2. Let dist(K) denote the distance covered by the vehicle by using Algorithm 3. Clearly, D ≤ dist(K), which is a random variable which is upper bounded by the sum of two terms. The first is K times the diameter of E, and the second is the length of the shortest path through the remaining m rem candidate locations in E K . Using Lemma 3.3, Cent(E t−1 ) l Figure 3. Illustrating proof of Lemma 4.1. The dashed line is perpendicular to n x(t) and passes through the centroid of E t−1 . By the centroid property, the area of the shaded region is at most two-thirds of the area of E t−1 .
Taking expectation with respect to the joint distribution of the measurements from the sensors and the target points, where the second step follows from the law of iterated expectations, and the third step is due to the application of Jensen's inequality [Bre92] to the square-root function. In the above inequality, the outer expectation is with respect to the measurements while the inner expectation is with respect to the target points. Now, conditioned on the value of Area(E K ), the only information about the candidate locations that can be obtained is the existence of the treasure inside E K . The remaining m − 1 locations are distributed independently and thus, the expected number of target points inside E K satisfies On substitution, and since Area(E K ) ≤ Area(E), we have Using Lemma 4.1, we have since by assumption, s = ⌈m/(ln(m)) 2 ⌉. Now, the right hand side of the above inequality is minimized with Substituting this value of K in the right hand side of (4.2), we obtain the right hand side of the first inequality. The left hand side is trivially true because the treasure can be placed at the diametrically opposite end of the region E.
Remark 4.3 (Number of sensors). Theorem 4.2 implies that with at most ⌈m/(ln(m)) 2 ⌉ number of sensors, and with a number of steps K * which grow logarithmically as a function of m, Algorithm 3 may lead to an average cost which is at most ln(m) times the optimal.

Formulation as a Matrix Game
Consider an output feedback zero-sum dynamic game where P 1 hides a non-moving object (treasure) in one of m points {p i } m i=1 on the plane and P 2 has to find the treasure with minimum cost, by traveling from point to point until she finds it, starting at p 0 . At each step, P 2 can either visit one of the m points, trying to guess the treasure position, or visit one of s(m) sensor points {p i } m+s i=m+1 , to get better information. The game is played over the set of mixed policies: • P 1 chooses a probability distribution y ∈ S m for the treasure over the m points; • P 2 chooses a probability distribution z ∈ S n over the set of all the possible n functions of the available information, mapping the information available to P 2 at some time step to the action to be taken at that step. Specifically, the information available consists of the sequence of points visited so far and the measurements collected from the sensors visited. The next action to take consists of the index of the next point to visit.
The game can be formulated as a matrix game with a very large number of columns, where the generic entry A ij corresponds to the Euclidean cost to find the treasure by playing policy j when the treasure is placed in i, namely: where r j (X −1 , Y −1 ) := 0 for all j (starting point) and the summation ends at the index k * ij for which r j (X k * ij , Y k * ij ) corresponds to the point i where the treasure is hidden. The minus sign in Eq. (5.1) is needed to maintain consistency with the formulation in Subsection 3.2, where P 1 is the minimizer. Indeed, P 1 hides the treasure to maximize the distance and therefore to minimize the entries of A.
The exact computation of the optimal mixed strategies is intractable because the size of the matrix is very large, in general. However, the results regarding the SSP algorithm have a computational complexity that is completely independent of the size of the game, which means that we can provide probabilistic guarantees for games with an arbitrarily large number of points.
In this particular game, only the player P 2 has a very large number of options, so we can assume that both players consider all possible m locations where P 1 can hide the treasure (all rows of A), but randomly select only a small number of pursuit strategies to construct their submatrices. This means that P 2 will never be surprised since she always considers all options for the actions of P 1 . However, the player P 1 that hides the treasure should respect the bounds provided by Theorems 3.4 and 3.5 to avoid unpleasant surprises.
The choice m k = m in the SSP algorithm is particularly interesting to apply in games where the matrix is "fat", with many more columns that rows. In these cases, further results can be obtained for the SSP procedure, as shown in Subsection 5.1. 5.1. SSP for "fat" matrix games.
5.1.1. Sampled security levelV (A 1 ). In the SSP algorithm, the sampled security level for P 1 is a random variable, given byV (A 1 ) = min In the case m 1 = m,V (A 1 ) only depends on n 1 and on the particular realization of the n 1 columns, and thus is a function of the random variable Π 1 . Thus, The following preliminary result essentially states that as the number of sampled columns increases, the sampled valueV (A 1 ) is expected to increase, or in other words, the probability thatV (A 1 ) is less than a fixed quantity decreases monotonically.
Lemma 5.1. For any fixed x ∈ R, P Π1 V (A 1 ) ≤ x is non-increasing with n 1 . Further, if every column of A is being sampled with a positive probability by the SSP algorithm, then, in the limit as n 1 goes to infinity, V (A 1 ) converges almost surely to the original value of the game V (A).
Proof of Lemma 5.1. We begin with the first claim.
For the second claim, let c j denote the jth element of the canonical basis of R N , and let C 1 denote the first column of Π 1 . Now, the probability that c j is sampled is given by P Π1 (c j ∈ Range(Π 1 )). By assumption, P C1 (C 1 = c j ) > 0, ∀j ∈ {1, ..., n}. This implies that P C1 (C 1 = c j ) < 1, ∀j ∈ {1, . . . , N }. For any j, the probability of c j being drawn in n 1 independent trials is Since P C1 (C 1 = c j ) ∈ (0, 1) by assumption, the probability that c j does not get sampled goes to zero exponentially with n 1 . This implies convergence in probability ofV (A 1 ) to V (A), and almost sure convergence is implied by the use of Borel-Cantelli lemma [Res98].
We now recall that the quantile X α of a random variable X is the inverse function of the cumulative distribution function and returns the value below which random draws from the given distribution would fall (α × 100)percent of the time. For any discrete random variable X and a real number α ∈ [0, 1], the quantile is defined as and is a non-decreasing function of α.
The next result shows that, for any fixed α, the quantile of the sampled valueV (A 1 ) is a non-decreasing function of n 1 .
Furthermore, for all α > 0, we have where the limit and the infimum commute due to convergence ofV (A 1 (n 1 )) established in Lemma 5.1.
Analogous to the quantile of the sampled value of the gameV (A 1 ), it can be shown that the quantile ofv is monotonically non-decreasing as in the following result.
Remark 5.4. Note that, since for both the bounds provided by Theorems 3.4 and 3.5 we have lim δ→0 k 1 = +∞, the previous results can be restated in terms of δ; in particularv α (n 1 , k 1 ) is non-increasing with δ for any fixed n 1 , and in the limit (δ → 0, n 1 → +∞) it converges in distribution to the value of the game.
Remark 5.5. It can be argued that the expectations of the a-posteriori outcomev and of the sampled value of the gameV have the same monotonicity and convergence properties of the corresponding quantilesv α (n 1 , k 1 ) andV α (n 1 ).

Simulations
We now present results of numerical implementation of the randomized technique applied to the outputfeedback hide-and-seek game, described in Section 5.
First, we chose a fixed geometry of m = 10 candidate treasure points and s = 2 sensor points, drawn uniformly from a 50-by-50 square region, and we ran Monte Carlo simulations of the Algorithm 2, with the a-posteriori guarantees described in Theorem 3.5, for increasing values of n 1 up to the corresponding a-priori bound (see Theorem 3.4). We setn 2 = 10, β = 2 · 10 −5 , and we repeated the simulations for different values of δ (or, equivalently, of k 1 ). Figure 4 shows the behavior of the curvesv α (n 1 , k 1 ) (for different values of k 1 ) andV α (n 1 ), as defined in Section 5.1, with α = 0.9. For simplicity, we only show curves obtained using the a-posteriori bound in Equation (3.3).
The plots endorse the monotonicity results obtained in Propositions 5.2 and 5.3; furthermore, the curves v α (n 1 , k 1 ) look reasonably "flat", implying that with the choice of n 1 that is a few orders of magnitude lower than the a-priori bound, one can obtain a security strategy that has a relatively small value of ǫ with high probability (see [BBHPD10] for further considerations).
To provide a comparison between the randomized method and the heuristic, we considered a different simulation setup and ran Monte Carlo simulations over 30 different geometries of m = 10 candidate treasure points, uniformly randomly distributed in a 50-by-50 square region, and s = 2 sensor points placed according to the rectangular heuristic from [SD96]. We applied Algorithm 1, withn 2 = 10, β = 2 · 10 −5 , δ = 0.02, and compared the sampled security value (in terms of quantileV α (n 1 )) to the cost of the Algorithm 3 (heuristic), as shown in Figure 5. The heuristic cost represents the seeker's security level, namely the outcome when the seeker uses the heuristic and the hider plays the best response to it, by placing the treasure in the last point to be visited according to the heuristic. Although this value is very good for the hider (i.e., very negative, which corresponds to a large time to find the treasure), we observe a significant gap between this value (the black dotted line) and the SSP curve (the magenta dash-dotted line), especially for large n 1 . This means that, while the hider can expect a large time until the treasure is found when playing against the heuristic policy, it should not expect such a favorable outcome when playing against the SSP algorithm. Moreover, this particular hiding policy is very fragile because if the seeker learns it, then she can find the treasure in one step. Clearly, the heuristic policy is not a Nash equilibrium. From the seeker's point of view, the heuristic provides a reasonable security level, better than the ETSP cost and with much less computation, because the first part of Algorithm 3 (the 'K steps') allows the exclusion of many points before computing the ETSP path (see Section 4). In general, an advantage of the heuristic with respect to the randomization method is that it does not require the knowledge of the entire geometry to determine the solution, but just the sensor locations and the geometry only at the last step.  It is important to note that the heuristic procedure was constructed assuming that the candidate treasure points are uniformly distributed, but other than that, it has not been optimized to any particular geometry and therefore it should be fairly robust to changes in the positions of the points. In contrast, the SSP technique constructed feedback policies that have been optimized for a specific geometry of the points and can therefore be fragile with respect to changes in the positions of the points away from the positions for which the game was sampled.

Conclusions and Future Directions
In this paper, we proposed two different techniques to solve the problem of finding a static object in a planar region, when directional measurements are available to the seeker. First, we presented a searching heuristic and characterized bounds on the expected distance covered by the searcher; then we addressed the problem as a large-dimensional game and applied recent results on randomized sampling approach to get security strategies guaranteed with high probability. Simulation results show that, at the cost of performing more computation, the randomized procedure provides a lower (better) security level (with probabilistic guarantees) to the hider, against the one provided by the search heuristic. On the other hand, the heuristic shows its benefits in that it can be implemented very efficiently and its performance does not rely on a specific geometry of the points.
Future work will focus on extending the problem to the continuous case, by assuming that measurements are available in any point of the plane and the object can be put anywhere in the plane; furthermore, the binary information sensor models considered in this paper can be replaced by more sophisticated sensors, providing continuous and noisy measurements.  Figure 5. Comparison between randomized technique and heuristic, over different geometries. The randomization provides a lower security level than the heuristic, at the cost of performing more computation