Aerial Surveillance System with Multiple Agents for Moving Targets
Satoshi HOSHINO1† , Takeshi KATSUMOTO2 , Shigemichi SAITOH1 , Naoaki ITABASHI2 , Tomoki
KABAYAMA2 , and Mitsuru KONO2
1

Department of Mechanical and Intelligent Engineering Graduate School of Engineering Utsunomiya University, Japan(Tel: +81-28-689-6053; E-mail: hosino@cc.utsunomiya-u.ac.jp)
2
SUBARU Inc., Japan

Abstract: In this paper, we focus on an aerial surveillance system composed of multiple agents, such as sentinels andsearchers. In the surveillance system, single sentinel detects a position of an incoming target, and multiple searchers
approach and identify the target. In order for the searchers to identify moving targets as many as possible, it is required
to optimize the approach behavior in consideration of the future positions. For these challenges, we use a directional
statistics and value iteration method. Through simulation experiments, we show that the surveillance system is able toestimate the future positions of a target. We further show that the searchers based on the optimized approach behavior
identify the most moving targets. Finally, we discuss the effectiveness of the surveillance system for the moving targets.
Keywords: Aerial Surveillance, Multi-Agent Systems, Directional Statistics, Bayes’ Theorem, Optimization.

1. INTRODUCTION
In this paper, we focus on an aerial surveillance systemcomposed of multiple agents, such as unmanned aerial
vehicles, UAVs. Compared to ground vehicles, the aerial
agents are capable of monitoring broader area. Basilico
et al. have presented an aerial surveillance system composed of two types of UAVs [1]. Fig. 1 illustrates thesurveillance system.
Sentinel

SearcherSearcherSearcherMonitoring area

Fig. 1 Aerial surveillance system composed of sentineland searchers
As the UAVs, single sentinel and multiple searchers
are used. The sentinel operates at a place higher than the
searchers. A monitoring area of the sentinel is drawn by
a red circle. If an unidentified event occurs in the area,
the sentinel detects the position. However, the sentinel
is not capable of identifying the event precisely. On theother hand, the searcher is able to identify the event in thesensing range drawn by a blue circle. Therefore, theseheterogeneous multi-agents played different roles in thesurveillance system.
Basilico et al. have succeeded in identifying eventsby dispatching the searchers to the events detected by thesentinel. However, fixed events, e.g., wildfires, have been
assumed. On the other hand, we assume moving targets,
such as animals, in this paper.
† Satoshi HOSHINO is the presenter of this paper.

In our surveillance system, one sentinel and multiple
searchers are used as illustrated in Fig. 1. The sentinelhovers in the same place, and the searchers move to approach targets. In order for the searchers to identify moving targets as many as possible, it is required to solve thefollowing challenges:
1. estimate the future positions of a target and2. approach the target efficiently.
For the first challenge, we use a directional statistics.
The target motion monitored by the sentinel is quantified
on the basis of von Mises circular distribution in Section
2. The von Mises distribution expresses the moving direction of a target. In Section 3, we estimate the future
positions of the target with the use of the von Mises distribution. For this purpose, a moving probability of thetarget is calculated on the basis of Bayes’ theorem. For
the second challenge, we optimize the approach behavior of searchers toward the target in Section 4. For thispurpose, we use a value iteration method and present two
reward functions focusing on the moving probability.
Through simulation experiments, we show that thesurveillance system is able to estimate the future positions of a target. We further show that the searchers
based on the optimized approach behavior identify themost moving targets. Finally in Section 6, we discuss theeffectiveness of the surveillance system for the moving
targets.

2. MOVING DIRECTION OF TARGET
For a moving target, Best et al. have proposed a trajectory prediction method in an indoor environment [2].
Since the moving direction of a target is restricted by
the environmental layout, they succeeded in predicting
the future trajectory by assuming destinations. On theother hand, the aerial environment does not have a layout. Hence, the moving direction is not restricted. As aresult, it is impossible to predict the moving direction.
For this problem, we use a directional statistics. The
target motion monitored by the sentinel is quantitatively

