
118
ships. For ships that meet certain criteria, installation
of AIS is internationally obligatory.
Kim and others have proposed the Distributed
Stochastic Search Algorithm (
DSSA ) with the aim of
realizing complete automatic ship collision avoidance
(Kim et.al. 2017). In
DSSA , ships having
communication function such as AIS exchange their
intentions (future plans of actions) of each other, and
automatically decide their courses to avoid collision
without relying on any central control like a VTS
center.
Since there is no brake on the ship, the speed
cannot be changed rapidly in principle. Therefore, in
DSSA , it was assumed that the ship would only
change the course while keeping the speed to avoid
collision. However, in consideration of the progress of
vessel maneuvering technology by using controllable
pitch propellers and the necessity to more effectively
avoid collision, we extend
DSSA in this paper so
that ships can change both course and speed.
The remaining part of this paper is structured as
follows. Section 2 mentions some related work on
computational approaches to ship collision avoidance.
Section 3 gives our general framework on distributed
ship collision avoidance and one of its latest
algorithms, Distributed Stochastic Search Algorithm
(
DSSA ). Section 4 presents DSSA
+
, as a
generalization of
DSSA
, and followed by
experimental evaluation showing its effectiveness in
Section 5. Finally, Section 6 concludes this work.
2 RELATED WORK
Several computational methodologies for realizing
automatic ship collision avoidance have been
proposed. Most of them deal with one-on-one or one-
to-many situations (Lamb and Hunt 1995; Lamb and
Hunt 2000; Lee et.al. 2004; Hu et al. 2008; Tsou &
Hsueh 2010; Tsou, et.al. 2010; Lazarowska 2015), and
very few studies have explicitly dealt with many-to-
many situations, where they simultaneously control
multiple ships that encountered with each other.
Although notable exceptions are the work on
evolutionary algorithm for computing multi-ship
trajectories avoiding collisions (Szlapczynski 2011;
Szlapczynski 2015), it is a centralized algorithm that
we believe become low performance if the number of
encountering ships increases.
On the other hand, by modeling ships as
autonomous agents, a series of distributed ship
collision avoidance algorithms are recently provided
(Kim, et.al. 2014; Kim et.al. 2015; Kim et.al. 2017). The
latest version of it, called DSSA, runs the distributed
stochastic search algorithm (Zhang, et.al. 2005) in
order to change courses of ships (while keeping their
individual current speeds).
3 DISTRIBUTED SCA
3.1 Framework
As shown in Figure 1, distributed ship collision
avoidance consists of two phases, which we call the
control phase and the search phase. We assume that all
ships iterate these two phases simultaneously. One
iteration of these phases is called one time step.
In the control phase, a ship, who does not reach
her goal, moves directly to the next position if she
finds no ship in her detection range. If she finds some
other ships in her detection range, they will shift into
the search phase.
In the search phase, several ships try to avoid
collisions by running a distributed algorithm. If all
ships find collision-free courses by that algorithm, or
if computation time exceeds a certain time limit, they
update the next positions based on the courses they
found, and will move there for the next time step.
Figure 1. Framework of Distributed SCA
3.2 Cost and Improvement
In a distributed algorithm, we assume that ships can
exchange intentions using a communication system
such as AIS. An intention of a ship in this context is
the course which will be selected by the ship at the
time point after one time step.
When receiving current positions, courses
(headings), speeds, and intentions of neighboring
ships, one ship (called self hereafter) will compute the
costs of current and every possible courses by using
the following formula:
,,
self self self
j Neighbors
Cost crs CR crs j EF crs
where
if will collide with ,
,
,
0,
self
TimeWindow
elf j
TCPA crs j
CR crs j
otherwise
180
dest
self
crs
EF crs
,
45,40, ,5,0,5, ,40,45,
dest
crs Dom crs