Olivier Marceau

Jean-Michel Vanpeperstraete

DCNS Research
5 rue de l’Halbrane
F-44340 Bouguenais

DCNS Research
280 avenue Aristide Briand
F-92220 Bagneux

Abstract—This paper studies an optimal autonomous underwater vehicule (AUV) path planning method for both reducing
average delay before pollutants detection in underwater mining,
oil or gas fields and reducing AUV occupancy time. The proposed technique, based on the bayesian search theory framework
and multi-objective optimization, extracts optimal boustrophedon
paths for leak detection in complex environment. We describe a
multi-objective nonlinear mixed integer optimization model for
both reducing global nondetection probability and path duration. We then propose a hierarchical algorithm combining two
functions. The main function is a multi-objective cross entropy
which places the tracklines. The second function sets the optimal
speeds on each trackline by means of an interior point method.
Numerical simulations show that the proposed framework is a
very promising approach because the optimal paths cross spill
of highly probable leaks before less probable ones. We show that
our optimized paths outperform boustrophedon paths of same
duration with uniform speed and spacing of trackline. Thanks to
Pareto efficiency approach, our tool propose optimal trajectories
for numerous AUV autonomies. Hence it can be used for both
real time path planning and design purpose.

I. I NTRODUCTION
Inspection of underwater mining fields for turbidity, oil
or gas leaks is an expensive task both for manning and
equipment costs. One way to reduce costs is the deployment
of autonomous underwater vehicles (AUVs). However AUVs
have limited power and are often assigned to numerous critical
tasks.
In order to increase AUVs effectiveness, one must take into
account every piece of a priori knowledge on the monitored
field. For our purpose, such an initial knowledge is summarized by three information. First, positions of probable leak
sources are induced by the topology of submarine exploitation:
a leak usually occurs on pipes junction, digging points or
high pressure tank. Second information is the local submarine
conditions like streams, temperatures, pressures or densities
which influence pollutants propagation. The last knowledge is
the history of previous leak events and previous inspections.
All these information can be combined to produce a simulation of pollutant propagation. See [5] and [6] for oil propagation models. Such a simulation permits to define potential
pollutant fill area for each identified leak source. Moreover
expertise, previous events and previous inspections analysis
allow to infer a priori probability occurrence of each leak. Fill
areas and corresponding leak probabilities are designed by a
priori leak map throughout this article.

Bayesian search theory permits to exploit a priori leak map
for building a metric which evaluates quality of a trajectory.
Such a theory aims to improve effectiveness of searching
efforts in a constrained and uncertain environment. This discipline was introduced by the Antisubmarine Warfare Operations
Research Group (ASWORG) during World War II [1]. Since
that time, search theory became a widely used discipline in
operations research; interested readers may consult extensive
surveys [7] and specialized books [8], [9]. More recently,
search theory was apply on the search of flight AF447 Rio Paris [10]. According to [11], a classical search theory problem
is characterized by three data sets:
•

•

•

the probabilities map of the searched object in various
possible location,
the local detection probability that an amount of local
search effort could detect the target,
the total amount of searching effort available.

In case of pollutant leak detection, the first set is the a priori
leak map, and third set is the total amount of time available on
the AUV. Second data set is generally more complex because
it requires a precise sensor measurement characterization. For
our purpose we choose a rather simple sensor model consisting
in a continuous local point measurement of characteristic time
τ such that probability of detection of a pollutant if the
sensor stay a duration ∆t in the leak fill area is given by
1 − exp(− ∆t
τ ).

1
0.9
0.8
0.7

detection probability

arXiv:1801.02377v1 [cs.SY] 8 Jan 2018

AUV Optimal Path for Leak Detection

0.6
0.5
0.4
0.3
0.2
0.1
0

measurement duration

Fig. 1. Pollutant detection probability in function of time spent in the spill
area.

Our aim is also to reduce time spent by the AUV on the
area to let this AUV fulfill other tasks. For example one can
say staying one more hour in the mining field is worthless
if global leak detection probability only increases of 0.1%.
The conventional method of handling multiple objectives is
to construct a combined objective and thus solve a single
objective problem. See [12], [13] for example of such methods.
However, there are several drawbacks to this. First, since
different objectives have different meanings, the combined
objective is difficult to interpret and validate. Second, in
combining several objectives in a single function, one must
know the relative importance of each objective.
In this paper, a multiobjective optimization (MOO) framework exhibits a set of solutions rather than a single solution.
Each solution makes a compromise among multiple and often
conflicting objectives. Such a set of solutions is commonly
known as a Pareto-optimal set in which Pareto-optimality is
defined in terms of a dominance relation between two solutions
as follows: given two solutions u and v, u 6= v, u is said to
dominate v if u is not worse than v in all objectives and u is
strictly better than v for at least one objective. For example,
for a minimization problem
min f (x) = (f1 (x), f2 (x), . . . , fK (x))
x∈X

