117
1 INTRODUCTION
According to statistics of ship accidents released by
the Japan Transport Safety Board of the Ministry of
Land, Infrastructure, Transport and Tourism, there
are more than 200 ship collision accidents each year in
Japanese waters. Since human, economic and
environmental damage caused by a ship collision
accident will be enormous, several legal or technical
measures have been taken at present.
One measure is the COLREG rules, which are
international operation rules to prevent ship collisions
enacted in 1972 and partial revision has continued
thereafter. However, since these rules basically set
action guidelines in the so-called one-to-one situation
where one ship faces another ship, they do not work
well in a narrow area nearby a large port, where
many ships are likely to get congested.
As another measure to prevent collisions, vessel
traffic service (VTS) centers have been established on
the coast of narrow and congested sea area, who
provide each ship with instructions on the safe and
efficient movement. However, in order to deal with
dangerous and emergent situations, quick and proper
instructions must be made, which is very challenging
even for experienced marine traffic controllers.
Furthermore, the cost of maintaining VTS centers is
tremendously high.
In order to support decision making by ship
officers, communication systems called automatic
radar plotting aid (ARPA) and automatic
identification system (AIS) are already working on
board. ARPA is the system to plot the positions of
neighboring ships, which are obtained through radar,
on screen, while AIS is the system that enables ships
to exchange various information such as id, types,
positions, speeds, destinations, with their neighboring
DSSA
+
: Distributed Collision Avoidance Algorithm in an
Environment where Both Course and Speed Changes are
Allowed
K. Hirayama, K. Miyake, T. Shiota & T. Okimoto
Kobe University, Kobe, Japan
ABSTRACT: Distributed Stochastic Search Algorithm (
DSSA ) is one of state-o
f
-the-art distributed algorithms
for the ship collision avoidance problem. In
DSSA
, whenever a ship encounters with any number of other
ships (neighboring ships), she will select her course with a minimum cost after coordinating their decisions
with her neighboring ships. The original
DSSA assumes that ships can change only their courses while
keeping their speed considering kinematic properties of ships in general. However, considering future
possibilities to address more complex situations that may cause ship collision or to deal with collision of other
vehicles (such as mobile robots or drones), the options of speed changes are necessary for
DSSA
to make
itself more flexible and extensive. In this paper, we present
DSSA
, as a generalization of DSSA , in which
speed change are naturally incorporated as decision variables in the original
DSSA . Experimental
evaluations are provided to show how powerful this generalization is.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 13
Number 1
March 2019
DOI: 10.12716/1001.13.01.11
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
s
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
 

119
The variable crs indicates a relative angle to
current ship heading, which can take not only any
angle from
45
degree (the leftmost) to
45
degree (the rightmost) at a step of 5 degree, but also a
special relative angle
dest
crs that leads directly to the
destination of self only if it is within
45 degree and
45 degree. Note that 0 degree of crs indicates a
current heading of self.

,
self
CR crs j computes a “collision risk” against
ship j when self changes her heading to crs.
TimeWindow is a constant length of time step for each
ship to predict future positions based on the
intentions of herself and her neighboring ships.

,TCPA crs j is the time to closest point of approach
against ship j when self changes her heading to crs and
ship j assumes to follow the received tentative
intention. Intuitively, the closer the time when self will
collide with ship j, the more the value of

,
self
CR crs j becomes.
On the other hand,

self
EF crs computes
“inefficiency” when self changes her heading to crs.
dest
is an absolute angle for the destination of self
and

crs
is an absolute angle for crs. Intuitively,
the closer the heading taken by self is to her
destination course, the smaller the value of

self
EF crs becomes. Note that a balance on the
impact to the cost between collision risk and
inefficiency can be controlled by a value of weighting
factor
.
In a distributed algorithm, the ships try to decide
their own intentions (the course which will be
selected at next time step) while exchanging their
tentative intentions. As her tentative intention, self
will try to select the course that achieves the
maximum cost reduction all the time. We thus define
the following variables:

max 0
self self self
crs Dom
improvement Cost Cost crs


argmax 0
self self self
crs Dom
intention Cost Cost crs


0
self
Cost
is the cost of a current heading of self
and

self
Cost crs is the cost when self changes her
heading to crs. Therefore,
s
elf
improvement is
nothing other than the maximum cost reduction while
s
elf
intention
is the course that achieves that
maximum cost reduction. We need to emphasize that
the values of these variables depend on tentative
intentions of neighboring ships. This is because a
value of

,TCPA crs j in computing collision risk
against ship j may vary depending on the tentative
intention of ship j.
By allowing the ships to exchange these tentative
intentions through a communication system such as
AIS, we have been considering that we can construct
various concrete distributed ship collision avoidance
algorithms. Among those presented so far, its latest
version is called Distributed Stochastic Search
Algorithm (
DSSA ).
3.3 DSSA
DSSA is one instantiation of distributed stochastic
search (Zhang, et.al. 2005) in the context of ship
collision avoidance. The technique of distributed
stochastic search was originally proposed to solve the
Distributed Constraint Optimization Problem
(DCOP), which is a general model for distributed
problem solving. This technique is quite simple but
powerful, and has been applied to solve various
distributed problem, such as the scheduling problem
on distributed sensor networks (Zhang, et.al. 2005).
Figure 2. Flowchart of DSSA from a global viewpoint
Following the scheme of distributed stochastic
search, we have built
DSSA for ship collision
avoidance, whose flowchart from a "global" viewpoint
is shown in Figure 2. In
DSSA , every ship (self) first
sets her current heading to her own intention. After
exchanging their intentions with neighboring ships,
self computes
s
elf
Cost ,
s
elf
improvement , and
_
s
elf
new intention
based on those exchanged
intentions. We should note here that
s
elf
intention is
not yet overwritten by
_
s
elf
new intention just
computed now. self is satisfied with her current
s
elf
intention if the maximum cost reduction
(
s
elf
improvement
) is equal to 0, and furthermore, the
system naturally reaches to a quiescence if all of the
ships are satisfied with their own intentions. On the
other hand, if any of the ships has a positive value for
s
elf
improvement , she will change her intention
probabilistically. More specifically, she will overwrite
her
s
elf
intention with _
s
elf
new intention with
probability
p
and will not do with probability
1
p
. With those updated intentions, the ships
proceed to the next round of exchanging intentions.
They repeat this process until a quiescence has been
reached or a predetermined time limit has come.