281
1 INTRODUCTION
Inland shipping is one of growing branches of
transportation. The impact of this field in Europe is
growing, as European Union is paying more and
more attention to so called sustainable transport.
However inland shipping means not only
professional transport of goods but also a wide
variety of plea
sure boat, leisure craft or other
recreational ships used for touristic purposes. All of
themneedtechnicalandsoftwareaidsfornavigation.
Themarketisofferingmostlyprofessionalequipment
likestandardizedInlandECDIS,whichisnotcovering
all needs of recreational tourists. The alternative for
thisareapplicationsdesigned fortouristicpurposes.
OneofanexamplemightbeMOBINAV,describedin
thi
spaper.Thesystemisbeingdevelopedunderthe
projectLIDER/039/693/L‐4/12/NCBR/2013financedby
PolishNationalCentreforResearchandDevelopment
(NCBiR).
The paper describes research on automatic route
planningfor MOBINAV system. The systemitself is
presented at first with the focus on spatial analysis.
Thena concept ofroute planninginsystem isgiven
followed by short i
ntroduction of graph searching
methods in the aspect of route planning. Finally
numerical experiment is described and the research
resultsarepresented.
2 MOBILENAVIGATIONININLANDWATERS
Everybranchofshipping,includinginlandshipping,
is mobile from definition, as mobilit
y is a core
attribute of navigation. However mobility is
especially important in recreational shipping, where
smartphonesandtabletsarethefirstchoicedevices.
Apart of professional InlandECDIS a range of
flexible applications dedicated for recreational users
isavailable.AnexampleofthiscanbeMOBINAV.
2.1 MOBINAV
Mobile inland navigation is a research project tha
t
combines issues of cartography, geoinformatics and
navigation and focuses on developing of advanced
Analysis of Graph Searching Algorithms for Route
Planning in Inland Navigation
W.Kazimierski&A.Sawczak
M
arineTechnologyLtd.,Szczecin,Poland
N.Wawrzyniak
M
aritimeUniversityofSzczecin,Szczecin,Poland
ABSTRACT:Routeplanning isoneofthecorefunctionalitiesofmodernnavigationalsystemsalsoininland
waters. There is a possibility of at least partial automation of this process with the use of graph searching
algorithms.Mainproblemhereistocreateagraphbasedonnauticalspatialdata.Thepa
perpresentsresearch
onexaminingdifferentgraphsearchingmethodsforinlandwaters.Theconceptofusingcombinedapproach
forvectorandrasterdataisgiven,followedbyresearchresultsforrasterdata.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 9
Number 2
June 2015
DOI:10.12716/1001.09.02.17
282
technology for processing and visualizing spatial
data. Measurable effect will be a prototype of
MOBINAV system, which will be an innovative
mobile inland navigation complying with the
requirements of recreational users. According to the
research hypothesis, implementation of advanced
mobile mapping methodology on modern mobile
technology will allow fulfillment of
recreational
sailors.
Thus,MOBINAVisanexampleofageoinformatic
system dedicated to the needs of a particular
audience.Assumptionsoftheprojectincludenotonly
the development of mobile mapping presentation
model,butalsoanappropriatesetofspatialanalysis
(Zaniewiczet.all,2014).
2.2 Spatialanalysisininland
waters
The basis for planning of every GIS system is
determination of user needs according to functional
requirements. During this process a set of spatial
analysisusefulfortheusershasbeenstated.Theset
includesfollowing:
analysis based on attribute selection such as:
finding the desired object, safety isobaths,
hazardousareas,depthpoint,etc.;
analysisbasedonspatialselection:findingnearby,
locatingspecifickilometer;
complex selection (combined) – selection
combining attribute and spatial selection, e.g.
findingthenearestPOIinspecifiedcategory;
analysisrelatedtotheroutes,inparticular:manual
routeplanning,automaticroutecalculation,route
validation,route’sstatistics;
analysis based on buffering: hazardous areas,
reportedzones,timebuffer;
bearing and distance, which are the basic
measurementsonthemap;
alarms–complexfunctionsusingselectedanalysis
e.g.alarmofcrossingdangerousisobaths,alarmof
approachingdanger,etc.
3 ROUTEPLANNINGININLANDNAVIGATION
One of the most important functions for users in
navigational system is the possibility of route
planning. Apart of classical, manual route planning
function,aninterestingalternativeis
automaticroute
planning. The system proposes the route to follow
based on input values. The bases for this are depth
anddangerousareas.
3.1 Specificityofinlandwaters
Inlandwatersarespecificareasintheaspectofroute
planning.Partofthemhasaformofriversorcanals,
which in
case of route planning are more or less
similartoroads.Vesselsarefollowingriverdirection
moving up or down the stream. The possibility of
crossing traffic is restricted to the areas of junctions
and the routes can be easily divided into legs and
waypoints.Convenientwayofpresentingthis
kindof
watersasspatialdataistheuseofvectordatamodel‐
topologicalvectormodelwouldbethebest.
Theotherspecificareasarelakes.Thesearelarger
areasandthevesselshaveapossibilityofmovingin
many directions. Although there are usually
recommendedroutes,theonlyrestrictionsin
factfor
routeplanningaresafetyissuesincludingdepthand
dangerousareas.Intheaspectofspatialdatamodel,
lakescanbe representedin both ways– with vector
datamodel,butalsowithrasterdatamodel.Bothof
themhaveadvantagesanddisadvantages.
3.2 Vectordataapproach
The common
approach in route planning which is
actually path finding problem (combinatorial
optimization) is to use available data as a discrete
structures for the purpose of conducting specific
search. The goal of such search is to find a sub‐
structure with a maximum (or minimum) value of
someparameter(eg.distance,speed
orevencomfort
oftravel).Spatialdataforinlandwatersincludelayer
indicator points of waterways‐hectometers, which
naturallyformagraphstructure. Consecutive points
are virtually connected with a line of a constant
distance value and several other parameters e.g.
speedlimitorwaterwaycategory.Thevectordataare
givenineachelectronicchartanddoesn’tneedtobe
postprocessed to conduct asearch. However inland
ENCs (Electronic Navigational Charts), besides
waterways include other water areas that are
availablefornavigationofleisurecraftsuchaslakes,
bays or periodic rivers (often poorly charted). In
inland ENC’s these areas
are not covered by any
specific vector data that can form a ready‐to‐use
searchstructure.
3.3 Rasterdataapproach
InMOBINAVoneofthegiven maplayerisaraster
ortophoto which depicts in detail (depending on an
availableresolution)allwaterareasinagivenspatial
domain.
Itcan’tbeuseddirectlyforarouteplanning,
but it’s relatively easy to transform it into a line
boundary(bysimpleimagecontouringprocess).Then
bydetermining the sizeof a regularquadratic mesh
(grid)andbyoverlappingmapwithit,anundirected
graphcanbebuilt.Itsverticesare
representedbygrid
nodes(orbygridcenters)andallcreatedintersection
pointsbetweenwaterareasboundaryandthecreated
mesh(Fig.1).
If the mesh used is regular (quadratic) a created
graph will generally have the same length of each
edge(ifgraphsweightsaredefinedasdistance,allthe
fragments of the route equal 1). To simplify the
algorithm, one can assume that “boundary” vertices
arealsoconnectedbyedgesofsuchlength.Although
itisnottrueinpractice,itwon’thavemajorimpacton
findingtheoptimalsolution(fastestroute)aslongas
thedefinedmeshisrelatively
dense.Itisanexample
of a so called grid graph, which can be defined as
finite,node‐inducedsubgraphoftheintegergrid.The
grid graph is thus represented by a node set
completelydefinedbythesetofnodesVandanedge
setE,asinequations
(1),(2):
1...01...0
lkV
(1)
283
1:,,,1:,,,
22
iiVjijijjVjijiE
(2)
where k = horizontal number of nodes, l = vertical
numberofnodes(MehlhornandSanders,2008).
Figure1.Chartfragmentoverlaidwithexemplarygrid.
Theubiquitousundirecteduniform‐costgridmap
is a highly popular method for representing
pathfinding environments in many fields, like video
gamesorrobotics(HaraborandGrastien, 2011).
3.4 Combinedapproach
BecauseMOBINAVsystemusesbothkindsofspatial
data(vectorandraster)comingoriginallyfrommany
sources with different resolution,
reliability and
validity (Wawrzyniak and Hyla, 2014) it seems
reasonabletousethebestoneavailable.Tobeableto
dothat,oneneedstocombinebothsearchtechniques
in order to find the optimal (fastest, easiest or the
most pleasurable) route. Such approach requires a
fewstages:
Spatialdivisionanddatahierarchyassignment
Rasterdataprocessing
Structureparametersdefinition
Graphbuilding
Graphsearch
Firstly it’s crucial to define which available data
will be chosen for route planning from the sources
thatarecurrentlyavailableforeacharea.Areasmay
be divided according to existing spatial data
allotment (e.g. chart cells) or concerning the type of
water area where the route will
be planned (rivers,
waterwaysseparatelyfromlakesandbays).Secondly
allparts ofrasterdata, ifchosen, mustbeconverted
into graph substructures as described in 3.3. Then,
taking into considerationall the type of data that is
goingtobeused,theweightingparametersoffuture
whole search structure must
be defined. The main
stage is to build the graph which will be a
combination of solutions described in 3.2 and 3.3
depending on a data chosen in first stage of the
approach. This task mostly consists of joining the
substructures into one graph representing all of the
area that
is going to be searched. The last and the
most important stage is conducting a search which
may use many available algorithms widely studied
and discussed (Biggs et. all, 1976; Gross and Yellen,
2004).
4 GRAPHSEARCHINGALGORITHMS
Graphsearchingisanimportanttopicinmanyareas,
particularlyinpathplanningusedincomputergames
and logistics. There are two main approaches: non‐
heuristic and heuristic algorithms (Cormen et. all,
2009).
4.1 Non‐heuristicalgorithms
Non‐heuristic algorithms search graph around
startingpointuntiltheyfoundgoal,alwaysreturning
anoptimalsolution.Noapproximationrulesareused,
soalotofoperationsisrequiredtodetermineapath,
looking for locally optimal solution (Ortega et. all,
2015).
4.1.1 BreadthFirstSearch
Breadth First Search is a simple algorithm for
searchingagraph.Itbeginswithastartingpointand
searches all adjacent vertices and marking them as
visited. In the second stage, vertices reachable at
distance of two edges are visited and the process
repeatsincreasing the
distance, until ending pointis
reached.Asaresult,algorithmoutputsatree,witha
root being a starting point, containing all vertices
accessiblefromthispoint.
4.1.2 Dijkstra’salgorithm
Dijkstra’s algorithm determines the shortest path
betweenstartingpointandevery other vertexinthe
searching area until itfounds
a goal. It begins from
starting point, then the algorithm visits the closest
vertices which are not yet examined. It expands
outwards until it reaches the goal. That means high
computational complexity of this algorithm but the
shortestroutewillalwaysbefound.
4.2 Heuristicalgorithms
Heuristicisasetof
ruleshelpinginfindingthebest
solution.Itis atechnique usedfor solving problems
quicker than classical methods. Heuristic algorithms
findapproximatesolution,sotheycanbeusedwhen
classicalmethodsarefailinginfindingexactpathor
havetoobigcomputationalload.Theriskishowever
thatthe
optimalsolutionwillnotbefoundatall.Thus
it can be said that heuristic algorithms approximate
optimalsolution(Koeniget.all,2004).
4.2.1 BestFirstSearchalgorithm
BestFirstSearchalgorithmissimilartoDijkstra’s
algorithm‐thedifferenceisintheuseofheuristic.It
providesestimatedinformationabouthow
farfroma
goalanyvertexis.Itchoosestheclosestpointtothe
goal,insteadofchoosingvertexclosesttothestarting
point. For example, if a goal is to the north of the
starting point, algorithm will be leading the path to
284
the north. Best First Searching works much quicker
thanDijkstra’salgorithmbutdeterminedpathdoesn’t
havetobetheshortestone.
4.2.2 A*algorithm
A* algorithm is the most popular choice for
pathfinding because it is quite flexible and can be
used in many contexts. It can be treated as a
combination of the Dijkstra’s and Best First Search
algorithms. Algorithm is favoring vertices that are
closetothestartingpoint(like
inDijkstra’salgorithm)
andverticesthatareclosetothegoal(likeinBestFirst
Search). By using heuristic, the algorithm searches
onlyalimitednumberoffields.
Usually A* algorithm is defined by two factors
g(n)andh(n)andisresultinginfindingleastvalueof
thecostfunction
f(n)asinequation(3):
() () ()
f
ngnhn (3)
where:
g(n)‐represents exact cost of route from starting
pointtoanyvertexn;
h(n)‐is a parameter specifying heuristic estimated
costofpathfromanyvertexntothegoal.
4.2.3 JumpPointSearch
JumpPointSearch isanoptimizedversionofthe
A* algorithm. This algorithmreduces
symmetries in
the search procedure by using the graph pruning.
This action eliminates certain vertices in searching
process. As a result, algorithm can consider long
„jump” along straight lines: horizontal, vertical and
diagonal. That makes the Jump Point Search work
faster than A* algorithm (Harabor and Grastien,
2011).
5 NUMERICALEXPERIMENT
The goal of the research was to examine graph
searching algorithms in the scope of implementing
themforinlandwaters.Forthispurposeanumerical
experiment comparing different algorithms in lake
environmentwasproposed.
5.1 Experimentoverview
The experiment was based on raster chart of Dąbie
Lake. It has
been modified in order to improve the
presentation.Thesummarycostrasterwascreatedby
adding raster charts containing information about
land,depth,fishingnetsandbuoyage.
The map has been introduced into on‐line
pathfinding software available at
https://github.com/qiao/PathFinding.js, which
allowedtesting of algorithms and theirsparameters.
On the basis
of raster map the grid graph has been
created. The approach placing grid nodes in mesh
centershasbeenused.Thisallowedusingofdiagonal
edges,aswellashorizontalandvertical.Onescenario
has been examined and five presented algorithms
havebeentested:
A*
Dijkstra’s
BestFirstSearch
BreadthFirstSearch
JumpPointSearch.
For heuristic algorithms Manhattan heuristic has
beenused.
5.2 Researchscenario
Theresearchscenarioispresentedin(Fig.2).
Figure2.Researchscenario.
ItassumedfindingtheshortestpathfromSzczecin
yachtharborinSmallDąbieLaketoLubczynaharbor.
Created raster is in fact a binary representation of
available and not available areas. The land and the
obstaclesthatareonitaremarkedindarkgrey,while
availablewatersarein
lightgrey.
The algorithms have been used to find the best
route with the criterion of distance. Thus the route
found by algorithm is the shortest path calculated
accordingthealgorithmused.
5.3 Resultsofexperiment
Results of experiment are presented in two ways –
graphically and numerically. Firstly the
picture
presenting path calculated for each algorithm is
given.Thisallowscomparingcalculated routes from
navigational point of view. Secondly the table with
numericalresultsispresented‐distanceofcalculated
route(roundedto1meter)andnumberofoperations
needed to find the route. This allows comparing
effectivenessofalgorithmsand
computationalload.
285
5.3.1 Graphicalcomparisonofalgorithms
In(Fig.3)themapofDąbieLakewithdetermined
by various algorithms paths along the lake is
presented.Itcanbenoticedthatallofthepathsavoid
successfully obstacles, however different solutions
werechosen.
In case of Dijkstra’s algorithm all lake area
has
been searched for finding optimal solution. After
passingSmallDabieLake,thepathfollowseastward
between leaving the nets on starboardside and that
the route goes near to east coast. Route has been
determinedafter34246operationsandthelengthof
routeis13890m.
Breadth
First Search algorithm is also a non‐
heuristicapproach,sothepathfoundbyitissimilar
toDijkstra’s.Majordifferenceisthatthecenterpartof
thepathisgoingstraightacrossthelake,betweenthe
fishingnets.Determinedroutehasalengthof13890
mattheperformance
ofthe34713operationbythe
algorithm. The distance is the same as in Dijkstra’s
buttherouteismuchmoreusefulfromnavigational
pointofviewasithaslesswaypoints,solesscourse
alterations.
In case of Best Fit Search, as well as in other
heuristic
algorithms, the area searched is much
smallerthan in case of non‐heuristic algorithm. This
results also in proposed path, as the algorithm is
locally driven towards suggested solution. The path
itselfgoesverynearwesterncoastpassingallfishing
nets far on starboard. Then the route is turning to
starboard
directly towards destination. Determined
routehasalengthof14871mattheperformanceof1
180operationsbythealgorithm.
Figure3.Graphicalpresentationofresults
Results obtained by A* algorithm are almost the
same as in case of Best First Search, but it is a bit
closer as it moves from the west coast earlier. The
route goes close to western coast until it finds clear
straight path to destination.Determined route has a
length of
13988 m at the performance of the 1 983
operationbythealgorithm.
Jump Point Search algorithm gives also very
similar results to other heuristic algorithms and is
almostthesameasA*path.Onlyasmallpartofthe
route, when leaving Small Dąbie Lake is different.
Route has been determined by with the
implementation of 7 442 operations. The length of
routeis13988m.
5.3.2 Numericalcomparisonofalgorithms
Graphical comparison of algorithms presented
aboveallowsstatingsomegeneralfindingsaboutthe
results and comparing them based on navigational
experience. However some numbers allowing
comparison
of methods are given below. Table 1
provides a summary of methods performance.
Number of operations and the length of the route
computed by each algorithm are included.The
lengthofrouteisgivenbothinpixelsandinmeters.
Table1.Summaryoftheresults.
_______________________________________________
TypeofRoutelengthNumberof
algorithm[pixels] [meters] operations
_______________________________________________
Non‐heuristicalgorithms
Dijkstra’s234,48 13889 34246
BreadthFirstSearch 234,48 13889 34713
Heuristicalgorithms
BestFirstSearch 251,05 14871 1180
A*236,14 13988 1983
JumpPointSearch 236,14 13988 7442
_______________________________________________
In conclusion, the shortest route is given by
Dijkstra’sandBreadthFirstSearchalgorithms.These
arebothnon‐heuristicalgorithmssotheyaremeantto
findoptimal solution.The cost howeverfor this isa
largecomputationalload‐about35000inbothcases.
The entire area of lake is searched
to find the best
solution. On the contrary the heuristic algorithms
focus only on the very small part of area to be
searched. Thanks to the use of heuristics, planned
routeisdeterminedatasignificantlyreducednumber
ofperformedoperations.Inthissituationhoweverthe
routeisnotthe
shortestpath.Thefastestsearchwas
performedwithBestFirstSearchalgorithms,butthe
route was the longest – almost 1000 meters longer
thanoptimalroute.Thebestcompromiseseemstobe
A*algorithm,whichperformedalmostasfastasBest
FirstSearch and path distance is reasonably close to
optimalonedeterminedbynon‐heuristicalgorithms.
The computational load in this situation is 1 983
operations,almost18timeslessthantheshortestpath
algorithmsdefiningandtherouteisonly100meters
longer. The route has also reasonable number of
waypoints.ThesamedistancewasobtainedbyJump
PointSearch algorithm butwith the use of almost 7
500operations.
286
5.4 Conclusions
Theresultspresentedintheprecedingchapterallows
statingafewinterestingconclusions.Firstly,itcanbe
noticedthatinthecasepresentinthepapermorethan
one shortest path is available. Both non‐heuristic
algorithms obtained the same distance of path,
however indicating slightly different route. The
common approach for them was however to move
eastwards after passing Small Dąbie Lake. Different
waywaschosenbyheuristicalgorithms.Allofthem
move close to western coast. This was probably the
resultofdensefishingnetlocationattheentranceto
BigDąbieLake. Insteadof movingbetweenthe nets
andcloseto easternshore,the algorithms“decided”
togonearthewesterncoastbutfarfromthefishing
gears.
Another important conclusion is that non‐
heuristic algorithms makes much more operation to
determineapaththanalgorithmswhichuseheuristic.
Insomealgorithmsitisevenmorethan30timesmore
operations. This is a cost of looking for optimal
solution. In such a case it seems to bereasonable to
useheuristicalgorithmsforreal‐timeapplicationsand
find an acceptable compromise between length of
pathandcomputationalload.
Itcanbealsonoticedthatsomeofthealgorithms
result in finding more useful paths for navigational
purposes.Inthiscasethenumberofcoursealteration
isimportantasthesailorsdonotwanttobeinvolved
inconstantalteringthecourse.
6 SUMMARY
The paper presents research on automated
route
planning in mobile inland navigation system. The
researcharebasedongraphcreatedasgridonraster
data. Various graph searching methods were
analysedandcompared.
The results of experiment lead to a few major
findings.Heuristicalgorithms,especiallyA*,seemsto
bereasonablecompromisebetweenlengthofplanned
routeandcomputationalloadforareal‐timesystem.
Non‐heuristic algorithms, like Dijkstra’s can find
optimal solution, but their computational load is
muchbigger.Theycanbeusedinsystems,whichare
not tending to work on‐line, for example for earlier
planning of routes in fixed areas. Other findings
relates to kind of data used. Raster data are
commonly available for larger areas like lakes, but
graph created based on them is much more
complicatedthantypicallyvector‐basedgraph.Thus,
inrealenvironmentscombinedsystemscanbeused.
First,somemajorroutescanbefoundonrasterchart
andconvertedtovectorandthencommongraphfor
all area can be implemented. It would be also
importantinfutureworkstointroducealsoadditional
informationtoweightingraph(notonlydistance)for
betterperformanceofsystem.
The problem itself and the results achieved are
interesting and the authors
will continue works on
thissubject. In future works othergraph parameters
shouldbeconsideredlike–constructionofgridgraph
based on mesh nodes, implementing additional
informationtoweightsorusingotherheuristics.
REFERENCES
Biggs Norman L., Lloyd Keith E., Wilson Robin J., Graph
theory1736‐1936,Oxford[Eng.]:ClarendonPress,1976
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.:
Introduction to Algorithms . The MIT Press, third
edition,2009
Gross,Jonathan L.;Yellen,JayHandbook of graphtheory.
CRCPress,
2004
Harabor D., Grastien A.: Online Graph Pruning for
PathfindingonGridMaps.25thNationalConferenceon
ArtificialIntelligence.AAAI,2005
Kazimierski, W., Wawrzyniak, N.: Exchange of
Navigational Information between VTS and RIS for
Inland Shipping User Needs, in Mikulski J.(ed.)
Telematics in the Transport Environment, Book Series:
CCIS
471,,Ustron,2014
Koenig S., Likhachev M., Furcy D., Planning A*, Artificial
Intelligence,155(1‐2):93‐146,2004
Mehlhorn K., Sanders P.: Data Structures and
Algorithms: The Basic Toolbox, Springer Verlag,
BerlinHeidelberg,2008
Ortega‐Arranz H., Llanos Diego R., Gonzalez‐Escribano
Arturo, The Shortest‐Path Problem: Analysis and
ComparisonofMethods, Morgan&Claypool,2015
Wawrzyniak, N., Hyla, T.: Managing Depth Information
UncertaintyinInlandMobileNavigationSystems.Book
Editor(s): Kryszkiewicz et al., Joint Rough Set
Symposium,LNAI,pp.343‐350,Granada‐Madrit,2014
Zaniewicz G., Włodarczyk‐Sielicka M., Kazimierski W.,
Problems of integration of spatial data from various
sources in inland mobile navigation, Annals of
Geomaticsvol.XII.3(65),Warsaw,2014(inpolish)