(1)

solution u is better than v with respect to objective i if fi (u) ≤
fi (v) and u is said to dominate v denoted as u ≺ v. One may
consult [14] for increasing knowledge on MOO. Hence Pareto
set is the set of non dominated solutions.
AUV path planning is a widely studied subject: [15]
describes a method to find minimal path duration to join
an arrival point in presence of obstacles and streams; [16]
proposes a traveling salesman problem (TSP) approach to
minimize flight time path for multiple site surveillance. Multiobjective path planning with exploration of the Pareto frontier
has previously been studied in [17] in a context of target
surveillance by AUVs.
II. P ROBLEM

FORMULATION

Before any mathematical modeling, we make several preliminary assumptions. First, all trajectories are calculated at
a constant depth. One can adapt our method by applying
it to several possible depths and then merging each Pareto
front and pruning dominated trajectories. Thus, without loss
of generality, our path planning problem is reduced to a
planar one. Then we restrict possible patterns to classical
boustrophedon ones (figure 2) and we enforce constant speed
on each trackline so the decision variables are the ”horizontal”
trackline positions and the AUV speed on the corresponding
trackline and we neglect streams.
Let i = 1, . . . , n denote potential leak sources. Each source
i is associated with an a priori probability of leak πi and with
a spill area Ai . In order to maximize leak detection, our AUV
must spend maximal time in each leak spill area. We restrain
possible tracklines to a finite set of m well chosen lines. Hence
boustrophedon pattern consist in a selection of ”horizontal”
tracklines in a set denoted by j = 1, . . . , m and we define

Fig. 2. Boustrophedon pattern in green dashed line among two spill of
pollutant emanating from two sources (red points).

vj the AUV speed on trackline j and δj the integer variables
representing the number of traveling on the trackline j. The δj
take their values between 0 and z, with z the maximal number
of times the AUV can travel a single trackline. With such
notations the classical search theory non detection probability
can be formulated


m
n
X
X
l
1
i,j
(2)
πi · exp −
δj 
PN D =
τ
v
j
j=1
i=1
with li,j the length of the trackline j inside the spill area
Ai and τ the characteristic time of the mobile sensor. Path
duration can be expressed
T =

m
X
lj
δj
vj

(3)

j=1

with lj the length of trackline j. One can notice that (2) and
(3) neglect ”vertical” pieces of the pattern.
AUV physical capacities and sensor requirements impose
vmin ≤ vj ≤ vmax for all j = 1, . . . , m and
m
X
lj
δj ≤ Tmax .
v
j=1 j

Finally our problem can be summarized



Pn
Pm l
minδ,v i=1 πi · exp − τ1 j=1 vi,jj δj

 min Pm lj δ
δ,v

j=1 vj j


∀j
=
1, . . . , m, δj ∈ {0, z}



∀j
=
1,
. . . , m, vmin ≤ vj ≤ vmax
 s.t.
 P m lj
j=1 vj δj ≤ Tmax

(4)






.




(5)

(5) is a Mixed Integer Programming (MIP) nonlinear biobjective problem.
Search theory also gives a mean to update distribution of
leak probability considering no detection occurs: immediately

after the AUV moves, updated leak probabilities πi′ are given
by formula


m
X
li,j 
1
(6)
δj
πi′ = πi exp −
τ j=1 vj
III. A LGORITHM DESCRIPTION
We propose a hierarchical approach to solve problem (5): a
main function select best tracklines and average speed while
a secondary function optimize speed on each trackline.
Trackline
selection
(δ, T )

(δ ∗ , v∗ )

IV. R ESULTS
Our algorithm was implemented in MATLAB and tested
on simulated data on a square area of size 10 km x 10 km
including 50 potential leak sources, 42 with a priori probability
of 0.05, 5 with an a priori of 0.15 and 3 with an a priori
of 0.80 (see figure 4). Each leak area is the convex hull of
an ellipse with random parameters. One potential trackline is
created on each extrema of every leak area, which conducts
to 100 potential tracklines. The AUV has an autonomy of 10
hours and can move between 2 and 5 knots. The sensor has
a characteristic time of 200 seconds. Given that the AUV
can range less than 20 tracklines, the number of possible
boustrophedon paths which must be explicitly enumerated is
approximatively 1040 .

