75
1 INTRODUCTION
For safety reasons, movement of ships on the sea
mustbemonitored.Whatismore,therealtimevessel
tracking isnotenough.Thosedata shouldbestored
and available for future use by authorized
institutions. Unfortunately, the number of vessels
seennearthecoastishuge.Furthermore,thesources
fromwhichtheinformat
ionaboutvesselstrajectories
can be possessed are also few – AIS, radars, mobile
observatory points – and each of them gives
thousandsofrecordsdescribingrouteofeachtracked
object. However, one must ask if all those data are
reallyimportantandprovidesignificantupdateinthe
knowledgeofposition,speedorstateofvessels.Most
ofshipswhicharemovingonBalt
icSeaarefollowing
knownrouts.Inaddition,becauseoftheirdimensions
their dynamic is limited. They cannot change their
speed and direction very quickly. That makes a
possibility to predict some parts of the routs on the
ba
sis of current parameters of motion to reduce the
amount of data stored in databases. In this paper
authors propose three different methods for ship
movementprediction.Performanceofthesemethods
wastestedonthebasisofrealvessels’tracksgathered
from AIS receiver. Authors also propose procedures
responsiblefor select
ionofdata recordswhich must
bestoredbecausetheyprovide significantupdate of
position or velocity parameters. Those procedures
mayalsobeusedinobservatorypointssuchasbuoys
or border guard vessels which send information by
radio links with limited bandwidth. Described
procedures will significant
ly reduce the number of
transmitted data from those objects. Which in turn
will reduce the time of transmission and may save
radiocommunicationresources.
Algorithms for Ship Movement Prediction for
Location Data Compression
A.Czapiewska&J.Sadowski
FacultyofElectronics,TelecommunicationsandInformatics,GdanskUniversityofTechnology,Poland
ABSTRACT: Due to safety reasons, the movement of ships on the sea, especially near the coast should be
tracked, recorded and stored. However, the amount of vessels which trajectories should be tracked by
authorizedinstitutions,ofteninrealtime,isusuallyhuge.Whatismore,ma
nysourcesofvesselspositiondata
(radars,AIS)producesthousandsofrecordsdescribingrouteofeachtrackedobject,butlotsofthatrecordsare
correlated due to limited dynamic of motion of ships which cannot change their speed and direction very
quickly. In this situation it must be considered how ma
ny points of recorded trajectories really have to be
rememberedtorecallthepathofparticularobject.Inthispaper,authorsproposethreedifferentmethodsfor
shipmovementprediction,whichexplicitlydecreasetheamountofstoreddata.Theyalsoproposeprocedures
which enable to reduce the number of tra
nsmitted data from observatory points to database, what may
significantly reduce required bandwidth of radio communication in case of mobile observatory points, for
exampleonboardradars.
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.09
76
This paper is divided into two parts. In the first
oneproposedalgorithmsarepresented.Inthesecond
parttheresultsofcomparisonanalysisareshown.
2 ALGORITHMSFORSHIPMOVEMENT
PREDICTION
In literature there are many methods used for
predictionandsystemmodelling,tomentionfew:an
autoregressive model
AR, a moving average model
AM or an autoregressive moving average model
ARMA. They are described i.e. in Kashyap (1982),
Grenier(1983) or Al‐Smadi (2009).Inthose methods
parameters of models must be established. Many
publicationsaredevotedtotheproblemofsettlement
of those parameters as it is
unique problem for
differentmodelsandsystems.Therefore,inthispaper
authors propose to use the simplest descriptions of
shipmovement:linearandcircular.Theycomparethe
performance of those two movement descriptions
with well‐known however complex Kalman filtering
estimation method.In thepaperauthors proves that
for ship movement
prediction the simplest model
description is efficient and sufficient. Thus, three
different algorithms designed for movement
prediction of vessels tra cks are discussed in this
paper.
Because most of the ships are moving by the
shortestroute we may assume that theyare moving
alongratherlinearpath.Thatiswhy,
firstalgorithmis
based on the monotonous, linear movement
description and it will be later called a linear
algorithm.
Second algorithm assumes that, while vessels
cannotdosharpturns,theymustfollowarcs.Sotheir
trajectories may bydescribedby a part of the circle.
This algorithm is called in this
paper a circle
algorithm.
The last algorithm is the most complex one
consideringthosethree.ItusesKalmanfiltering.
Authors made also some assumptions about
system that might use those algorithms. They
presumed that vessels trajectories data would be
gatheredbysomeremoteobservatorypoints(sensors)
connected to central database
via radio links. To
reduce the amount of transmitted data, one of the
algorithmsmentionedabovewillbeused.Prediction
ofvessels’tracksmustbeperformedonthebothsides
ofdatacommunicationchannel:
central data base (central server) will calculate
coordinates of vessels between records of true
positionsreceived
fromremotesensors;
remotesensorswillperformthesamepredictionin
order to decide if the real coordinates of vessels
differfromestimated/predictedonesbymorethan
specifiedthreshold.
Itisobvious, that the amount of data whichwill
have to be transmitted and stored in database will
depend
ontherequiredaccuracyofrouteestimation
(theestablishedthreshold).
Authors also assumed that the basic source of
information about vessels would be Automatic
Identification System AIS (IMO (1998)) system
(Automatic Identification System) and information
from this system were used to conduct comparative
analysis.
2.1 Linearalgorithm
Every vessel through AIS
system sends information
aboutitsmovement:
ifitismovingornot,
itsspeedoverground(SOG),
its direction of movement COG (Course Over
Ground),
andcurrentposition.
If the position of vessel is given in Cartesian
coordinate system (not in WGS‐84 coordinates) the
next
positionmightbeestimatedasfollows.
Firstly,thespeedgiveninknots(SOG)shouldbe
convertedtom/s(sog)withequation:
SOGsog *514444,0
. (1)
Then the overall shift s in time t of the moving
objectmustbecalculated:
tsogs
. (2)
Tocalculatetheshiftinxandyaxis(respectively
x
and y
)thecourseCOGofthevesselmustbe
takenintoaccount:

