Introduction

Imagine a game of hide-and-seek is being played. After the hiders conceal themselves (subsequent relocations are allowed), the seekers, familiar with the environment, start to search for the hiders. Most people who played the game as schoolchildren know that an effective search begins with the seekers checking places having high probabilities of containing a hider, from previous experience: A closet, an attic, a thick bush, and so on. After the most likely locations are exhausted, the next step is to carry out a systematic search of the environment, possibly with some seekers guarding certain escape routes. Occasionally, during game play, hiders may attempt to relocate themselves to avoid being found. While they succeed sometimes, the hiders may end up being spotted by the seekers and instead getting found earlier.

Although a child's play, this game captures the two key interacting ingredients of pursuit evasion (PE) games: Passively estimating the distribution of hidden targets and actively planing to reduce the uncertainty of this distribution. The general goal in PE research is to algorithmically clear evading targets from a workspace. As pursuers try to ensure the workspace is evader-free, they always need to maintain the pursuit status, remembering whether a region outside of the pursuers' field-of-view is contaminated or cleared (one bit of information per region).

This paper, expanding upon [45,46], studies exactly the passive ingredient of PE games, reasoning about the information residing in unobservable regions of the environment. In particular, we introduce the notion of filters over shadow information spaces for tracking moving targets in unobservable regions, as a generalization of this aspect of PE. To achieve this, we first process sensor observation history and compress it in a lossless fashion for our task classes, for storage and effective computation. Next, depending on whether the targets of interest are moving nondeterministically or probabilistically, concrete problems are formulated and solved by carefully manipulating and fusing observation and data. At a higher level, at any time, our algorithm can estimate the number of targets hidden in regions not directly observable. We note that, although the active problem of planning a pursuit path is not addressed in this work, heuristic search strategies can be readily implemented on the space of filter outputs.

The mathematical study of PE games dates back to at least four decades ago, with its roots in differential games [14,15,13]. Although optimal strategies for differential PE games are still actively pursued [2,26,23,41], a variant of differential PE games, visibility based PE, has received much attention recently. Development of visibility based PE games can be traced back to [28], in which a PE game on discrete graph is introduced with the goal of sweeping evaders residing on continuous edges of a graph. The evaders can move arbitrarily fast, but must move continuously. The Watchman Route problem [6,7], formulated twelve years later as a variant of the Art Gallery problems [24,34], involves finding shortest route to clear static intruders. An intruder is considered cleared if a line of sight exists between the intruder and a point of the watchman route.

Influenced by these two threads of research, [37] defined what we know today as visibility based PE games in which the discrete graph domain is replaced by a path connected interior of a 2D polygon and a continuously moving evader is considered to be cleared if it falls into the visible region of a pursuer (in this case the pursuer is equipped with two flashlights and is called a $2$ -searcher). Thinking along the same lines as the Art Gallery problems, it was soon established that for a pursuer with an omnidirectional infinite range sensor (an $\infty$ -searcher), it is NP-hard to decided the minimum number of pursuers needed for the class of simply connected polygons [22,12]. The insight that bitangents and inflections fully capture the critical changes leads to a generalization from polygons to curved environments [21] and form the basis of some critical events used in our paper.

Various sensing and motion capabilities are explored in visibility based PE. Interestingly, it turns out that a $2$ -searcher is as capable as an $\infty$ -searcher in simple polygons [27]. Pursuers with a single flashlight/beam (a $1$ -searcher) are investigated in detail in [35] and [18], with the latter limiting the pursuer's motion to the boundary of the environment. Variations along this line include limited field-of-view [9], unknown environments [31], and bounded speed [39]. Another theme in PE games is to discretize time and put speed bounds on both pursuers and evaders. In this setting, sufficient conditions and strategies for a single pursuer to capture an evader are given to the classical lion-and-man problem in the first quadrant of the open plane [33]. This problem is then extended to $\mathbb{R}^n$ and multiple pursuers in [19], and multiple pursuers with limited range in [4]. Finally, PE is also studied in the probabilistic context [42,16] and abstract metric spaces [1].

Since we provide algorithms for tracking moving targets, our work is also closely related to target tracking and enumeration. The problem of accurately counting the number of targets with overlapping footprints is solved with a novel approach of integrating over Euler characteristics in [3]. With a virtual sensor that reports visible features of polygonal environment as well as indistinguishable targets, static targets are counted under various setups in [10]. A filtering algorithm is provided in [36] to count moving targets with a network of binary proximity sensors. In [43], Simultaneous Localization and Mapping (SLAM) and Detection and Tracking of Moving Objects (DTMO) are combined to attack both problem simultaneously. A specialization of our problem is investigated in [38] in which the sensor field-of-view becomes one dimensional beams. Real-time people counting with a network of image sensors is studied in [44].

The main contributions of this work are twofold. First, as explained above, we generalize visibility based PE by introducing a richer class of problems and providing a framework as a submodule for systematically attacking these problems. Second, the capability of effectively tracking hidden, moving targets, a general type of situation awareness, applies to a large class of time critical tasks in both civilian and national security applications. For example, in a fire evacuation scenario, knowing the the expected number of people trapped in various parts of a building, firefighters can better decide which part of the building should be given priority when they coordinate the search and rescue effort.

The rest of the paper is organized as follows. Section II provides a mathematical definition of what we mean by ``shadow components'' and ``component events'', which can be best captured using a chronological sequence. Section III brings in moving targets and field-of-view events. Section IV defines appropriate information spaces [20] for our problem, and introduces combinatorial filters as the tool of choice of compressing observation history. Section V formulates and solves the problem of estimating the number of targets hidden in shadow components for nondeterministically moving targets. Section VI extends the problem formulation and solutions to probabilistically moving targets and imperfect sensors. We provide implementation, simulation results and algorithmic analysis in Section VII, and conclude in Section VIII.