Science of Autonomy for Swarms of Ocean Vehicles 21.1 Time-Optimal Path Planning for Swarms of Ocean Vehicles 485
Part B | 21.1
Specifically, one member of each swarm switches to another swarm and all subsequently reform the swarms
in fastest time at 11 target locations (Fig. 21.2a). In
other words, we start with 11 swarms of 11 vehicles
each at the 11 starting points upstream of the island
(shown by open circles). Each of the initial swarms is
to break up and distribute one member to each of the 11
target points downstream of the island (shown by colored markers), resulting in 11 new swarms, each made
up from 1 member of each of the original 11 swarms.
The goal is to achieve the new configuration in minimum time, communicating data to each swarm leader,
while avoiding the island. The optimal paths computed
by our level-set-based method are the black curves in
(Fig. 21.2a). We see three classes of paths. Most paths
go above the island and get a boost from the first shed
eddy. A second group goes below the island and intercepts the eddy at a later point. The final grouping
remains below the island and avoids the eddy.
The second example is an all-back-to-ship fastesttime recovery scenario (Fig. 21.2b). A formation of 100
vehicles starts upstream of the island (black dots). The
goal is to find the quickest paths to bring all the vehicles
to a single pick-up point (18, 1:5) downstream of the
island, utilizing wakes and eddies while avoiding the
island (simulating the recovery of a swarm of AUVs by
a single ship). The optimal set of paths are found by the
level-set-based method and are shown as black curves
in Fig. 21.2b. Roughly three quarters of the vehicles are
sent over the island to take full advantage of the first
eddy. Most of the remaining vehicles avoid the eddy by
passing under the island, although some go under the
island and catch the eddy later.
21.1.3 Maintain Swarms Formations
Building on the above, we created algorithms for maintaining swarm formations. The first example consists of
three swarms of two to four members each, organized
in the shape of a line, triangle or square, coordinating
their paths based on gradients or dynamics (Fig. 21.2c).
For the algorithm illustrated, the coordination is based
on local gradients (Fig. 21.2c), using a local control
algorithm.
Here, the goal is to bring each of the three swarms
from their start locations to their target locations in
minimum time while maintaining their formation and
avoiding the island. We utilize our level-set-based
method to compute the optimal paths for the center of
mass of each swarm (black curves starting from black
dot and finishing at black star). Around each centerof-mass-path we construct the swarm paths by using
the headings for the optimal center-of-mass-path and
adding a velocity component at each step to maintain
each vehicle position relative to the center of mass. To
prevent the vehicle paths from diverging, we allow the
center of mass to move at a speed lower than the maximum vehicle speed (i. e., the center of mass moves with
a velocity that is a function of the instantaneous flow).
A drawback of this local control approach is that the
allowable separation between vehicles depends on the
flow dynamics. The distance between vehicles has to be
small if the flow speed is highly variable in space (large
flow gradients). The smoother the flow in space, the
larger the spacing between vehicles can be. In [21.12],
we develop a more powerful methodology based on local level-sets which allows maintaining complex shapes
in large flow gradients; a time optimal path is computed
for the group leader and finite-time local level sets are
computed continuously in time for the other vehicles in
the swarm. The latter provide reachable sets for each of
these vehicles for each finite-time horizon (which could
be a time step) and allow a subsequent shape optimization algorithm to find and sustain an optimal swarm
formation.
21.1.4 Forbidden Regions
Forbidden regions are areas which are denied to the
vehicles (for safety reasons or security restrictions)
but do not affect the flow field [21.3]. In the example that follows, this constraint information is provided
to the vehicles ahead of time, just as restricted regions or forecasts of hazardous weather can be provided
to an aircraft. In these conditions, the goal is still to
compute time-optimal paths, but under the additional
constraint of avoiding the provided or forecast forbidden regions.
For example, consider a uniform barotropic jet exiting a strait or estuary (sudden expansion or 2-D coastal
flow), as illustrated in Fig. 21.3. The non-dimensional
speed of the vehicle is 0:5, while the largest current
speed is 2:5 (Fig. 21.3a,b). The width of the inlet is one
third of the total width of the channel. In the simulation (Fig. 21.3c), nine vehicles are released from the
lower edge of the inlet (black dot) and are required
to achieve a triangular formation (colored dots). The
unconstrained time-optimal paths constructed from the
level-set-based algorithm are shown by colored lines.
The vehicle heading for the tip of the triangle rides
along the central jet, while the vehicles targeting the
four endpoints closest to the inlet use the upper and
lower recirculation eddies. Overall, we can see from
Fig. 21.3c that the algorithm correctly predicts the
shapes of the optimal paths.
In the companion case (Fig. 21.3d), two forbidden regions are added (gray shaded area), which block
seven of the nine paths in the free run (Fig. 21.3c). The
Part B | 21.1
Specifically, one member of each swarm switches to another swarm and all subsequently reform the swarms
in fastest time at 11 target locations (Fig. 21.2a). In
other words, we start with 11 swarms of 11 vehicles
each at the 11 starting points upstream of the island
(shown by open circles). Each of the initial swarms is
to break up and distribute one member to each of the 11
target points downstream of the island (shown by colored markers), resulting in 11 new swarms, each made
up from 1 member of each of the original 11 swarms.
The goal is to achieve the new configuration in minimum time, communicating data to each swarm leader,
while avoiding the island. The optimal paths computed
by our level-set-based method are the black curves in
(Fig. 21.2a). We see three classes of paths. Most paths
go above the island and get a boost from the first shed
eddy. A second group goes below the island and intercepts the eddy at a later point. The final grouping
remains below the island and avoids the eddy.
The second example is an all-back-to-ship fastesttime recovery scenario (Fig. 21.2b). A formation of 100
vehicles starts upstream of the island (black dots). The
goal is to find the quickest paths to bring all the vehicles
to a single pick-up point (18, 1:5) downstream of the
island, utilizing wakes and eddies while avoiding the
island (simulating the recovery of a swarm of AUVs by
a single ship). The optimal set of paths are found by the
level-set-based method and are shown as black curves
in Fig. 21.2b. Roughly three quarters of the vehicles are
sent over the island to take full advantage of the first
eddy. Most of the remaining vehicles avoid the eddy by
passing under the island, although some go under the
island and catch the eddy later.
21.1.3 Maintain Swarms Formations
Building on the above, we created algorithms for maintaining swarm formations. The first example consists of
three swarms of two to four members each, organized
in the shape of a line, triangle or square, coordinating
their paths based on gradients or dynamics (Fig. 21.2c).
For the algorithm illustrated, the coordination is based
on local gradients (Fig. 21.2c), using a local control
algorithm.
Here, the goal is to bring each of the three swarms
from their start locations to their target locations in
minimum time while maintaining their formation and
avoiding the island. We utilize our level-set-based
method to compute the optimal paths for the center of
mass of each swarm (black curves starting from black
dot and finishing at black star). Around each centerof-mass-path we construct the swarm paths by using
the headings for the optimal center-of-mass-path and
adding a velocity component at each step to maintain
each vehicle position relative to the center of mass. To
prevent the vehicle paths from diverging, we allow the
center of mass to move at a speed lower than the maximum vehicle speed (i. e., the center of mass moves with
a velocity that is a function of the instantaneous flow).
A drawback of this local control approach is that the
allowable separation between vehicles depends on the
flow dynamics. The distance between vehicles has to be
small if the flow speed is highly variable in space (large
flow gradients). The smoother the flow in space, the
larger the spacing between vehicles can be. In [21.12],
we develop a more powerful methodology based on local level-sets which allows maintaining complex shapes
in large flow gradients; a time optimal path is computed
for the group leader and finite-time local level sets are
computed continuously in time for the other vehicles in
the swarm. The latter provide reachable sets for each of
these vehicles for each finite-time horizon (which could
be a time step) and allow a subsequent shape optimization algorithm to find and sustain an optimal swarm
formation.
21.1.4 Forbidden Regions
Forbidden regions are areas which are denied to the
vehicles (for safety reasons or security restrictions)
but do not affect the flow field [21.3]. In the example that follows, this constraint information is provided
to the vehicles ahead of time, just as restricted regions or forecasts of hazardous weather can be provided
to an aircraft. In these conditions, the goal is still to
compute time-optimal paths, but under the additional
constraint of avoiding the provided or forecast forbidden regions.
For example, consider a uniform barotropic jet exiting a strait or estuary (sudden expansion or 2-D coastal
flow), as illustrated in Fig. 21.3. The non-dimensional
speed of the vehicle is 0:5, while the largest current
speed is 2:5 (Fig. 21.3a,b). The width of the inlet is one
third of the total width of the channel. In the simulation (Fig. 21.3c), nine vehicles are released from the
lower edge of the inlet (black dot) and are required
to achieve a triangular formation (colored dots). The
unconstrained time-optimal paths constructed from the
level-set-based algorithm are shown by colored lines.
The vehicle heading for the tip of the triangle rides
along the central jet, while the vehicles targeting the
four endpoints closest to the inlet use the upper and
lower recirculation eddies. Overall, we can see from
Fig. 21.3c that the algorithm correctly predicts the
shapes of the optimal paths.
In the companion case (Fig. 21.3d), two forbidden regions are added (gray shaded area), which block
seven of the nine paths in the free run (Fig. 21.3c). The