Synthesis of Surveillance Strategies via Belief Abstraction

arXiv:1709.05363v2 [cs.RO] 19 Mar 2018

Suda Bharadwaj1 and Rayna Dimitrova2 and Ufuk Topcu1

Abstract— We study the problem of synthesizing a controller
for a robot with a surveillance objective, that is, the robot is
required to maintain knowledge of the location of a moving,
possibly adversarial target. We formulate this problem as
a one-sided partial-information game in which the winning
condition for the agent is specified as a temporal logic formula.
The specification formalizes the surveillance requirement
given by the user, including additional non-surveillance
tasks. In order to synthesize a surveillance strategy that
meets the specification, we transform the partial-information
game into a perfect-information one, using abstraction to
mitigate the exponential blow-up typically incurred by such
transformations. This enables the use of off-the-shelf tools for
reactive synthesis. We use counterexample-guided refinement
to automatically achieve abstraction precision that is sufficient
to synthesize a surveillance strategy. We evaluate the proposed
method on two case-studies, demonstrating its applicability to
large state-spaces and diverse requirements.

I. INTRODUCTION
Performing surveillance, that is, tracking the location of
a target, has many applications. If the target is adversarial,
these applications include patrolling and defense, especially
in combination with other objectives, such as providing
certain services or accomplishing a mission. Techniques for
tracking non-adversarial but unpredictable targets have been
proposed in settings like surgery to control cameras to keep a
patient’s organs under observation despite unpredictable motion of occluding obstacles [1]. Mobile robots in airports have
also been proposed to carry luggage for clients, requiring the
robots to follow the human despite unpredictable motion and
possibly sporadically losing sight of the target [2].
When dealing with a possibly adversarial target, a strategy
for the surveying agent for achieving its objective can be seen
as a strategy in a two-player game between the agent and
the target. Since the agent may not always observe, or even
know, the exact location of the target, surveillance is, by its
very nature, a partial-information problem. It is thus natural
to reduce surveillance strategy synthesis to computing a winning strategy for the agent in a two-player partial-information
game. Game-based models for related problems have been
extensively studied in the literature. Notable examples include pursuit-evasion games [3], patrolling games [4], and
graph-searching games [5], where the problem is formulated
as enforcing eventual detection, which is, in its essence a
search problem – once the target is detected, the game ends.
For many applications, this formulation is too restrictive.
1 Suda Bharadwaj and Ufuk Topcu are with the University of Texas at
Austin
2 Rayna Dimitrova is with the University of Leicester, UK. Most of this
work was done while Rayna Dimitrova was a postdoctoral researcher at UT
Austin.

Often, the goal is not to detect or capture the target, but to
maintain certain level of information about its location over
an unbounded (or infinite) time duration, or, alternatively, be
able to obtain sufficiently precise information over and over
again. In other cases, the agent has an additional objective,
such as performing certain task, which might prevent him
from capturing the target, but allow for satisfying a more
relaxed surveillance objective.
In this paper, we study the problem of synthesizing strategies for enforcing temporal surveillance objectives, such as
the requirement to never let the agent’s uncertainty about
the target’s location exceed a given threshold, or recapturing
the target every time it escapes. To this end, we consider
surveillance objectives specified in linear temporal logic
(LTL), equipped with basic surveillance predicates. This formulation also allows for a seamless combination with other
task specifications. Our computational model is that of a twoplayer game played on a finite graph, whose nodes represent
the possible locations of the agent and the target, and whose
edges model the possible (deterministic) moves between
locations. The agent plays the game with partial information,
as it can only observe the target when it is in it’s area of sight.
The target, on the other hand, always has full information
about the agent’s location, even when the agent is not in
sight. In that way, we consider a model with one-sided partial
information, making the computed strategy for the agent
robust against a potentially more powerful adversary.
We formulate surveillance strategy synthesis as the problem of computing a winning strategy for the agent in a
partial-information game with a surveillance objective. There
is a rich theory on partial-information games with LTL
objectives [6], [7], and it is well known that even for
very simple objectives the synthesis problem is EXPTIMEhard [8], [9]. Moreover, all the standard algorithmic solutions
to the problem are based on some form of belief set construction, which transforms the imperfect-information game into
a perfect-information game and this may be exponentially
larger, since the new set of states is the powerset of the
original one. Thus, such approaches scale poorly in general,
and are not applicable in most practical situations.
We address this problem by using abstraction. We introduce an abstract belief set construction, which underapproximates the information-tracking abilities of the agent
(or, alternatively, overapproximates its belief, i.e., the set
of positions it knows the target could be in). Using this
construction we reduce surveillance synthesis to a two-player
perfect-information game with LTL objective, which we then
solve using off-the shelf reactive synthesis tools [10]. Our
construction guarantees that the abstraction is sound, that is,

if a surveillance strategy is found in the abstract game, it
corresponds to a surveillance strategy for the original game.
If, on the other hand, such a strategy is not found, then the
method automatically checks if this is due to the coarseness of the abstraction, in which case the abstract belief
space is automatically refined. Thus, our method follows
the general counterexample guided abstraction refinement
(CEGAR) [11] scheme, which has successfully demonstrated
its potential in formal verification and reactive synthesis.
Contributions. We make the following contributions:
(1) We propose a formalization of surveillance objectives as
temporal logic specifications, and frame surveillance strategy
synthesis as a partial-information reactive synthesis problem.
(2) We develop an abstraction method that soundly approximates surveillance strategy synthesis, thus enabling the
application of efficient techniques for reactive synthesis.
(3) We design procedures that automatically refine a given
abstraction in order to improve its precision when no surveillance strategy exists due to coarseness of the approximation.
(4) We evaluate our approach on different surveillance objectives (e.g, safety, and liveness) combined with task specifications, and discuss the qualitatively different behaviour of the
synthesized strategies for the different kinds of specifications.
Related work. While closely related to the surveillance
problem we consider, pursuit-evasion games with partial
information [3], [12], [13] formulate the problem as eventual
detection, and do not consider combinations with other
mission specifications. Other work, such as [14] and [15],
additionally incorporates map building during pursuit in an
unknown environment, but again solely for target detection.
Synthesis from LTL specifications [16], especially from
formulae in the efficient GR(1) fragment [17], has been
extensively used in robotic planning (e.g. [18], [19]), but
surveillance-type objectives, such as the ones we study here,
have not been considered so far. Epistemic logic specifications [20] can refer to the knowledge of the agent about
the truth-value of logical formulas, but, contrary to our
surveillance specifications, are not capable of expressing
requirements on the size of the agent’s uncertainty.
CEGAR has been developed for verification [11], and later
for control [21], of LTL specifications. It has also been
extended to infinite-state partial-information games [22],
and used for sensor design [23], both in the context of
safety specifications. In addition to being focused on safety
objectives, the refinement method in [22] is designed to
provide the agent with just enough information to achieve
safety, and is thus not applicable to surveillance properties
whose satisfaction depends on the size of the belief sets.
II. GAMES WITH SURVEILLANCE OBJECTIVES
We begin by defining a formal model for describing
surveillance strategy synthesis problems, in the form of a
two-player game between an agent and a target, in which the
agent has only partial information about the target’s location.
A. Surveillance Game Structures
We define a surveillance game structure to be a tuple G =
(S, sinit , T, vis), with the following components:

