Decision-Theoretic Planning for Autonomous Robotic Surveillance.
In this paper, we introduce a decision-theoretic strategy for surveillance as a first step towards automating the planning of the movement of an autonomous surveillance robot. In our opinion, this particular application is interesting in its own right, but it also provides a test-case for formalisms aimed at dealing both with (low-level) sensor, localisation, and navigation uncertainty and with uncertainty at a more abstract planning level. After a brief discussion of our view on surveillance, we describe a very simple formal model of an environment in which the surveillance task has to be performed. We use this model to illustrate our decision-theoretic strategy and to compare this strategy with other proposed strategies. We treat several simple examples and obtain some general results.
Introduction
In several projects, robots are employed to perform surveillance tasks. See, for example,
[5, 6, 7]. However, in most of these projects, the robots are typically used as a kind
of flexible sensor platform controlled by some external human operator who makes the
high-level decisions on where to go, and how to use the on-board sensors.
We are interested in automating this high-level decision making process to allow an
autonomous mobile robot plan itself how to perform the surveillance task. Little work
has been done in this area, with the the notable exception of [2, 3]. We believe this
autonomous robotic surveillance application is interesting in its own right, but it also
provides a test-case for formalisms aimed at dealing both with (low-level) sensor, local-
isation, and navigation uncertainty and with uncertainty at a more abstract planning
level.
In section 2, we give our view on what surveillance is. We then give in section
3 a simple formal model of an environment in which the surveillance task has to be
performed. In section 4 we describe several surveillance strategies that have been studied
in [3], and introduce our proposed decision-theoretic strategy. Finally, section 5 contains
some examples illustrating the various strategies and some preliminary results.
Surveillance
In dictionaries, surveillance is defined as a close watch kept over something or someone.
We feel one should add that the purpose of this close watch is to detect the occurrence
of some relevant events. Which events are considered relevant depends on the overall
reason for the surveillance.
Of course, this close watch is not limited to visual means. In principle, any kind of
sensor can be used. Also, the person or thing to be closely watched should be understood
to include areas, places, (parts of) aerospace, et cetera. Familiar examples of surveillance
tasks include the observation of suspected members of a criminal organization by the
police, the detection of airplanes in a no-fly zone by the military, and the look-out for
suspicious behaviour of people in a shop by a security-guard.
There are at least two disctinct difficulties involved in detecting relevant events.
1. The relevant events have to be in sensor range.
2. Once detected, the events have to be recognised as relevant.
For some applications, such as the observation of a place which is in plain view of a
(static) camera (see e.g. [1]), the first difficulty does not arise. The difficulty that
remains here is to recognise or classify particular events as belonging to the class of relevant
events. Such a classification may vary from rather straightforward (e.g. speeding
cars) to quite complex (e.g. suspect behaviour of people in a shop). Although the issue
of automatic classification of events is extremely important, and essential for artificial
intelligence, we concentrate our research on the first difficulty.
As soon as the relevant events are not guaranteed to occur within sensor range, it
becomes essential to get the available sensors in such a position that the relevant events
are (most likely) detected. Mobile robots seem to be excellently suited for automating
the process of moving sensors, since robot navigation and self-localization, although still
not trivial, are nowadays considered fairly standard tasks. Of course, the difficulty of
navigation and self-localization, and therefore of surveillance, depends on the type of
environment in which the tasks have to be performed. But some successes have been
obtained in a variety of environments, ranging from structured in-door environments,
like office buildings, to out-door environments, like aerospace.
The use of robots in surveillance tasks is not new, but in most of the existing projects
in this area, the robots are typically used as a kind of flexible sensor platform controlled
by some external human operator who makes the high-level decisions on where to go,
and how to use the on-board sensors. We are interested in automating this planning
task to make the surveillance robots more autonomous and less dependent on human
control.
Our main concern is to develop strategies or algorithms that make use of the available
recources (sensors, manoeuvring capabilities, et cetera) such that the probability
of relevant events remaining undetected is minimised. (This is only a preliminary description
of the goal of surveillance. See below.) The fact that detecting relevant events
does not guarantee them to be recognised as relevant, can (and should) be modelled by
introducing some uncertainty in the classification of events.
When evaluating surveillance strategies one should compare them with alternative
strategies, but also with alternatives to robotic surveillance, such as the use of security
cameras, smoke detectors, et cetera. Of course, one can also consider combining robotic
surveillance with simple static sensors and, for example, use a surveillance robot to check
out alarms raised by smoke detectors to decrease the amount of false alarms reported
to police and fire departments.
An important issue when evaluating surveillance strategies is to clarify the goal of
surveillance. We cannot simply say that the goal is to detect all relevant events, since
it is not possible to develop strategies that guarantee to achieve this goal in case the
relevant events are not necessarily in sensor range. We used as a preliminary description
that the probability of relevant events remaining undetected should be minimised. This
is similar to the description used in [6].
This description should at least be refined to take into account the fact that some
relevant events can have more serious consequences than others. near a storage
room of highly inflammable toxic material is more serious than a flooding of a rarely
used basement with no electric outlets.) This can be done by saying that not detecting
a relevant event involves some cost, which may vary depending on the event, and that
one should minimise the expected cost of not detecting relevant events.
Using such a decision-theoretic criterion has a number of advantages. For example,
at least from a theoretical point of view, it seems obvious how to further refine this
criterion to incorporate other types of cost, such as the danger of damage to the robot,
or the cost of false alarms (in case the recognition of relevant events is not completely
reliable). However, several serious problems remain.
The first problem is that the expected cost of the whole surveillance plan or decision
policy should be minimised. In general, such a policy cannot be reduced to a sequence of
simple decision problems, but involves looking (far) ahead at (many) possible outcomes
of (many) future actions. Therefore, in realistic applications one will probably need
heuristics and approximate methods to arrive at feasible solutions.
Another problem is that the application of decision theory requires a great amount
of data. The necessary probabilities of events and costs of possible outcomes of actions
are not always readily available. This is a good reason for preferring policies which are
robust, in the sense that they are not influenced much by small changes in the data.
Also, it can be argued that in realistic applications one should settle for satisfactory
policies rather than insist on optimal policies.
It should be mentioned that we explicitly adopt an asymmetrical view on surveillance,
in the sense that the goal can be described as detecting (or minimising the cost of not
detecting) relevant events. In [3], the goal of surveillance seems (at least sometimes) to
be understood as maintaining a maximally correct model of the state of the environment
with respect to both the presence and the absence of relevant events. We call this the
symmetrical view on surveillance.
We believe that for a surveillance robot with, for example, detecting fires or intruders
as primary goal, the asymmetrical view on surveillance is the most appropriate, and
the decision-theoretic formalisation of the goal is the most natural. In [4], the issues
mentioned in this section are discussed in more detail.
3 A Simple Environment Model
In this section we introduce a very simple, formal model of the environment for the
surveillance task.
Definition 3.1 An environment E is a tuple hX; A is a set
ng of mutually disjoint spatial areas, or locations, A 0 2 X is the start
location of the robot, A ' X \Theta X represents the relation of immediate accessibility (for
the robot) between locations, C is a function assigning to each location X i 2 X the cost c i
associated with not detecting a relevant event occurring at X i , P 0 is a function assigning
to each location X that at time 0 an event occurs at
is a set of transition probabilities. That is, for every
contains denoting the (prior) probability that at time t a relevant event
starts at denoting the (prior) probability that the relevant event at
stops at time t.
For the rest of this paper, we assume that for every
A. As a consequence, we can simplify the description of an environment
Further, we assume that P t (X
do not depend on the time t, and we drop the subscript t. We also assume that
the environment is connected, in the sense that for every there is a path
We write r t to denote the sensor range of the robot at time t, and we assume that
then we say that
is visited at time t. The decision strategies should decide which immediately accessible
location to visit next. For the moment, we do not take recognition uncertainty into
account and assume a relevant event to be detected whenever it is in the sensor range
of the robot.
The above definition provides a very abstract model of the decision problem. For
realistic applications, we have to take into account that a robot can have several sensors,
each with its own sensor range, that the sensor range is not necessarily an element of
X , that the actions of the robot may include changing its location, its orientation, and
possibly manipulating aspects of the environment, such as opening a door, and that the
exact state and dynamics of the environment, the exact position of the robot in the
environment, and the recognition of relevant events are uncertain, et cetera. See [4] for
a more detailed discussion of the simplifying assumptions of the given model.
In spite of the many simplifying assumptions, the model is sufficiently general to
capture the abstract environment used in [3] to experimentally compare different surveillance
strategies. In that experimental set-up, all locations are assumed to be immediately
accessible from each other, i.e., . The dynamics at each location is
modelled by a Markov process, and P (X are viewed as transition
probabilities between possible states of a location.
In our opinion, for many typical surveillance applications it is not appropriate to
model the dynamic behaviour of a location X i as a Markov process. For example,
although the start of a fire can be assumed to have an extraneous cause (nature or some
agent other than the surveillance agent), it is typically the case that the detection of a
fire influences the probability of the fire being extinguished. The detection of a relevant
event should trigger some appropriate response of the surveillance agent, such as raising
an alarm, or taking more direct countermeasures against the event.
Not all applications of surveillance are meant to trigger intervening responses to the
observed relevant event. For example, observations made in the context of a scientific
study are primary aimed at information gathering, not at intervening. However, when
interventions do play a role their effects should be incorporated in the model of the
surveillance problem. Since the particular actions triggered by a detection are them-
selves, strictly speaking, not part of the surveillance behaviour of the agent, we will
leave them out of our considerations.
In our examples, we assume that relevant events do not stop spontaneously, but that
they stop immediately when detected by the surveillance agent. Formally, P (X
0, and P t+1 (X It is possible to introduce some time
delay for the countermeasures to take effect, but this raises the problem of deciding how
important it is to monitor areas where relevant events are known or have been observed
to occur. It is also possible to allow P (X and to model the effect of the actions
triggered by observing a relevant event as an increase in P (X Our assumption
can be viewed as an extreme instance of this possibility.
Given our assuptions, it is possible to express P t (X in terms of P (X
and the amount of time that has passed since the last visit to X i .
Proposition 3.1 be an environment where P
implies that P t+1 (X
, where t 0 is the largest time point - t such that r t
4 Surveillance Strategies
In [3] a surveillance strategy is proposed based on the newly introduced notion of confi-
dence, which can be viewed as a second-order uncertainty measure. Whenever sensory
information about the state of a location becomes available, the probability of an event
occurring at that location at that time is updated, and one is assumed to be very confident
about this assessment of the state of the location. This confidence then drops
gradually over time during a period in which no fresh sensory information concerning
this particular location is obtained. The rate by which the confidence decreases depends
on the transition probabilities: the more likely the changes, the higher the decrease rate.
Specifically, the factor - p is used as confidence decrease rate, where p is the transition
probability leaving from the observed state and - is some unspecified parameter. The
actually used computation of confidence is slightly more complicated, due to the fact
that some time after the observation it is no longer clear which transition probability
should be used in the computation of the decrease rate.
In our model, the situation is simpler, since we assumed that when visiting a location
X i at time t, the robot either observes that no relevant event occurs at X i or the robot
immediately stops the relevant event. In both cases, the robot can be confident that no
relevant event is going on at X i after t. This confidence can decrease over time due to
the possibility that a relevant event starts after t. This rate of this decrease of course
depends on P (X 1). The transition probability P does not play a role.
Since the factor - P (X i !1) is meant to be a decrease rate, one can infer that
Lemma 4.1 Let my.
It follows that if one assumes that by visiting X i the confidence that no relevant
event is going on at X i becomes 1, then the location with the lowest confidence at time
t is the location X i such that P (X is the time of the
last visit to X i .
The policy proposed in [3] can be described as follows.
maximum confidence Choose the action that changes the sensor range to the neighbouring
location which has the lowest degree of confidence attached to it.
This policy is experimentally compared to the following policies.
random exploration Randomly choose a location as the next sensor range.
methodical exploration Choose all the locations, one after the other, and always in
the same order, as the sensor range at the next moment.
maximum likelihood Choose the action that changes the sensor range to the neighbouring
location with maximal uncertainty, where the uncertainty at location X i
is measured by min(P (X
Notice that both random and methodical exploration, as described above, allow
choosing non-neighbouring locations. Actually, in the experiments of [3] it is assumed
that all locations are directly accessible from each other X). This is only
realistic in case changing attention to a far removed location involves no or only a negligible
amount of cost or time. It is of course not difficult to restrict random exploration
to choosing randomly between neigbouring locations only, but it is not clear how to put
a similar restriction on methodical exploration.
One possible policy that can be considerd to be a local variant of methodical exploration
is the following.
interval Minimise the maximum time interval between visits of locations by
choosing the action that changes the sensor range to the neighbouring location
which has not been visited for the longest time.
We propose to use this minimax interval policy as a kind of reference strategy. Since
this strategy does not use information about the uncertainties, it can be used to clarify
how much other strategies which do use uncertainty information gain in efficiency.
It should be mentioned that in the case of the maximum likelihood policy many
uncertainty measures, including, for example, entropy, give rise to the same preferences
as min(P (X As we will see in section 5, the maximum likelihood
policy seems more appropriate for (symmetrical) surveillance understood as maintaining
a maximally correct model of the state of the environment with respect to both the
presence and the absence of relevant events, than for (asymmetrical) surveillance aimed
at detecting relevant events.
In [3], no explicit choice is made between such a symmetrical view on surveillance and
the asymmerical view we take. Several criteria are used to evaluate the performance of
the strategies in the experiments, including the (symmetrical) criterion of the percentage
of erroneous estimations of the state of each location and the (asymmetrical) criterion
of the percentage of non detected relevant events.
We propose a surveillance strategy based on decision-theoretic considerations. By
decision-theoretic surveillance we understand the kind of behaviour guided by the following
decision policy.
minimum expected cost Choose the action that minimises the expected cost.
This decision policy can be interpreted both globally and locally. Under the global
interpretation, the action that has to be chosen corresponds to the behaviour of the
surveillance agent from the start to the end of the surveillance task. There is not an
inherent end to a surveillance task, but in practice each particular task has a limited
duration (say, until the next morning when the employees return to the office building,
or until the batteries of the robot have to be recharged).
The (global) expected cost EC T until time T can be computed by the following
formula.
Notice that a choice to visit X i at t not only removes the term P t (X
the above sum, but it also has some indirect benefits, due to the fact that it reduces
t.
The behaviour of the surveillance agent from the start to the end of the surveillance
task can also be viewed as consisting of a sequence of simpler actions. One can apply the
above decision policy locally to choose at each time between the possible simple actions
by comparing the consequences of these simple actions, or perhaps by comparing the
(expected) consequences of small sequences of simple actions.
Let us say that an n-step policy compares the (expected) consequences of sequences
of n (simple) actions. Of course, the policy is more easily implemented for small n,
whereas, in general, it better approximates the global policy for large n. Since the goal
of surveillance should be interpreted as global minimisation of expected cost, it will
be interesting to study under what conditions the local policy is already (sufficiently)
equivalent to the global policy for small n.
None of the policies considered in [3] takes into account a notion of cost. If the
cost C(X i ) of not detecting a relevant event is the same for all X i , then minimising
the expected cost reduces to maximising the probability of detecting a relevant event.
Notice that this is still different from the maximum likelihood policy.
5 Examples and First Results
We have defined three decision policies for surveillance which make use of some kind of
uncertainty information, namely maximum confidence, maximum likelihood, and minimum
expected cost. The following proposition shows that these policies essentially agree
if there is no (relevant) uncertainty information to be used.
Proposition 5.1 Let Assume that for all
Then the maximum confidence policy
and the one step minimum expected cost policy both reduce to the minimax interval
policy. Also, for sufficiently small transition probabilities P 1), the maximum
likelihood policy will agree with the minimax interval policy.
It follows that we can expect a difference between the mentioned policies only in
the case of varying probabilities (or costs). Our first example illustrates the difference
between the various surveillance strategies introduced so far.
Example 5.1 Consider an environment is a set
consisting of two rooms,
0.8. The strategy based on maximum likelihood will always look
at room X 1 (where the uncertainty is maximal), and will never take a look at room X 2 .
The strategy based on methodical exploration goes back and forth between both rooms,
just as the maximum confidence policy does.
The strategy based on one step minimising expected cost is slightly more complicated.
again 0.8, since room X 2 was
visited at the immediately preceding time step. However, P only increased
to 0.75, which is not enough to get chosen. Only at time 3, P
increased above the 0.8 probability that a relevant event occurs in room 2. We thus obtain
a sequence where room X 1 is only chosen every third time step. See table 1, where for
the first six time steps the expected costs (of not visiting a room) are displayed. The one
step minimum expected cost policy chooses the room with the (maximal) expected cost
printed in boldface.

Table

1: The expected costs of example 5.1.
In this example, the maximum likelihood policy does not result in an exhaustive
exploration of the environment. Both maximum confidence and minimum expected cost
behave better in this respect. The problem with the maximum likelihood criterion is
that P (X not guaranteed to result in a preference to visit X i
rather than X In fact, if P (X
then the criterion prefers X j . Notice that not only in the artificial example above,
but also in practical applications, with sufficiently many locations and sufficiently high
transition probabilities, it can happen that P (X
Since the maximum likelihood criterion does not prefer locations where the chance
of detecting a relevant event is high, but is more interested in locations where the
occurrence of a relevant event is highly unknown, we conclude that the criterion is more
appropriate for symmetrical surveillance than for asymmetrical surveillance.
In example 5.1, the one step minimum expected cost policy results in a behaviour
which seems intuitively appealing, since it clearly reflects the fact that P (X
substantially lower than P confidence, just as methodical
exploration, treats both rooms the same. However, we will see below that this intuitive
appeal may be somewhat misleading.
The maximum confidence policy does also take the probabilities P
account, since the rate of confidence decrease is a function of these
probabilities. However, the decrease rate proposed in [3] does not result in a different
treatment of both rooms in the example. Thus one can view the example as an indication
that in the minimum expected cost policy the probabilistic information is used more
directly and taken more seriously than in the maximum confidence policy.
The maximum confidence policy does not consider at all the possibility that for some
areas it may be relatively more important to detect events. This is easily implemented in
the minimum expected cost policy by letting the cost C(X i ) of not detecting a relevant
event depend on the area X i . Such varying costs may cause a problem, since they may
prevent the one step mimimum expected cost policy to obtain an exhaustive exploration
of the environment.
It can be shown that if the cost of not detecting a relevant event is constant over the
different areas X i , then, in the long run, the one step mimimum expected cost policy
will result in an exhaustive exploration of the environment. More precisely, one can
show the following.
Proposition 5.2 Let Assume that for all
in the long run, every X i 2 X is visited when applying the
one step mimimum expected cost policy, and there is a finite upper bound N i on the
length of the time interval between visits of X i .
If relevant events will not stop spontaneously before they are detected, exhaustive
exploration implies that all relevant events will eventually be detected. But even among
policies that are 100% successful with respect to (eventually) detecting relevant events
there may be a difference in performance if, for example, early detection is considered
to be important.
Table

2: The expected costs of example 5.2.
The following simple modification of example 5.1 shows that, in general, proposition
5.2 is no longer valid (and the one step minimum expected cost policy is no longer
guaranteed to result in an exhausite exploration of the environment) if the costs are
allowed to vary.
Example 5.2 Consider the situation of example 5.1, but now assume C(X 1
3. Then the expected cost of not visiting room 1 has an upper bound of 1,
whereas the expected of not visiting room 2 is 2.4 even when it has been visited the
previous moment. Therefore, by the one step minimum expected cost policy, room 2 will
always be chosen. See table 2, where for the first four time steps the expected costs (of
not visiting a room) are displayed. The one step minimum expected cost policy chooses
the room with the (maximal) expected cost printed in boldface.
This effect of ignoring room 1 can be avoided by allowing the cost of not detecting
an event to grow as a function of the time passed since the event has started. However,
if the mentioned (expected) costs are correct, then this ignoring of room 1 may be
defensible. Intuitively, one should not require a surveillance agent to explore irrelevant
or unimportant areas of the environment. This is substantiated by the following.
Proposition 5.3 In the environment of example 5.2 the one step minimum expected
cost policy minimises the global expected cost.
Perhaps a more important problem than possibly preventing an exhaustive exploration
of the environment is that the varying cost can form an obstacle to obtaining
optimal behaviour using the local (one step) mimimum expected cost policy.
Example 5.3 Consider an environment is a set
consisting of three rooms,
As in example 5.2, the one step minimum expected cost policy will always choose
room 2. But now the (possibly justifiable) ignoring of room 1 will make it impossible to
visit room 0, and in the long run the expected cost of not visiting room 0 will be very
high.
Obviously, such problems can be solved theoretically by looking more than one step
ahead. Since looking ahead many steps is computationally expensive, it would be useful
to develop some methods for assessing the number of steps required to obtain satisfactory
behaviour.
Even for constant costs, the one step minimum expected cost policy is not guaranteed
to globally minimise the expected cost.
Proposition 5.4 In the environment of example 5.1 the one step minimum expected
cost policy does not minimise the global expected cost.
Actually, in example 5.1, the global expected cost of the one step minimum expected
cost policy is higher than that of the back and forth behaviour resulting from
the methodical exploration and the maximum likelihood policy. The two step minimum
expected cost policy already results in the same back and forth behaviour.
The cause of the problem with the one step minimum expected cost policy in our
model is that visiting a location at time t decreases the probability of a relevant event
occurring at that location after t. It is worth investigating whether one can take into
account such indirect benefits of visiting a location by adjusting the costs.
Proposition 5.5 Let t 0 be the time of the last visit to X i before t, and T be the time
of the next visit after t. Then the indirect benefits of a visit to X i at t are equal to the
following.
then the above expression provides a lower bound of the indirect benefits
of a visit to X i at t instead of later. Incorporating this amount of the indirect benefit into
the one step minimum expected cost policy is similar to employing a two step minimum
expected cost policy, and it result in the back and forth behaviour in the environment
of example 5.1.
Proposition 5.6 Let t 0 be the time of the last visit to X i before t. Then the indirect
benefits of a visit to X i at t have the following upper bound.
lim
This upper bound can be used to argue that it is not optimal to visit room 1 in the
environment of example 5.2.
6 Conclusions and Further Work
We do not claim that our discussion of decision-theoretic surveillance establishes the
minimum expected cost policy as the best policy for surveillance. To substantiate such
a claim, one needs to evaluate the performance of different possible strategies when
applied to much more realistic surveillance problems than those discussed thus far.
However, as we mentioned before, we believe that the decision-theoretic view on surveillance
is sufficiently general to, at least theoretically, incorporate many of the necessary
refinements to the model presented in this paper.
To properly evaluate surveillance strategies, one should clarify which kind of surveillance
task one is considering, since the term 'surveillance' is used to refer to quite
different problems. Actually, it may be impossible to find an unqualified best policy
for all surveillance problems. For example, the maximum likelihood policy seems to be
intimately connected with a symmetrical view on surveillance, whereas the minimum
expected cost policy is devised with the asymmetrical interpretation in mind. In gen-
eral, we expect the minimum expected cost policy to behave well in situations where
the probabilities and costs matter and where early detection is important.
We introduced a simple, formal model of an environment in which surveillance tasks
can be performed. The main purpose of this environment model is to clarify the distinctions
between different surveillance strategies. In the future, we plan to refine the
environment model presented in this paper to incorporate the uncertainties a real surveillance
robot has to face: sensor uncertainty, navigation uncertainty, et cetera. A simulation
program is being developed to experimentally evaluate different surveillance
strategies in varying environments. Also, some further theoretical work is needed to
clarify the situations under which local strategies can be used to obtain globally optimal
(or satisfactory) performance.

Acknowledgments

The investigations were carried out as part of the PIONIER-project Reasoning with
Uncertainty, subsidized by the Netherlands Organization of Scientific Research (NWO),
under grant pgs-22-262.



--R

Visual surveillance in a dynamic and uncertain world.
A new approach in temporal representation of belief for autonomous observation and surveillance systems.
Repr'esentation Dynamique de l'Incertain et Strat'egie de Perception pour un Syst'eme Autonome en Environnement ' Evolutif. Dissertation, L' ' Ecole Nationale Sup'erieure de l'A'eronautique et de l'Espace
Issues in surveillance.
On the lookout: The air mobile ground security and surveillance system (AMGSSS) has arrived.
SPAWAR Mobile Detection Assessment and Response System.
AUV survey design qpplied to oceanic deep convection.
--TR
autonomous robots;surveillance;decision-theoretic planning