559
1 INTRODUCTION
Due to the fact that about 90% of global trade is
transported by ships (Allianz Global Corporate &
SpecialtySE2018),safetyofnavigationisavitalissue
in maritime transport. Recent trends in ship
navigation include the development of unmanned
shipstechnology.Thelatestdevelopmentsinthis
area
include the concept of a full‐electric 120 TEU
autonomousshipcalledYaraBirkeland,designedby
Kongsberg Maritime AS (Kongsberg Maritime AS
2018) and construction of a testing site in china for
unmanned ships, called the Wanshan Marine Test
Field, by China Classification Society, Zhuhai
Municipal Government, Wuhan University
of
Technology & Zhuhai Yunzhou Smart Co. (China
ClassificationSocietyetal.2018).
Unmanned ships can be remotely controlled or
autonomous ships. For such vessel solutions
providing possibility of autonomous navigation are
needed. Autonomous navigation system has to
determine a safe trajectory for a ship in a collision
situationatsea
andafterthatcontroltheshipʹsmotion
inordertomovealongthedeterminedtrajectory.
Increase of computing power enables the
development of algorithms for determination of a
shipʹs safe trajectory in near real time. Due to that
many new algorithms for shipʹs safe trajectory
planning have
been developed recently. The latest
shipʹstrajectoryplanning approachesproposedinthe
literatureinclude:differentialgames(Lisowski2016),
fuzzylogicandgametheory(Lisowski&Mohamed‐
Seghir 2019), the fast marching method (Liu et al.
2017), a Collision Threat Parameters Area (CTPA)
technique (Szlapczynski & Szlapczynska 2017), a
Voronoi diagram
(Candeloro et al 2017)and Energy
Efficient A* (EEA*) (Lee et al 2015). A recent
comparison of different shipʹs trajectory planning
methodsinpresentedinFişkinetal.(2018).
Modernadvancedcontrolmethods,suchase.g.a
hybrid switching controller (Tomera 2017), Linear
Matrix Inequalities (LMI) (Rybczak 2018)
or an
Verification of Ship's Trajectory Planning Algorithms
Using Real Navigational Data
A.Lazarowska
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT: The paper presents results of shipʹs safe trajectory planning algorithms verification. Real
navigationaldata registeredfrom a radar with an Automatic RadarPlotting Aid on board theresearch and
trainingshipHoryzontIIwereusedasinputdatatothealgorithms.Thealgorithmsverified
inthepresented
research include the Ant Colony Optimization algorithm (ACO), the Trajectory Base Algorithm (TBA), the
VisibilityGraph‐searchAlgorithm(VGA)anttheDiscreteArtificialPotentialFieldalgorithm(DAPF).Details
concerning data registration and exemplary results obtained with the use or real navigational data are
introducedandsummarizedin
thepaper.Presentedresultsprovetheapplicabilityofproposedalgorithmsfor
solvingtheshipʹssafetrajectoryplanningproblem.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 13
Number 3
September 2019
DOI:10.12716/1001.13.03.10
560
adaptive backstepping method (Witkowska &
Śmierzchalski 2018), are then applied in order to
execute the ship movement along the desired
trajectory.
Analysisoftheseapproachesenablestostatethat
most of these methods were verified by simulation
tests, sometimes with only simple navigational
scenarios.Thereforetheaimofa
researchpresentedin
this paper was to verify developed different shipʹs
trajectory planning using real navigational data
registeredonboardaship.
2 DATAREGISTRATION
In order to obtain real navigational situations, a
system for registration of data from a ship was
developed and installed on board Horyzont II a
Research/Training
ship owned by Gdynia Maritime
University, shown in Figure 1. The data were
registered during the XLI Horyzont II voyage to
Spitsbergen in 2018. A system for data registration
installedonboardHoryzontIIisshowninFigure2.
Figure1.TheResearch/TrainingshipHoryzontII.
Figure2.Asystemfornavigationaldataregistration.
Figure3. OSD and TTM sentences of an exemplary
navigationalsituationregisteredonboardHoryzontII.
Figure4.HoryzontIIpositionregistered byMarineTraffic
onthe12
th
ofSeptember2018.
Inputdatatothealgorithmswereregisteredform
the radar with ARPA with the use of the NMEA
standard, a serial asynchronous data transmission
protocol used for communication between marine
electronic equipment and external devices. The
sentencesmarkedasOSD(OwnShipData)andTTM
(Tracked Target Message) are needed for
shipʹs
trajectorycalculation.OSDandTTMsentences ofan
exemplarynavigationalsituationregisteredonboard
Horyzont II are shown in Figure 3. Navigational
situationshowingHoryzontIIpositionispresentedin
Figure4andHoryzontIItrackisshowninFigure5,
561
both registered by Marine Traffic on the 12
th
of
September2018.
Figure5.HoryzontIItrackregisteredbyMarineTrafficon
the12thofSeptember2018.
3 SHIPʹSTRAJECTORYPLANNING
ALGORITHMS
Navigational data registered on board a ship were
usedtoverifytheperformanceonfourdifferentshipʹs
trajectory planning algorithms: the Ant Colony
Optimization algorithm (ACO), the Trajectory Base
Algorithm (TBA), the Visibility Graph‐search
Algorithm(VGA)anttheDiscreteArtificialPotential
Field algorithm
(DAPF). These algorithm represent
both stochastic and deterministic optimization
methods.Belowashortdescriptionofthealgorithms
ispresented.
3.1 TheAntColonyOptimizationalgorithm(ACO)
This algorithm belongs to the heuristic methods, to
the subgroup called the Swarm Intelligence (SI)
methods.TheSImethodsareapproachesinspiredby
the
collectivebehaviourofcoloniesofinsectsorother
animalcommunities.TheSIalgorithmutilizefeatures
ofinsectcoloniessuchasself‐organization,flexibility
and robustness. The operation principle of ACO is
inspired by the ant colony foraging behaviour.
Foraging ants deposit a chemical substance on the
ground,calledapheromone.Other
antscansmellthis
substance and they choose a path, where the
pheromone concentration is higher. By using this
trail‐lyingandtrail‐followingbehaviour,antsareable
tofindtheshortestpathbetweenthefoodsourceand
theirnest.Thisbeha viourisappliedto artificialants
used in the
ACO algorithm to solve different
optimizationproblems.
In the ACO algorithm for shipʹs safe trajectory
planningartificialantsmoveonthegraphcomposed
ofadmissibleownshippositionsinordertofindthe
shortest trajectory between the current own ship
position and the defined final waypoint. After data
initialization, which
includes the definition of
parameterssuchasalphaandbetacoefficients,initial
pheromone trail amount at each of the possible
waypoints, pheromone evaporation coefficient,
number of ants, maximum number of steps to be
made byan ant andnumber of iterations, every ant
constructsitspathfromthecurrentOS
positiontothe
final waypoint using the action choice rule given as
Equation 1, where
j
wp
t
is the pheromone trail
amount deposited on the neighbouring vertex,
ij
wp
istheheuristicinformationcalledvisibility,whichis
expressed as an inverse of the distance between the
currentvertex(i)andtheneighbouringvertex(j).
jij
ij
lil
ant
i
wp wp
ant
wp
wp wp
lwp
tt
Pt
tt
(1)
After that the pheromone trail update is applied,
composedofpheromoneevaporationandpheromone
depositaccordingtoEquation2.Afterachievementof
themaximumnumberof iterationsorthemaximum
runtime,theshortesttrajectoryisreturnedasafinal
solution.
1
11
jjj
m
ant
wp wp wp
ant
ttt
(2)
3.2 TheTrajectoryBaseAlgorithm(TBA)
Thisalgorithmbelongs tothedeterministicgroupof
methods. In this method a database storing
trajectories, constituting candidate solutions is
searched through in order to find the shortest
trajectorysolvingaconsiderednavigationalsituation.
Trajectories in the database are stored according to
increasing
valueof their fitnessfunction Equation3,
definedasthelengthofatrajectory.
1
22
11
1
min
M
ii i i
i
Ixxyy
(3)
COLREGscomplianceofthesolution,similarlyas
in ACO approach, of the solution is assured by a
proper shape and size of the target ship domain.
Trajectories are evaluated in the same order as they
aresortedinthedatabase,thereforewhenatrajectory
not exceeding the constraints is
found, the selection
process in stopped, and found trajectory constitutes
the shortest trajectory solving the considered
situation.
3.3 TheVisibilityGraph ‐searchAlgorithm(VGA)
Thisalgorithmbelongstothegraphtheorymethods.
thenavigationalenvironmentisrepresentedwiththe
use of a visibility graph composed of vertices
includingthestartand
finalownshipwaypointsand
the vertices belonging to the areas of obstacles and
edges connecting these vertices, for which the
connection does not intersect the areas occupied by
obstacles.
The visibility graph‐search algorithm used for
findingtheshortestcollision‐freeownshiptrajectory
applies a version of A*
algorithm. Applied fitness
function (Equation 4) is composed of two
components:thefirstoneg(v), definedasthe length
562
of the currently considered path from the start
waypointto the currently consideredvertex and the
second component h(v), defined as the Euclidean
distancefromthecurrentvertextothefinalwaypoint.
f
vgvhv (4)
3.4 TheDiscreteArtificialPotentialFieldalgorithm
(DAPF)
This method utilizes the concept of an Artificial
Potential Field and applied it to a discrete two‐
dimensionalconfigurationspace,constitutingagrid‐
basedmapcomposedofanumberofcells,including
freecells,cellsoccupiedbyobstacles,astartcell
anda
goalcell.everycellisdescribedbythreeparameters:
thepositionofitscentre(xandycoordinates)andits
potential.Thegoalcellhasapotentialequaltozero,
cellsoccupiedby obstacleshavea potential equalto
infinity, free cells are assigned with increasing
potentialsfromgoal
celltostartcell,cellsontheright
side from the line segment connecting the start and
goalcellhavelowerpotentialsthantheseontheleft
sideinordertoenforcefulfilmentofrules14and15
ofCOLREGs.Thesearchalgorithmcalculatesashipʹs
safe trajectory by
choosing at every step from the
neighbouringcellsthenextcellwiththelowestvalue
of its potential. After the cell has been chosen, it is
assignedapotentialequaltoinfinityinordertoavoid
generation of loops in the trajectory constituting the
solution.
Figure6.Targetshiphexagondomain.
4 RESULTS
The shipʹs safe trajectory planning algorithms
conciselydescribedaboveweretestedwiththeuseof
navigational data registered on board the ship
Horyzont II. Two exemplary situations were chosen
for presentation in this paper, encounters with four
and fourteen target ships. Shipʹs trajectory planning
algorithms were implemented
in MATLAB
programming language. Target ships were modeled
withtheuseofhexagondomainsshowninFigure6.
Thedimensionsofthetargetshipdomainusedinthe
algorithmsare:a=1.05NM,b=0.65NM,c=0.4NM,
d = 0.4 NM and e = 0.65
NM. The following
parametersof ACO algorithmwereused:τ
0= 1,ρ=
0.1,α=1,β=2,iterations=20andant_number=10.
4.1 Testcase1anencounterwithfourtargetships
Table1.Inputdatafortestcase1.
_______________________________________________
ShipΨVDN
[º][kn] [NM] [º]
_______________________________________________
0132.2 10.7‐‐
1137.5 3.48 1.39 346.1
2144.3 5.02 1.61 109.7
3318 19.04 12.55 123.5
4307.8 17.02 5.02 170.9
_______________________________________________
Test case 1 is an encounter situation between an
ownshipandfourtargetships.Inputdatadescribing
thisnavigationalsituationaregiveninTable1,while
numerical results for all of the algorithms including
the length of the safe trajectory in nautical miles,
calculatedcourseofanownshipat
consecutivestages
of its movement along the determined trajectory in
degreesandtheruntimeofthealgorithminseconds
arelistedinTable2.Graphicalresultsobtainedforthe
VGAalgorithm,forwhichtheshortestsafeownship
trajectorywascalculated,areshowninFigure7along
with the
instantaneous positions of all of the target
ships. Figure 8 presents a comparison of trajectories
obtainedbydifferentalgorithms.Allofthealgorithms
found a solution for the considered encounter
situation. As it can be seen the trajectories do not
differsignificantly.TBAachievedthelowestruntime,
while VGA obtained
the shortest trajectory in a
reasonableamountoftime.
Table2.Resultsoftestcase1.
_______________________________________________
Method distance[NM]course[º] runtime[s]
_______________________________________________
ACO9.22144,118 13.99
TBA9.22146,121 0.27
VGA9.08141,126 1.41
DAPF 9.22145,120 0.99
_______________________________________________
Figure7.SafetrajectorycalculatedbyVGAfortestcase1.
563
Figure8. Comparison of safe trajectories calculated by
differentalgorithmsfortestcase1.
4.2 Testcase2anencounterwithfourteentargetships
Testcase2isanencountersituationbetweenanown
ship and fourteen target ships. Input data defining
this navigational situation are shown in Table 3.
Numerical results are listed in Table 4. Graphical
resultsobtainedfortheVGAalgorithmare
presented
inFigure9.InFigure10acomparisonoftrajectories
obtainedbydifferentalgorithmsisshown.Asafeown
shiptrajectoryforthistestcasehasalsobeenfoundby
all of the algorithms. for this situation the results
obtained by different algorithm also do not vary
considerably.For
thistestcaseTBAalsoreachedthe
lowest run time and VGA achieved the shortest
trajectory.
Table3.Inputdatafortestcase2.
_______________________________________________
ShipΨVDN
[º][kn] [NM] [º]
_______________________________________________
0160.9 11.6‐‐
1273.6 7.62 1.67 338.1
2315.2 7.87 5.1257.8
3340.9 22.43 2.73 16.4
4341.2 19.44 2.273.1
5337.7 11.09 1.84 12.1
6340.8 10.71 4.43 16.3
7340.1 16.69 8.44 169.1
8350.2 17.47 3.74 236.3
9353.1 17.53 2.55 246.1
10134.2 5.37
3.93 182.4
11352.1 17.22 5.05 210.1
12354.8 17.25 5.33 212.4
13353.5 17.16 6.92 205.1
14 353.4 17.34 9.08 200.8
_______________________________________________
Figure9.SafetrajectorycalculatedbyVGAfortestcase2.
Table4.Resultsoftestcase2.
_______________________________________________
Method distance[NM]course[º] runtime[s]
_______________________________________________
ACO 9.25170,142 20.91
TBA 9.22172,147 0.32
VGA 9.13167,145 8.36
DAPF 9.37168,127 0.71
_______________________________________________
Figure10. Comparison of safe trajectories calculated by
differentalgorithmsfortestcase2.
5 DISCUSSIONANDCONCLUSIONS
Thepaperpresentsresultsofresearchonverification
of shipʹs safe trajectory planning algorithms based
upon real navigational data registered on board a
ship.Realnavigationaldatausedasinputdataforthe
algorithms enable for an in depth evaluation of the
algorithms performance, before their
application in
safeshipcontrolsystemonboardaship.
564
All of four tested algorithms were able to find a
solution to the considered encounter situations.
Solutions obtained by different algorithms varied
slightly in terms of the length of the determined
trajectoryandwithregardtotheirruntime.Thebest
results were achieved with the use of the VGA
algorithm, the TBA algorithm was characterized by
insignificantly longer trajectories but achieved in
lowerruntime.
Further research will include tests of the
algorithms applied in safe ship control system
onboardaship.Itwouldalsobevaluabletoinclude
datafromtheAutomaticIdentificationSystem,what
willallow for
taking intoaccount the dimensions of
the vessels in the process of shipʹs safe trajectory
calculation.
REFERENCES
Allianz Global Corporate & Specialty SE. 2018. Safety and
shipping review. https://www.agcs.allianz.com/insights/
white‐papers‐and‐ case‐studies/safety‐and‐shipping‐
review‐2018/Accessed22January2019.
Candeloro, M., Lekkas A.M., Sorensen A.J. 2017. A
voronoidiagram‐based dynamic path‐planning system
for underactuated marine vessels. Control Engineering
Practice61:41‐54.
China
Classification Society, Zhuhai Municipal
Government, Wuhan University of Technology &
Zhuhai Yunzhou Smart Co. 2018. Wanshan marine test
field. https://www.marineinsight.com/shipping‐
%20news/construction‐worlds‐largest‐unmanned‐
marinetesting‐site‐starts/Accessed22January2019.
Fişkin, R., Kişi, H. & Nasibov, E. 2018. A Research on
Techniques, Models and Methods Proposed for
Ship
Collision Avoidance Path Planning Problem.
International Journal Maritime Engineering 160 (A2): 187‐
206.
Kongsberg Maritime AS. 2018. Autonomous ship project.
https://www.km.kongsberg.comAccessed22January
2019.
Lee, T., Kim, H., Chung, H., Bang, Y. & Myung, H. 2015.
Energy efficient path planning for a marine surface
vehicle considering heading angle.
Ocean Engineering
107:118131.
Lisowski,J. 2016.Analysisof Methods of Determining the
Safe Ship Trajectory. TransNav, the International Journal
onMarineNavigationandSafetyofSeaTransportation,Vol.
10,No.2:223‐228.
Lisowski, J. & Mohamed‐Seghir, M. 2019. Comparison of
Computational Intelligence Methods Based on Fuzzy
Sets
and Game Theory in the Synthesis of Safe Ship
Control Based on Information from a Radar ARPA
System.RemoteSensing11(1),82.
Liu, Y., Bucknall, R. & Zhang, X. 2017. The fast marching
method based intelligent navigation of an unmanned
surfacevehicle.OceanEngineering142:363–376.
Rybczak, M. 2018. Improvement
of control precision for
ship movement using a multidimensional controller.
Automatika59(1):63–70.
Szlapczynski, R. & Szlapczynska, J. 2017. A method of
determiningandvisualizingsafemotionparametersofa
ship navigating in restricted waters. Ocean Engineering
129:363–373.
Tomera,M. 2017.Hybridswitchingcontrollerdesignforthe
maneuveringand
transitofatrainingship.International
JournalofAppliedMathematicsandComputerScience27(1):
63–77.
Witkowska,A.&Smierzchalski,R.2018.Adaptivedynamic
control allocation for dynamic positioning of marine
vessel based on backstepping method and sequential
quadraticprogramming.OceanEngineering163:570–582.
