Z. Liu et al. / Annual Reviews in Control 41 (2016) 71–93 75
3.1. Path planning
As the fundamental aspect of USV guidance systems, path plan-
ning can generally be distinguished between the global and local
approaches. From the literature, a broad spectrum of efficient and
intelligent path planning techniques for USVs are identified in the
following.
3.1.1. Global path planning
1. Optimization methods : As an attractive method, advanced opti-
mization method (OM) can directly produce optimal trajectories
or paths that might include sophisticated characteristics, such
as spatiotemporal-optimal, danger level (collision probability),
fuel saving, weather routing, formation control, and scheduled
missions.
Inspired by the behavior of biological systems, evolutionary al-
gorithm (EA) represent a class of artificial intelligence increas-
ingly employed in the design of USV path planners. EA can be
characterized into an optimization problem with specified con-
straints. Genetic algorithm (GA) are to date the most widely
adopted method for waypoints generation ( Campbell et al.,
2012 ). In Svec and Gupta (2011, 2012) , a strongly-typed genetic
programming (GP)-based evolutionary approach is developed to
enable USVs to protect a target from intruder boats.
Due to their expensive computational costs, especially when
constraints such as obstacles, USV dynamic limits, and mission
constraints must be satisfied, optimization methods are limited
for real-time implementation.
2. Heuristic search algorithms : Application of heuristic approaches
in path planning first appeared in the early 20 0 0s. The A
∗
search algorithm is a widely used grid-based strategy, which
can quickly find an optimal path with the least number of
nodes. But the drawbacks of large computational memory costs
and unwanted sharp turns result in difficulty in its practical ap-
plication in the cases where quick and real-time control of USVs
are necessary.
In Larson, Bruch, and Ebken (2006) , the A
∗
search algorithm
is chosen to find an optimal path within a limited amount of
time. Another application is presented in Naus and Wa
˙
z
(2013) ,
where the A
∗
algorithm is employed to search the shortest and
safest trajectory in an electronic navigational chart. A
∗
and lo-
cally bounded optimal planning under uncertainty are com-
bined in Svec, Schwartz, Thakur, and Gupta (2011) . In Zhuang,
Su, Liao, and Sun (2012) , a marine radar image-based local path
planning method is developed for USVs. The path is searched
by Dijkstra’s algorithm which is a special case of the A
∗
algo-
rithm. To improve performance with respect to paths and com-
putational consumption, a modified version of the A
∗
algorithm
named as direction priority sequential selection (DPSS) is ap-
plied in Naeem, Irwin, and Yang (2012a) . In Svec, Thakur, Shah,
and Gupta (2012) , a combination of a model-predictive and an
A
∗
based algorithm is introduced. An A
∗
based curvature path
planning algorithm is proposed in Kim, Park, and Myung (2013) ,
where both the actual turning capability of USVs, and the en-
vironmental information, such as the terrain, buoy and fairway,
are explicitly considered in the cost map.
3.1.2. Local path planning
1. Line-of-sight : A successful guidance technique that is widely
employed in missile guidance, line-of-sight (LOS) methods are
equally valid for USVs ( Annamalai & Motwani, 2013; Breivik
et al., 2008; Caccia, Bibuli, Bono, & Bruzzone, 2008a; Cac-
cia et al., 2005; Desa, Maurya, Pereira, Pascoal, & Prabhude-
sai, 2007; Fredriksen & Pettersen, 2006; Naeem, Sutton, & Xu,
2012b; Peng, Wang, Chen, Hu, & Lan, 2013; Sharma & Sutton,
2013; Tran, Choi, Baek, & Shin, 2014; Xu, Sutton, & Sharma,
2007 ). There are also modified versions for better real-time im-
plementation such as biased-LOS ( Naeem et al., 2012a ). Despite
these, there are still drawbacks associated with LOS, including:
(1) the potential to overshoot, caused by the environmental dis-
turbances compensating action ( Campbell et al., 2012 ), and (2)
the connection between the waypoints still being rigid lines,
even though paths have been smoothed to some extent.
2. Potential fields : As defined in the potential field (PF) approach,
the objectives are assigned with attractive fields, while obsta-
cles are distributed with repulsive fields. USVs are thus moving
toward the attractive fields and away from the repulsive fields
( Khatib, 1986 ). Although this method is characterized by its ef-
fective implementation and low computational consumption in
real-time, it is normally only employed for local path planning
since it is prone to guide USVs to local minima instead of the
objectives ( Campbell et al., 2012 ).
An interesting implementation of a PF-based USV path plan-
ning scheme is introduced in Healey, Horner, Kragelund, Wring,
and Monarrez (2007) . In Soltan, Ashrafiuon, and Muske (2009) ,
obstacles are approximately enclosed by ellipse fields which
are the solutions of a class of ordinary differential equations
(ODEs). However, much effort is still required to overcome the
local-minima problem by employing depth-first and best-first
search techniques, wavefront-based strategies, or harmonic po-
tential functions.
3.1.3. Hybrid path planning
In order to ensure the safe and effective path planning for USV
moving among the preliminarily specified or dynamically chang-
ing waypoints in the dynamic and hazardous environment, increas-
ing efforts have recently been dedicated to the hybrid path plan-
ning strategy that consists of both global and local path plan-
ning approaches. In Larson et al. (2006) and Larson, Bruch, Hal-
terman, Rogers, and Webster (2007) , a hybrid path planning ap-
proach is presented, which is constituted by a two-layered hier-
archical architecture combining with both global and local path
planning functions. The A
∗
algorithm is employed to find a feasi-
ble solution for the global path planning, while a behavior-based
common world model approach is utilized to manage the near-
field changes that arise to the previously defined path, so that the
USV can keep following the preplanned path. Casalino, Turetta, and
Simetti (2009) presents a multi-layered hierarchical architecture, a
global path is computed in the first layer based on the Dijkstra al-
gorithm, while the second layer modifies this predefined path in a
locally optimal way adopting the A
∗
method. In Svec et al. (2012) , a
lattice-based hybrid path planning method is developed with con-
sideration of the USV dynamics.
3.2. Path replanning
As the major role of path replanning, collision avoidance ( Yu
& Zhang, 2015 ) is generally overlooked in the basic guidance laws
(an obstacle-free path is commonly assumed). Unfortunately, re-
cent statistics show that 60% of casualties at sea are caused by
collisions ( Naeem et al., 2012a ). Obstacles, such as lobster traps,
buoys, fishing nets, submerged rocks, other maritime traffic, new
constructions, variable water levels, and sea debris, can all po-
tentially contribute to collision risks. Without the ability to avoid
collisions, USVs may collide with any objects present along the
planned path. In addition, a collision avoidance module can also
enhance the autonomy of USVs to avoid approaching objects by
conducting autonomous path replanning.
3.2.1. Protocol-free collision avoidance
In Soltan, Ashrafiuon, and Muske (2011) , obstacles are as-
sumed to be enclosed by elliptical shapes, and a set of ordinary