expressed on the basis of the von Mises distribution. The
von Mises distribution has a circular shape. Thus theprobability density is defined along the circle of a monitoring area. Fig. 2 shows a top view of the monitoringarea. In the surveillance system, the monitoring area isdivided into cells.

f(¹, µ)xyFig. 4 Example of von Mises distribution (β = 5, μ = 0)

Fig. 2 Top view of circular monitoring area of sentinel
divided into cells
The circle indicates the monitoring area of a sentinel.
The sentinel detects the position of an incoming target.
The target moves toward a destination. The blue cells
corresponding to the edge of the monitoring area are candidates for the destinations. From these candidate cells,
the target selects a destination. The destination cell is unknown to the system, i.e., sentinel and searchers.
The von Mises distribution is based on the target motion. The target motion is monitored by the sentinel.
Hence, the moving direction of the target is expressed by
the probability density function of the von Mises distribution as follows:
exp{β cos(θ − μ)}f (μ, θ) =,2πI0 (β)(1)

where β is a statistical direction. This parameter represents a measure of concentration on the moving direction. I0 represents the modified Bessel function of order
0. μ and θ are angle parameters defined in the 2D space,(x, y), as illustrated in Fig. 3.

y

The target is moving in the direction of μ = 0 indicated by the arrowed line. For each of the candidate cells,
the probability density is drawn by a red bar. The shape ofthe von Mises distribution becomes sharp and the probability densities of the candidate cells in the moving direction are increased as β increases. On the other hand, theshape of the distribution becomes smooth as β decreases.
β in Eq. (1) is derivable from a statistical direction of
the moving target [3]. As well as our previous work, wederive β by using the Newton-Raphson method. For thispurpose, we define the statistical direction as follows:N
I1 (β)1 =cos(μn − μa ),I0 (β)
N n=1

where I1 (·) represents the modified Bessel function oforder 1. μn is a moving direction of the target in n-th
monitoring step as illustrated in Fig. 5. The sentinel continues to monitor the moving direction, μn , of the target
in each time step.

y
Monitoring area

¹n=3
¹n=2
¹n=1
TargetDestination(2)x

Fig. 5 Monitored moving direction of targetµ¹
TargetMonitoring areax
Fig. 3 Angle parameters μ and θ
The circle denotes the monitoring area. The target
moves in the direction parallel to the axis of y. For thismoving direction, μ, the probability density of the vonMises distribution, given a destination to each of the candidate cells depending on θ, is derived as shown in Fig.
4.

From the N directionaldata, μa in Eq. (2) is calcuN−1  n=1 sin(μn ). While μn indicates
lated as μa = tanN
n=1 cos(μn )the moving direction at that position, μa indicates themoving direction based on the entire data N . Therefore,
β is increased as a target moves in a linear manner. In
this case, the target is expected to continue moving in thesame direction. On the other hand, β is decreased as atarget moves in different directions. In this case, since
the probability densities of all the candidate cells become
uniform, the target is expected to move in any direction.

3. FUTURE POSITIONS OF TARGET
Each time a target is monitored, the probability densityof the von Mises distribution, f , is calculated from Eq.

(1). The probability densities in the candidate cells (seeblue ones in Fig. 2) are used for estimating the future
positions of the target. For an unknown destination of thetarget, we assume a destination cell, θη . At time t, thecurrent position of the target is represented by xt . The
moving probability of the target from xt to Xt+1 at timet + 1 is formulated as follows:
P (Xt+1 |xt , θη ) = K −1 exp[−α{δ(xt , Xt+1 , θη )−δ(xt , θη )}] × f (μ, θ),tTarget(a)Next cells Xt+1 in χ+(b)Cells with moving probabilities

(3)

