511
1 INTRODUCTION
Predicting the movement of ships maneuvering on
confined water is essential to the safety of people,
equipment, cargo and the environment. Increase of
computational power of personal and portable
computersallowstoimplementcomplexalgorithms
into advanced decision support systems also in the
fieldofmarinenavigation.
Suchasystemshouldincludethefollowingma
in
functions:
analysis of the navigational situation online, in
continuousmode,
warningbeforethedangeroussituationmaytake
place, e.g. possible collision or exit from a
particularlimitedareainanundesirabledirection,
providing transparent information that can be
used in co‐operation with local authorities and
otherauxiliaryunitsofthearea,
itshallgivetheanswersto“whatif”and“when”
questions,inthefieldofshipmaneuveringactions
andnavigationalsituations.
All these requirements may be fulfilled with
neuroevolutionary methods. These methods are
intensively studied and implemented in different
fields of science, including robotics (Haasdijk et al.,
2010;Leeetal.,2013),a
utomationprocesses(Kenneth
etal.,2005),multi‐agentsystems(Nowaketal.,2008),
designing and diagnostic (Larkin et al., 2006) and
many others. Neuroevolutionary algorithms are
successful methods for optimizing neural networks
topologies, especially in dynamic continuous
reinforcement learning tasks. Their significant
advantage over gradient‐based algorithms is the
capabilit
y to modify network topologies along with
connectionweights.
The basic concept of the system is presented in
figure1.
Intelligent Prediction of Ship Maneuvering
M.Łącki
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:Inthispapertheauthorpresentsan idea oftheintelligent shipmaneuveringpredictionsystem
with the usage of neuroevolution. This may be also be seen as the ship handling system that simulates a
learning process of an autonomous control unit, created with artificial neural network. The control unit
observesinputsignalsandcalculatestheva
luesofrequiredparametersofthevesselmaneuveringinconfined
waters. In neuroevolution such units are treated as individuals in population of artificial neural networks,
whichthroughenvironmentalsensingandevolutionaryalgorithmslearntoperformgiventaskefficiently.The
maintask of the system is tolearncontinuously and predict theva
lues of anavigationalparameters of the
vesselaftercertainamountoftime,regardinganinfluenceofitsenvironment.Theresultofapredictionmay
occurasawarningtonavigatortoawarehimaboutincomingthreat.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 10
Number 3
September 2016
DOI:10.12716/1001.10.03.17
512
Starting
position
Realfinal
position
Predicted
position
Prediction
error
Figure1.Estimationofapositionandcourseofthevessel
asaccurateaspossibletoherfinalpositionisthemaintask
ofadvancedpredictionsystem.
Throughcontinuouslearningprocess,thesystem
shall predict the vessel position and state of the
environmentafterspecifiedtimeintervalasaccurate
aspossibleincomparisontofinalrealpositionofthe
ship. It is possible to calculate a probable position
when there is a simulation model of the vessel
available.
It is required that simulation model
includes the equations and coefficients for wind,
currentandwaves.Butinmostcasessuchadvanced
non‐linear simulation model is not available. And
again, a good solution for this problem is
neuroevolution.
2 ARTIFICIALINTELLIGENCEWITH
NEUROEVOLUTION
Neuroevolutionary methods are part of intelligent
computing methods that are inspired by the
developmentofbiologicalnervoussystems(Lehman
and Miikkulainen, 2013). Neuroevolution is capable
of finding solution of complex tasks with artificial
neural networks (ANN) created with evolutionary
algorithms (EA). Such combination gives an
advantageofflexibilityandadaptation,whichallows
to adjust computational structures to
dynamically
changingtasks.
In neuroevolution ANN is treated as an
individual in a population of multiple networks.
Basic topologies of the initial population are
randomly determined at the beginning of learning
process. Each individual begins the process of
findingasolutionwiththesamestartingparameters.
The action of each
individual is usually assessed
with the reinforcement learning algorithms (Stanley
et al., 2005) and evolutionary stage of the system
shallselectindividualsbestsuitedtothetaskduring
selection stage, which determines the whole
populationtoimproveitsgeneticmaterialovertime.
5
6
123
4
2
5
0.02
2
3
5
‐0.11
4
3
6
0.9
5
5
6
‐1.0
9
6
4
0.75
10
No Yes No No No
1
4
‐0.4
1
No
From
To
Weight
Innov.num.
Disabled?
Figure2.Anexampleofencodedartificialneuralnetwork
topology (phenotype) into a connection genome
(genotype),duetoNEATmethod
Evolutionary stage of the system consist three
mainprocesses:
selectionofthebestindividuals,
reproduction (with cross‐over and mutation sub‐
processes),
replacement (offspring replaces worst
individuals).
In case of the evolutionary method the genetic
encoding of neural network topology is very
important. Author of this paper implemented the
modifiedNEATmethodtothissystem(Figure2).
NEAT (NeuroEvolution of Augmenting
Topologies) adjust the topology of ANN’s with EA
(Stanley and Risto,
2002a) gradually to given task,
allowstoobtainasetofANN’sthatarebestfittedto
thistask(Łącki,2009).
Each node represents a neuron that produces a
realvaluebetween0and1asaresultofnormalized
weighted sum of its inputs. Normalization of
weighted sum is
performed with sigmoid function,
asinEquation1.
1
1
j
j
j
S
o
e
(1)
where:
o
j–outputvalueofanneuron,
S
j – weighted sum of input values xnj with weights
w
nj,
–slopecoefficient,
j–bias.
Addingthebiassignalofconstantvalue1,allows
to shift the output value of the activation function
(Figure3).Influenceofbia s maybeadjustedthrough
changing weight of this signal, when the mutation
stage is performed in evolutionary process during
creationofanoffspringinthe
reproductionstage.
513
Figure3.Influenceofbiascoefficient
jtovalueofsigmoid
function
Inthisstagetwobestneuralnetworksarechosen
anditsgeneticmaterialiscrossed‐overtocreatetwo
new individuals. Cross‐over of disparate topologies
is processed in a meaningful way by pairing up
genes with the same historical markings, called
innovation numbers. With this approach the
offspringmaybe
formedinoneofthreeways:
In uniform crossover, matching genes are
randomlychosenfor the offspringgenome,with
higherprobabilityforbetterfittedparent.
In blended crossover, the connection weights of
matchinggenesareaveraged.
Inelitecrossoverdisjointsandexcessesaretaken
from more fit parent only, all redundant genes
from less fit parent are discarded. All matching
genesareaveraged.
Genes that do not match with the range of the
other parent’s innovation numbers are called
disjoints (when they occur within the genome)
or
excesses(whentheyoccuroutsideofthegenome).
These three types of crossoverwere found to be
most effective in neuroevolutionary algorithms in
comparisontoothercrossovermethods(Stanleyand
Risto,2002b).
Genes that have been disabled in previous
generationshaveasmallchanceofbeingre‐enabled
during new
offspring creation, allowing ANNs to
makeuseofoldersolutionsonceagain(Łącki,2012).
Evolutionary neural network can keep historic
trails of the origin of every gene in the population,
allowingmatchinggenestobefoundandidentified
even in different genome structures. Old behaviors
encodedinthepre‐
existingnetworkstructurehavea
chance to not to be destroyed and pass their
properties through evolution to the new structures,
thus provide an opportunity to elaborate on these
originalbehaviors.
The number of inputs and outputs is fixed.
During evolution, inmutation stage, the number of
internal neurons and connections
may change. In
classic NEAT method the number of nodes and
connections may only increase over time, with
possibilitytotemporarydisabletheconnection.This
guaranties to transfer learning experience from
ancestorsto newoffspringandfast learningof new
tasks for new population but it may be
disadvantageous in
such dynamic environments as
shipmaneuveringinrestrictedwaters.Inthiscasean
experienceofoldpopulationmaybeinsufficientand
itslearningabilitytoslow,duetosizeofexperienced
ANN’s.Throughmutation,thegenomesinmodified
NEAT will gradually get larger for complex tasks
and lower their size in
simpler ones. Genomes of
varying sizes will result, sometimes with different
connectionsatthesamepositions.
Historical markings represented by innovation
numbers allow neuroevolutionary algorithm to
perform crossover operation without analyzing
topologies. Genomes of different organizations and
sizesstay compatiblethroughoutevolution, andthe
variable‐length genome problem is essentially
solved. This procedure allows for used method to
increase complexity of the structure while different
networksstillremaincompatible.
During elite selection process the system
eliminatesthe lowest performing members of every
specializedgroupofindividualsfromthepopulation.
In the next step the offspring replaces eliminated
worst individuals. Thus the
quantity of the
population remains the same while itsquality shall
improveaccordingtoassumedgoalsandrestrictions
ofthetask.
3 INPUTSANDOUTPUTSOFNETWORKS
Input and output signals of ANN’s must be
determined at the beginning of designing phase of
the system. Proper set of signals considered
in the
model is crucial for efficient performance of the
system and for its fidelity and accuracy in
comparisontotherealnavigationalsituation.
Inputsignalsinthesystem,withthreedegrees of
freedomvesselmovement,areasfollows:
Ships’courseoverground,
Ships’angularvelocity,
Ships’speedoverground,
Ships’position,
Angleandvelocityofacurrent,
Angleandvelocityofawind.
Mainpropellerrevolutions (currentandpreset),
Rudders’angle(currentandpreset).
Infutureresearchothersignalsfromenvironment
maybetakenintoaccount,i.e.waves,cargo,trimand
roll.
OutputsignalsofANNsshallgeneratethevalues
for important parameters that may change after
certain amount of time. Most important signals in
predictionprocessare:
Ships’position,
Ships’courseoverground,
Ships’speedoverground,
Ships’angularvelocity.
Alloftheinputandoutputsignalsareencodedas
realvaluesbetween0and1.
Computational flexibility and ability to adapt a
network topology to a given task allows to design
complexsetsofinputsandoutputsofANN’s.
Since the neural network with multiple outputs
learns slower than one with only one output, the
proposal of the author is to divide a population of
ANNsintodifferentspecializedgroupsofnetworks,
designed to calculate a predicted value of a single
particularoutputsignal(Figure4).
514
Position Courseoverground
Speedoverground Angularvelocity
Figure4.Divisionofpopulationinto specializedgroupsof
ANNs
This is a very sophisticated neuroevolutionary
method that can deal with premature convergence
that preserves diversity and gradual complexity of
exploredsolutions.
Each group has separate ranking list and
individuals compete only within their own group.
This approach requires much more memory
allocationforhigheramountofgenetic materialbut
eliminates
unnecessaryinfluenceofunwantedinput
signalstooutputvalues.
Performance of each individual is measured in
predicted time interval and its fitness value is
calculatedasadifferencebetweenrealandpredicted
value(Formula2).
2
ini
f
rp min
(2)
where: f
i – fitness value of an individual i (a cost
criteria), r
n – real value of a signal of n‐group, pi –
predictedvalueofasignalofanindividuali.
Inthiscasetheindividualswithleastfitness value
aremorelikelytoreproducetheirgeneticmaterialin
nextgeneration.
General algorithm for data flow to prediction
systemispresentedonfigure5.
Inputsignalshavebeendividedintotwo
groups–
environmental and steering signals. Group of
environmentalsignalsconsistalldataincomingfrom
vesselssurroundings(i.e.winds and currents speed
anddirection)whichcreatesaninputstatevectorfor
thesystem.
Implementation of mathematical model of wind
to the motion control in neuroevolutionary
prediction system increases its performance and
robustnessinsimulatedenvironment.
Under pressure of wind force, depending of the
ships’ design (location of the superstructure, the
deployment of on‐board equipment andcargo, etc.)
shetendstodeviatefromthecourse,withthewind
orintothewind.Thesmallerthespeedanddraftof
theship,
thegreatertheinfluenceofwind.Ofcourse,
the size of the side surface exposed to wind is
essentialtotheshipsmovement.
Whentheshipmovesforwardthecenterofeffort
of the wind (wind point, WP) is generally close to
amidships, away from pivot point (PP). This
differencecreates
asubstantialturningleverbetween
PP and WP, thus making the ship, with the
superstructuredeploymentatstern,toswingthebow
intothewind.
Ship’s
movement
Steering
signals
Environmental
signals
Newstate
Neuroevolutionary
predictionsystem
Comparison
Best
ANNs
storage
Figure5. General algorithm of prediction system with
neuroevolutionarymethod
Forshipmovingforwardtherearedefinedterms
of relative wind speed V
rw and angle of attack
rw
(Isherwood,1973).Windforcesactingonsymmetrical
ship are in general calculated from data as ship’s
overall length, surfaces affected by the wind, air
density and coefficients calculated from available
characteristics of ships model, i.e. from wind loads
data of Oil Companies International Marine Forum
(OCIMF, 1977). This organization identifies safety
and
environmentalissues facing oiltankers, barges,
terminals and offshore marine operations, and
developsandpublishesrecommendedstandardsthat
will serve as technicalbenchmarks for regionaland
worldwideexploitation.
Additionalforces that affectshipsmovementare
waterflowsfrom current and tides. Inthis case the
watermovesinrelationtothe
bottomofariver,sea
oranocean.
PositionoftheMoonandtheSuninrelationtothe
Earth affects mostly waters in the oceans. Many
naval ports of the world have their locations at a
riverestuaries.Currentsofthat rivers may be often
affectedbyoceantides.
Tidalforceisdeterminedby
the difference in forces at the Earthʹs center and
surface.Tidal forces are mostly available from local
authoritiesifaformoftimetablesetsandcharts.
Tidal charts are grouped insets, each setcovers
the time interval betweentwo consecutive high
tidesinthe
area.Thesechartstheygivetheaverage
tidal flowinformationfordesiredtime span for the
shipmaneuveringarea.Informationonatidalchart
consistsofdirectionandaverageflowspeedinknots
forspecifiedtides.
An alternative to the tidal charts is the tidal
diamonds method, which may be
found on most
nautical charts. With this method one can relate
515
certain points on the chart to a table that will
calculatethedirectionandvelocityoftidalflowand
according to this flow the estimated position of the
vesselcanbecalculatedregardingthedirectionofthe
tide.
The gravitational tides are not the only one
affectingflowofthe
water,there are also terrestrial
tides, atmospheric tides and thermal tides.
Atmospherictidesarecausedbytheradicaleffectsof
weather and solar thermal tides and in most cases
theyreinforceoceanictides.
Underthepressureofacurrentashipisdrifting
together with the water, relative to the
ground and
anyfixedobjects. Whentheshipismovingincurrent
the speed over ground is resultant velocity of ship
speedandvelocityofthecurrent.
Stronger water flowsmay cause the tendency to
swing the ship with the stern or bow towards the
side, which may lead to dangerous
situation. This
might be particularly difficult to overcome when
working in following tide because of the small
effectivenessoftherudderatlowspeed.
Steeringsignalsconsistdatathatmaybechanged
by a user of the system (i.e. a navigator or a
commander on the bridge). Steeringsignals include
propellersrevolutionsorthrustandruddersangles.
All these input signals affect ship’s movement
which creates a new state of the environment with
themovingvesselinit.
Atthesametimethesimilarnewstateparameters
arebeingcalculatedintheneuroevolutionarysystem,
regarding the same input signals. The real
and
predicted values are compared and the result of
comparisonprovidessubstantialinformationforthe
systemthatallowstoelaboratethequalityofcreated
ANN’s and overall performance of whole
population.DuringevaluationtherankingofANNs
itcreatedandthebestnetworksarestoredforfuture
exploitation.
4 SIMULATION
MODELSANDRESULTSOF
PREDICTION
For the purpose of a ship movement simulation an
applicationhasbeencreatedbytheauthor(Figure6).
Figure6.Anapplicationfortestingbehaviorofsimulation
modelsofdifferentvessels
Thedesignedapplicationallowstochoosespecific
model of the vessel, to set a starting parameters of
navigationalsituationinrestrictedwaters,including
speedand direction of awind and awatercurrent,
and run a simulation with partially observable
prediction values that can be saved to a file and
analyzed
offlineafterthesimulation.
Two simulation models of ships with three‐
degrees‐of‐freedomhadbeenusedinthesystemfor
the purpose of systems performance test. Main
parametersofshipshasbeencomparedintable1.
Table1.Mainparametersofsimulationshipmodels.
_______________________________________________
NameBlueLady CapeNorman
_______________________________________________
TypeVLCCContainership
Scale1:241:1
Length13,78[m] 175[m]
Beam2,38[m]26,5[m]
Draft0,86[m]14,2[m]
Capacity/Tonnage 22,83[T]1504[TEU]
Max.speed3,1[kn]20,4[kn]
_______________________________________________
The sets of output data of ANN’s has been
calculated and recorded during task evaluation in
every generation as the results of simulation. The
population consist four separate groups of ANNs,
with 50 individuals each,resulting in200 ANNs in
total.
The chart presents evaluation of the simulation
for
200generations(Figure7). Since there isalways
onlyoneoptimalsolutionforeveryparameterinthe
prediction system, the algorithm tends to converge
quickly to this solution. These simulation results
prove a good performance of learning process of a
singleoutputneuralnetwork.
Figure7. The examples of average fitness values of
specializedgroupsofANNs
For two different models of the vessels the
average fitness values become at stable levels after
about 20‐40 generations, which took about few
minutesofsimulationonastandardPC.
516
Spreadofaveragefitnessforspeedovergroundis
greaterforcontainership,regardingitsgreaterrange
ofpossiblepredictedspeedvalues.
Additionalcharacteristicsoflearning process are
shownonfigure8.
Figure8.Thecomparisonoflearningspeedduringentering
astrongcurrentafterdifferentgenerationnumber.
Thesetwochartsillustratesthatlearningspeedin
neuroevolutionaryalgorithmsstrictlydependsonthe
ageofpopulation.Youngerpopulationadoptsfaster
to new sudden changes due to smaller genome of
individuals. But on the other side the older
populationismoreexperiencedandisabletoreactto
newstatesrelying
onlearnedpatterns.
5 REMARKS
Intelligent maneuvering prediction system for
maritimetransporthassomevaluablebenefits:
increaseofthesafetyofnavigationinarestricted
water area by improving the data analysis for
decision‐makerduringmaneuvers,
improvement of the operation of ships in port,
duetotheincreasedbandwidth,
reductionofoperatingcostsofvessels,
minimizationoftheoccurrenceofhumanerrors,
reduction of the harmful impact of transport on
theenvironment.
It is important to notice that all these benefits
strictlydepend onproperadjustmentofevolutionary
parameters, the size of ANNs population and the
encoding methods of signals consideredin serviced
environment.
Neuroevolutionaryapproach to shiphandling in
confined waters
improves a quality of maneuvers
andsafetyofnavigationeffectively(Łącki,2008).For
the simulation study, mathematical model of three‐
degrees‐of‐freedom maneuvering VLCC tank ship
with the single‐propeller and single‐rudder was
applied to test the prediction performance of the
system.Artificialneuralnetworksbasedonmodified
NEATmethodincreasecomplexityandperformance
ofconsideredmodelofshipmaneuveringinconfined
waters.
Implementation of additional input signals
related to influence of wind and current allows to
simulatecomplexbehaviorofthevessel(Łącki,2012)
intheenvironmentwithmuchlargerstatespacethan
it was possible
in a classic state machine learning
algorithms (Łącki, 2007).simulation results of
maneuvers in variable wind and current conditions
of different ship models encourage to further
research of the neuroevolutionary methods which
may finally be implemented into advanced
navigationalpredictionsystemstoincreasethesafety
ofnavigation.
REFERENCES
Haasdijk,E., Rusu,A.A. &Eiben, A.E.2010. HyperNEAT
forLocomotionControlinModularRobots.
Isherwood,J.W.1973.TransactionsofRoyalInstitutionon
Naval Architects, Wind resistance of merchant ships,
vol.115,327–332.
Kenneth, S., Nate, K., Rini, S. & Risto, M. 2005.
Neuroevolutionofanautomobilecrashwarningsystem
,
WashingtonDC,USA.
Larkin, D., Kinane, A. & O’Connor, N. 2006. Towards
hardware acceleration of neuroevolution for
multimediaprocessingapplicationsonmobiledevices,
HongKong,China.
Lee,S.,Yosinski,J.,Glette,K.,Lipson, H.&CluneJ 2013.
Applications of Evolutionary Computing, Evolving
gaits for physical robots with the
HyperNEAT
generativeencoding:thebenefitsofsimulation.
Lehman,J.&Miikkulainen,R.2013.Neuroevolution,
Scholarpedia,vol.8,30977.
Łącki,M.2007.Machine LearningAlgorithmsinDecision
MakingSupport inShip Handling. , Katowice‐Ustroń,
WKŁ.
Łącki,M.2008.Neuroevolutionaryapproachtowardsship
handling.,Katowice‐Ustroń,WKŁ.
Łącki, M. 2009. Ewolucyjne sieci NEAT w sterowaniu
statkiem. Inżynieria Wiedzy i Systemy Ekspertowe,
Warszawa:
Akademicka Oficyna Wydawnicza EXIT,
pp.535–544.
Łącki,M. 2012. TransNav‐InternationalJournal on
Marine Navigation and Safety of Sea
Transportation, Neuroevolutionary Ship
HandlingSysteminaWindyEnvironment,vol.6.
Nowak,A.,Praczyk, T. & Szymak,P.2008.Zeszyty
Naukowe Akademii Marynarki Wojennej, Multi‐
agentsystemofautonomousunderwatervehicles
‐preliminaryreport,vol.4,99–108.
OCIMF 1977. Prediction of Wind and Current Loads on
VLCCs,OilCompaniesInternationalMarineForum.
Stanley, K.O. & Risto, M. 2002a. Efficient evolution of
neuralnetworktopologies.
Stanley, K.O. & Risto, M. 2002b. Efficient Reinforcement
Learning Through Evolving Neural Network
Topologies.
Stanley, K.O., Bryant, B.D. & Risto, M. 2005. IEEE
Transaction on Evolutionary Computing, Real‐time
neuroevolution in the NERO video game, vol.9, 653–
668.