0

1

2

3

4

vis(4, 18) = false, vis(4, 17) = false,

5

6

7

8

9

vis(4, 19) = true, vis(4, 23) = false

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

(a) Surveillance arena

(4, 18)
(3, 17) (3, 19) (3, 23) (9, 17) (9, 19) (9, 23)

(b) Transitions from the initial state

Fig. 1: A simple surveillance game on a grid arena. Obstacles
are shown in red, the agent (at location 4) and the target (at
location 18) are coloured in blue and orange respectively.
• S = La × Lt is the set of states, with La the set of
locations of the agent, and Lt the locations of the target;
init
• s
= (lainit , ltinit ) is the initial state;
• T ⊆ S × S is the transition relation describing the
possible moves of the agent and the target; and
• vis : S → B is a function that maps a state (la , lt ) to
true iff position lt is in the area of sight of la .
The transition relation T encodes the one-step move of
both the target and the agent, where the target moves first
and the agent moves second. For a state (la , lt ) we denote
succ t (la , lt ) as the set of successor locations of the target:
succ t (la , lt ) = {lt0 ∈ Lt | ∃la0 . ((la , lt ), (la0 , lt0 )) ∈ T }.
We extend succ t to sets of locations of the target by
stipulating that the set succ t (la , L) consists of all possible
successor locations of the target
for states in {la } × L.
S
Formally, let succ t (la , L) = lt ∈L succ t (la , lt ).
For a state (la , lt ) and a successor location of the target lt0 ,
we denote with succ a (la , lt , lt0 ) the set of successor locations
of the agent, given that the target moves to lt0 :
succ a (la , lt , lt0 ) = {la0 ∈ La | ((la , lt ), (la0 , lt0 )) ∈ T }.
We assume that, for every s ∈ S, there exists s0 ∈ S
such that (s, s0 ) ∈ T , that is, from every state there is at
least one move possible (this might be staying in the same
state). We also assume that when the target moves to an
invisible location, its position does not influence the possible
one-step moves of the agent. Formally, we require that if
vis(la , lt000 ) = vis(la , lt0000 ) = false, then succ a (la , lt0 , lt000 ) =
succ a (la , lt00 , lt0000 ) for all lt0 , lt00 , lt000 , lt0000 ∈ Lt . This assumption
is natural in the setting when the agent can move in one step
only to locations that are in its sight.
Example 1: Figure 1 shows an example of a surveillance
game on a grid. The sets of possible locations La and Lt for
the agent and the target consist of the squares of the grid. The
transition relation T encodes the possible one-step moves of
both the agent and the target on the grid, and incorporates
all desired constraints. For example, moving to an occupied
location, or an obstacle, is not allowed. Figure 1b shows the
possible transitions from the initial state (4, 18).
The function vis encodes straight-line visibility: a location
lt is visible from a location la if there is no obstacle on
the straight line between them. Initially the target is not
in the area of sight of the agent, but the agent knows the
initial position of the target. However, once the target moves
to one of the locations reachable in one step, in this case,
locations {17, 19, 23}, this might no longer be the case. More
precisely, if the target moves to location 19, then the agent
observes its location, but if it moves to one of the others,
then the agent no longer knows its exact location.


(4, {18})
(3, {19}) (3, {17, 23})

(9, {19}) (9, {17, 23})

Fig. 2: Transitions from the initial state in the belief-set game
from Example 2 where vis(4, 17) = vis(4, 23) = false.

The outcome of given strategies fa and ft for the agent
and the target in Gbelief , denoted outcome(Gbelief , fa , ft ), is
a run s0 , s1 , . . . of Gbelief such that for every i ≥ 0, we have
si+1 = fa (s0 , . . . , si , Bti ), where Bti = ft (s0 , . . . , si ).
C. Temporal Surveillance Objectives

B. Belief-Set Game Structures
In surveillance strategy synthesis we need to state properties of, and reason about, the information which the agent
has, i.e. its belief about the location of the target. To this end,
we can employ a powerset construction which is commonly
used to transform a partial-information game into a perfectinformation one, by explicitly tracking the knowledge one
player has as a set of possible states of the other player.
Given a set B, we denote with P(B) = {B 0 | B 0 ⊆ B}
the powerset (set of all subsets) of B.
For a surveillance game structure G = (S, sinit , T, vis) we
define the corresponding belief-set game structure Gbelief =
(Sbelief , sinit
belief , Tbelief ) with the following components:
• Sbelief = La × P(Lt ) is the set of states, with La the set
of locations of the agent, and P(Lt ) the set of belief sets
describing information about the location of the target;
init
init
init
• sbelief = (la , {lt }) is the initial state;
• Tbelief ⊆ Sbelief × Sbelief is the transition relation where
((la , Bt ), (la0 , Bt0 )) ∈ Tbelief iff la0 ∈ succ a (la , lt , lt0 ) for
some lt ∈ Bt and lt0 ∈ Bt0 and one of these holds:
(1) Bt0 = {lt0 }, lt0 ∈ succ t (la , Bt ), vis(la , lt0 ) = true;
(2) Bt0 = {lt0 ∈ succ t (la , Bt ) | vis(la , lt0 ) = false}.
Condition (1) captures the successor locations of the target
that can be observed from the agent’s current position la .
Condition (2) corresponds to the belief set consisting of all
possible successor locations of the target not visible from la .
Example 2: Consider the surveillance game structure
from Example 1. The initial belief set is {18}, consisting of
the target’s initial position. After the first move of the target,
there are two possible belief sets: the set {19} resulting from
the move to a location in the area of sight of the agent, and
{17, 23} consisting of the two invisible locations reachable
in one step from location 18. Figure 2 shows the successor
states of the initial state (4, {18}) in Gbelief .

Based on Tbelief , we can define the functions succ t :
Sbelief → P(P(Lt )) and succ a : Sbelief × P(Lt ) → P(La )
similarly to the corresponding functions defined for G.
A run in Gbelief is an infinite sequence s0 , s1 , . . . of states
in Sbelief , where s0 = sinit
belief , (si , si+1 ) ∈ Tbelief for all i.
A strategy for the target in Gbelief is a function ft :
+
Sbelief
→ P(Lt ) such that ft (π · s) = Bt implies Bt ∈
∗
succ t (s) for every π ∈ Sbelief
and s ∈ Sbelief . That is, a
strategy for the target suggests a move resulting in some
belief set reachable from some location in the current belief.
A strategy for the agent in Gbelief is a function fa : S + ×
P(Lt ) → S such that fa (π · s, Bt ) = (la0 , Bt0 ) implies Bt0 =
∗
Bt and la0 ∈ succ a (s, Bt ) for every π ∈ Sbelief
, s ∈ Sbelief
and Bt ∈ P(Lt ). Intuitively, a strategy for the agent suggests
a move based on the observed history of the play and the
current belief about the target’s position.