where
the normalizing constant, K, is defined as K =xt+1 ∈χ+ P r(Xt+1 |xt , θη ). δ(·) represents a distancecomposed of the parameters. Thus δ(xt , Xt+1 , θη ) =δ(xt , Xt+1 ) + δ(Xt+1 , θη ), where δ(A, B) represents an
Euclidean distance between A and B. χ+ is a set of xt+1 ,which is a reachable position from the current position,
xt , in one step.
Eq. (3) is based on a probabilistic dynamics model[2]. As can be seen in the last factor, the probability density function is additionally used in this model. As a result, the moving probability of the target is calculated inconsideration of the moving direction even in the aerial
environment. In each cell, the moving probability of thetarget at time t is formulated as follows:
P (Xt+1 |x1:t ) =θη ∈Θ [P (Xt+1 |xt , θη ) × P (θη |x1:t )], (4)where x1 represents a position when the target was firstly
monitored by the sentinel. Θ represents a set of the candidate cells for a destination. P (Xt+1 |xt , θη ) is derived directly from Eq. (3). P (θη |x1:t ) is calculated using Bayes’
theorem given the monitored positions, x1 , x2 , · · · , xt:= x1:t , up to time t as follows:
P (θη |x1:t ) ∝ P (xt |xt−1 , θη ) × P (θη |x1:t−1 ),

xt+1

Â+
x Xt+1(5)where P (xt |xt−1 , θη ) is the likelihood of monitoring andderived directly from Eq. (3). P (θη |x1:t−1 ) is recursively
updated as the previous posterior.
Given a destination cell, θη ∈ Θ, the moving probability of a target from xt to Xt+1 is calculated withinthe χ+ from Eq. (3) and Eq. (4). This calculation process is repeated for all the candidate cells, Θ. In each cellwithin χ+ , the moving probability is calculated depending on the number of candidate cells. After the calculation for all the candidate cells, the moving probability ineach cell is averaged. For the averaged moving probabilities, a cell with the maximum probability is estimated as
the next position of the target, x̂t+1 . Fig. 6 illustrates thecalculation process.
In Fig. 6(a), the target is shown by a black dot. The
current position is xt . The set of cells surrounded by
the thick line is χ+ . Each of the cells, Xt+1 , is reachable from the current position, xt in one step. For thesecells, the moving probabilities are calculated as shown in
Fig. 6(b). Highly colored cells have higher probabilities.
As an example, the cell with a red dot has the maximum
probability. Thus the cell is an estimated next position of
the target, x̂t+1 .

Fig. 6 Calculation of moving probability

On the basis of the estimated position, x̂t+1 , the next
position, x̂t+2 , is further estimated. Hence, by repeating the calculation described above, the future positions,x̂t+1 , x̂t+2 , · · · , of the target are gradually estimated. Finally, the target reaches a candidate cell. Therefore, aseries of the positions, x̂ = {x̂t+1 , x̂t+2 , · · · }, is the estimated future positions of the target at time t. Fig. 7 illustrates the estimated future positions based on the moving
probability.

Target xt

Future positions

x

Estimated destination

Fig. 7 Estimated future positions of target x̂
At time t, the target position is xt . For the current position, the calculation is repeated until the target reaches
a candidate cell. A gray cell has the maximum probability in each calculation. Therefore, the series of the cells
is the estimated future positions, x̂. Moreover, when theestimated future position reaches a candidate cell, the cellis the estimated destination.
The estimation result described above is for the target
in xt . After the target moved to xt+1 in the next time stept + 1, the position is monitored and the probability density function of the von Mises distribution is calculated
as described in Section 2. Based on the moving direction, the estimation process described in this section issequentially executed. This enables the surveillance system to estimate the correct future positions even if thetarget changes the moving direction.

4. APPROACH BEHAVIOR OF
SEARCHERSIn terms of surveillance, searchers are required to take
into account not only a monitoring spot, but also a seriesof actions toward the spot. This is the optimal approach
behavior of searchers. We have proposed an optimal patrolling strategy for mobile robots [4]. This strategy wasbased on a value iteration method [5]. In this paper, therefore, we use the value iteration method for the optimal
approach behavior.
A value iteration method has been used for calculating
an optimal action at every state in a space divided into
finite number of discrete states. The output of this method
was a so-called state-action map that converts each state
to an action [6]. As illustrated in Fig. 2, the space of theenvironment is already divided into the cells. Therefore,
we also focus on this state-action map.
In the value iteration method, the state is defined as acell occupied by a searcher, and the action is defined asa moving direction of the searcher in the cell. The optimal action indicating the moving direction in each cell isgiven to the searchers as the policy. For calculating thepolicy, the following value function is used:V (si ) =P (sj |si , ai,j )sj ∈S