180/cos
180/sin
COGsy
COGsx
. (3)
Finally,newcoordinatesoftheobjectare:
yyy
xxx
'
'
. (4)
The x and y are coordinates of the object in
previous moment. Those values must be known‐
fromAISsystem orfromprevious estimations ifthe
errorsofthoseestimationaresmallerthanestablished
threshold.
2.2 Circlealgorithm
Circle algorithm should be better to describe
movementsofmaneuveringvessel.
Inthisalgorithm
the main assumption isthat ships have huge inertia
whatmakesthemdisabletoperformquickdirection
orspeedchanges.Thedirectionisusuallychangedon
arc trajectory. To write equation of pa rticular circle
one must know the coordinates of circle center (a,b)
anditsradius
r.Tofindthoseparametersknowledge
ofcoordinatesofthreepoints((x
1,y1),(x2, y2)and(x3,
y
3)) lying on the circumference is needed. Than
asystemofequationscanbewritten:
77
022
022
022
22
3
2
3
2
33
2
22
2
2
2
2
22
2
22
1
2
1
2
11
2
rbbyyxaxa
rbbyyxaxa
rbbyyxaxa
. (5)
Fromaboveequationstheparametersofthecircle
can be found. At first, those equations must be
rewrittento:
dbca , (6)
where
13
31
xx
yy
c
,

13
2
3
2
1
2
1
2
3
2 xx
yyxx
d
;



1212
12
2
2
yyxxc
exxd
b
, (7)
where
2
2
2
1
2
2
2
1
yyxxe .
Then to find value of circle radius the circular
equationmightbeused.
Whenthe speed of object is known thelengthof
thearcspassedbytheobjectintimetcanbefound
from equation (2). Symbols used in following
equationsareexplainedinFigure1.As
weknowthe
value of s and r,the angle and va lueof R can be
calculatedfrom:
2
sin2
2
360
rR
r
s
. (8)
Then two circle equations might be written. One
with center in (a, b) and radius r. The other with
centerin(A,B)andradiusR:


2
2
2
2
2
2
)(
)(
ByAxR
byaxr
. (9)
Modifying above system of equations and using
beneathsymbols:
2222
2
222222
2
222
1
22
22
22
baaDDG
baCCDF
CE
aA
BbAaRr
D
aA
bB
C
(10)
onecanget:
0
2
GyEEy
DCyx
. (11)
Asaresultofabovecalculationstwopointslying
on the circle are found. To decide which one is the
correctonetheCOGparametermightbeused.
While implementing this algorithm one must be
aware that not for every three points system of
equations (5) is solvable. In
that case it is
recommendedto use linear algorithmfor such three
points.
Figure1.ExplanationofsymbolsusedinEquation(8)–(11).
2.3 Kalmanfiltering
Kalman filtering is an recursive algorithm which
providesmeanstoestimatethestateofdiscretelinear
dynamicprocessinsuchawaythatitminimizesthe
meanofthesquarederror(Welch&Bishop2006).It
means that Kalman filtering may be used for ship
movementestimation.The
following equations were
written basing on the theory found in mentioned
Welch & Bishop (2006) and Grewal & Andrews
(2008).
Thestatevectoris:
y
x
v
v
y
x
x
, (12)
78
where x, y represents position coordinates of the
objectandv
x,vyarevaluesoflinearspeedinxandy
axis.SpeedvaluesdependsfromSOGandCOG.
Thetransitionmatrixforthisstatevectoris:
1000
0100
010
001
t
t
A , (13)
where t is time difference between current
measurementandpreviousone.
Theprocessnoisecovariancematrixisadiagonal
oneQ=I
q,whereIisidentitymatrixandqmustbea
positivevalue.
The measurement noise covariance matrix is
calculatedineveryrecursion:
vy
vx
y
x
r
r
r
r
000
000
000
000
R
, (14)
where diagonal values are variances of last three
measurementsofx,yandv
x,vy.
MatrixHthatrelatesthestatetothemeasurement
vectorisanidentitymatrix,aselementsofstatevector
andmeasurementvectorarethesame.
Procedures of Kalman filtering are conducted in
twophases.Infirstone,apredictionphase,thestate
vector and a priori estimate error covariance is
updated:
QAPAP
xAx
T
. (15)
Insecondphase,acorrectionone,KalmangainK
is calculated and state vector as well as error
covariancematrixarecorrected:



PHKIP
xHzKxx
RHPHHPK
1
TT
. (16)
Duringthefollowingcomparativeanalysis,itwas
assumedthat theinitialstatevectorof Kalman filter
consists of the oldest measurements (those with the
smallest timestamp). While the first measurement
vector consists of measurements with the second
smallest timestamp. Because there are needed three
measurements to fill measurement noise covariance
matrixfirstthreeiterationsofKalmanfilteringdonot
return any result. Those three measurements must
alwaysberememberedandsendtodatabasecenter.
Whenthedistancebetweenestimatedpositionand
truepositionisgreaterthanestablishedthresholdthe
true position must be remembered and also send to
database
center.Whatismore,innextfilterrecursion,
itisforbiddentousetheestimatedstatevector.Asa
statevectormustbeusedrememberedmeasurement
(trueposition).
3 COMPARATIVEANALYSIS
To perform a comparative analysis of presented
algorithms data from AIS system were recorded. A
receivingAISantennawasplaced
on theroofofthe
building of Faculty of Electronics,
Telecommunications and Informatics of Gdansk
University of Technology. Location of antenna and
sensitivityofreceiverallowedtorecordAISdatafrom
all vessels in the Bay of Gdansk. Duration time of
recording wasapproximately one hour. For
comparative analysis were
used only records of
vessels that were moving. Information about ship
movement is send as navigational status in AIS
system. All algorithms were executed on data
converted from WGS84 coordinate system to
PUWG2000 coordinate system. For each algorithm
weredetermined:
estimatedroute,
numberofpositionsgatheredbyAISsystem
(true
positions),
number of positions that must be stored in
database,
rootmeansquareerrorforeachtrajectory.
Resultsachievedforthreevesselsarediscussedin
paragraphs3.1–3.3.Inparagraph3.4thereisshown
analysisforallmovingshipsrecordedwithinanhour.
3.1 VesselMMSI
212425000
ThisobjectwasmovingtowardsharborinGdynia.Its
dimensionsare185x30manditsdraughtis10.9m.In
Tables 1‐4 are presented results for different
thresholds.Therearerootmeansquareerrorsforpath
calculatedwithutilizationofallpositions(RMSofall
positions)andcalculatedonly
forestimatedpositions
(RMS of estimated positions). In the last column is
informationaboutthenumber ofrememberedpoints
giveninpercentage.Thenumberofallpointsforthis
vessel is 616 (length of trajectory is several
kilometers).
Table1. Results for vessel MMSI 212425000 and threshold
equalto10m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear4.85.110.8
Circle4.64.911.7
Kalman4.85.111.2
_______________________________________________
79
Table2. Results for vessel MMSI 212425000 and threshold
equalto50m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear23.223.74.2
Circle23.624.25.2
Kalman23.323.84.5
_______________________________________________
Table3. Results for vessel MMSI 212425000 and threshold
equalto100m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear47483.4
Circle41423.6
Kalman46463.6
_______________________________________________
Table4. Results for vessel MMSI 212425000 and threshold
equalto200m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear80802.1
Circle93942.6
Kalman77782.3
_______________________________________________
Forthisparticularvesselallofthealgorithmsgave
similarresults. Nevertheless, they allowedto reduce
numberofstoreddatasignificantly.
3.2 VesselMMSI235000193
This vessel was moving towards Gdansk. Its
dimensionsare80x13manditsdraughtis6.6m.For
thisobjectonly96pointswererecordedthat
allowed
torecalltrajectoryoflengthabout170m.InTables5–
7areshownresultsfordifferentthresholdsasitwas
showninpreviousparagraph.
Table5. Results for vessel MMSI 235000193 and threshold
equalto10m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear3.34.853.1
Circle4.45.126.0
Kalman3.24.754.2
_______________________________________________
Table6. Results for vessel MMSI 235000193 and threshold
equalto50m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear25.128.421.9
Circle20.020.77.3
Kalman26.529.821.9
_______________________________________________
Table7. Results for vessel MMSI 235000193 and threshold
equalto100m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear424615.6
Circle58604.2
Kalman61612.1
_______________________________________________
As it can be seen for this particular object and
trajectory linear algorithm gives the worst results,
especiallyforlargevalueofthreshold.However,only
forthiscasethelinearalgorithmperformssopoorly.
3.3 VesselMMSI244482000
This object was also moving towards harbor in
Gdansk.Itsdimensions
are83x12manditsdraughtis
3.6 m. This vessel, in spite of navigational status
suggesting that itwas moving, was maneuvering to
moorinKaszubianCana l,whatcanbeseeninFigure
2.
Nevertheless,allofthediscussedalgorithmswere
executedforthisobject.ResultsareshowninTables
8
and9asinpreviouscases.
Forthisvesselalsoallofthealgorithmsperformed
equally. The root mean square errors are similar as
wellasthenumberofdatathatmustberemembered
indatabase. However,asthe ship wasmaneuvering
in space of few meters with very
low speed, this is
oneoftheeasiestcasestoestimatetheroute.
Figure2.PointsofrouteofvesselMSSI244482000.
Table8. Results for vessel MMSI 244482000 and threshold
equalto10m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear5.25.59.2
Circle5.35.69.6
Kalman5.35.59.4
_______________________________________________
80
Table9. Results for vessel MMSI 244482000 and threshold
equalto50m.
_______________________________________________
Algorithm RMSof RMS ofStored
allpositionsestimatedpositions positions
_________ _______________ _______
mm%
_______________________________________________
Linear7.17.10.1
Circle7.17.10.4
Kalman7.77.70.2
_______________________________________________
3.4 Comparisonforallrecordedvessels
As it can be seen in above tables, the position
prediction RMS error value is rather similar for all
algorithms and strongly depends on established
threshold of error estimation. For this reason,
comparisonforallrecordedvesselswasmadeonlyon
the bases of
number points that must be stored to
fulfill the threshold condition. In Figures 3 – 6 are
shown results for different thresholds. They are
shown as column plots. On axis X are values of
number of positions that must be remembered (in
[%]) in ranges. Those ranges depends, of course,
on
the value of position prediction error threshold. On
axisYisthenumberofcases(alsoin[%])inwhichthe
stored number of positions is within the particular
range.
As it can be seen all algorithms enables to
significantlyreducethenumberofdatathatmustbe
storedin
memorytorecallthevesseltra ck. Evenifthe
thresholdis10mtheamountofstoreddataforhalfof
casesislessthan10%.Forgreatervaluesofthreshold
the amount of points that must be remembered
decreasesrapidlytofewpercentforoverahalfofthe
cases.Forthreshold100mthereisneedtostoreonly
5% of positions for 90% of cases. It proves the
statement made in the introductionthat thenumber
ofrememberedpointscanbegreatlyreduced.
Figure3. Stored positions for all algorithms for threshold
10m.
Figure4. Stored positions for all algorithms for threshold
50m.
Figure5. Stored positions for all algorithms for threshold
100m.
Figure6. Stored positions for all algorithms for threshold
200m.
All of the algorithms give similar results.
However,slightlybetter seemtobelinear algorithm
and the one using Kalman filtering over circular
algorithm. As the linear algorithm is much less
complexthanKalmanfilteringauthorssuggestusing
thelinearone.
4 CONCLUSIONS
Asitwasmentionedintheintroduction,due
tosafety
reasons,movementofvesselsnearthecoastmustbe
monitored. It is not enough to observe the situation
ontheseainrealtime,butitisalsoimportanttohave
opportunitytostorethosedata.However,theamount
of data that concerns trajectories for each vessel
81
gatheredonlyfromAISsystemishuge.Thenumber
oftrackedobjectsisalsosignificant.Thatmeans,there
isanurgentneedtohaveapossibilitytoreducethis
amountofdata.
In this paper authors discuss algorithms that
allows to reduce stored data to only few percent of
the
origin number and recall later the routes of the
vessels with acceptable error. Those algorithms may
beusednotonlytoreducestoreddatabutalsomight
be used to reduce datathat must be send to central
databasefromremotesensors.Inthatcase,mentioned
algorithms(orjustone
previouslyselectedand used
alsoon the receiver side) must be performed on the
transmitter side. This feature is very important if
observatory points use radio communication means
fordata transmission.Thereductionofdatawilllead
to spare radio resources by shortening the time of
transmissionorreducingthechannel
bandwidth.
***
This work was financially supported by Polish
NationalCentreforResearchandDevelopmentunder
grantno.OROB/0022/03/001.
REFERENCES
Al‐Smadi A. M. 2009. Estimating autoregressive moving
average model orders of non‐Gaussian processes,
Proceedings of International Conference on Electrical and
ElectronicsEngineeringELECO2009,pages133‐136
Grenier Y. 1983. Estimation of non‐stationary moving‐
average models, Proceedings of IEEE International
ConferenceonICASSP’83,volume8,pages268
‐271
GrewalM.S.,AndrewsA.P.2008.KalmanFilteringTheory
andPracticeusingMATLAB
IMOResolutionMSC.74(69).1998.
KashyapR.L.1982.OptimalChoiceofARandMAPartsin
Autoregressive Moving Average Models, IEEE
Transactions on Pattern Analysis and Machine Intelligence,
pages99‐104
Welch G.,Bishop G.
2006. An Introduction to the Kalman
Filter