Since the states of a belief-set game structure track the
information that the agent has, we can state and interpret
surveillance objectives over its runs. We now formally define
the surveillance properties in which we are interested.
We consider a set of surveillance predicates SP = {pk |
k ∈ N>0 }, where for k ∈ N>0 we say that a state (la , Bt ) in
the belief game structure satisfies pk (denoted (la , Bt ) |= pk )
iff |{lt ∈ Bt | vis(la , lt ) = false}| ≤ k. Intuitively, pk is
satisfied by the states in the belief game structure where the
size of the belief set does not exceed the threshold k ∈ N>0 .
We study surveillance objectives expressed by formulas of
linear temporal logic (LTL) over surveillance predicates. The
LTL surveillance formulas are generated by the grammar
ϕ := p | true | false | ϕ ∧ ϕ | ϕ ∨ ϕ | ϕ | ϕ U ϕ | ϕ R ϕ,
where p ∈ SP is a surveillance predicate,
is the next
operator, U is the until operator, and R is the release
operator. We also define the derived operators finally: ϕ =
true U ϕ and globally: ϕ = false R ϕ.
LTL formulas are interpreted over (infinite) runs. If a run
ρ satisfies an LTL formula ϕ, we write ρ |= ϕ. The formal
definition of LTL semantics can be found in [24]. Here we
informally explain the meaning of the formulas we use.
Of special interest will be surveillance formulas of the
form pk , termed safety surveillance objective, and
pk ,
called liveness surveillance objective. Intuitively, the safety
surveillance formula pk is satisfied if at each point in time
the size of the belief set does not exceed k. The liveness
surveillance objective
pk , on the other hand, requires
that infinitely often this size is below or equal to k.
Example 3: We can specify that the agent is required to
always know with certainty the location of the target as p1 .
A more relaxed requirement is that the agent’s uncertainty
never grows above 5 locations, and it infinitely often reduces
this uncertainty to at most 2 locations: p5 ∧
p2 . 
D. Incorporating Task Specifications
We can integrate LTL objectives not related to surveillance, i.e., task specifications, by considering, in addition to
SP, a set AP of atomic predicates interpreted over states of
G. In order to define the semantics of p ∈ AP over states
of Gbelief , we restrict ourselves to predicates observable by
the agent. Formally, we require that for p ∈ AP, and states
(la , lt0 ) and (la , lt00 ) with vis(la , lt0 ) = vis(la , lt00 ) = false it
holds that (la , lt0 ) |= p iff (la , lt00 ) |= p. One class of such
predicates are those that depend only on the agent’s position.
Example 4: Suppose that at goal is a predicate true exactly when the agent is at some designated goal location. We
can then state that the agent visits the goal infinitely often
while always maintaining belief uncertainty of at most 10
locations using the LTL formula
at goal ∧ p10 . 

E. Surveillance Synthesis Problem
A surveillance game is a pair (G, ϕ), where G is a
surveillance game structure and ϕ is a surveillance objective.
A winning strategy for the agent for (G, ϕ) is a strategy fa
for the agent in the corresponding belief-set game structure
Gbelief such that for every strategy ft for the target in Gbelief
it holds that outcome(Gbelief , fa , ft ) |= ϕ. Analogously, a
winning strategy for the target for (G, ϕ) is a strategy ft
such that, for every strategy fa for the agent in Gbelief , it
holds that outcome(Gbelief , fa , ft ) 6|= ϕ.
Surveillance synthesis problem: Given a surveillance
game (G, ϕ), compute a winning strategy for the agent for
(G, ϕ), or determine that such a strategy does not exist.
It is well-known that two-player perfect-information
games with LTL objectives over finite-state game structures
are determined, that is exactly one of the players has a
winning strategy. This means that the agent does not have a
winning strategy for a given surveillance game, if and only
if the target has a winning strategy for this game. We refer
to winning strategies of the target as counterexamples.
III. BELIEF SET ABSTRACTION
We used the belief-set game structure in order to state the
surveillance objective of the agent. While in principle it is
possible to solve the surveillance strategy synthesis problem
on this game, this is in most cases computationally infeasible,
since the size of this game is exponential in the size of
the original game. To circumvent this construction when
possible, we propose an abstraction-based method, that given
a surveillance game structure and a partition of the set of the
target’s locations, yields an approximation that is sound with
respect to surveillance objectives for the agent.
An abstraction partition is a family Q = {Qi }ni=1 of
subsets of Lt , Qi ⊆ Lt such that the following hold:
Sn
•
i=1 Qi = Lt and Qi ∩ Qj = ∅ for all i 6= j;
• For each p ∈ AP, Q ∈ Q and la ∈ La , it holds that
(la , lt0 ) |= p iff (la , lt00 ) |= p for every lt0 , lt00 ∈ Q.
Intuitively, these conditions mean that Q partitions the set of
locations of the target, and the concrete locations in each of
the sets in Q agree on the value of the propositions in AP.
If Q0 = {Q0i }m
i=1 is a family of subsets of Lt such that
Sm
0
Q
=
L
and
for each Q0i ∈ Q0 there exists Qj ∈ Q
t
i=1 i
0
such that Qi ⊆ Qj , then Q0 is also an abstraction partition,
and we say that Q0 refines Q, denoted Q0  Q.
For Q = {Qi }ni=1 , we define a function αQ : Lt → Q by
α(lt ) = Q for the unique Q ∈ Q with lt ∈ Q. We denote also
with αQ : P(Lt ) → P(Q) the abstraction function defined
by αQ (L) = {αQ (l) | l ∈ L}. We define a concretization
function γ : P(Q) ∪ Lt →SP(Lt ) such that γ(A) = {lt } if
A = lt ∈ Lt , and γ(A) = Q∈A Q if A ∈ P(Q).
Given a surveillance game structure G = (S, sinit , T, vis)
and an abstraction partition Q = {Qi }ni=1 of the set Lt , we
define the abstraction of G w.r.t. Q to be the game structure
Gabstract = αQ (G) = (Sabstract , sinit
abstract , Tabstract ), where
• Sabstract = (La ×P(Q))∪(La ×Lt ) is the set of abstract
states, consisting of states approximating the belief sets
in the game structure Gbelief , as well as the states S;

(4, 18)
(3, {Q4 , Q5 })

(3, 19)

(9, {Q4 , Q5 })

(9, 19)