×{R(sj |si , ai,j ) + γV (sj )}, (6)where si and sj represent cells i and j occupied by asearcher. ai,j represents an action to move j from i.
P (sj |si , ai,j ) is a state transition probability, 0 or 1, fromsi to sj given action ai,j . R(sj |si , ai,j ) is a reward function and γ is a discount factor.
By repeating the recursive calculation of the valuefunction, finally, the state value is optimized on the basis
of Bellman update [7]. For the optimal value function,V ∗ = maxai,j ∈Ai V , an optimal action in each state is
obtained with the use of the greedy algorithm. The optimal action in state s is represented by π ∗ (s). This policy
π ∗ is used by the searchers as the state-action map. Consequently, the searchers are enabled to move toward a cellwith the maximum value of V ∗ according to the moving
direction, i.e., π ∗ . A series of the actions is the optimal
approach behavior of searchers toward the target.
In the surveillance system, the searcher in a cell is allowed to move to the adjacent cells. Hence, the finite
action set is defined as A ={front, front right, right, backright, back, back left, left, front left}. Fig. 8 illustrates anexample of V ∗ and π ∗ .
7.0 7.4 7.0 6.7 6.5 6.7 6.5 6.5
7.4 7.4 7.4 7.0 6.7 6.8 6.7 6.7
7.0 7.4 7.0 6.7 6.5 6.7 6.7 7.0
6.8 7.0 7.1 6.6 6.5 6.7 7.0 7.4
6.6 6.8 6.6 6.5 6.7 7.0 7.4 7.4(a)Optimized value function V ∗(b)Optimal policy π ∗left,” and “front,” as depicted by the gray cells. π∗ (s) enables searchers to optimally approach the target not onlyin the black cell, but also in other cells.
As can be seen in Eq. (6), the optimal approach behavior depends on the reward function. In this paper, we
present the following reward function:R(sj |si , ai,j ) = ω1 P (i)
Dpmax (i)Dd (i)+ω2 1 −
+ ω3 1 −,MM. p(i) represents a moving probabilwhere P (i) = pp(i)maxity of cell i, and pmax represents the maximum moving
probability defined as pmax = maxi p(i). Dpmax (i) and
Dd (i) are normalized distances by M . M is a diameter ofthe monitoring area. Dpmax (i) represents a distance between a cell with the maximum moving probability andi, and Dd (i) represents a distance between an estimateddestination cell and i. ω1 , ω2 , and ω3 are weights.
The reward function in Eq. (7) enables the searcher
to proactively approach the target in consideration of themoving probability and destination. In this paper, we
further take into account an encounter area between the
searcher and target. The encounter area is defined by two
circular areas of the searcher and target. A radius of eachcircle is calculated from the velocity and time. Thus theoverlapped area of the two circles is the encounter area.
Fig. 9 illustrates the encounter areas.
SearcherSearcherSearcherTargetFig. 9 Encounter areas between three searchers and target
The black dot indicates the moving target. The otherthree, red, green, and blue dots indicate the searchers.
As an example, it is assumed that the target moves withtwice the velocity of the searchers. Between the target
and each of the three searchers, cells corresponding to
the encounter areas are painted in the same colors. In thispaper, we present the following reward function:R(sj |si , ai,j ) = α(i) ω1 P (i)Fig. 8 Optimal approach behavior
In Fig. 8(a), at the black cell in which V ∗ (s) = 6.6,
the greedy algorithm simply selects a cell with the highest
state value from the eight adjacent gray cells in addition
to the current cell. In Fig. 8(b), π ∗ (s) indicates the moving direction by an arrow. A double circle represents amonitoring spot, which is the end of the approach. Thus
the optimal approach behavior of a searcher at the black
cell is composed of the following actions: “left,” “front

(7)


+ω2

Dpmax (i)
1−
M




+ ω3

Dd (i)
1−
M


, (8)

