31
1 INTRODUCTION
The problem of collision avoidance is an up‐to‐date
anddynamicallydevelopingresearchtopic.
Control systems, providing opportunity of safe
control of an object in a dynamic environment,
enabling collision avoidance of both stationary and
moving obstacles, occurring in the vicinity, are
applied in autonomous mobile robots, unmanned
vehicles, aircraft ant
i‐collision systems and also
marinecontrolsystems,calledGuidance,Navigation
andControl(GNC)systems.
Currently, the existing ship collision avoidance
systemsdeterminetheriskofcollisionwiththeuseof
parameters such as the Closest Point of Approach
(CPA)andtheTimetotheClosestPointofApproa
ch
(TCPA),indicatethecollisionthreatbyappropriate
alarm and allow to check the effects of the planned
manoeuvre (the trial manoeuvre function of an
Automatic Radar Plotting Aid‐ARPA), but do not
giveproposalsofsafecourseorspeedalterations.
Thedevelopmentoftheship’ssafecontrolsystem,
enablinga
utomaticdeterminationofasafetrajectory
of the ship, is still a current and important research
problem. The solution of this issue can then be
extended for application to other mobile objects
(airplanes,unmannedvehicles,mobilerobots).
Inordertoobtainthesafeandoptimaltrajectoryof
a ship a variety of det
erministic and heuristic
optimizationmethodsareproposed intheliterature.
Among the most recent proposals the following
methods should be mentioned: the A* algorithm
(Naeem et al. 2012), the Ant Colony Optimization
(Escario et al. 2012, Tsou & Hsueh 2010), the
cooperativepathplanning(Tam&Bucknall2013),the
different
ial games (Lisowski 2016b), the dynamic
programming (Lisowski 2016a), the fast marching
method (Liu & Bucknall 2015), the fuzzy logic
approach(Mohamed‐Seghir2016,Pereraetal.2011),
Multi-criteria ACO-based Algorithm for Ship’s
Trajectory Planning
A.Lazarowska
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT: The paper presents a new approach for solving a path planning problem for ships in the
environment with static and dynamic obstacles. The algorithm utilizes a heuristic method, classified to the
groupofSwarmIntelligenceapproaches,calledtheAntColonyOptimization.Themethodisinspiredbya
collect
ivebehaviourofantcolonies.Agroupofagents‐artificialantssearchesthroughthesolutionspacein
ordertofindasafe,optimaltrajectoryforaship.Theproblemisconsideredasamulti‐criteriaoptimization
task.Thecriteriatakenintoaccountduringproblemsolvingare:pathsafety,pathlengt
h,theInternational
RegulationsforPreventingCollisionsatSea(COLREGs)complianceandpathsmoothness.Thepaperincludes
thedescriptionofthenewmulti‐criteriaACO‐basedalgorithmalongwiththepresentationanddiscussionof
simulationtestsresults.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 11
Number 1
March 2017
DOI:10.12716/1001.11.01.02
32
thegeneticalgorithm(Tam&Bucknall2010,Tsouet
al.2010),theneuralnetworks(Ahnetal.2012,Simsir
etal.2014)andthepotentialfieldmethod(Xueetal.
2011).Inthelastfewyearsanewapproachemerged,
based upon the use of auto‐negotiation of
manoeuvres (Hornauer
& Hahn 2013, Szłapczyńska
2015). The multi‐criteria optimization methods are
alsopresentinthecurrentliterature(Szłapczyński&
Szłapczyńska2012,Śmierzchalskietal.2013).
Theproblemisacomplexoptimizationtask,soit
is very difficult to develop a method, applicable in
commercial
solutions,thatwilltakeintoaccountallof
the constraints and process requirements, such as
static and dynamic obstacles, fulfilment of the
InternationalRegulationsforPreventing Collisionsat
Sea(COLREGs),near‐realtimeoperation.
Theaimoftheresearchpresentedinthispaperis
to develop an algorithm for ship’s safe
trajectory
planning, applicable in a GNC system, utilizing a
multi‐criteriaACO‐basedalgorithm.
2 SHIP’STRAJECTORYPLANNING
Figure1showsadiagramofanGNCsystem,where
the ship’s safe trajectory planning algorithm is
applied in the Trajectory Generator (TG) module.
Besides the different sensors, a computer with an
advanced optimization algorithm, constitutes the
basic component of a TG. The TG computes a safe,
optimal trajectory based upon the motion data
(positionandvelocity)ofanownship(OS)andother
vessels from the Navigation System and passes the
resultstotheMotionControlSystem.
The ship’s safe, optimal trajectory
planning
problemcanberegardedasanoptimizationtask.The
optimizationcriteriathatshouldbetakenintoaccount
during problem solving include: path safety (not
exceeding static and dynamic navigational
constraints), path length, COLREGs compliance and
pathsmoothness(thesmallestcoursealterations).
Due to the need to take into account
several
criteria, when searching for the safe and optimal
trajectoryoftheship,thetaskshouldberegardedasa
multi‐criteriaoptimizationproblem.
3 MULTI‐CRITERIAACO‐BASEDALGORITHM
Itwasdecided,thattheWeightedObjectivesMethod
will be applied as a multi‐criteria optimization
approach. The idea of this
method is to transform a
multi‐criteria optimization into a single criterion
optimization, by an application of a fitness function
constitutingaweightedsumofdifferentcriteria,asin
Equation1.
k
i
ii
xfwxF
1
)()( (1)
Thefitnessfunctionisthanevaluatedasinasingle
criterionoptimizationtask.
In the research presented in this paper a fitness
functionappliedtosolvingship’strajectoryplanning
problemisdefinedbyEquation2.
)()(
)()()(
43
21
pruleswpsmoothnessw
plengthwpsafetywpfitness
(2)
Thesafetycriterionsafety(p)evaluatesthesafetyof
the trajectory. It is checked, whether the trajectory
does not intersect static obstacles (lands, shallows)
and does not cause collision with other ships
occurringinthevicinityofanownship.
Thecriterionlength(p) iscalculatedas a lengthof
the
minimaltrajectory(alinesegmentjoininganown
ship actual position (the starting waypoint) to the
finalwaypoint)dividedbyalengthoftheevaluated
trajectory.
The smoothness(p) criterion evaluates the
smoothnessofthetrajectory, thatmeansthevaluesof
course alterations at consecutive stages of the
trajectory.Whenthe course
alterationisless than15
degreesormorethan60degrees,thecalculatedvalue
of this criterion fulfilment for the evaluated path is
reducedbyapredefinedpenaltyfactor.
Figure1.GNCsystemdiagrambasedupon(Fossen2011).
33
The rules(p) criterion is applied to evaluate the
COLREGs compliance of the trajectory. When the
evaluated trajectory consists of a manoeuvre to the
portside,thevalueofthiscriterionfulfilmentforthe
evaluated path is reduced by a predefined penalty
factor.
Multi‐criteriaACO‐basedalgorithmforship’ssafe
trajectory planning, presented in this paper, is a
development of an algorithm presented in
(Lazarowska 2013). The previous version was
developed to solve a problem regarded as a single
criterion optimization task. The fitness function
applied there was defined as the length of the
trajectory.Theoperationprincipleissimilar
forboth
versions of the algorithm: single and multi‐criteria
approach. The difference is in the fitness function
appliedtofindthefinalsolution.
Inputdataconcernmotionparametersofallofthe
ships taking part in an encounter situation, their
courses,speeds,bearingsanddistancesfromanown
ship.The
AntColonyOptimizationmethodisapplied
to calculate a set of solutions (trajectories). These
solutions are then evaluated with the use of a
specifiedfitnessfunctionandasolutioncharacterized
bythehighestvalueofthepathfitnessconstitutesthe
finalsolution(trajectory).
The first step of the algorithm is
the input data
reception from the Navigation System. Based upon
the received information, in the next step relative
courses,speedsandbearingsoftargetships(TSs)are
calculated. After that, the dangerous TSs check
procedure is executed. It is applied to evaluate,
whether the TS constitutes a dangerous object
(obstacle).A
TSis consideredasadangerousobject,
whenitintersectsitscoursewiththecourseofanown
ship.
In the next step a construction graph is built,
taking intoaccount both static (lands,shallows) and
dynamic (TSs) constraints. The graph vertices
constitutepossibleownshippositions.
Then,theACO
calculationsareperformed.Inthis
procedure, at first ACO parameters, such as: the
pheromonetrailamountonallvertices(τ
0),theαand
β coefficients used in the formula calculating ant’s
next move probability, the pheromone evaporation
rate(ρ),thenumberofants,themaximumnumberof
ant’s steps and the number of iterations, are
initialized. Afterwards, two steps are repeated for a
defined number of iterations: the solution
construction
procedure and the pheromone trail
updateprocedure.
In the solution construction procedure every ant
buildsits path from the starting vertex of the graph
(currentpositionofanownship)totheendingvertex
(the defined final point of the trajectory). At every
step an ant chooses the next own ship
position (the
vertexonthegraph)withtheuseoftheactionchoice
rule, which works similarly to the roulette wheel
selection procedure used in the evolutionary
algorithms.Theprobabilisticchoiceofthenextvertex
depends on the value of the parameter called the
pheromonetrailon the neighbouring vertex
andthe
heuristicinformationcalledvisibility.Thevisibilityis
defined as the inverse of the distance between the
currentvertexandtheneighbouringvertex.
The pheromone trail update procedure is
composedoftwostages:thepheromoneevaporation
and the pheromone deposit. The function of the
pheromone evaporation is to reduce the
value of
pheromone trail on all vertices. During the
pheromonedepositacertainvalueofthepheromone
trail is added to all vertices belonging to the paths
constructed by ants in the iteration. The aim of this
mechanism is to increase the pheromone trail value
ontheverticesconstitutingparts
oftheshortestpaths,
whatenhancestheprobabilityoftheirselectionbythe
antsinthesubsequentiterations.
Next,trajectoriesbelongingtothesetofsolutions
determined with the use of ACO method, are
smoothened in order to receive more optimal paths
and evaluated with the use of a fitness function
defined by Equation 2. In the last step the solution
characterized by the highest value of a fitness
function is presented in a numerical and graphical
form.
Figure2showstheflowchartof themulti‐criteria
ACO‐based algorithm for ship’s safe trajectory
planning.
Figure2. Flowchart of the multi‐criteria ACO‐based
algorithmforship’strajectoryplanning.
4 SIMULATIONTESTS
The developed algorithm was implemented as a
computer program in MATLAB programming
language. The MATLAB environment was chosen
due to the possibility of using in‐built functions for
34
graphical presentation of results. The calculations
were run on a PC with Intel Core i5 2.27 GHz
processor and 32‐bit Windows 7 Professional
operatingsystem.
Tworepresentativetestcaseswerechosenforthe
presentationinthispaper:withtwoTSsandwithfour
TSs.Motionparametersoftheships
takingpartintest
casesarelistedinTables1and3.Figures3–5and7–
9 show graphical results – the trajectory of an OS
along with positions of TSs at consecutive stages of
their movement. Tables 2 and 4 present numerical
resultsoftestcases.
Table1.Testcase1motionparametersofallships.
_______________________________________________
Setting Course Speed Bearing Distance
Ship [°][kn] [°][nm]
_______________________________________________
0 019.0
─
─
1 709.0340 7.0
2 245 9.0206.0
_______________________________________________
Figure3.Graphicalpresentationoftestcase1.
Figure4.Graphicalpresentationoftestcase1–OSmoving
alongthetrajectory.
The simulation tests were performed taking into
account different optimization criteria and
constraints: a single criterion: path length and
multiple criteria: path length and path safety, path
smoothness(angles)andpathsafety,pathsmoothness
(angles)andCOLREGscomplianceofthepath(rules)
andalloftheabovementionedcriteria.Figures6
and
10 show the comparison of the OS trajectories
calculatedbythealgorithmfordifferentoptimization
criteria.
Figure5. Graphical presentation of test case 1 – OS at the
finalwaypoint.
Figure6.Graphicalpresentationoftestcase1–trajectories
calculatedfordifferentoptimizationcriteria.
Table2.Resultsoftestcase1.
_______________________________________________
optimization path path course path
length fitness alteration safety
criteria[nm][°]
_______________________________________________
length9.42 0.9759 11;25 safe
length+safety 9.42 0.9807 11;25 safe
angles+safety 10.23 1.0000 22;49 safe
angles+rules 9.57 0.9800 8;56;45 safe
allcriteria9.42 0.9852 11;25 safe
_______________________________________________
35
Table3.Testcase2motionparametersofallships.
_______________________________________________
Setting Course Speed Bearing Distance
Ship [°][kn] [°][nm]
_______________________________________________
0 020.0
─
─
1 9010.5 326 7.8
2 270 20.5 465.8
3 180 10.0 212.4
4 200 17.0 115.5
_______________________________________________
Figure7.Graphicalpresentationoftestcase2.
Figure8.Graphicalpresentationoftestcase2–OSmoving
alongthetrajectory.
Figure9. Graphical presentation of test case 2 – OS at the
finalwaypoint.
Figure10.Graphicalpresentationoftestcase2–trajectories
calculatedfordifferentoptimizationcriteria.
Table4.Resultsoftestcase2.
_______________________________________________
optimization path path course path
length fitness alteration safety
criteria[nm][°]
_______________________________________________
length9.31 0.9693 14;14;18 collision
length+safety 9.59 0.9549 14;14;45 safe
angles+safety 10.38 0.9600 16;61 safe
angles+rules 9.59 0.9600 14;14;45 safe
allcriteria9.59 0.9687 14;14;45 safe
_______________________________________________
5 DISCUSSIONANDCONCLUSIONS
In Tables 2 and 4 results of test cases are compared
withregardto:pathlength,fitnessfunctionvalueof
thesolution,coursealterationsneededtoexecutethe
determinedtrajectoryandsafetyofthesolution.
36
The multi‐criteria approach enables to take
different criteria into account: constraints of the
process and optimization objectives. Such approach
allowstoconsiderthesystemoperator’s(navigator’s)
preferences,whichcriteria he/shewould liketo take
intoaccountduringproblemsolving.
Differentcriteriatakenintoaccount,astheresults
ofsimulation
testsindicate,leadtodifferentsolutions.
The criterion that must be taken into account is the
pathsafety,whatisconfirmedbytheresultsinTable
4. Including only path length in the fitness function
can lead to obtainment of a shorter trajectory, but
withacollisionpoint.
Tosum
up,themulti‐criteriaACO‐basedapproach
forship’ssafepathplanning,presentedinthispaper,
enables to solve the considered problem by
calculation of a collision‐free trajectory of an OS.
The method enables taking into account all of the
importantassumptionsandconstraintsoftheprocess,
suchasthe
static(lands,shallows)anddynamic(TSs)
obstacles, the COLREGs, optimality of the solution
andnear‐realtimeofcalculations(underoneminute).
The above mentioned features of the proposed
approach allows its application in modern NGC
systems. The method presented here can also be
applied to other fields, where an
obstacle avoidance
problem of a moving object in a dynamic
environment occur, such as for example the task of
mobilerobotsnavigation.
REFERENCES
AhnJ.H.,RheeK.P.,YouY.J.2012:Astudyonthecollision
avoidance of a ship using neural networks and fuzzy
logic,AppliedOceanResearch,Vol.37,pp.162–173.
Escario, J. B., Jimenez, J. F. and Giron‐Sierra, J. M. 2012:
Optimisationofautonomousshipmanoeuvresapplying
ant colony optimisation
metaheuristic, Expert Systems
withApplications,Vol.39(11),pp.10120–10139.
Fossen T.I. 2011: Handbook of Marine Craft
HydrodynamicsandMotionControl,1sted.,JohnWiley
&Sons,Ltd.
Hornauer S., Hahn A. 2013: Towards Marine Collision
Avoidance Based on Automatic Route Exchange, 9th
IFACConferenceonControlApplicationsinMarine
Systems,
Vol.46(33),pp.103–107.
Lazarowska A. 2013: Application of Ant Colony
Optimization in Shipʹs Navigational Decision Support
System, In: A. Weintrit (ed.), Navigational Problems,
Marine Navigation and Safety of Sea Transportation, CRC
Press/Balkema,London,UK,pp.53–62.
LisowskiJ. 2016a: Analysisofmethodsofdeterminingthe
safe
shiptrajectory,TransNav,theInternationalJournalon
MarineNavigationandSafetyofSeaTransportation,Vol.10,
No.2,pp.223–228.
LisowskiJ.2016b:Thesensitivityofstatedifferentialgame
vessel traffic model, Polish Maritime Research, Vol. 23,
Issue2,pp.14–18.
Liu Y., Bucknall R. 2015: Path planning algorithm
for
unmanned surface vehicle formations in a practical
maritime environment, Ocean Engineering, Vol. 97, pp.
126–144.
Mohamed‐Seghir M. 2016: Computational Intelligence
MethodforShipTrajectoryPlanning,Proceedingsofthe
21st International Conference on Methods and Models
inAutomationandRobotics,pp.1–6.
Naeem, W., Irwin, G., Yang, A. 2012:
Colregs‐based
collision avoidance strategies for unmanned surface
vehicles,Mechatronics,Vol.22,pp.669–678.
PereraL.,J.CarvalhoJ.,GuedesSoaresC.2011:Fuzzylogic
baseddecisionmakingsystemforcollisionavoidanceof
ocean navigation under critical collision conditions,
Journalof MarineScienceandTechnology,Vol.16(1),pp.
84–99.
Simsir U., Amasyali M.F., Bal M., Celebi U.B., Ertugrul S.
2014:Decisionsupportsystemforcollisionavoidanceof
vessels,AppliedSoftComputing,Vol.25,pp.369–378.
Szłapczyńska J. 2015: Data Acquisition in a Manoeuver
Auto‐negotiation System, TransNav, the International
Journal on Marine Navigation and Safety of Sea
Transportation,Vol.9,No.3,pp.343–348.
SzłapczyńskiR.,SzłapczyńskaJ.2012:EvolutionarySetsof
Safe Ship Trajectories: Evaluation of Individuals,
TransNav, the International Journal on Marine Navigation
andSafetyofSeaTransportation,Vol.6,No.3,pp.345–353.
Śmierzchalski R., KuczkowskiŁ., Kolendo P.,
Jaworski B.
2013: Distributed Evolutionary Algorithm for Path
Planning in Navigation Situation, TransNav, the
InternationalJournalonMarineNavigationandSafetyofSea
Transportation,Vol.7,No.2,pp.293–300.
Tam, C., Bucknall, R. 2010: Path‐planning algorithm for
shipsinclose‐rangeencounters,JournalofMarineScience
andTechnology
,Vol.15,pp.395–407.
Tam, C., Bucknall, R. 2013: Cooperative path planning
algorithmformarinesurfacevessels,OceanEngineering,
Vol.57,pp.25–33.
Tsou, M., Hsueh, C. 2010: The study of ship collision
avoidance route planning by ant colony algorithm,
Journal of Marine Science and Technology‐TAIWAN, Vol.
18,
pp.746–756.
Tsou,M.,Kao,S.,Su,C.2010:Decisionsupportfromgenetic
algorithms for ship collision avoidance route planning
andalerts,JournalofNavigation,Vol.63,pp.167–182.
Xue, Y., Clelland, D., Lee, B., Han, D. 2011: Automatic
simulationofshipnavigation,OceanEngineering,Vol.38,
pp.2290–2305.