Fig. 3: Transitions from the initial state in the abstract game
from Example 5 where αQ (17) = Q4 and αQ (23) = Q5 .
init init
sinit
abstract = (la , lt ) is the initial abstract state;
• Tabstract ⊆ Sabstract × Sabstract is the transition relation
such that ((la , At ), (la0 , A0t )) ∈ Tabstract if and only if
one of the following two conditions is satisfied:
(1) A0t = lt0 , lt0 ∈ succ t (γ(At )) and vis(la , lt0 ) = true,
and la0 ∈ succ a (la , lt , lt0 ) for some lt ∈ γ(At ).
(2) A0t = αQ ({lt0 ∈ succ t (γ(At ))|vis(la , lt0 ) = false}),
and la0 ∈ succ a (la , lt , lt0 ) for some lt ∈ γ(At ) and
some lt0 ∈ succ t (γ(At )) with vis(la , lt0 ) = false.
As for the belief-set game structure, the first condition
captures the successor locations of the target, which can be
observed from the agent’s current location la . Condition (2)
corresponds to the abstract belief set whose concretization
consists of all possible successors of all positions in γ(At ),
which are not visible from la . Since the belief abstraction
overapproximates the agent’s belief, that is, γ(αQ (B)) ⊇ B,
the next-state abstract belief γ(A0t ) may include positions in
Lt that are not successors of positions in γ(At ).
Example 5: Consider again the surveillance game from
Example 1, and the abstraction partition Q = {Q1 , . . . , Q5 },
where the set Qi corresponds to the i-th row of the grid.
For location 17 of the target we have αQ (17) = Q4 ,
and for 23 we have αQ (23) = Q5 . Thus, the belief set
B = {17, 23} is covered by the abstract belief set αQ (B) =
{Q4 , Q5 }. Figure 3 shows the successors of the initial
state (4, 18) of the abstract belief-set game structure. The
concretization of the abstract belief set {Q4 , Q5 } is the set
{15, 16, 17, 18, 19, 20, 21, 22, 23, 24} of target locations. 
An abstract state (la , At ) satisfies a surveillance predicate
pk , denoted (la , At ) |= pk , iff |{lt ∈ γ(At ) | vis(la , lt ) =
false}| ≤ k. Simply, the number of states in the concretized
belief set has to be less than or equal to k. Similarly, for
a predicate p ∈ AP, we define (la , At ) |= p iff for every
lt ∈ γ(At ) it holds that (la , lt ) |= p. With these definitions,
we can interpret surveillance objectives over runs of Gabstract .
Strategies (and wining strategies) for the agent and the
target in an abstract belief-set game (αQ (G), ϕ) are defined
analogously to strategies (and winning strategies) in Gbelief .
In the construction of the abstract game structure, we
overapproximate the belief-set of the agent at each step.
Since we consider surveillance predicates that impose upper
bounds on the size of the belief, such an abstraction gives
more power to the target (and, dually less power to the agent).
This construction guarantees that the abstraction is sound,
meaning that an abstract strategy for the agent that achieves
a surveillance objective corresponds to a winning strategy in
the concrete game. This is stated in the following theorem.
Theorem 1: Let G be a surveillance game structure, Q =
{Qi }ni=1 be an abstraction partition, and Gabstract = αQ (G).
For every surveillance objective ϕ, if there exists a wining strategy for the agent in the abstract belief-set game
•

v0 : (4, 18)
(4, 18)
(3, {Q4 , Q5 })(9, {Q4 , Q5 })

(a) Abstract counterexample tree

(4, 18)
(3, {17, 23}) (9, {17, 23})

(b) Concrete counterexample tree

Fig. 4: Abstract and corresponding concrete counterexample
trees for the surveillance game in Example 6.
(αQ (G), ϕ), then there exists a winning strategy for the agent
in the concrete surveillance game (G, ϕ).
IV. BELIEF REFINEMENT FOR SAFETY
A. Counterexample Tree
A winning strategy for the target in a game with safety
surveillance objective can be represented as a tree. An
abstract counterexample tree Cabstract for (Gabstract , pk ) is
a finite tree, whose nodes are labelled with states in Sabstract
such that the following conditions are satisfied:
•
•
•

The root node is labelled with the initial state sinit
abstract .
A node is labelled with an abstract state which violates
pk (that is, sabstract where sabstract 6|= pk ) iff it is a leaf.
The tree branches according to all possible transition
choices of the agent. Formally, if an internal node v is
labelled with (la , At ), then there is unique A0t such that:
(1) ((la , At ), (la0 , A0t )) ∈ Tabstract for some la0 ∈ La , and
(2) for every la0 ∈ La such that ((la , At ), (la0 , A0t )) ∈
Tabstract , there is a child v 0 of v labelled with (la0 , A0t ).

A concrete counterexample tree Cbelief for (Gbelief , pk )
is a finite tree defined analogously to an abstract counterexample tree with nodes labelled with states in Sbelief .
Due to the overapproximation of the belief sets, not
every counterexample in the abstract game corresponds to
a winning strategy for the target in the original game.
An abstract counterexample Cabstract in (Gabstract , pk ) is
concretizable if there exists a concrete counterexample tree
Cbelief in (Gbelief , pk ), that differs from Cabstract only in the
node labels, and each node labelled with (la , At ) in Cabstract
has label (la , Bt ) in Cbelief for which Bt ⊆ γ(At ).
Example 6: Figure 4a shows an abstract counterexample
tree Cabstract for the game (αQ (G), p1 ), where G is the
surveillance game structure from Example 1 and Q is the
abstraction partition from Example 5. The counterexample
corresponds to the choice of the target to move to one of
the locations 17 or 23, which, for every possible move of
the agent, results in an abstract state with abstract belief
B = {Q4 , Q5 } violating p1 . A concrete counterexample tree
Cbelief concretizing Cabstract is shown in Figure 4b.

B. Counterexample-Guided Refinement
We now describe a procedure that determines whether an
abstract counterexample for a safety surveillance objective
is concretizable. This procedure essentially constructs the
precise belief sets corresponding to the abstract moves of
the target that constitute the abstract counterexample.

v1 : (3, {Q2 })

v2 : (9, {Q2 })

v3 : (2, A) v4 : (4, A) v5 : (8, A)

v6 : (4, A) v7 : (8, A) v8 : (14, A)

Fig. 5: Abstract counterexample in Example 7. The leaf
nodes are labelled with the abstract belief set A = {Q1 , Q2 }.
1) Forward belief-set propagation: Given an abstract
counterexample tree Cabstract , we annotate its nodes with
states in Sbelief in a top-down manner as follows. The root
node is labelled with sinit
belief . If v is a node annotated with the
belief set (la , Bt ) ∈ Sbelief , and v 0 is a child of v in Cabstract
labelled with an abstract state (la0 , A0t ), then we annotate v 0
with the belief set (la0 , Bt0 ), where Bt0 = succ t (la , Bt ) ∩
γ(A0t ). The counterexample analysis procedure based on
this annotation is given in Algorithm 1. If each of the leaf
nodes of the tree is annotated with a belief set (la , Bt ) for
which (la , Bt ) 6|= pk , then the new annotation gives us a
concrete counterexample tree Cbelief , which by construction
concertizes Cabstract . Conversely, if there exists a leaf node
annotated with (la , Bt ) such that (la , Bt ) |= pk , then we can
conclude that the abstract counterexample tree Cabstract is not
concretizable and use the path from the root of the tree to
this leaf node to refine the partition Q.
Theorem 2: If Algorithm 1 returns a path πabstract in
Cabstract , then Cabstract is not concretizable, and πabstract is
a non-concretizable path, otherwise Cabstract is concretizable.
Example 7: Let G be the surveillance game structure from
Example 1, and consider the surveillance game (G, p5 ).
Let Q = {Q1 , Q2 } consist of the set Q1 , corresponding to
the first two columns of the grid in Figure 1a and the set Q2
containing the locations from the other three columns of the
grid. Figure 5 shows a counterexample tree Cabstract in the
abstract game (αQ (G), p5 ). The analysis in Algorithm 1
annotates node v1 with the concrete belief set {17, 23},
and the leaf node v3 with the set B = {16, 18, 22, 24}.
Thus, this counterexample tree Cabstract is determined to be
unconcretizable and the partition Q should be refined.

