301
1 INTRODUCTION
In earlier papers the author has presented the
Evolutionary Sets of Safe Ship Trajectories (ESoSST)
method (Szlapczynski 2011, Szlapczynski &
Szlapczynska 2011, Szlapczynski & Szlapczynska
2012). This method, instead of finding the optimal
own track forthe unchanged courses and speeds of
otherships,wassearchingforan
optimalset ofsafe
trajectories of all ships involved in an encounter,
combining evolutionary approach (Smierzchalski &
Michalewicz 2000) with goals typical for methods
basedongamestheory(Lisowski2007).Themethod
hasbeenfurtherdevelopedin(Szlapczynski2012)to
support Traffic Separation Schemes (TSS) (Anwar &
Khalique 2006) and
thus to be applied in Vessel
TrafficService(VTS)centers.
The method uses evolutionary algorithm which
works as follows. First, the initial population of
individuals (each being a potential solution to the
problem) is generated. It includes individuals
consisting of tracks being straight segments and
tracks generated randomly as well as
automatically
determined TSS‐compliant tracks. Each track is a
sequence of nodes containing geographical
coordinates. The initial population is a subject to
subsequentiterationsofevolutionaryalgorithm.Each
oftheseiterationsconsistsofthefollowingsteps:
Evolutionary operations: individuals (sets of
tracks)aremodifiedbymeansofrandommutation
operators as well as specialized operators
dedicated to the problem. The latter include
collision‐avoidanceoperatorsandTSS‐compliance
operators.
Reproduction: pairs of parents are selected from
alloftheindividualsandoffspringisproducedas
a result of their mating. The offspring inherits
some features from each parent. Three types of
crossover operators are used here: random track
exchange, one‐point track crossover and
intermediaterecombinationofnodes.
Evaluation: each of the individuals (including
parentsandtheoffspring) isassignedavalueofa
fitness function, which reflects the quality of the
solution represented by this individual. This
involvesdetectingandpenalizingallcollisionsas
Evolutionary Ship Track Planning within Traffic
Separation Schemes – Evaluation of Individuals
R.Szlapczynski
GdanskUniversityofTechnology,Poland
ABSTRACT:Thepaperpresentsanextendedversionoftheauthor’sEvolutionarySetsofSafeShipTrajectories
method. The method plans safe tracks of all ships involved in an encounter including speed reduction
maneuvers,ifnecessary,andtakingintoaccountRule10ofCOLREGS,whichspecifies
ships’behaviorwithin
TrafficSeparationSchemes governedbyIMO.Thepaperfocusesontheevaluationphaseoftheevolutionary
processandshowshowfitnessfunctionisdesignedtocomparevariouspossibletracksaswellastoassessthe
qualityofafinalsolution.Theimpactofthefitnessfunctiononthe
method’sresultsisillustratedbyexamples.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 7
Number 2
June 2013
DOI:10.12716/1001.07.02.18
302
well as penalizing violations of COLREGS Rules
13to17andTSSviolations(Rule10ofCOLREGS).
Succession: the next generation of individuals is
selected.Theselectionisbasedontheresultsofthe
evaluation.Theindividualsarechosenrandomly,
with the probability strictly depending on the
fitnessfunctionvalue.
Normally, the evolutionary algorithm ends when
oneofthefollowinghappens:
maximumacceptabletimeornumberofiterations
isreached,
thesatisfactorilyhighvalueoffitnessfunctionhas
beenreachedbyoneoftheindividuals,
theevolutionceasestobringanyimprovement.
Recently the method has been further extended,
themainnewfeaturebeingplanningspeedreduction
maneuvers within TSS, when necessary. The
extensionshaveresultedinchangesintheevaluation
phase of the evolutionary process. The fitness
function had to be redesigned to address
these new
issues.Thepapershows howthenewfitnessfunction
isabletocomparevariouspossibleshiptracksaswell
astoassessthequalityofafinalsolution.Thepaperis
organizedasfollows.First,theoptimisationproblem
ispresented(Section2).Thenitisexplainedwhythe
evaluation
phaseiscrucialtotheprocess(Section3).
This is followed by a discussion of the evaluation
problems, which have to be solved (Section 4). The
construction of the fitness function is shown next
(Section5)andsomeexampleresultsofapplyingthis
fitness function are provided (Section 6). Finally
a
summaryandconclusionsaregiven.
2 OPTIMIZATIONPROBLEM
Itisassumedthatweareoperatinginagoodvisibility
whenCOLREGS rules 13‐17 abideand within a TSS
governedbyIMO,whereRule10additionallyabides.
Thegoalistofinda setoftracks,whichminimizesthe
average
timelossorwaylossspentonmanoeuvring,
whilefulfillingthefollowingconditions:
none of the stationary constraints (including TSS
Inshore Traffic Zone [ITZ] and separation zones)
areviolated,
none of the ship domains (Coldwell 1983) are
violated,
thecoursealterationshouldnotbetoosmallortoo
large (minimum and maximum alteration values
areconfigurableandbydefaultaresetto15and60
degreesrespectively),
a ship only manoeuvres when she is obliged to
and, in case of head‐on and crossing encounters,
manoeuvres to starboard are favoured over
manoeuvrestoport,
COLREGS rules (Cockcroft & Lameijer 2011,
COLREGS 1972) arenotviolated (especially Rule
10andRules13to17),
speed alterations are not to be applied unless
necessary (collision cannot be avoided by a
configuredmaximumcoursealterationvalue),
ifspeedalterationhastobeapplied,thenumberof
speedalterationsshouldbeminimized(e.g.aship
can reduce her speed to avoid collision and get
back to a normal speed once the situation is safe
again).
Itisalsoassumedthatwearegiventhefollowing
data:
stationary constraints (landmasses and other
obstaclesandthelocationsandparameters ofeach
TSS’sparts),
positions,coursesandspeedsofallshipsinvolved,
simplifieddataonships’manoeuvrability.
Some of the above mentioned parameters are
provided either by ECDIS (landmasses and TSS
coordinates) or by Automatic Identification System
(AIS); motion parameters also by Automatic Radar
Plotting Aid (ARPA). At present, no information on
ship’s manoeuvring abilities is provided in AIS
messages, however these
data can be directly
obtained by a VTS operator from a ship’s navigator
and perhaps in future the content of AIS messages
willbeextendedtoincludemoreinformation.
3 WHYISEVALUATIONPHASECRUCIAL?
Ingeneralevaluationisnecessaryforconvergingtoa
solution and for telling how good this
solution is
accordingtothegivenset of criteria and constraints
(Michalewicz & Fogel 2004). The most important
purposesofevaluationareasfollows.
1 Comparing between various individuals and
making sure that a progress is made that way,
because otherwise the evolutionary process will
notconvergeatall.
2
Guarantying convergence to aʺgoodʺ optimal
solution. Otherwise we might face a situation
when we converge to a solution that is optimal
according to the given fitness function but turns
out to be unacceptable, because our fitness
function does not reflect our set of optimisation
criteriawellenough.
3 Decidingwhen
ourbestindividualiscloseenough
to the optimal solution, so that we can return a
solution to the user faster and save on
computationaltime.
4 Deciding when our solution (best set of ship
tracks)isacceptableandwhenitisnot.Knowing
that a solution is unacceptable we
might apply a
speedreduction(ifpossible)orinformthatfinding
the demanded solution is not possible for the
givendata(e.g.becauseofshipdomainsbeingtoo
large when compared with the given width of a
laneorwiththecurrentdistancesbetweenships).
While the first three tasks are
typical for
evolutionary processes, the fourth one is more
challenging. Solving it is absolutely necessary for
making a decision on speed reduction. If there are
ship domain violations in a solution, than we know
for certain that this solution is incorrect and speed
reductionshouldprobablybeapplied.Unfortunately,
usually
therewillbenoshipdomainviolationsinthe
solution, because the method will rather find a safe
track at the cost of large way loss. Therefore the
decisiononthespeedreductionmustbemadeonthe
basis of fitness function value alone, rather than on
the basis of the
accompanying data on registered
collisions.Inpractice,itistheunacceptablylowtotal
fitness function value that will always trigger an
attempt to improve the solution by reducing the
303
speed of the ship that has the lowest fitness value
assignedtoitstrack.
4 EVALUATIONPROBLEMSANDTHEIR
SOLUTIONS
Tomakesurethatfitnessfunctionsatisfiestheneeds
specified in the previous section, the following
problemsmustbeaddressed:
1 How to compare unacceptable individuals with
each other (differ
between various levels of
unacceptableindividualsanddecidewhichoneis
‘less unacceptable’ and which one is ‘more
unacceptable’)?
2 Howtocomparetracksthatusetrafficlaneswith
ones,whichavoidlanescompletely?
3 How to compare tracks which involve speed
reductionwiththeonesthatdonot?
4
How to decide, that we are close enough the
optimum? If we want a normalized fitness
function than value ‘1’ should be assigned to an
idealsolution,butwedonotknowwhattheideal
solutionis,otherwisewewouldnʹthavetosearch
forit.
5 How to assign fitness
function values in such a
waythatva luesbelowcertainthresholdwouldbe
unacceptableforcertain?
The answer to the first problem has been
introducing a number of diagnostic factors: static
constraint factor, collision avoidance factor,
COLREGS‐compliance factor and TSS‐compliance
factor, all of which reflect various conditions that
have to be met. The first three factors have already
been described in the author’s earlier papers. In
general,eachofthesefourfactorshasbeenassigneda
differentdegreeofpenaltyforconditionviolations:
static constraint violations (penalized most
severely because they have to be avoided at all
cost),
collisionswithotherships(penalizedslightlyless
severely because they might sometimes be
eliminated as a side effect of avoiding static
constraintviolations),
violationsof Rules13‐17ofCOLREGS (penalized
moderately, because they are secondary when
comparedtocollisions),
violations of Rule 10 of COLREGS (penalized
dependingonaparticularclassofviolation–e.g.
moving against the traffic direction is penalized
nearlyasseverelyasviolatingstaticconstraints).
The second of the above listed issues has been
solvedbyintroducingalaneencouragementfactor(a
component of the
TSS‐compliance factor), which is
usedforencouragingthemethodtoplantrajectories,
whichusetrafficlanes.Foreachtrackapercentageof
thetrack’slengththattransitsthroughatrafficlaneis
determined and used for estimation of the track’s
quality.
As for the third issue, the tracks, which utilize
speed reduction and those that do not, are not
compared with each other at all by the ESoSST
method.Themethodtriestofindsafetrackswithout
speedreductionfirstandonlyifitfailstodoso, speed
reductionisapplied.Insuchcasesthereisnopenalty
for
speedreduction,becausespeedreductionisthen
treatedasanecessity.
The fourth issue is strictly connected to the
normalizationoffitnessfunction.Inearlierversionsof
theESoSSTmethodtrackfitnesswasrelativelyeasyto
normalise. A track economy factor and various
compliancefactorswereallfromthe<0,1>range
and
the track fitness function was simply a product of
them all. However, once the TSS‐compliance factor
has been introduced, the normalization is more
complex,becauseofthelaneencouragementfactor.If
wepenalizetra j ectoriesfornotusingtrafficlanes,we
might end up with some safe tracks being
assigned
verylowtrackfitnessvalues.Ontheotherhand,ifwe
reward using traffic lanes, some of the tracks may
have their fitness values larger than 1, or close to 1
despite some obvious faults. Therefore a concept of
referencetrackfitnesshasbeenintroduced. Although
we do not know
the ideal track, we can try to
determine the upper boundary of its fitness. This
upperboundarymustbe carefully placed: placing it
too high results in underestimating future solution,
placing it too low – in overestimating the solution.
Therefore the upper boundary – a reference track
fitnessvalue–
isdetermined as follows.Anoptimal
trackofaparticularshipissoughtfor,totallyignoring
allothershipsandcollisionavoidancerules. Due to
ignoring other ships, we avoid way loss that is
usuallyaneffectofcollisionavoidanceandweobtain
theshortesttrack,whichmeetsstaticconstraintsand
isTSS‐relatedconstraints.Ifwedivideafitnessvalue
ofanytrackbythistrack’sreferencefitnessvalue,we
will get the desired normalized fitness value. This
normalized fitness value approaches 1 as the track
getsclosertothereferencetrack(theonewithnoway
lossform collision
avoidance).Detailedformulas for
normalizedfitness function are providedinthe next
section.
Thelastofthelistedproblems–decidingwhena
track is unacceptable – is also connected to
normalization and pa rtly solved by the reference
fitnessvalue. Whenreferencefitness valueisusedfor
normalizing a track’s fitness,
we know that the
differencebetweencurrentfitnessvalueandvalue‘1’
can only be blamed on way loss due to collision
avoidance. Therefore it is merely a question of
settings(personalchoice)howmuchwaylosscanbe
accepted before speed reduction is applied. In the
method is has
been assumed, that by default, a 5%
way loss (fitness value of 0.95) can be accepted and
anylargerwayloss(lowerfitnessvalues)willtrigger
anattempttoimprovethisbyreducingspeed.Apart
from that, any detected violations of COLREGS
(including Rule 10) will automatically trigger speed
reduction,because
thepresenceofsuchviolationsin
the final set of tracks means that the method has
failedtoproduceasafesolution.
The role of evaluation, reference tracks and
reference fitness values in the evaluation process is
summarised by Fig. 1, which depicts the method’s
mainalgorithm.
304
Figure1. The ESoSST method’s main algorithm including
theuseofreferencetracksandreferencefitnessvalues.
5 FITNESSFUNCTION
Thefitnessfunctionused in the method is a sum of
fitnessvaluesofalltrajectoriesinaset:
n
i
i
fitnesstrajectoryfitness
1
_
, (1)
where:
i
i
i
fitnesstrackreference
fitnesstrackbasic
fitnesstrack
__
__
_
. (2)
Basic track fitness is the track fitness value before
normalization:
iiii
ii
tcfccfcafscf
factoreconomytrackfitnesstrackbasic
*
____
. (3)
scf
i (static constraint factor), cafi (collision avoidance
factor) and ccf
i (COLREGS‐compliance factor) have
alreadybeendescribedintheauthor’searlierpapers.
Track_econ_factor
i is computed in a different way for
shipswhichhavetoreducetheirspeedthanforthose,
whichdonot.Forchangingpropeller’s settings,that
isforships,whichreducetheirspeed:
i
ii
i
lengthtrack
losswaylengthtrack
factorecontrack
_
__
__
(4)
Forfixedpropeller’ssettings, thatisfor shipswhich
donotreducetheirspeed:
i
ii
i
timetrack
losstimetimetrack
factorecontrack
_
__
__
(5)
where:
i=theindexofthecurrentship,
track_time
i=thetotaltimebythei‐thshipbetweenthe
endpoints of its track [hours]; time_loss
i = the total
time loss of the i‐th ship computed as a difference
betweenthetracktimeandthetimespentoncovering
a straight segment joining the track’s endpoints.
time_loss
i includes temporary fall in speed (for fixed
propeller’s settings) due to course alteration
manoeuvres.track_length
i=thetotallengthofthei‐th
ship’strack[nauticalmiles];way_loss
i=thedifference
between the length of the i‐th ship’s track and the
lengthofastraightsegmentjoiningtheendpointsof
thei‐thship’strack[nauticalmiles].
In case of speed reduction, the track economy
factor would be much lower for time‐oriented track
economy factor (5)
and would lead to unacceptably
low track fitness va lue and total fitness function
value. Therefore the length‐oriented track economy
factor(4)isusedforships,whichreducetheirspeed.
tcf
ifactor fromformula(3)is responsible for TSS‐
complianceandiscomputedasgivenby(6).
11
*__1
1
leflpf
penaltyviolationTSStcf
i
m
k
ki
, (6)
where m = the number of TSS rules violations
registered for the current ship; k = the index of a
registered violation, TSS_violation_penalty
k = the
penalty for the k‐th of the registered TSS rules
violations;lef=laneencouragementfactorappliedto
encourage using traffic lanes, usually from the <1.1,
1.5> range, set to 1.2 by default; lpf
i = track’s lane
percentage factor (a percentage of the track’s length
thattransitsthroughatrafficlane).
reference_track_fitness
i from equation (2) is the
fitnessvalueofapredeterminedtrackofthei‐thship,
foundwithouttakingintoaccountpotentialcollisions
withotherships.
305
6 EXAMPLERESULTS
In this section some examples showing the
importance of a well‐designed fitness function are
presented. For all three scenarios it will be shown
howdifferentfitnessvaluesmightbeassignedtothe
samesolutionbydifferentfitnessfunctionsandwhat
the consequences of right or wrong
evaluation are.
The ship domains for all scenarios have been set to
valueswhichenabletwoshipsonlytotransitthrough
alaneparalleltoeachother.Ithasalsobeenassumed
thatashipmayreduceitsoriginalspeedby0.3or0.5
oftheinitialvalue.
6.1 Scenario
1
In this scenario it will be exemplified, how fitness
function leads to convergence to the right or wrong
solution.Theresultsofusingfitnessfunctionwithout
lane encouragement factor and with lane
encouragement factor are shown in Figs. 2 and 3
respectively.Firstafitnessfunctionwithasimplified
TSS
‐compliance factor is used, where TSS violations
arepenalized,butusingtrafficlanesisnotrewarded
– the formula, which is used for TSS‐compliance
factor,isgivenby(7):
m
k
ki
penaltyviolationTSStcf
1
__1
. (7)
Asaresult,atracknotusingalaneischosendueto
smallerwayloss.ThisisshowninFig.2.Incontrast
tothis,afullformulaforTSS‐compliancefactor(6)is
usedlaterandtheresultispresentedinFig.3.Herea
tracktransiting
throughalaneischosen,asrequired
byCOLREGS.
Figure2. A ship track by a fitness function without lane
encouragementfactor.
Figure3. A ship track by a fitness function using lane
encouragementfactor.
6.2 Scenario2
Inthisscenarioitwillbeshown,howfitness function
mightleadtomisinterpretationofthefinalsolution.
Hereanincomplete(notnormalized)fitnessfunction
results in accepting a solution as a near‐optimal,
whereas in fact it is far from optimal. The initial
positions,coursesandspeeds
ofall shipsareshown
inFig.4.First,afitnessfunction,whichdoesnotuse
reference track fitness is used, with a lane
encouragementfactorsetto1.5.Itisgivenby(8):
iiii
ii
tcfccfcafscf
factorecontrackfitnesstrack
*
___
(8)
The solution obtained for such simplified, non‐
normalized fitness function is shown in Fig. 5. All
threeshipstransitthroughatrafficlane(althoughthe
overtakingshipexitsthelaneandentersitagain)and
therefore,duetohighlaneencouragementfactor,the
solution is highly rated and is
accepted as near‐
optimal,whichiswrong.
Figure4.InitialparametersofshipsfromScenario2, speeds
lefttoright:15,12and12knots.
306
Figure5. A solution accepted by the method with a
simplified,non‐normalizedfitnessfunction
Incontrasttothis,whenevaluatedaccordingto(2)
and(3)thefitnessvalueofthesolutionfromFig.5is
much lower, because the reference fitness value for
thistrackishigh(thereferencetrackisshowninFig.
6).ThereforethesolutionfromFig.5isdismissedand
the method applies a speed reduction for this ship.
Theshipreducesitsspeedby0.3oftheoriginalvalue
(from15to10.5knots).Thefinalsolutionisshown
inFig.7.Thetwoshipshavingthesamespeedtransit
throughalaneparalleltoeachother,whilethethird
ship reduces its speed and follows them keeping a
safedistance.
Figure6.AreferencetrackofthefastestshipfromScenario
2(farleftinFigure5)
Figure7. A solution returned by the method with
normalized fitness function – the fastest ship reduces its
speed
6.3 Scenario3
In this scenario it will be shown, how incomplete
fitness function results in another kind of
misinterpretation of the final solution. Here a
simplified,non‐normalizedfitnessfunctionleadstoa
situation opposite to that from Scenario 2 – to
dismissing an acceptable solution and to undesired
and
unsuccessfulattemptstoimproveitbyapplying
speed reduction manoeuvres. The initial positions,
courses and speeds of all ships are shown in Fig. 8.
First,asimplifiedfitnessfunction,whichdoesnotuse
referencetrackfitnessisused,similarlytoScenario2.
Asaresult,thesolutionshowninFig.
9isunderrated
anddismissedasunacceptable.
Figure8.InitialparametersofshipsfromScenario5, speeds
lefttoright:15and18knots
307
Figure9. A solution dismissed by the method with a
simplified, non‐normalized fitness function due to
seeminglytoolargewayloss
Because of the lack of COLREGS violation, the
methodassumesthatthesolution’slowfitnessvalue
is a consequence of way loss due to collision
avoidance and tries to improve the solution by
applying speed reduction manoeuvres. These
manoeuvreshoweverobviouslycannotdecreaseway
loss and the method eventually returns a
similar
solution(showninFig.10)accompaniedbyamessage
that no acceptable solution could be found for the
givenparameters.Incontrasttothis,whenevaluated
accordingtoformulas(2)and(3)thefitnessvalueof
the solution from Fig. 9 is properly rated, based on
the reference track
(shown in Fig.11). Therefore the
solutionfromFigure9isacceptedasacorrectone,as
itshould.
Figure10. A solution dismissed by the method with a
simplified, non‐normalized fitness function after a failed
attempttodecreasewaylossbyspeedreduction
Figure11.Areferencetrackofthefasterofthetwoshipsin
Scenario3.
7 SUMMARYANDCONCLUSIONS
Inthepaperithas beendiscussedhowtheevaluation
phaseaffectstheresultsreturnedbytheEvolutionary
SetsofSafeShipTrajectoriesmethod.Inparticular,it
wasshownthatthefitnessfunctioniscrucial notonly
fortheconvergencetotheacceptablesolutionbutalso
for
the assessment of this solution’s quality and
telling when it actually is acceptable. The imprecise
assessmentofthealreadyfoundshiptrackcanleadto
communicating a failure or to planning a speed
reductionmaneuverwhenitisneithernecessarynor
desired. As has been shown by the examples, the
fitness function presented in the paper successfully
dealswiththeabovementionedissuesandresultsin
planningshiptrackswhich aresafe, economicaland
TSS‐compliant.
As has already been mentioned in Section 2, the
currentversionofthemethodassumesgoodvisibility
anddoesnotsupportRule19ofCOLREGS.
Also,as
for now, the method does not take into account the
bathymetry data and ship’s draught. Additionally,
due to the fact, that no information on ships
maneuverability is provided by AIS, the method
applies a largely simplified ship dynamics model.
ThereforefurtherresearchontheESoSSTmethodand
further
developmentofthemethodisplanned.Itwill
be focused on handling all the above mentioned
problems. Future tasks also include working on the
scalability of the presented approach – dealing with
largernumbersofshipsandlargerareas.
REFERENCES
AnwarN. & Khalique A. 2006. Passage Planning Principles.
WitherbySeamanshipInternational,Livingston,United
Kingdom
308
CockcroftA.N.&Lameijer,J.N.F.2011.AGuidetoCollision
AvoidanceRules.Butterworth‐Heinemann.
ColdwellT.G.1983.MarineTrafficBehaviourinRestricted
Waters.TheJournalofNavigation.36,431‐444.
COLREGS. 1972. [with amendments adopted from
December 2009]). Convention on the International
Regulations for Preventing Collisions at Sea. International
MaritimeOrganization,London.
Lisowski J. 2007. The Dynamic Game Models of Safe
Navigation,InternationalJournalonMarineNavigationand
SafetyofSeaTransportation,Vol.1,no.1.,11‐18
MichalewiczZ.&Fogel,D.B.2004.HowTo SolveIt:Modern
Heuristics.Springer‐Verlag.
SmierzchalskiR.&Michalewicz, Z.2000.Modeling
ofa Ship
Trajectory in Collision Situations at Sea by Evolutionary
Algorithm,IEEETransactionsonEvolutionaryComputation
No.3Vol.4,pp.227‐241.
Szlapczynski R. 2011. Evolutionary Sets of Safe Ship
Trajectories: A New Approach to Collision Avoidance.
TheJournalofNavigation.64,169‐181.
Szlapczynski R & Szlapczynska
J. 2011, On Evolutionary
Computing in Multi‐Ship Trajectory Planning. Applied
Intelligence,vol.37,iss. 2,155‐174,SpringerNetherlands,
http://www.springerlink.com/content/j40qp07031634568
(freeaccess)
Szlapczynski R. 2012. Evolutionary Sets of Safe Ship
Trajectories within Traffic Separation Schemes. The
JournalofNavigation.vol.66,iss.1.,pp.65‐81.
SzlapczynskiR&
SzlapczynskaJ.2012.EvolutionarySetsof
Safe Ship Trajectories: Evaluation of Individuals.
InternationalJournalofMarineNavigationandSafetyofSea
TransportationVol.6,No.3,2012,s.345‐353.
