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.
25
3 ALGORITHMFORSHIPCOLLISION
AVOIDANCE
3.1 ShipCollisionAvoidancebyDistributedLocal
Search
We propose DLSA to prevent ship collisions as a
precedentstudy.Thevariablesusedare:
TimeStep:estimatedpositioninaspecifictime.
Detection of Range: distance to recognized
neighboringships.
NeighboringShips:
shipslocatedinthedetection
rangeandabletoexchangeinformation.
SafetyDomain:distancethatmustbemaintained
from neighboring ships. Ships entering this
domainareconsideredtohavecollided.
Number of Collisions: expected number of
collisionswithneighboringships.
Remaining Time: time remaining for the soonest
expectedcollisionexpectedmostrapidly.
Collision Risk: sum of the number of collisions
andremainingtime.
Ok? Message: includes information on position,
speed,andcourse.
Improvement Message: includes the number
indicatinghowmuchcollisionriskisreduced.
ID:identificationgivenataninitialstateandused
when
improvement is the same as that for a
neighboringship.AshipwithahigherpriorityID
hastherighttochoosethenextcourse.
Figure1.ContactableneighboringbyDoR
Figure2.Variables
Theproceduresforpreventingshipcollisionsare
showninFigure3.Eachshipsearchesitsvicinityto
find a target ship. If a target ship exists, it is
registered in the neighboring ships list. Individual
ships exchange an ok? Message and compute cost
function. If a collision risk exists, individual ships
exchangeimprovementmessages.Theshipwiththe
largestimprovementhastherighttochoosethenext
possiblecourse. Aship withhigher priorityhas the
righttoselectthenextcourseiftheimprovementfor
severalshipsissame.Ifthecollisionriskdisappears,
the ships move tothe next
position. This process is
repeated until all ships arrive at the destination.
Simultaneously altering the course of neighboring
ships is restricted because of the possibility of
enteringintoaninfiniteloop.Theshipsallhavefour
typesofvariables–TimeStep(T),ShipDomain(D),
DetectionofRange (DoR),and
Course(C).Figure1
showsthedifferencebasedonDoR.UsingDoR,the
number of recognizable neighboring ships changes.
The variable definitions are provided in Figure 2.
Anyshipcanpreventatargetshipfrompenetrating
theirsafetydomain.Figure4showsthesimulation
withsix ships.All shipsarrived
attheir destination
withoutcollision.
Figure3.AlgorithmforShipCollisionAvoidancebyDLSA
26
Figure5.ProcedureforDTSA
Figure4.Simulated encountersamong 6 shipsby
DLSA
3.2 ShipCollisionAvoidancebyDistributedTabuSearch
DLSA suffers from QLM, in which a ship cannot
change its course even though a collision risk still
exists. To solve this problem, we applied DTSA.
DTSA enables individual ships to choose another
coursecompulsorily.For efficiencyandsimplicity of
the algorithm, we modified the cost function. To
compute the cost function, the relative bearing from
the ship’s heading to the destination is added. The
candidate courses are also modified. Table 1 shows
the difference between DLSA and DTSA. Figure 5
illustratestheDTSA
procedure. Allships repeatthis
process until they arrive at their destination. Each
shipchecksforwhetherithasarrivedthedestination.
If not, the ship searches the vicinity to find a
neighboringship.Theshipexchangesanok?Message
and improvement messages with its neighbors. The
shipwiththe
highestimprovementchoosesthenext‐
intendedcourse.Ifthereisnocollision,allindividuals
movetothenextposition.Ifnot,theshipexchanges
theexchangedinformationwithitsneighboringship.
IfaQLMsituationoccurs,thecurrentselectedcourse
27
is stored in the tabu list. The ship chooses the next‐
intended course randomly except for any course in
thetabulist.Ifthecollisionriskhasdisappeared,all
ships move to the next position. Figure 6 shows a
simulationwith five ships. All ships arrived attheir
destinationwithout
collision.
Table1.DifferencebetweenDLSAandDTSA
_______________________________________________
DifferenceDLSADTSA
_______________________________________________
Costfunction Numberof Numberofexpected
expectedcollisions collisions+
+remainingtime remainingtime+
relativebearingfrom
headingtodestination
Candidatecourses 3kindsUser’sneeds
RemedyforQLM NoneTabuSearch
_______________________________________________
Figure6.Simulatedencountersamong5shipsbyDTSA
4 EXPERIMENTS
Our experiment used six different situations
dependingonthenumberofshipsandshipposition
to test the performance of DTSA as compared to
DLSA.Eachvariablehasthefollowinggivenvalues:
SafetyDomain={2,3,4}miles,RangeofDetection=
{10, 20} miles, and Speed =
{1, 2, 3}. The minus and
plus signs indicate the port and starboard,
respectively. To evaluate the performance, we
computed an average distance and the number of
failures. We used MATLAB for the experiments.
Table2 showsthe meaning ofthe index usedin the
experimentalresults.
4.1 Experiment1
Weexperimentedwithsixshipswiththreevariables.
Figure7(left)illustratesthesituationforexperiment1.
Table 3 shows the neighboring ship list. Each ship
recordsitsneighboringshipsinthelist.Thatis,ship1
recognizesships2and3.Ship2recognizesships1,3,
and5.Thereis
nocollisionriskforships1,3,4,and6,
butships2and5areatriskofcollision.Allvariables
areusedbyexchanging theirvaluesinonesituation.
In total, forty‐two experiments were conducted.
Figure 10 shows the result for experiment 1.
ComparedwithDLSA,DTSA
hasabetterresult.The
average distance and the amount of failures had a
tendency to decrease as the number of candidate
courses increased. The cases of 45 and ALL DTSA
showedthe bestresults, whichwereno failures and
lowaveragedistance. Table4showsthevariablesand
valuesused
inthisexperiment.
Figure7.Situationforexperiments1(left)&2(right)
Figure8. Situation for experiments 3 (left, 10 ships with
samedirection)&4(right,20shipswithoppositedirection)
Figure9.Situationforexperiments5(left,20shipwithsame
direction)&6(right,100shipsinitializedrandomly)
Table2.CandidatecoursebyIndexusedinexperiments
_______________________________________________
IndexCandidatecourse
_______________________________________________
15‐15°,0°,+15°
30‐30°,0°,+30°
45‐45°,0°,+45°
ALL‐45°,‐30°,‐15°,0°,+15°,+30°,+45°
_______________________________________________
Table3.Listofneighboringshipsforexperiment1
_______________________________________________
Numberofships 1 2 3 4 5 6
_______________________________________________
1x o o x x x
2o x o x o x
3o o x x x x
4x x x x o o
5x o x o x o
6x x x o o x
_______________________________________________
28
Table4.Variablesandvaluesforexperiment1
_______________________________________________
VariablesValues
_______________________________________________
SafetyDomain2,3,4(miles)
RangeforDetection10,20(miles)
Speed1(20knots)
_______________________________________________
Figure10.Resultforexperiment1.
4.2 Experiment2
Inexperiment2,weexperimentedwithfiveshipsthat
individual ships encounter, as shown in Figure
7(right).Thetracksofships1,2,3,and4producedan
Xshape.Ship5cutsacrossthespacesimultaneously.
Figure 11 shows the result for experiment 2. In the
experimental
result,exceptfor15DLSA,theaverage
distanceshowedsimilarfigures.Thecasesof30and
ALL DTSA recorded no failures and low average
distance.15DLSAhadthegreatestdrawbackinterms
ofaveragedistance.Table5showsthevariablesand
thevaluesforexperiment2.
Table5.Variablesandvaluesforexperiments2‐6
_______________________________________________
VariablesValues
_______________________________________________
SafetyDomain2,3,4(miles)
RangeforDetection10,20(miles)
Speed1,2,3(1=>1mile/3min)
_______________________________________________
Figure11.Resultforexperiment2
4.3 Experiment3
Weexperimentedwithtenshipstravelinginthesame
directiontowardthedestination,asshowninFigure
8(left). Figure 12 shows the result for experiment 3.
Compared with DLSA, DTSA demonstrated better
performance overall. All DTSA showed low and
uniformaveragedistance.AmongallDTSA, only15
DTSA
recordedafailure.Table5showsthevariables
andvaluesusedinexperiment3.
Figure12.Resultforexperiment3
4.4 Experiment4
Weexperimented withtwentyships traveling inthe
opposite direction away from the destination, as
showninFigure8(right).Inthisexperiment,DLSAis
unable to compute a situation involving more than
twenty ships. We therefore used DTSA only in this
experiment.Figure13showstheresultfor
experiment
4: the larger the candidate course, the smaller the
failurecounts.ALLDTSAperformedbestinregardto
average distance and 45 DTSA had the highest
averagedistance.Only15DTSArecordedanyfailures
(seven).Table5showsthevariables andvaluesused
inexperiment4.
Figure13.Resultforexperiment4.
4.5 Experiment5
We experimented with twenty ships moving in the
same direction toward the destination, as shown in
Figure9(left).Table5showsthevariablesandvalues
29
usedinexperiment5andFigure14showstheresult.
Failures occurred only in the 15 DTSA case (two).
ALLDTSA showed thelowestaveragedistanceand
45 DTSA showed the highest average distance. The
patternoftheexperimentalresultwassimilartothat
ofexperiment4.
Figure14.Resultforexperiment5
4.6 Experiment6
We used one hundred ships in experiment 6, as
shown in Figure 9(right). The ship positions and
headingswereinitializedrandomly.Theredandblue
circles indicate the origin and destination for the
individual ships. Table 5 shows the variables and
valuesusedinexperiment6andFigure
15showsthe
result. ALL DTSA had no failure and the lowest
averagedistance.Inaddition,thepatternoftheresult
showed a similar tendency to that of experiments 4
and5.
Figure15.Resultforexperiment6
5 CONCLUSION
Weexplainedearlierthatseveralalgorithmsworkin
specific situations, such as one‐on‐one situations. To
avoid ship collisions in multiple‐ship situations, we
applied DTSA and DLSA as a precedent study. We
used the tabu search algorithm to avoid the QLM
problem. We improved cost function by
adding the
relative heading toward the destination and also
increased the candidate courses as per the users’
needs. Our experiments demonstrated how
individualshipscanavoidcollisionsinmultiple‐ship
situations. In the experimental results, DTSA
outperformed DLSA. Some experiments showed
similar patterns: The more the number of candidate
courses
isincreased,theshortertheaveragedistance;
thelessthesizeofthedegreeofthecandidatecourse,
the greater the failure count. This is because a ship
canboreoffquicklyifitdrasticallyaltersitscourse.In
experiments 4, 5, and 6, the experimental results’
patternsweresimilar.45
DTSArecordedthehighest
averagedistance.Inthecaseof45DTSA,therangeof
fluctuationforthecandidatecoursewaslarger. ALL
DTSA showed the lowest average distance in most
cases.Thismeans thatthe morecandidatesolutions,
thebettertheperformance.
REFERENCES
Fan, L. & Ajit, N. 2014. 17th International Conference on
PrinciplesandPracticeofMulti‐AgentSystems (PRIMA
2014):190‐205.
Fujii, Y. & Tanaka, K. 1971. Traffic Capacity. Journal of
Navigation24:543‐552.
Glover, F. 1989. Tabu Search‐Part I. ORSA Journal on
Computing1(3):190‐206.
Goodwin, E.M. 1975. A
Statistical Study of Ship Domains.
JournalofNavigation28:329‐341.
Hasegawa,K.,Kouzuki,A.,Muramatsu,T.,Komine,H.,&
Watabe, Y. 1989. Ship Auto‐navigation Fuzzy Expert
System (SAFES). Journal of the Society of Naval
ArchitectureofJapan166.
International Maritime Organization, 1972. Convention on
the International Regulations for Preventing
Collisions
atSea.
Kim, D., Hirayama, K., & Park, G. 2014. Collision
Avoidance in Multiple‐ship Situations by Distributed
Local Search. Journal of Advanced Computational
IntelligenceandIntelligentInformatics18(5):839‐848.
Kim, E., Kang, I., & Kim, Y. 2001. Collision Risk Decision
System for Collision Avoidance. Korean Institute of
IntelligentSystems
11:524‐527.
Lee, S., Kwon, K., & Joh, J. 2004. A Fuzzy Logic for
Autonomous Navigation of Marine Vehicles Satisfying
COLREG Guidelines. International Journal of Control,
AutomationandSystems2:171‐181.
Russell, S. & Norvig, P. 2003. Artificial Intelligence: A
ModernApproach,Pearson:137‐160.
Szlapczynski,R.2006.AUnified
MeasureofCollisionRisk
DerivedfromtheConceptofaShipDomain.Journalof
Navigation59:477‐490.
Szlapczynski, R. 2007. Determining the Optimal Course
Alteration Manoeuvre in a Multi‐target Encounter
Situation for a Given Ship Domain Model. Annual of
Navigation12:75‐85.
Tsou, M., Kao, S., & Su, C. 2010.
Decision Support from
GeneticAlgorithmsforShipCollisionAvoidanceRoute
PlanningandAlerts.JournalofNavigation63:167‐182.
Wang, N., Meng, X., Xu, Q., & Wang, Z. 2009. A Unified
Analytical Framework for Ship Domains. Journal of
Navigation62:643‐655.
Yokoo,M.,Durfee,E.,Ishida,T.,&Kuwabara,K.1998.
The
Distributed Constraint Satisfaction Problem:
Formalization and Algorithms. IEEE Trans. on
KnowledgeandDataEngineering10:673‐685.
Yokoo, M. & Hirayama, K. 1996. Distributed Breakout
Algorithm for Solving Distributed Constraint. Second
Int.Conf.onMultiagentSystems:401‐408.