When the analysis procedure determines that an abstract
counterexample tree is unconcretizable, it returns a path in
the tree that corresponds to a sequence of moves ensuring
that the size of the belief-set does not actually exceed the
threshold, given that the target behaves in a way consistent
with the abstract counterexample. Based on this path, we can
Input: surveillance game (G, pk ),
abstract counterexample tree Cabstract
Output: a path π in Cabstract or CONCRETIZABLE
while there is a node v in Cabstract whose children
are not annotated with states in Sbelief do
let (la , Bt ) be the state with which v is annotated;
foreach child v 0 of v labelled with (la0 , A0t ) do
annotate v 0 with (la0 , succ t (la , Bt ) ∩ γ(A0t ));
if there is a path π in Cabstract from the root to a leaf
annotated with a sate sbelief where sbelief |= pk
then return π; else return CONCRETIZABLE;

Algorithm 1: Analysis of abstract counterexample trees
for games with safety surveillance objectives.

then refine the abstraction in order to precisely capture this
information and thus eliminate this abstract counterexample.
2) Backward partition splitting: Let πabstract = v0 , . . . , vn
be a path in Cabstract where v0 is the root node and vn is
a leaf. For each node vi , let (lai , Ait ) be the abstract state
labelling vi in Cabstract , and let (lai , Bti ) be the belief set
with which the node was annotated by the counterexample
analysis procedure. We consider the case when (lan , Btn ) |=
pk , that is, |{lt ∈ Btn | vis(la , lt ) = false}| ≤ k. Note that
since Cabstract is a counterexample we have (lan , Ant ) 6|= pk ,
and since k > 0, this means At ∈ P(Q).
We now describe a procedure to compute a partition Q0
that refines the current partition Q based on the path πabstract .
Intuitively, we split the sets that appear in Ant in order to
ensure that in the refined abstract game the corresponding
abstract state satisfies the surveillance predicate pk . We may
have to also split sets appearing in abstract states on the path
to vn , as we have to ensure that earlier imprecisions on this
path do not propagate, thus including more than the desired
newly split sets, and leading to the same violation of pk .
Formally, if Ant = (lan , {Bn,1 , . . . , Bn,mn }), then we split
some of the sets Bn,1 , . . . , Bn,mn to obtain from Ant a set
0
0
, . . . , Bn,m
A0n = {Bn,1
0 } such that
n
n
|{lt ∈ γ(C ) | vis(lan , lt ) = false}| ≤ k, where
0
0
∩ Btn 6= ∅}.
C n = {Bn,i
∈ A0n | Bn,i
This property intuitively means that if we consider the sets
in A0n that have non-empty intersection with Btn , an abstract
state composed of those sets will satisfy pk . Since (lan , Btn )
satisfies pk , we can find a partition Qn  Q that guarantees
this property, as shown in Algorithm 2.
What remains, in order to eliminate this counterexample,
is to ensure that only these sets are reachable via the considered path, by propagating this split backwards, obtaining
a sequence of partitions Q  Qn  . . .  Q0 refining Q.
Given Qj+1 , we compute Qj as follows. For each j,
we define a set C j ⊆ P(Lt ) (for j = n, the set C n
was defined above). Suppose we have defined C j+1 for
some j ≥ 0, and Ajt = (laj , {Bj,1 , . . . , Bj,mj }). We split
some of the sets Bj,1 , . . . , Bj,mj to obtain from Ajt a set
0
0
j
A0j = {Bj,1
, . . . , Bj,m
⊆ A0j with
0 } where there exists C
j

γ(C j ) = {lt ∈ γ(Ajt ) | succ t (laj , {lt })∩γ(Aj+1
) ⊆ γ(C j+1 )}.
t
This means that using the new partition we can express
precisely the set of states that do not lead to sets in A0j+1 that
we are trying to avoid. The fact that an appropriate partition
Q can be computed, follows from the choice of the leaf node
vn . The procedure for computing the partition Q0 = Q0 that
refines Q based on πabstract is formalized in Algorithm 2.
Example 8: We continue with the unconcretizable abstract
counterexample tree from Example 7. We illustrate the
refinement procedure for the path v0 , v1 , v3 . For node v3 ,
we split Q1 and Q2 using the set B = {16, 18, 22, 24},
obtaining the sets Q01 = Q1 ∩ {16, 18, 22, 24} = {16},
Q02 = Q1 \ {16}, Q03 = Q2 ∩ {16, 18, 22} = {18, 22, 24}
and Q04 = Q2 \ {18, 22, 24}. We thus obtain a new partition
Qv3  Q. In order to propagate the refinement backwards (to

ensure eliminating Cabstract ) we compute the set of locations
in Q2 from which the target can move to a location in Q02 or
Q04 that is not visible from location 3. In this case, these are
just the locations 18, 22 and 24, which have already been
separated from Q2 , so here backward propagation does not
require further splitting.

Let Q and Q0 be two counterexample partitions such that
Q0  Q. Let Cabstract be an abstract counterexample tree
in (αQ (G), pk ). We define γQ0 (Cabstract ) to be the set of
abstract counterexample trees in (αQ0 (G), pk ) such that
0
0
Cabstract
∈ γQ0 (Cabstract ) iff Cabstract
differs from Cabstract only
in the node labels and for every node in Cabstract labelled with
0
(la , At ), the corresponding node in Cabstract
is labelled with
0
an abstract state (la , At ) such that γ(A0t ) ⊆ γ(At ).
The theorem below states the progress property (eliminating the considered counterexample) of Algorithm 2.
Theorem 3: If Q0 is the partition returned by Algorithm 2 for an unconcretizable abstract counterexample
Cabstract in (αQ (G), pk ), then γQ0 (Cabstract ) = ∅, and also
γQ00 (Cabstract ) = ∅ for every partition Q00 where Q00  Q0 .
Example 9: In the surveillance game (G, p5 ), where G
is the surveillance game structure from Example 1, the agent
has a winning strategy. After 6 iterations of the refinement
loop we arrive at an abstract game (αQ∗ (G), p5 ), where
the partition Q∗ consists of 11 automatically computed sets
(as opposed to the 22 locations reachable by the target in
G), which in terms of the belief-set construction means 211
versus 222 possible belief sets in the respective games.
In the game (G, p2 ), on the other hand, the agent does
not have a winning strategy, and our algorithm establishes
this after one refinement, after which, using a partition of
size 4, it finds a concretizable abstract counterexample. 
V. BELIEF REFINEMENT FOR LIVENESS
A. Counterexample Graph
The counterexamples for general surveillance properties
are directed graphs, which may contain cycles. In particular,
pk each
for a liveness surveillance property of the form
Input: surveillance game (G, pk ), abstraction partition
Q,
unconcretizable path π = v0 , . . . , vn in Cabstract
Output: an abstraction partition Q0 such that Q0  Q
let (laj , Ajt ) be the label of vj , and (laj , Btj ) its annotation;
n
A :={Q ∩ Btn | Q ∈ An
t , Q ∩ Bt 6= ∅}∪
n
n
n
{Q \ Bt | Q ∈ At , Q \ Bt 6= ∅};
n
Q0 := (Q \ An
t ) ∪ A; C := {Q ∈ A | Q ∩ Bt 6= ∅}
for j = n − 1, . . . , 0 do
if Ajt ∈ Lt then break;
B := {lt ∈ γ(Ajt ) | succ t (la , {lt }) ⊆ γ(C)};

A :={Q ∩ B | Q ∈ Ajt , Q ∩ B 6= ∅}∪
{Q \ B | Q ∈ Ajt , Q \ B 6= ∅};
Q0 := (Q0 \ Ajt ) ∪ A; C := {Q ∈ A | Q ∩ B 6= ∅}
return Q0

Algorithm 2: Abstraction partition refinement given an
unconcretizable path in an abstract counterexample tree.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

Fig. 6: Agent locations on an (infinite)
path in the abstract counterexample
graph from Example 10. In the graph,
the first node is labelled with (4, 18),
the second with (9, {Q2 }), and all
other nodes with some (la , {Q1 , Q2 }).

infinite path in the graph has a position such that, from this
position on, each state on the path violates pk . An abstract
counterexample graph in the game (Gabstract ,
pk ) is
a finite graph Cabstract defined analogously to the abstract
counterexample tree. The difference being that there are no
leaves, and that for each cycle ρ = v1 , v2 , . . . , vn with
v1 = vn in Cabstract that is reachable from v0 , every node
vi in ρ is labelled with state siabstract where siabstract 6|= pk .
Example 10: We saw in Example 9 that in the safety
surveillance game (G, p2 ) the agent does not have a
winning strategy. We now consider a relaxed requirement,
namely, that the uncertainty drops to at most 2 infinitely ofp2 ).
ten. We consider the liveness surveillance game (G,
Let Q = {Q1 , Q2 } be the partition from Example 7.
Figure 6 shows an infinite path (in lasso form) in the
abstract game (αQ (G),
p2 ). The figure depicts only the
corresponding trajectory (sequence of positions) of the agent.
The initial abstract state is (4, 18), the second node on the
path is labeled with the abstract state (9, {Q2 }), and all other
nodes on the path are labeled with abstract states of the form
(la , {Q1 , Q2 }). As each abstract state in the cycle violates
p2 , the path violates
p2 . The same holds for all infinite
paths in the existing abstract counterexample graph.

A concrete counterexample graph Cbelief for the belief
game (Gbelief ,
pk ) is defined analogously.
An abstract counterexample graph Cabstract for the game
(Gabstract ,
pk ) is concretizable if there exists a counterexample Cbelief in (Gbelief ,
pk ), such that for each
0
1
infinite path πabstract = vabstract
, vabstract
, . . . starting from
the initial node of Cabstract there exists an infinite path
0
1
πbelief = vbelief
, vbelief
, . . . in Cbelief staring from its initial
i
node such that if vabstract
is labelled with (la , At ) in Cabstract ,
i
then the corresponding node vbelief
in Cbelief is labelled with
(la , Bt ) for some Bt ∈ P(Lt ) for which Bt ⊆ γ(At ).
B. Counterexample-Guided Refinement
1) Forward belief-set propagation: To check if an abstract
counterexample graph Cabstract is concretizable, we construct
a finite graph D whose nodes are labelled with elements of
Sbelief and with nodes of Cabstract . By construction we will
ensure that if a node d in D is labelled with h(la , Bt ), vi,
where (la , Bt ) is a belief state, and v is a node in Cabstract ,
then v is labelled with (la , At ) in Cabstract , and Bt ⊆ γ(At ).
Initially D contains a single node d0 labelled with
hsinit
belief , v0 i, where v0 is initial node of Cabstract . Consider
a node d in D labelled with h(la , Bt ), vi. For every child v 0
of v in Cabstract , labelled with an abstract state (la0 , A0t ) we
proceed as follows. We let Bt 0 = succ t (la , Bt ) ∩ γ(A0t ). If
there exists a node d0 in D labelled with h(la0 , Bt0 ), vi, then
we add an edge from d to d0 in D. Otherwise, we create such
a node and add the edge. We continue until no more nodes