v
12000

Speed
optimization

leak spill area

10000

Fig. 3. Hierarchical architecture for AUV path planning.

8000

This decomposition aims to divide one difficult problem into
several easier problems while producing optimal solutions for
problem (5).

y (m)

6000

A. Speed optimization

4000

2000

Considering only the trackline speeds and assigning a global
path duration T , problem (5) become


P
Pm
1
minµj |δj =1 n
i=1 πi ·exp (− τ
j=1 li,j µj )

1
.
≤µj ≤ v 1
∀j=1,...,m, vmax
PN∗ D (δ, T ) = 
min
s.t. Pm
j=1 lj µj =T

1
vj

(7)
for all j =

with µj the inverse of trackline speeds (µj :=
1, . . . , m).
Thanks to the substitution of vj by µj , (7) is a welldefined convex problem which can be easily solved by mean
of an interior point method. Readers who want to improve
knowledge in convex optimization and interior point method
may consult [4].

0

-2000
-2000

0

2000

4000

6000

8000

10000 12000

x (m)

Fig. 4. Target area with 50 potential leak sources. Yellow leak surfaces are
less probable ones and red are the most probable.

By applying the proposed algorithm on such a test case, we
obtain a pareto set of thirty solutions given on figure 5. Our
20
18

path duration (in hours)

16

B. Trackline selection optimization
(7) and substituting discrete variables
δj by binary variables
Pz
δj,k for k = 1, . . . , z (δj =
δ
k=1 j,k ) permits to rewrite
problem (5):


minδ,T PN∗ D (δ, T )

 minδ,T T




∀j = 1, . . . , m, ∀k = 1, . . . , z, δj,k ∈ {0, 1}  .
s.t. Pm Pm
lj
j=1
j=1 vmax δj,k ≤ T ≤ Tmax
(8)
(8) is a biobjective mixed programing problem with with one
nonlinear objective, z · m binary variables and one continuous
variable T . Thus our problem is well-posed for applying
the multiobjective cross-entropy method (MOCE) introduced
by [3] as an extension of the original cross-entropy method
(CE) [2]. The cross-entropy method is a stochastic learning
algorithm inspired from rare event simulations.

14
12
10
8
6
4
2
0
0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

non detection probability

Fig. 5. Pareto set.

methods takes approximatively fifteen minutes on a standard
desktop computer.
For a given trajectory, one can estimate updated leak probabilities according to (6). Figure 6 shows such a trajectory

with updated leak probabilities. This example shows that our

10000

8000

y (m)

6000

4000

2000

0

-2000

0

2000

4000

6000

8000

10000

12000

x (m)

Fig. 6. Example of a trajectory with updated leak probabilities, non detection
probability of 0.4 and path duration of 7.5 hours. Green tracklines are traveled
at lowest speed while red trakclines are traveled at highest speed. Blue dashed
tracklines are neglected for detection.

algorithm choose trajectories which cross first the fill area of
high leak probability.
On a design point of view, the bicriteria Pareto Front can be
modified in a detection probability curve in function of path
duration. Moreover one can easily compare 1 AUV versus 2
AUVs configuration. We also add to this comparison result
of a non optimized path consisting of boustrophedon with
regularly spaced tracklines at a constant speed on full path.
Figure 7 illustrates this approach and show that optimized 1
0.9
1 AUV - regular path
1 AUV - optimized path
2 AUV - regular path
2 AUV - optimized path

0.8

detection probability

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0

2

4

6

8

10

path duration (in hours)

Fig. 7. Comparison between regularly spaced and optimized path with one
or two AUVs.

AUV trajectories almost reach regular 2 AUVs trajectories.
The noticeable break on each curve matches with transition
between one low speed trackline patterns and two high speed
tracklines patterns. Transitions between higher number of
tracklines are also apparent but less significant. Note that our
approach for n AUVs only consists in increasing path duration
by a factor n. The optimal tracklines - AUVs assignment is a
difficult problem which is beyond this article scope.

