23
1 INTRODUCTION
Severalmethodsareusedtopreventshipcollisions,
such as lookouts, radar, and VHF radio. More
advancedmethodologies,suchasshipdomain,fuzzy
theory, and genetic algorithm, have been proposed
(Szlapczynski 2006, 2007, Goodwin 1975, Fujii &
Tanaka 1971, Hasegawa, Kouzuki, Muramatsu,
Komine, & Watabe 1989,Wang, Meng Xu, & Wang
2009, Lee, Kwon, & Joh 2004, Kim, Kang, & Kim
2001). However, in realit
y, collisions between ships
frequently occur. This is partly due to the ever‐
increasing size and speed of ships each year. A
primary cause of ship collisions is officer error.
Officersgenerallyhavesomeexpertiseinfindingsafe
routes tha
t will avoid ship collisions; however,
particularly when shipping lanes are crowded and
many ships encounter each other simultaneously,
findingsuchroutesisespeciallydifficultforofficers.
The needtorepeatthis ta skthroughout the voyage
multiplies the risk of human error. To support the
need to find safe routes for ship tra
vel in crowded
waters, we proposed the Distributed Local Search
Algorithm (DLSA) as a precedent study (Kim,
Hirayama, & Park 2014). In DLSA, we assume that
ships can exchange information with each other
(using a communication device such as the
Automatic Identification System (AIS)) to
cooperatively est
ablish routes to avoid collisions.
Morespecifically,whenmultipleshipsmeet,theship
that can reduce collision risk most significantly has
therightto chooseitsnextcourse. Wherethere isa
Ship Collision Avoidance by Distributed Tabu Search
D.Kim,K.Hirayama,&T.Okimoto
KobeUniversity,Kobe‐shi,Hyogo‐ken,Japan
ABSTRACT: More than 90% of world trade is transported by sea. The size and speed of ships is rapidly
increasinginordertoboosteconomicefficiency.Ifshipscollide,thedamageandcostcanbeastronomical.Itis
verydifficultforofficerstoascertainroutestha
twillavoidcollisions,especiallywhenmultipleshipstravelthe
samewaters.Thereareseveralwaystopreventshipcollisions,suchaslookouts,radar,andVHFradio.More
advancedmethodologies,suchasshipdomain,fuzzytheory,andgeneticalgorithm,havebeenproposed.These
methods work well in one‐on‐one situations, but are more difficult to a
pply in multiple‐ship situations.
Therefore,weproposedtheDistributedLocalSearchAlgorithm(DLSA)toavoidshipcollisionsasaprecedent
study.DLSAisadistributedalgorithminwhichmultipleshipscommunicatewitheachotherwithinacertain
area.DLSAcomputescollisionriskbasedontheinformat
ionreceivedfromneighboringships.However,DLSA
suffersfromQuasi‐LocalMinimum(QLM),whichpreventsashipfromchangingcourseevenwhenacollision
riskarises.Inourstudy,wedevelopedtheDistributedTabuSearchAlgorithm(DTSA).DTSAusesatabulistto
escapefromQLMthatalsoexploitsamodifiedcostfunct
ionandenlargeddomainofnext‐intendedcoursesto
increaseitsefficiency.WeconductedexperimentstocomparetheperformanceofDLSAandDTSA.Theresults
showedthatDTSAoutperformedDLSA.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 9
Number 1
March 2015
DOI:10.12716/1001.09.01.03
24
tieinthemaximumriskreduction,theonewiththe
highest priority has the right to choose its next
course. These choices are then relayed to their
neighboring ships as their current courses. Each
individualship computes its collisionrisk based on
the information on current courses that it receives
fromtheneighboringships.Thisprocessisrepeated
untilthecollisionriskdisappears.DLSAworkswell
empirically,but, according to ourrecent study, itis
sometimestrappedinQuasiLocalMinimum(QLM)
thatpreventsashipfromchangingcourseevenwhen
atriskofcollision.
To deal with this issue,
we developed a new
distributed algorithm called the Distributed Tabu
Search Algorithm (DTSA). DTSA enables a ship to
searchforanewcoursecompulsorilywhentrapped
in QLM, to allow it to escape. Furthermore, DTSA
exploits a modified cost function and enlarged
domain of next‐intended courses to increase its
efficiency.
The cost function, which computes the
collision risk of the current course in DLSA, is
modifiedsothatitincludesthe notionofefficiency.
Morespecifically,weaddtherelativebear ingofthe
currentcoursetothedestination.Inthisway,DTSA
enables ships to find shorter paths to their
destinationswhileavoidingcollisions.
Our paper is organized as follows: in Section 2,
we outline the background of this work. We then
describe DLSA and DTSA in Section 3 and explain
howDTSA isapplied to shipcollision avoidancein
Section 4. We present our experimental analysis in
Section5and
ourconclusionsinSection6.
2 BACKGROUND
2.1 ExistingmethodsforCollisionAvoidance
There are many methods for preventing ship
collisionsatsea.Fromaregulationpointofview,the
1972ConventionontheInternationalRegulationsfor
PreventingCollisionsatSea(COLREGs)(IMO1972)
compels or recommends that ships follow
specific
regulations, for example, navigational lights, traffic
laws of the waterways, and the buoyage system.
From a technological point of view, several
algorithmsareusedinshipcollisionavoidance,such
asshipdomain(Fujii&Tanaka1971,Goodwin1975),
fuzzy theory (Hasegawa, Kouzuki, Muramatsu,
Komine,&Watabe1989),andgeneticalgorithm
(GA)
(Tsou,Kao,& Su2010). Theship domainalgorithm
computes collision risk depending on whether the
ship’ssafetydomainispenetrated.Thefuzzytheory
computesthemembershipfunctionforcollisionrisk.
To compute collision risk, several parameters‐
Variation of Compass Degree (VCD), Time to the
Closest Point of Approach
(TCPA), and Distance to
theClosestPointofApproach(DCPA)‐areused.The
GA is based on the principle of evolution, that is,
survival of the fittest. Tsou, Kao, & Su (2010) used
GA to find the safest and shortest path that also
complied with COLREGs. The fitness function is
defined
asthedistancefromtheturningpointtothe
originalroute.Aschromosomeconstitution,thereare
four parameters‐avoidance time, turning angle,
restoration time and limited angle. They found
optimum routes under three situations in which a
ship can encounter a target ship. Fan & Ajit (2014)
suggested collision avoidance
without mutual
communication.Theywereinspiredbynature,such
asthebehaviorofhumansincrowdedareas.Intheir
study, however, individual agents can stop at
anytime,whichisimpossibleforships.Asmentioned
previously, these works well in one‐on‐one
situations,but,withmultipleshipscollisionsmaybe
difficult
toavoid.Tosolvethisproblem,wesuggest
DLSAasaprecedentstudy.
2.2 DistributedLocalSearchAlgorithm
Local Search Algorithm (LSA) is a metaheuristic
methodtosolvetheoptimizationproblemandanin‐
complete algorithm. Examples are hill‐climbing,
simulatedannealing,andthetabusearchalgorithm.
A solution may
or may not be found for a certain
problem.LSAhasbeenusedforthenursescheduling
and travelling sales‐man problems. LSA is a
centralizedsystembasedonacomputerorserver.If
thesystemisbroken,itisimpossibletomaintainit.
In comparison, DLSA does not have a
server or a
computer (Russell & Norvig 2003, Yokoo, Durfee,
Ishida,&Kuwabara1998,Yokoo&Hirayama1996).
An individual agent solves a certain problem by
exchanging information with other agents locally.
DLSA is flexible during a system failure. DLSA is
easilyappliedtoshipcollisionavoidanceinmultiple‐
ships
situations. All ships can chart their course
freely. Theypreferacourse that will allow them to
reachtheirdestinationsafelyand quickly.Acertain
sea area, such as an entry port, crossing area, or
narrowareahasnooptionbuttobecrowdedbecause
allshipswilltravelina
similarpattern.Inaddition,
each individual ship must find a solution by itself
usinglocalinformation.Therefore,weappliedDLSA
toavoidshipcollisionsasprecedentstudy.
2.3 TabuSearchAlgorithm
TabuSearch(TS)isaheuristicmethodproposedby
Glover (Glover 1989). Tabu means prohibited. By
usingmemoryto
prohibitcertainmoves,TSsearches
for global optimization rather than local
optimization. There are several kinds of memory
structures, such as, short, intermediate, and long‐
term memory. The short‐term memory prohibits a
solution(move)frombeingselectedinthetabu list.
The intermediate‐term memory may lead to bias
moves
toward promising areas. The long‐term
memoryguidestonewsearchareasfordiversity.TS
is being used in integer programming, scheduling,
routing, and the traveling sales‐man problem. In
conventionalproblems,applicationoftheshort‐term
memoryonlyissufficient.Inourpaper,weuseTSto
escape QLM,
which prevents a ship in risk of
collision from changing course. In this paper, we
describethenewmethodwithDTSAandtheuseof
DLSA as a precedent study for ship collision
avoidance.