and edges can be added to D. The procedure is guaranteed to
terminate, since both the graph Cbelief , and Sbelief are finite,
and we add a node labelled hsbelief , vi to D at most once.
If the graph D contains a reachable cycle (it suffices to
consider simple cycles, i.e., without repeating intermediate
nodes) ρ = d0 , . . . , dn with d0 = dn such that some di is
labelled with (la , Bt ) where (la , Bt ) |= pk , then we conclude
that the abstract counterexample Cabstract is not concretizable.
If no such cycle exists, then D is a concrete counterexample
pk ).
graph for the belief game (Gbelief ,
Example 11: The abstract counterexample graph in the
game (αQ (G),
p2 ) discussed in Example 10 is not
conretizable, since for the path in the abstract graph depicted
in Figure 6 there exists a corresponding path in the graph D
with a node in the cycle labelled with a set in Gbelief that
satisfies p2 . More precisely, the cycle in the graph D contains
a node labelled with (19, {10}). Intuitively, as the agent
moves from the upper to the lower part of the grid along
this path, upon not observing the target, it can infer from the
sequence of observations that the only possible location of
the target is 10. Thus, this paths is winning for the agent. 
Theorem 4: If Algorithm 3 returns a path π in the graph
D constructed for Cabstract , then Cabstract is not concretizable,
and the infinite run in Gbelief corresponding to π satisfies
pk , otherwise Cabstract is concretizable.
2) Backward partition splitting: Consider a path in the
graph D of the form π = d0 , . . . , dn , d00 , . . . , d0m where
dn = d0m , and where for some 0 ≤ i ≤ m for the
label (lai , Bti ) it holds that (lai , Bti ) |= pk . Let πabstract =
0
v0 , . . . , vn , v00 , . . . , vm
be the sequence of nodes in Cabstract
corresponding to the labels in π. By construction of D,
0
. We apply the
πabstract is a path in Cabstract and vn = vm
refinement procedure from the previous section to the whole
Input: surveillance game (G,
pk ), abstract
counterexample graph Cabstract with initial node v0
Output: a path π in a graph D or CONCRETIZABLE
graph D = (D, E) with nodes D := {d0 } and edges
E := ∅;
annotate d0 with hsinit
belief , v0 i;
do
D0 := D;
foreach node d in D labelled with h(la , Bt ), vi do
foreach child v 0 of v in Cabstract labelled (la0 , A0t )
do
Bt0 := succ t (la , Bt ) ∩ γ(A0t );
if there is a node d0 ∈ D labelled with
h(la0 , Bt0 ), v 0 i then
add an edge (d, d0 ) to E
else
add a node d0 labelled h(la0 , Bt0 ), v 0 i to D;
add an edge (d, d0 ) to E
while D 6= D0 ;
if there is a lasso path π in D starting from d0 such that
some node in the cycle is annotated with hsbelief , vi and
sbelief |= pk
then return π; else return CONCRETIZABLE;

