Science of Autonomy for Swarms of Ocean Vehicles 21.1 Time-Optimal Path Planning for Swarms of Ocean Vehicles 483
Part B | 21.1
Jacobi equation governing the minimum-time navigation problem in dynamic flows. The reachability fronts
are evolved from the vehicle start points y s until they
reach the desired end points y f , combining nominal
vehicle motions due to steering and advection by the
dynamic flow environment, as shown by (21.1). An optimal trajectory X
P (y s ; t) and the corresponding vehicle
heading directions are then extracted from the evolution of the reachability fronts. This is done by solving
the backtracking (21.2) where the solution
o is differentiable, starting from an end point y f and integrating
backward in time to the start point y s
@@
o
@t
C Fjr
o
j C v r
o
D 0 ;
(21.1)
d X
P .y s ; t/
dt
D Dv .X
P ; t/ F
r
o
.X
P ; t/
jr o .X
P ; t/j
with X
P .y s ; T
.y f // D y f :
(21.2)
We also extended the methodology to the case of
coordinated motions of swarms of vehicles and to the
case of uncertain stochastic flows. Coordinated motion
in this context refers to maintaining swarm formations
of specific geometrical shapes by the vehicles, regardless of the ocean currents. Accounting for uncertainties
in the predicted ocean fields allows us to yield the
paths that best compromise between least uncertainty
and least total travel time.
Our approach is interdisciplinary: It is inspired
by ideas in fluid and ocean sciences, computational
sciences, numerical methods, and uncertainty quantification, and applies them to path planning, which has
roots in robotics and optimal control. The methodology
is based on solving (stochastic) partial differential equations. In this sense, it is rigorous and obviates the need
for heuristics. To compute the level set evolution, i. e.,
the viscosity solution to the Hamilton–Jacobi equation,
we either use our finite-volume code for partial differential equations (PDE) (with varied orders, limiters,
etc.) or narrow-band level set and fast marching methods for efficient computations. For the uncertain flow
case, we employ our stochastic PDEs solvers [21.15].
In all cases, the computational cost increases only geometrically with the number of grid points (and not with
the path length). We refer to the above-mentioned references for descriptions of numerical algorithms. Next,
we illustrate results under diverse fluid and ocean conditions, as well as diverse vehicle behaviors.
21.1.1 Canonical Steady Flows
We first evaluated our level-set-based methodology
by computing time-optimal paths in canonical steady
ocean flow features. Such problems include, for example, determining how to time-optimally enter or leave
an ocean eddy, cross an ocean jet, or maneuver in a meander/wave field [21.13]. The results can be very useful
as rules-of-thumb for time-optimal operations.
To exemplify such canonical steady flow problems, we consider idealized 2-D-in-space .x; y/ non-dimensional highway scenarios (2-D: two-dimensional),
as illustrated in Fig. 21.1 [21.13]. In the first case
(Fig. 21.1a), the vehicle is deployed from .0; 0:4/,
with the goal of reaching the point at .0; 0:8/. The speed
of vehicle is 1. The flow consists of two different jets,
both flowing in the positive y direction. The first jet
(narrow band with black arrows on the left) has a higher
speed, v 1 D 2, than the vehicle. The second jet (narrow
band with red arrows on the right) has a constant speed
equal to that of the vehicle, v 2 D 1. From (Fig. 21.1a),
the optimal path takes advantage of the higher jet flow
on the left to reach the goal point. In the second case
(Fig. 21.1b), the vehicle is deployed from .0:6; 0:6/
and the goal point is at .0:6; 0:6/. The speed of the vehicle is 1. In this case, we have two different jets flowing
in opposite directions, both with a speed of 1:5 (faster
than the vehicle). The first jet (upper narrow band with
black arrows) flows in the negative x direction. The second jet (lower narrow band with red arrows) flows in the
positive x direction. As can be seen from (Fig. 21.1b),
the vehicle rides the first jet to an upstream position of
the second jet in order to compensate for the unfavorable flow of the lower jet. Then, the vehicle crosses the
second jet as quickly as possible to reach its goal. In another highway test (Fig. 21.1c), the vehicle is deployed
from .0:6; 0:6/ and the goal point is at .0:6; 0:6/.
The speed of the vehicle is 1. In this case, we have two
different jets flowing with a speed of 1:5 (faster than
the vehicle). The first jet (upper narrow band with red
arrows) flows in the positive y direction. Therefore, it
is infeasible to use any trajectory crossing this jet flow.
The second jet (lower narrow band with black arrows)
flows in the positive x direction. As can be seen from
(Fig. 21.1c), the vehicle first skirts the upper flow on the
right-hand side. Then it moves to an upstream position
of the second jet and crosses it as quickly as possible to
reach the goal.
21.1.2 Time-Dependent 2-D Flows
Time-dependent flows are now considered. To evaluate
robustness, a large number of 2-D flows were utilized,
including flows at the exit of a strait, flows behind islands, and wind-driven flows. Such flows have also been
utilized to evaluate our approach for the path planning
of swarms of vehicles [21.3, 10–12, 14].
Next, we present three examples of time-optimal
path planning for swarms of vehicles in the context of
Part B | 21.1
Jacobi equation governing the minimum-time navigation problem in dynamic flows. The reachability fronts
are evolved from the vehicle start points y s until they
reach the desired end points y f , combining nominal
vehicle motions due to steering and advection by the
dynamic flow environment, as shown by (21.1). An optimal trajectory X
P (y s ; t) and the corresponding vehicle
heading directions are then extracted from the evolution of the reachability fronts. This is done by solving
the backtracking (21.2) where the solution
o is differentiable, starting from an end point y f and integrating
backward in time to the start point y s
@@
o
@t
C Fjr
o
j C v r
o
D 0 ;
(21.1)
d X
P .y s ; t/
dt
D Dv .X
P ; t/ F
r
o
.X
P ; t/
jr o .X
P ; t/j
with X
P .y s ; T
.y f // D y f :
(21.2)
We also extended the methodology to the case of
coordinated motions of swarms of vehicles and to the
case of uncertain stochastic flows. Coordinated motion
in this context refers to maintaining swarm formations
of specific geometrical shapes by the vehicles, regardless of the ocean currents. Accounting for uncertainties
in the predicted ocean fields allows us to yield the
paths that best compromise between least uncertainty
and least total travel time.
Our approach is interdisciplinary: It is inspired
by ideas in fluid and ocean sciences, computational
sciences, numerical methods, and uncertainty quantification, and applies them to path planning, which has
roots in robotics and optimal control. The methodology
is based on solving (stochastic) partial differential equations. In this sense, it is rigorous and obviates the need
for heuristics. To compute the level set evolution, i. e.,
the viscosity solution to the Hamilton–Jacobi equation,
we either use our finite-volume code for partial differential equations (PDE) (with varied orders, limiters,
etc.) or narrow-band level set and fast marching methods for efficient computations. For the uncertain flow
case, we employ our stochastic PDEs solvers [21.15].
In all cases, the computational cost increases only geometrically with the number of grid points (and not with
the path length). We refer to the above-mentioned references for descriptions of numerical algorithms. Next,
we illustrate results under diverse fluid and ocean conditions, as well as diverse vehicle behaviors.
21.1.1 Canonical Steady Flows
We first evaluated our level-set-based methodology
by computing time-optimal paths in canonical steady
ocean flow features. Such problems include, for example, determining how to time-optimally enter or leave
an ocean eddy, cross an ocean jet, or maneuver in a meander/wave field [21.13]. The results can be very useful
as rules-of-thumb for time-optimal operations.
To exemplify such canonical steady flow problems, we consider idealized 2-D-in-space .x; y/ non-dimensional highway scenarios (2-D: two-dimensional),
as illustrated in Fig. 21.1 [21.13]. In the first case
(Fig. 21.1a), the vehicle is deployed from .0; 0:4/,
with the goal of reaching the point at .0; 0:8/. The speed
of vehicle is 1. The flow consists of two different jets,
both flowing in the positive y direction. The first jet
(narrow band with black arrows on the left) has a higher
speed, v 1 D 2, than the vehicle. The second jet (narrow
band with red arrows on the right) has a constant speed
equal to that of the vehicle, v 2 D 1. From (Fig. 21.1a),
the optimal path takes advantage of the higher jet flow
on the left to reach the goal point. In the second case
(Fig. 21.1b), the vehicle is deployed from .0:6; 0:6/
and the goal point is at .0:6; 0:6/. The speed of the vehicle is 1. In this case, we have two different jets flowing
in opposite directions, both with a speed of 1:5 (faster
than the vehicle). The first jet (upper narrow band with
black arrows) flows in the negative x direction. The second jet (lower narrow band with red arrows) flows in the
positive x direction. As can be seen from (Fig. 21.1b),
the vehicle rides the first jet to an upstream position of
the second jet in order to compensate for the unfavorable flow of the lower jet. Then, the vehicle crosses the
second jet as quickly as possible to reach its goal. In another highway test (Fig. 21.1c), the vehicle is deployed
from .0:6; 0:6/ and the goal point is at .0:6; 0:6/.
The speed of the vehicle is 1. In this case, we have two
different jets flowing with a speed of 1:5 (faster than
the vehicle). The first jet (upper narrow band with red
arrows) flows in the positive y direction. Therefore, it
is infeasible to use any trajectory crossing this jet flow.
The second jet (lower narrow band with black arrows)
flows in the positive x direction. As can be seen from
(Fig. 21.1c), the vehicle first skirts the upper flow on the
right-hand side. Then it moves to an upstream position
of the second jet and crosses it as quickly as possible to
reach the goal.
21.1.2 Time-Dependent 2-D Flows
Time-dependent flows are now considered. To evaluate
robustness, a large number of 2-D flows were utilized,
including flows at the exit of a strait, flows behind islands, and wind-driven flows. Such flows have also been
utilized to evaluate our approach for the path planning
of swarms of vehicles [21.3, 10–12, 14].
Next, we present three examples of time-optimal
path planning for swarms of vehicles in the context of