where α(i) = 1 if cell i is in the encounter area; otherwise, α(i) = 0.
The reward function in Eq. (8) enables the searchers toapproach the target in consideration of the encounter areain addition to the moving probability and destination. In
other words, even if a cell has a higher moving probability

or is estimated as a destination, the cells in another area
are all ignored.

5. SIMULATION EXPERIMENT
5.1. Estimation Accuracy
5.1.1. Simulation Settings
In this experiment, an incoming target moves toward a
destination cell. For this moving target, the future positions are estimated in each simulation step. For the estimation, α used in Eq. (3) is given as α = 0.5. In order
to discuss the estimation accuracy, we focus on a gap between the estimated destination and true destination. Fig.
10 shows two moving paths of the target.
xPath 1x
Path 2

TargetFig. 10 Straight path (Path 1) and curved path (Path 2)

the monitoring area, we can see that the moving direction was predicted successfully. As the estimation result,
Table 1 shows the averaged estimation gap in each step.
Table 1 Estimation gap [m]As for Path 1, the estimation gap was 12.9 [m]. Since
the size of a cell was 20 [m] × 20 [m], both the methods successfully estimated the correct destination. As
for Path 2, the proposed method estimated the destination with the sevenfold greater accuracy than the comparison method. This is because that the target continuously changed the moving direction rightward. For thistarget, since the moving direction was correctly predicted
as shown in Fig. 11(b), the proposed method succeededin estimating the destination.
5.2. Surveillance System
5.2.1. Simulation Settings
Fig. 12 illustrates the surveillance environment. The
pink circle indicates the monitoring area with a radius of
300 [m].
Sensing range

The target depicted by a black dot is coming into themonitoring area. The radius of the monitoring area is 300[m]. The target has two destinations marked by “x” andmoves along the straight and curved paths. For comparison, the destination is estimated from the most resent
monitored positions, xt and xt−1 . A linear path thatpasses through xt and xt−1 is applied, and the point ofintersection between the linear path and the edge of themonitoring area is the estimated destination of the target.
5.1.2. Estimation Results
For the moving target in Fig. 10, two destinations are
estimated with the use of the proposed method and comparison method based on a linear path. Fig. 11 shows themoving probability of the target.

(a)Path 1(b)Path 2

Fig. 11 Moving probability of target at time t
At time t, the future positions of the target were calculated. The brightness of color in each cell indicates themoving probability. In these results, the moving probabilities of the cells along Path 1 and Path 2 were relatively higher. Although right after the target came into

Estimation method
Linear
Proposed
12.9
12.9
235.9
32.6

Path
1
2

Searcher

Waypoint
Path
TargetPath

200 [m]Searcher Searcher

Destination

Fig. 12 Surveillance environment
The red dots denote the initial positions of the three
searchers. The moving velocity of the searchers is 300[m/min]. Each searcher is allowed to identify the target
in the sensing range depicted by a red circle with a radiusof 50 [m]. In total, 1000 trials are conducted. In eachtrial, one target comes into the monitoring area. At thesame time, a waypoint and destination cells are given to
the target in a random manner. The waypoint is given
within a dashed circle. The destination is given from thecandidate cells. The target moves toward the waypointand destination at a velocity of 600 [m/min].
In order for the searchers to approach the target,
three comparison strategies are applied. The first strategy allows the searchers to approach the current position of the target. The second and third strategies are
based on the probabilistic approach. The future positions of the target at time t are already estimated asx̂ = {x̂t+1 , x̂t+2 , · · · , x̂N }, where x̂N corresponds tothe estimated destination. As for the moving probability,
a cell of x̂t+1 has the maximum probability, pmax . Hence,the second strategy allows the searchers to approach theestimated destination, x̂N , and the third strategy allows
the searchers to approach a cell with pmax , x̂t+1 . In order for the searchers to optimally approach the target, twomore strategies are applied. In the fourth and fifth strategies, Eq. (7) and Eq. (8) are used as the reward function. The weights are given as ω1 = 0.5, ω2 = 0.2, andω3 = 0.3.
5.2.2. Surveillance Results
In order to evaluate the probabilistic approach of by
the searchers, the results of the first, second, and third
strategies are compared. Table 2 shows the number ofidentified targets for 1000 targets.
Table 2 Number of identified targets
1st : Current position684