Algorithm 3: Analysis of abstract counterexample
graphs for games with liveness surveillance objectives.

path πabstract , as well as to the path-prefix v0 , . . . , vn .
Let Q and Q0 be two counterexample partitions such that
0
Q  Q. Let Cabstract be an abstract counterexample graph
in (αQ (G),
pk ). We define γQ0 (Cabstract ) to be the set
pk ) such
of abstract counterexample graphs in (αQ0 (G),
0
that for every infinite path π in Cabstract
there exists an infinite
path π in Cabstract such that for every node in π 0 labelled with
(la , A0t ) the corresponding node in Cabstract is labelled with
an abstract state (la , At ) such that γ(A0t ) ⊆ γ(At ).
Theorem 5: If Q0 is the partition obtained by refining Q
with respect to an uncocretizable abstract counterexample
pk ), then γQ0 (Cabstract ) = ∅, and
Cabstract in (αQ (G),
also γQ00 (Cabstract ) = ∅ for every partition Q00 with Q00  Q0 .
Example 12: We refine the abstraction partition Q from
Example 6 using the path identified there, in order to
eliminate the abstract counterexample. For this, following
the refinement algorithm, we first split the set Q1 into sets
Q01 = {10} and Q02 = Q1 \{10}, and let Q03 = Q2 . However,
since from some locations in Q02 and in Q03 the target can
reach locations in Q02 and Q03 that are not visible from the
agent’s position 19, in order to eliminate the counterexample,
we need to propagate the refinement backwards along the
path and split Q02 and Q03 further. With that, we obtain
an abstraction partition with 10 sets, which is guaranteed
to eliminate this abstract counterexample. In fact, in this
example this abstraction turns out to be sufficiently precise
to obtain a winning strategy for the agent.

C. General surveillance and task specifications
We have described refinement procedures for safety and
liveness surveillance objectives. If we are given a conjunction
of such objectives, we first apply the refinement procedure
for safety, and if no path for which we can refine is found,
we then apply the refinenment procedure for liveness.
In the general case, we check if the counterexample
contains a state for which the concrete belief is a strict
subset of the abstract one. If this is not the case, then
the counterexample is concretizable, otherwise we refine
the abstraction to make this belief precise. In the special
case when we have a conjunction of a surveillance and task
specifications, we first refine with respect to the surveillance
objective as described above, and if this is not possible, with
respect to such a node. Since the set of states in the game
is finite, the iterative refinement will terminate, either with a
concretizable counterexample, or with a surveillance strategy.
VI. EXPERIMENTAL EVALUATION
We report on the application of our method for surveillance synthesis in two case studies. We have implemented the
simulation in Python, using the slugs reactive synthesis
tool [10]. The experiments were performed on an Intel i55300U 2.30 GHz CPU with 8 GB of RAM.
A. Liveness Surveillance Specification + Task Specification
Figure 7a shows a gridworld divided into regions. The
surveillance objective requires the agent to infinitely often
know precisely the location of the target (either see it, or have

(a) Gridworld with a user provided (b) Gridworld showing visibility of the
abstraction partition with 7 sets, agent. All locations shown in black are
marked by black lines..
invisible to the agent.

Fig. 7: 10x15 gridworld with a surveillance liveness specification. The agent is blue, and the target to be surveilled is
orange. Red states are obstacles.

(a) t1

(b) t3

(c) t4

(d) t5

(e) t6

(f) t7

Fig. 8: Evolution of the agent’s belief about the target’s
location as it moves to the goal and loses sight of the target.
Grey cells represent the locations the agent believes the
target could be in. We show the belief at different timesteps
t1 , . . . , t7 (note that t2 is excluded for space concerns)

a belief consisting of one cell). Additionally, it has to perform
the task of patrolling (visiting infinitely often) the green
’goal’ cell. Formally, the specification is
p1 ∧
goal .
The agent can move up to 3 grid cells away at each step.
The sensor mode, that is, the visibility function, used here
is ’line-of-sight’ with a range of 5 cells. The agent cannot
see through obstacles (shown in red) and cannot see farther
than 5 cells away.
Using the abstraction partition of size 7 shown in Figure
7a, the overall number of states in the two-player game is
15×10+27 = 278 states. In contrast, solving the full abstract
game will have in the order of 2150 states, which is a statespace size that state-of-the-art synthesis tools cannot handle.
Figure 8 shows how the belief of the agent (shown in
grey) can grow quickly when it cannot see the target. This
growth occurs due to the coarseness of the abstraction, which
overapproximates the target’s true position. In 7 steps, the
agent believes the target can be anywhere in the grid that
is not in its vision. It has to then find the target in order to
satisfy the surveillance requirement. Figure 9 illustrates the
searching behaviour of the agent when it is trying to lower
the belief below the threshold in order to satisfy the liveness
specification. The behaviour of the agent shown here will
contrast with the behaviour under safety surveillance which
will we look at next.

(a) t5

(b) t7

(c) t9

Fig. 9: The agent has to search for the target in order to
lower its belief below the surveillance liveness specification.

(a) t1

(d) t5

(b) t3

(e) t6

(c) t4

(f) t7

Fig. 10: Evolution of the agent’s belief about the target’s
location in a game with an abstraction partition of size 12.

In this example, an abstraction partition of size 7 was
enough to guarantee the satisfaction surveillance specification. For the purpose of comparison, we also solve the game
with an abstraction partition of size 12 to illustrate the change
in belief growth. Figure 10 shows the belief states growing
much more slowly as the abstract belief states are smaller,
and thus they more closely approximate the true belief of the
agent.
The additional abstraction partitions result in a much larger
game as the state space grows exponentially in the size
of the abstraction partition. Table I compares the sizes of
the corresponding abstract games, and the time it takes to
synthesize a surveillance controller in each case.
Size of abstraction partition
7
12

Size of abstract game
278
4346

Synthesis time
237s
810s

TABLE I: Comparison of synthesis times for the two cases
A video simulation can be found at http://goo.gl/
YkFuxr.
B. Safety surveillance specification + task specification
Figure 11 depicts an environment created in Gazebo where
the red blocks model buildings. The drone is given full line
of sight vision - it can detect the target if there is no obstacle
in the way. In this setting, we enforce the safety surveillance
objective p30 (the belief size should never exceed 30)
in addition to infinitely often reaching the green cell. The
formal specification is
p30 ∧
goal . Additionally, the
target itself is trying to reach the goal cell infinitely often as
well, which is known to the agent.
We used an abstraction generated by a partition of size
6, which was sufficiently precise to compute a surveillance

Fig. 11: A Gazebo environment where the red blocks are
obstacles that the drones cannot see past. The green drone
is the agent and the orange drone is the target.
strategy in 210 s. Again, note that the precise belief-set game
would have in the order of 2200 states.
We simulated the environment and the synthesized surveillance strategy for the agent in Gazebo and ROS. A video of
the simulation can be found at http://goo.gl/LyC1gQ.
This simulation presents a qualitative difference in behaviour
compared to the previous example. There, in the case of liveness surveillance, the agent had more leeway to completely
lose the target in order to reach its goal location, even though
the requirement of reducing the size of the belief to 1 is
quite strict. Here, on the other hand, the safety surveillance
objective, even with a large threshold of 30, forces the agent
to follow the target more closely, in order to prevent its
belief from getting too large. The synthesis algorithm thus
provides the ability to obtain qualitatively different behaviour
as necessary for specific applications by combining different
objectives.
C. Discussion
The difference in the behaviour in the case studies highlights the different use cases of the surveillance objectives.
Depending on the domain, the user can specify a combination
of safety and liveness specification to tune the behaviour
of the agent. In a critical surveillance situation (typical in
defense or security situations), the safety specification will
guarantee to the user that the belief will never grow too large.
However, in less critical situations (such as luggage carrying
robots in airports), the robot has more flexibility in allowing
the belief to grow as long as it can guarantee its reduction
in the future.
VII. CONCLUSIONS
We have presented a novel approach to solving a surveillance problem with information guarantees. We provided a
framework that enables the formalization of the surveillance
synthesis problem as a two-player, partial-information game.
We then presented a method to reason over the belief that
the agent has over the target’s location and specify formal
surveillance requirements. The user can tailor the behaviour
to their specific application by using a combination of safety
and liveness surveillance objectives.
The benefit of the proposed framework is that it allows
it leverages techniques successfully used in verification and

reactive synthesis to develop efficient methods for solving the
surveillance problem. There are several promising avenues
of future work using and extending this framework. Some
of which currently being explored are the following;
• Synthesizing distributed strategies for multi-agent
surveillance in a decentralized manner. These compositional synthesis methods avoid the blow up of the state
space that occurs in centralized synthesis procedures as
the number of surveillance agents grow.
• Incorporating static sensors or alarm triggers for the
mobile agent(s) to coordinate with.
• Allowing for sensor models to include uncertainty and
detection errors while still providing surveillance guarantees.
R EFERENCES
[1] T. Bandyopadhyay, M. H. Ang, and D. Hsu, Motion Planning for 3D Target Tracking among Obstacles. Berlin, Heidelberg: Springer
Berlin Heidelberg, 2011, pp. 267–279.
[2] H. H. Gonzalez-Banos, C.-Y. Lee, and J. C. Latombe, “Real-time combinatorial tracking of a target moving unpredictably among obstacles,”
in Proc. ICRA 2002, vol. 2, May 2002, pp. 1683–1690 vol.2.
[3] T. H. Chung, G. A. Hollinger, and V. Isler, “Search and pursuit-evasion
in mobile robotics,” Autonomous Robots, vol. 31, p. 299, Jul 2011.
[4] N. Basilico, N. Gatti, and F. Amigoni, “Patrolling security games:
Definition and algorithms for solving large instances with single
patroller and single intruder,” Artif. Intell., vol. 184-185, June 2012.
[5] S. Kreutzer, Graph Searching Games. Cambridge University Press,
2011, pp. 213–261.
[6] L. Doyen and J. Raskin, Games with Imperfect Information: Theory
and Algorithms. Cambridge University Press, 2011, pp. 185–212.
[7] K. Chatterjee, L. Doyen, and T. A. Henzinger, “A survey of partialobservation stochastic parity games,” Formal Methods in System
Design, vol. 43, no. 2, pp. 268–284, Oct 2013.
[8] J. H. Reif, “The complexity of two-player games of incomplete
information,” J. Comput. Syst. Sci., vol. 29, no. 2, pp. 274–301, 1984.
[9] D. Berwanger and L. Doyen, “On the power of imperfect information,”
in Proc. FSTTCS 2008, ser. LIPIcs, vol. 2, 2008, pp. 73–82.
[10] R. Ehlers and V. Raman, “Slugs: Extensible GR(1) synthesis,” in Proc.
CAV 2016, ser. LNCS, vol. 9780. Springer, 2016, pp. 333–339.
[11] E. M. Clarke, O. Grumberg, S. Jha, Y. Lu, and H. Veith,
“Counterexample-guided abstraction refinement,” in Proc. CAV 2000,
ser. LNCS, vol. 1855. Springer, 2000, pp. 154–169.
[12] J.-C. Chin, Y. Dong, W.-K. Hon, C. Y.-T. Ma, and D. K. Y. Yau,
“Detection of intelligent mobile target in a mobile sensor network,”
IEEE/ACM Trans. Netw., vol. 18, no. 1, pp. 41–52, Feb. 2010.
[13] A. Antoniades, H. J. Kim, and S. Sastry, “Pursuit-evasion strategies
for teams of multiple agents with incomplete information,” in Proc.
CDC 2003, vol. 1, Dec 2003, pp. 756–761 Vol.1.
[14] R. Vidal, O. Shakernia, H. J. Kim, D. H. Shim, and S. Sastry, “Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation,” IEEE Transactions on Robotics and Automation,
vol. 18, no. 5, pp. 662–669, Oct 2002.
[15] H. J. Kim, R. Vidal, D. H. Shim, O. Shakernia, and S. Sastry,
“A hierarchical approach to probabilistic pursuit-evasion games with
unmanned ground and aerial vehicles,” in Proc. CDC 2001, vol. 1,
2001, pp. 634–639 vol.1.
[16] A. Pnueli and R. Rosner, “On the synthesis of a reactive module,” in
Proc. POPL’89. ACM, 1989, pp. 179–190.
[17] N. Piterman, A. Pnueli, and Y. Sa’ar, Synthesis of Reactive(1) Designs.
Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 364–380.
[18] T. Wongpiromsarn, U. Topcu, and R. M. Murray, “Receding horizon
temporal logic planning,” IEEE Transactions on Automatic Control,
vol. 57, no. 11, pp. 2817–2830, Nov 2012.
[19] H. Kress-Gazit, G. E. Fainekos, and G. J. Pappas, “From structured
english to robot motion,” in Proc. IROS 2007, Oct 2007, pp. 2717–
2722.
[20] R. van der Meyden and M. Y. Vardi, “Synthesis from knowledge-based
specifications (extended abstract),” in Proc. CONCUR’98, ser. LNCS,
vol. 1466. Springer, 1998, pp. 34–49.

[21] T. A. Henzinger, R. Jhala, and R. Majumdar, “Counterexample-guided
control,” in Proc. ICALP 2003, 2003, pp. 886–902.
[22] R. Dimitrova and B. Finkbeiner, “Abstraction refinement for games
with incomplete information,” in Proc. FSTTCS 2008, ser. LIPIcs,
vol. 2, 2008, pp. 175–186.
[23] J. Fu, R. Dimitrova, and U. Topcu, “Abstractions and sensor design in
partial-information, reactive controller synthesis,” in Proc. ACC 2014.
IEEE, 2014, pp. 2297–2304.
[24] C. Baier and J. Katoen, Principles of model checking. MIT Press,
2008.