V. C ONCLUSION
This article proposes a new method for AUV path planning
for early leak detection in mining or oiling fields. Numerical
experiments show that optimized paths outperform classical
regularly spaced boustrophedon paths. Thanks to a bicriteria
and time effective approach, our algorithm can serve purpose
of both real time decision aid and design of a new system.
Furthermore our optimized path can reduce number of AUVs
required to monitor an area and thus can highly reduce initial
and maintenance costs of a monitoring system.
Future works may develop several aspects. First our algorithm will be evaluated on realistic leak fill areas using
existing propagation models [5] and [6]. Then optimized paths
could take into account submarine streams. Third, each kind
of pollutant has is own significance, thus our approach should
include one objective for each potential pollutant in the area
instead of mixing all pollutants in the same objective . Another
promising field could be the extension of our model to multiple
heterogeneous AUVs.
R EFERENCES
[1] B. O. Koopman, Search and screening. Operations Evaluation Group,
Office of the Chief of Naval Operations, Navy Department, 1946.
[2] R. Y. Rubinstein and D. P. Kroese, The cross-entropy method: a unified
approach to combinatorial optimization, Monte-Carlo simulation and
machine learning. Springer Science & Business Media, 2013.
[3] A. Ünveren and A. Acan, “Multi-objective optimization with cross
entropy method: Stochastic learning with clustered pareto fronts,” in
Evolutionary Computation, 2007. CEC 2007. IEEE Congress on. IEEE,
2007, pp. 3065–3071.
[4] R. H. Byrd, J. C. Gilbert, and J. Nocedal, “A trust region method based
on interior point techniques for nonlinear programming,” Mathematical
Programming, vol. 89, no. 1, pp. 149–185, 2000.
[5] K. H. Hyun and R. He, “Coastal upwelling in the south atlantic bight: A
revisit of the 2003 cold event using long term observations and model
hindcast solutions,” Journal of Marine Systems, vol. 83, no. 1, pp. 1–13,
2010.
[6] E. W. North, E. E. Adams, A. E. Thessen, Z. Schlag, R. He, S. A.
Socolofsky, S. M. Masutani, and S. D. Peckham, “The influence of
droplet size and biodegradation on the transport of subsurface oil
droplets during the deepwater horizon spill: A model sensitivity study,”
Environmental Research Letters, vol. 10, no. 2, p. 024016, 2015.
[7] S. J. Benkoski, M. G. Monticino, and J. R. Weisinger, “A survey of the
search theory literature,” Naval Research Logistics (NRL), vol. 38, no. 4,
pp. 469–494, 1991.
[8] L. D. Stone, Theory of optimal search. Elsevier, 1976, vol. 118.
[9] A. R. Washburn, Search and detection.
Institute for Operations
Research and the Management Sciences, 2002.
[10] L. D. Stone, C. Keller, T. Kratzke, and J. Strumpfer, “Search analysis
for the location of the af447 underwater wreckage,” Report to BEA, pp.
1–8, 2011.
[11] J.-P. Le Cadre and G. Souris, “Searching tracks,” IEEE Transactions on
Aerospace and Electronic systems, vol. 36, no. 4, pp. 1149–1166, 2000.
[12] A. Nègre, H. Zhang, O. Marceau, B. De Saporta, D. Laneuville, and
F. Dufour, “Stochastic control for underwater optimal trajectories,” in
Aerospace Conference, 2012 IEEE. IEEE, 2012, pp. 1–7.
[13] Y. Yang, A. A. Minai, and M. M. Polycarpou, “Decentralized cooperative
search by networked uavs in an uncertain environment,” in American
Control Conference, 2004. Proceedings of the 2004, vol. 6. IEEE,
2004, pp. 5558–5563.
[14] M. Ehrgott, Multicriteria optimization. Springer Science & Business
Media, 2006.
[15] C. Petres, Y. Pailhas, Y. Petillot, and D. Lane, “Underwater path planing
using fast marching algorithms,” in Oceans 2005-Europe, vol. 2. IEEE,
2005, pp. 814–819.

[16] M. Soulignac and P. Taillibert, “Fast trajectory planning for multiple site
surveillance through moving obstacles and wind,” in Proceedings of the
Workshop of the UK Planning and Scheduling Special Interest Group,
2006, pp. 25–33.
[17] X. Tian, Y. Bar-Shalom, and K. R. Pattipati, “Multi-step look-ahead
policy for autonomous cooperative surveillance by uavs in hostile
environments,” in Decision and Control, 2008. CDC 2008. 47th IEEE
Conference on. IEEE, 2008, pp. 2438–2443.