2nd : x̂N
703

3rd : x̂t+1 with pmax
724

Compared to the first strategy, the searchers based on
the second and third strategies identified more targets.
This result indicates the effectiveness of estimating thefuture positions of the target. The third strategy resulted
in the best performance from the three strategies. Thus
the result of this strategy is compared to the fourth andfifth strategies as shown in Table 3.
Table 3 Increased number of identified targets based on
optimal approach behavior
3rd : x̂t+1 with pmax724

4th : Eq. (7)754

5th : Eq. (8)846Compared to the third strategy, the searchers based on
the fourth and fifth strategies identified more targets. This
result indicates the effectiveness of optimizing a seriesof the actions of the searchers. It is noticeable that, although both the fourth and fifth strategies were optimal,
the number of identified targets based on the fifth strategy was increased by approximately 100, compared to
the fourth strategy. This result indicates the effectivenessof taking the encounter area into account. In other words,
the searchers successfully identified the most targets byignoring the cells outside the encounter areas.
In order to observe the optimal approach behavior of
the searchers, their trajectories are compared. Fig. 13
shows a result in a trial. The trajectories of the searchers
are depicted by red, green, and blue lines. The target andthe trajectory are depicted by the arrow and black line.
In Fig. 13(a), the trajectory of the moving target
reached the destination. This result indicates that the
searchers failed to identify the target. In Fig. 13(b), on
the other hand, the target was identified by a searcher.
These results were caused by the different behavior of thesearcher denoted by the red line. The red searcher in Fig.
13(a) first moved in the anterior direction of the target.
After that, the searcher changed the direction dependingon the target. However, since the target moved with twice
the velocity of the searcher, the searcher was left behind

TargetIdentify(a)4th : Eq. (7)(b)5th : Eq. (8)Fig. 13 Comparison of optimal approach behavior

by the target. In contrast, the red searcher in Fig. 13(b)moved almost in the same direction as the target; accordingly, this behavior successfully enabled the searcher toapproach and identify the target.

6. CONCLUSIONSIn this paper, we presented an aerial surveillance system composed of single sentinel and multiple searchers.
In order for the searchers to identify moving targets, thefuture positions were estimated and the approach behavior was optimized. In the simulation experiments, thesystem succeeded in estimating the future positions of atarget regardless of the straight and curved moving paths.
Furthermore, the searchers based on the optimal approach
behavior successfully identified targets as many as possible. Especially, the surveillance performance was increased more than 10 [%] in consideration of the encounter areas between the searchers and target. Fromthese results, finally, the effectiveness of the surveillancesystem for the moving targets was shown.

REFERENCES[1] N. Basilico and S. Carpin, “Deploying Teams of
Heterogeneous UAVs in Cooperative Two-Level
Surveillance Missions,” IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp.610–615, 2015.
[2] G. Best and R. Fitch, “Bayesian Intention Inference
for Trajectory Prediction with an Unknown Destination,” IEEE/RSJ Int. Conf. on Intelligent Robots
and Systems, pp.5817–5823, 2015.
[3] S. Hoshino and K. Maki, “Safe and Efficient Motion Planning of Multiple Mobile Robots based on
Artificial Potential for Human Behavior and Robot
Congestion,” Advanced Robotics, Vol.29, No.17,
pp.1095–1109, 2015.
[4] S. Hoshino et al., “Optimal Patrolling Methodologyof Mobile Robot for Unknown Visitors,” Advanced
Robotics, Vol. 30, Issue 16, pp. 1072–1085, 2016.
[5] A.G. Barto and R.S. Sutton, “Reinforcement Learning: An Introduction,” MIT Press, 1998.
[6] R. Ueda and T. Arai, “Value Iteration under theConstraint of Vector Quantization for Improving
Compressed State-Action Maps,” IEEE Int. Conf.
on Robotics and Automation, pp. 4771–4776, 2004.
[7] R. Bellman, “The Theory of Dynamic Programming,” Bulletin of the American Mathematical Society, Vol. 60, No. 6, pp. 503–515, 1954.