335
1 INTRODUCTION
In the last decades marine traffic increased
significantly and consequently did the collision risk
for vessels. A lot of assistance systems like GPS,
ARPA, AIS or ECDIS were introduced to prevent
ship accidents, however, their number is still on a
constant, high level. Only groundings have
decreased slightly. About half of the accidents are
causedbyhumanfact
orsandtakeplaceincongested
areas,duringportapproachorinharbours,asstated
by reports of the Baltic Marine Environment
Protection Commission‐Helsinki Commission
(HELCOM).
On‐boardandonshoreassistancesystems,aswell
as future collision avoidance systems, can benefit
from knowledge ab
out suggested trajectories for all
vessels in an encounter, which are not only locally
optimised but also coordinated between vessels to
provide guidance in critical traffic situations.
Trajectoryplanningmethodsareusedalreadytoplan
manoeuvres or guide single vessels in two‐vessel
encounters. An overview of the most import
ant
approaches is given by Statherosetal.(2007) and
Tametal.(2009). Some collision avoidance
approaches are limited to two‐vessel encounters or
estimateevasivemanoeuversfortheownvesselonly.
Forthisworkthefocusisonapproachesforn‐vessel
scenarios optimising all the trajectories of the
involved vessels. Heuristic op
timization algorithms
are mainly used to solve this problem. One of the
first and most promising approaches using an
evolutionary algorithm is presented by
Smierzchalski(1999). Many other approaches use
heuristic methods like fuzzy‐logic, neural networks
or ant algorithms. However, the most sophisticated
approach is presented by Szlapczynski(2011) and
Trajectory Planning with
Negotiation for Maritime
Collision Avoidance
S.Hornauer&A.Hahn
UniversityofOldenburg,Germany
M.Blaich&J.Reuter
UniversityofAppliedSciencesKonstanz,Germany
ABSTRACT:Theproblemofvesselcollisionsornear‐collisionsituationsonsea,oftencausedbyhumanerror
duetoincompleteoroverwhelminginformation,isbecomingmoreandmoreimportantwithrisingmaritime
traffic. Approaches to supply navigators and Vessel Traffic Services with expert knowledge and suggest
tra
jectoriesforallvessels toavoid collisions,are oftenaimedatsituationswherea singleplanner guidesall
vesselswithperfectinformation.Incontrast,wesuggestatwo‐partprocedurewhichplanstrajectoriesusinga
specialised A* and negotiates trajectories until a solution is found, which is acceptable for all vessels. The
solutionobeyscollisionav
oidancerules,includesadynamicmodelofallvesselsandnegotiatestrajectoriesto
optimisegloballywithoutaglobalplannerandextensiveinformationdisclosure.Theprocedurecombinesall
componentsnecessarytosolveamulti‐vesselencounterandistestedcurrentlyinsimulationandonseveraltest
beds. The first results show a fast converging opti
misation process which after a few negotiation rounds
alreadyproducefeasible,collisionfreetrajectories.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 9
Number 3
September 2015
DOI:10.12716/1001.09.03.05
336
Szlapczynski,R.& SzlapczynskaJ.(2012a,b). They
use an evolutionary algorithm with specialised
operators to shape the convergence of the
optimisation. In Szlapczynski(2012,2013) this
approach is extended to the use within traffic
separationschemes(TSS).Inordertolimitthevariety
of individuals of a population during
evolutionary
optimisation Szlapczynskis approach generates
tracks, already partially valid within a TSS after
which a number of defined violation are penalised
using a specialised fitness function. A further
improvementofthisalgorithmismadefortracksin
restricted visibility according to the rule 19 of the
Collision Avoidance Regulations (COLREGs)
and is
presentedinSzlapczynski(2015).
All these approaches are more suitable for
onshore applications like Vessel Traffic Services
(VTS) because the information about the current
trafficsituationhastobecomplete.However,foran
on‐board usage the limited common situation
awarenesslimitsglobalplanningapproacheswithn‐
vessels. Suggested
trajectories for several vessels
mustnotonly take informationintoaccount, which
areoften hard orimpossible to acquirefora single,
planning observer, but also satisfy a number of
constraints imposed by COLREGs and the vesselʹs
dynamicmodel.
1.1 Methodology
Thispaperproposesastagedproceduretofind
and
distribute and near optimal set of trajectories for a
number of vessels. During the procedure,
independent components for motion prediction,
trajectory generation and trajectory negotiation are
usedtooptimisealltrajectoriesaccordingtoaglobal
performance measure (safety / efficiency). First, the
motionpredictionestimatesthefuturemotionofthe
othervesselsbasedontheirtrajectoriesoronmotion
models ifatrajectory isunavailable after whichthe
trajectory generation algorithm plans a new
avoidancetrajectoryinalocalarea,giventhelocally
availableinformationwhichwillincreaseduringthe
negotiation. Finally the trajectory negotiation
componentisusedtofind
aglobaloptimalsolution
as fast as possible while the amount of data that
needstobetransferrediskeptaslittleaspossible.A
beneficial side effect is that the intentions of all
vesselsin acritical situationare knownearly inthe
process.
Even thoughnew communication infrastructures
are
being developed, which will provide advanced
communication architectures in the future, i.e. by
Muetal.(2011),thebandwidthisstill consideredas
limited in the near future. Therefore, the explicit
communication of all missing information is
regardedtoocostlyonsealeadingtoourapproachof
exchanging trajectories only.
These trajectories
containimplicitinformationaboutpreferences,ship’s
capabilities,partsoftheship’svaluefunctionandthe
environment without needing to explicitly disclose
all those information. Furthermore, decentralised
algorithms are considered as computationally
favourable and can find Pareto‐Optimal solutions
without needing to know the value function of
trajectories for other
negotiators, as shown by
Heiskanen(1999).
The described procedure is modelled and tested
in a simulation to compare a number of different
trajectorygenerationandnegotiationapproachesand
afterwards evaluated in different scenarios using
simulationandinseveralmaritimetest‐bedsatLake
ConstanceandtheGermanBight.
2 TRAJECTORY
DEFINITION
A trajectory is the exact path of the vessel over
ground; similar to tracks for vojage planning but
including exact turns. Therefore a Trajectory is
defined by j waypoints w
0..wj‐1 and a speed v to
travel alonge the trajectory. To achive continuous
turning rates the segments between the waypoints
can be interpolated using fifth order Bézier curves.
Thus, the trajctory consist of j‐1 Bézier curves.
Figure1showsanexampleofatrajectorydefinedby
fourwaypointsw
0..w3.
Figure1. A vessel trajectory defined by four waypoints.
The first waypoint is the current vessel position. The
segmentsbetweenthewaypointsareinterpolatedbythree
Béziercurves.
The Bézier curves used for the interpolation are
parametric curves B
k(c). A Bézier curve of order n
used for the k‐th path segement is defined by n+1
controlpointsP
0..PnandaBernsteinpolynomial:
 

,,
0
,0,1,0
n
kinik
i
B
cbcP c kj

 (1)
withb
i,nthei‐thBernsteinpolynomialofordern.The
interpolation is applied between the waypoints w
k‐1
andw
k.Thelengthofthecurveforthek‐thsegment
iscalculatedby:
  
22
k
Lc xc ycdc


 (2)
Tocalculatethepositionof the vesselalonge the
trajectoryatanytimetheparametercisdefinedasa
functionofthenormalisedtime

1k
k
tT
ct
t
 (3)
with T
k the time when waypoint wk is reached and
Δt
k=Tk–Tk‐1 the time required to pass the segment,
337
whichiscalculated applingthetrack speedvto the
lengthofthecurveL
k(c).Usingequation1and3the
position of the vessel on the trajectroy at any time
p(t)canbecalculatedby:
 

,,
0
,0
n
in i j
i
p
tbctP kj

 (4)
Thisinterpolationmethodallowsthedefinitionof
a complete vessel trajectoy

,
R
Wv
usinga set of
waypointsW={w
0..wj‐1}andthetrackspeedv.
3 MOTIONPREDICTION
Toidentifypossiblecollisionsandfortheavoidance
algorithms, knowledge about future motions of the
own and other vessels is necessary. Possible
information about the vessel’s current state can be
received e.g. by an AIS/ARPA system. For motion
prediction,necessaryinformation
areposition,speed,
direction of motion and the length of the vessel.
Furtheroptionalinformationliketherateofturnora
route plan consisting of waypoints can be used to
improvetheperformanceoftheprediction.Thus,an
approach considering all available information is
proposed in this work. If waypoints
and a track
speed are available, this information is used to
generateatrajectory,andthetrajectoryfollowing(TF)
method described in section 3.3 is used to estimate
thevessel’sposition,travelingalongthistrajectory.If
waypoints for a vessel are unavailable, the future
motion of the vessel is predicted
using two simple
motion models. One model is used for straight line
motion and another model is used for circular
motion. Due to the imprecise estimation of vessels
accelerationandtheunknowndesiredspeedduring
an acceleration or deceleration manoeuvre the
assumption of a constant velocity is used for both
models.

Forstraightlinemotiontheconstant velocity(CV)
model is used. This non‐holonomic model allows
movementswithverylowvelocityuncertainties.This
leads to a good state estimation for straight line
motion but for manoeuvring motions the state
estimationimpairs.The modelfor acircularmotion
uses an approximately
constant turn rate to define
the orientation change of a vessel and is called
constant turn rate and velocity (CTRV) model. The
velocity uncertainties in this model are larger than
for the constant velocity model. This improves the
state estimation for manoeuvring motions but
impairs the accuracy of a straight line
motion
estimation.Themodelsarebasedonexperiencefrom
the target tracking community and explained in
detailbyLi&Jilkov(2003).Fortwo‐vesselencounter
scenarios, Schusteretal.(2014) presented an
approach to generate an evasive trajectory for the
own vessel, using those two models for the motion
predictionoftheothervessel.
3.1 ConstantVelocityModel(CV)
Fortheconstantvelocitymodelthelongitudinaland
lateralposition p=(x,y)
T
and velocities v=(ẋ,ẏ)
T
can
be used. The direction of motion is used as
orientation of the vessel θ. This orientation can be
differenttothetrueheading.However,forthiswork
theassumptionisthattheheadingcorrespondswith
the direction of motion. Based on a starting state s
0
thepositionofavesselcanbecalculatedatanytimet
withthesystemequation.UsingthetimedifferentΔt
relating to the starting timeΔt=t‐t
0 the system
equationfortheconstantvelocitymodelisgivenby:






0
0
0
0
0
0
arctan
cv
x
xt
xt
yyt
yt
y
st t
x
xt
x
yt
y
























 (5)
3.2 ConstantTurnRateandVelocity(CTRV)
The circular motion model is defied by a non zero
turningrate
andthe constanttrack speedv.
If turning rate is zero the CV model is used. The
tangentvelocityvectorv=(vx,vy)
T
isdefinedby:






cos
sin
vt
vx t
vt
vy t
vt







 (6)
The radius vector r(t) pointing from a vessel
position p(t) to the centre of the circle is calculated
usingthisvectorv(t)andtheturningrate:

,0
vt
rt
 (7)
Thepositionofthevesselp(t)onthecircularpath
is calculated using the radius difference vector
Δr=r(t)–r
0. This radius difference vectorΔr points
fromthestartingpositiontothecurrentposition:
0
p
tp r

 (8)
Applyingequation7toequation8leadsto:

0
0
,0
vt v
pt p

 (9)
Using equation 9 for the vessel postion leads to
thesystemequationfortheCTRVmodel:
338
0,
))())(((
))())(((
=
)(
)(
)(
)(
)(
=)(
0
0
0
0
0
v
t
sintsinv
y
costcosv
x
t
tv
t
ty
tx
t
CTRV
s
(10)
3.3 TrajectoryFollowing
Toestimatethepositionofavesseltravelingalonga
trajectorythetrajecotrydefinitionfromequation4is
used. The orientation of the vessel at any time θ(t)
can by calculated using the time derivatives at
positionp(t):



yt
tarcan
x
t




 (11)
Thecurvatureκ(t)ofthecurvecanbecalculated
usingthefirstandsecondtimederivativeatp(t):

   
 

3
22
2
x
tyt xtyt
t
xt yt
 

 (11)
For this motion model the turning rateω(t)
changesovertimeandiscalculatedwiththeproduct
ofthetrackspeedvandthecurvatureκ(t):
 
ttv


 (12)
Using equation (5), (11) and (13) leads to the
system equation for a vessel moving along a
trajectorydefinedasasequenceofBéziercurves:
kj
TTt
vt
v
tx
ty
arctan
Ptcb
Ptcb
t
tv
t
ty
tx
t
jj
j
y
ini
n
i
j
x
ini
n
i
TF
<<0,
],[,
)(
)(
)(
))((
))((
=
)(
)(
)(
)(
)(
=)(
1
,,
0=
,,
0=
s
(13)
3.4 ObstacleHandlingwithSafetyDistance
The information aboutthe future motion, estimated
either by CV model, CTRV model or the trajectory
following method, is stored in a three dimensional
grid with x,y and time. This grid is further called
obstaclegrid.Allgridcellswithinasafetydistance
to
the trajectories are marked as occupied and
consequently prohibitedforthe own vessel. For the
safety distance a Davis domain (Davisetal.1982)
scaledbytheshiplengthisusedtoobtainanautical
behaviourtakingintoaccounttheCOLREGs.
4 TRAJECTORYGENERATION
For trajectory generation weusea
discrete space as
introduced above. Therefore, the own trajectory is
mappedtothegridandcomparedwiththeobstacle
grid.Ifacelloftheownpathismarkedasoccupied
by another vessel in the obstacle grid a potential
collisionisdetectedandanadoptedA*algorithmis
triggered
to find a new set of waypoints for an
avoidance trajectory. To guarantee the feasibility of
movingalongthiswaypointsanapproachtakinginto
account the kinematic constraints of a vessel as
presented by Blaichetal.(2012a) is used. This
approachonlyusescells,reachablebytheownvessel
considering
the heading in the current cell and the
turning circle of the vessel. This constraint cell‐
neighbourhoodisnamedasT‐Neighbourhoodbecause
the reachable cells can be modelled as a T‐shaped
geometry. Because planning takes place only in a
local area the waypoints of the avoidance trajectory
are
asubsetofalargerglobaltrajectory.Atangential
connectionbetweentheavoidancetrajectoryandthe
globaltrajectoryisusedtoreachasmoothtransition.
As presented by Blaichetal.(2012a) two virtual
obstacles, representing the turning circle of the
vessel, are used as so called connection ‐funnel. As
search algorithm an A* algorithm using the
T‐Neighbourhood as presented by
Blaichetal.(2012b) is applied and modified for the
n‐vesselscenarioswithtrajectorynegotiation.
4.1 SpecialisedA*fornegotiatedtrajectories
TheA*searchisappliedtoagrid.Eachcellcofthis
gridrepresentstheposition
ofavesselreachingthis
cell within a minimum of time. Additionally the
orientationofthevessel,reachingthiscell,isstored.
Thus,thegridis2.5Dwithc=(x,y,θ)
T
storingtoeach
position one orientation. Suppose that the vessel
movesonthegridittakesdiscretestepskfromcellc
k
tocellc
k+1.Thismotionisdefinedbyanactionu.The
setofpossibleactionsapplicablefromcellc
kiscalled
action space U(c
k). The T‐Neighbourhood limits
action space to a straight‐line motion, a left and a
rightturn.Thegoalofthesearchalgorithmistofind
asequenceofreachableandcollisionfreecellsfroma
startcellc
0correspondingtopositionp0toagoalcell
c
g with minimum costs. As cost function the
A*‐algorithm combines a cost‐to‐come function
g(c
k,u) with a heuristic cost‐to‐go function h(ck) to
estimate the total cost f(c
k,u) to reach a grid cell
applyingactionu:
,
kk k
f
cgcuhc
 (14)
Forthecost‐to‐comefunctiong(c
k,u),asimplified
version without turn penalties but considering the
covered distances d(c
k,u) for reaching cell ck by
applying action u to c
k‐1 is used. Additionally, the
339
distancetotheorginaltrajectoryd(c
k,R
0
)isusedalso.
Thisleadstothecost‐to‐comefunction
 

0
1
,,,
kk k k
g
cu
g
cdcudcR


 (15)
with δ and τ as scaling factors. For the distance
function d(c
k,u) to the previous cell the Euclidian
distance between the cells c
k‐1 and ck is used. To
calculate the distance between c
kand R
0
an
approximation of the area between c
k‐1 and ck‐1 and
theclosestpointstotheoriginaltrajectoryisusedas
trajectory distance function d(c
k,R
0
). For the
approximationtheaveragedistancebetween c
k‐1and
c
k‐1 to R
0
multiplied by the Euclidian distance
betweenthetwopointsonR
0
isused.Anillustration
ofthisapproximationisshowninFigure2.
Figure2. Distance between avoidance trajectory and
originaltrajectory.
Tousetheareainsteadofthedistancebetweenck
andR
0
hastheadvantagethatthedistanceD(R*,R
0
)
between the resulting trajectory R* and the original
trajectory R
0
is the sum up of the distances d(ck,R
0
)
fromthecellsequenceestimatedbytheA*algorithm:

*0 0
0
,,
j
k
k
D
RR dcR
 (17)
withtrajectoryR*containingaswaypointsallcellsof
theA*solution.
Thecompletecostofatrajectoryisdefinedasthe
cost‐to‐comeg(c
g,u)forthegoalcell.
AsheuristicfunctiontheEuclidiandistancefrom
cellc
ktothegoalcellcgisused.
The trajectory R* estimated by the A*‐algorithm
contains as waypoints W*, a list of connected cells
fromthestartingcellc
0tothegoalcellcg.Toachieve
a trajectory Rʹ as a sparse representation of R*, a
Dougles‐Peuker algorithm is used to eliminate
needless waypoints using a certain threshold. This
sparsetrajectoryRʹmakesitpossibletoexchangethe
complete trajectories between all agents during
negotiationprocess.
5 TRAJECTORYNEGOTIATION
Aftertheinitial
solutionisfoundbythepath‐finding
component, the locally planned avoidance
trajectories are negotiated between all involved
vessels. The initial, single trajectory for the own
Vessel isplanned,ignoring informationabout other
vesselandusedasaninitialofferinthenegotiation.
This first trajectory is considered the desired
trajectory
of each vessel, if no other vessel would
interfere. The value of other trajectories will be
calculated in between this best solution and a
hypothetical worst solution, which is usually
unfeasible.Inanumberofnegotiationroundsvessels
broadcasttheirproposalfortheirtrajectoryintheset
of all trajectories.
At the end of the first round,
intentionsofallvesselsare known,though theyare
verylikelytoconflict.Insubsequentrounds,vessels
discard sets with low value and re‐plan their
trajectoryinsetswithahighvalue.Thenewsetsare
exchanged as an offer while the global
measure is
designed to let the negotiation converge to an
optimal, common solution. This procedure helps to
compensate for incomplete information without the
need to exchange state space information explicitly
andbalancethecostsandbenefitsequallyamongall
participants through the design of the trajectory‐set
selectionprocess.
The
following steps are our adoption of an
algorithmofStevenP.Waslander(2007)who,inhis
thesis, designed distributed algorithms for agents
which reach optimal solutions using concepts of
game theory without the need to maintain all
information locally at one central point. The
cooperative decentralised penalty method is modified to
workonthepaths,already locallyoptimised bythe
path‐finding component, to perform a global
optimisation.
In our adopted algorithm, a number of agents
aA
follow a number of trajectories Ra(W,v),
consisting of waypoints w
0..wj‐1 where w0 is the
starting position of the vessel which moves along
thattrajectoryandw
j‐1asitsdestination.
The original algorithm does not have a path‐
finding component which already minimises the
distance from a desired optimal trajectory and the
originaltrajectoriesarefullydefinedondiscretetime
steps. The path‐finding component works on a
smaller,minimalnumberofwaypoints,asdescribed
inparagraph
4.1.Theagentcostfunctionistherefore
modifiedfromtheoriginalapproachto:
d
aa a a
CR R R
 (19)
where
d
a
R
isthedesiredtrajectoryofagentawhich
is in our case a straight line from its position to its
destination. Our decentralised augmented cost
function contains no penalty function because the
interconnectedconstraints,imposedbytrajectoriesin
theneighbourhoodoftheagents,arealreadyfulfilled
bythepath‐finding
algorithmandtrajectorieswhich
violateconstraintscannotbegenerated.Thisleadsto
adecentralisedaugmentedcostfunction:



|log
Aug
aai a aaa
a
CRR dCR

 (20)
The function is defined on all neighbouring
vessels
iA
where ia which in our first
approach includes all other vessel. The notation
i
j
R
referstothefixedknowledgeoftheagentof
the trajectories of other agents. The disagreement
point d
a, a point which represents the costs of the
worst case solution, if the agents do not reach an
340
agreement,isinourcollisionavoidancecasedefined
as an usually unfeasible solution, which maximises
theagentcostfunction.Thisresultsinatrajectoryat
the fringes of the state space where the distance
between the ideal straight line trajectory is at its
maximum. We use the same penalty parameter
0
asInalhanetal.(2002)toensureconvergence
ofthecostfunction.
Thedecentralisedoptimisationproblemisnowto
minimiseequation(20)whilewereduce
i
inorder
to reach the Nash Bargaining Solution. For an
explanation of the cost decomposition of the Nash
Bargaining Cost function from the central to the
decentralisedcasethereaderisreferredtoWaslander
(2007). The detailed adopted algorithm, applied to
ourproblemisasfollows:
1 The first local
trajectory of the own vessel is
planned, using the A* component regardless of
theothervessel’strajectories.
2 The waypoints of single trajectories from each
agentarebroadcasted,afterwhicheachagenthas
|a|‐Setsofsingletrajectories,oneforeveryagent
anditself.
3 Allsetsofsingletrajectoriesare
mergedtooneset
0
a
R
, with one trajectory for each agent. Also an
initialvalue
0
ischosen.
4 The disagreement point da is determined by
maximising the agent cost function as described
earlier.
5 Each agent performs a new search for a feasible
trajectoryforitselfwhilekeepingtheothersfixed.
Thedynamicsofthesystemaretaken careofby
the path finding component.
The search
minimises the agent cost function and
consequently also the augmented cost function.
Thenewtrajectoryfortheownagentmergedwith
theothertrajectoriesofset
0
a
R
formthefirstfull
solution
1
a
R
6 Thefullset
1
a
R
isbroadcastedtoallotheragents
inthe neighbourhood. After this step each agent
hasonefullsolutionfromeachotheragent.
7 In a while loop the following steps are repeated
until the new planned trajectory at step t is less
differentfromthepreviouslyplannedatstept–1
byadefinedɛ.
8 Theagentssearchineachreceivedtrajectoryseta
new own trajectory, using the path finding
component, while keeping the other trajectories
fixed.Attheendofthissteptheaugmentedcost
function gives an evaluation for each received
solutionset.
9 The agent select
its preferred solution set
t
a
R
fromall setscalculated whichisthe set withthe
lowestaugmentedcost.
10 Thepreferredset
t
a
R
isbroadcastedtoallagents
initsneighbourhoodandanew
a
chosen.
11 Thewhileloopbeginsiftheconditionstillholds.
In the domain it is important to improve best
practises and collision avoidance manoeuvres and
not interfere with operations in a way that
application of the approach supersedes planned
situation handling by legislative institutions. At the
sametimethe
approachshouldbeequallybeneficial
to all vessels. Bargaining as a global decentralised
searchforaglobalNashSolutionisusedtomaximise
the benefits for each vessel in an equal manner, in
this case shorter trajectories. This is considered an
additional incentive to use the system apart from
safety concerns
and similar approaches were used
successfullyinmanydifferentdomainsinthepastas
canbeseeni.e.inMuthoo(1999).Onaship’sbridge
our approach can be used integrated in an ECDIS
systemas anexpertsystem formarinersor it could
be implemented in the ship`s system
for autonomic
collisionavoidance.
6 EVALUATION
Theprocedureiscurrentlyevaluatedinasimulation
environment,implementedbytheHTWG‐Konstanz.
Inthe situation,depictedinfigure5,twosimulated
vessels start approximately 600 meters apart with
speed and heading chosen to lead to a crossing
situationand,ifnothandled,to
acollisioninabout5
minutes. However, the system anticipates the
collisionandsuggestsasmalldetourforbothvessels
which,duetoCOLREGs,could notbe handledthat
wayoncethevesselareinthecrossingsituation,but
whichisamorebeneficialsolutionforboth.Figure5
shows
anongoing optimisation withthetrajectories
stillbeingoptimisedandthedesiredtrajectoryofthe
vesselinthelowerleftcorner,asastraightline.
In the simulation the convergence towards a
globaloptimumcouldbeobserved.Sincetheagents
exchangeeachsetoftrajectoriesinthesimulationin
several rounds,
it could be observed that after the
first trivial solution of straight lines, the path
planning component planned a suboptimal solution
in the sense that each agent tried to avoid the
collision in the assumption that the other agents
would not change its course. In the consequent
rounds, the trajectories
changed gradually towards
the optimal solution of a straight line while
minimising the augmented cost function and the
overalltrajectorylength,asshowninfigure4.Itcan
alsobeshownthatthenegotiationsconvergeafter20‐
30 rounds towards an acceptable solution, and
alternatebetweengoodsolutionsafter5‐10
rounds.
Figure4. Average summed trajectory length in meters for
allvesselsineachnegotiationround
341
Figure5.Twovesseljustbeforeacrossingsituation.
Thestabilityof thesolutionsfoundvaried inthe
beginning because, in contrast to the constraint
penalty and trajectory distance function used by
Waslander (2007), our path finding led a to more
complicated convergence behaviour. Towards a
Pareto optimal solution, each vessel accepted
solutions within a strictly optimising margin,
however within
this margin solutions were
alternating between favourable solutions for each
vessel.
Collisionfreetrajectoriescouldbe foundinmost
of the trials after the first or second round, which
wereconsiderabledetoursbutsafe.Theapproachis
alreadytestedonatestbedonLakeKonstanzusing
pleasure crafts. First
results are in line with the
simulationoutcomes.
7 CONCLUSION
The procedure applies the negotiation schema from
Waslander (2007) in the maritime domain and
utilisesapath‐findingcomponenttoobeyCOLREGs
and include the dynamic model of the ship. The
negotiationconvergestowardsaglobaloptimumby
using local optimisation
and exchanging only
trajectories.Thisleadstoacollisionfreesub‐optimal
solution for all participating vessels afterjusta few
negotiationrounds.
After first promising results from the simulation
the next step is to verify the results in detail in the
testbedsonLakeKonstanzandinthe
eMIRtestbed
at the German Bight for merchant vessels and
measure the impact of currents and changing
situationsonthenegotiationprogress.
REFERENCES
Blaich,M.,RosenfelderM.,SchusterM.,Bittel,O.&Reuter
J. 2012a. Extended Grid Based Collision Avoidance
Considering COLREGs for Vessels. In Proc. of the 9th
IFAC Conference on Manoeuvring and Control of Marine
Craft(MCMC)
Blaich,M.,RosenfelderM.,SchusterM.,Bittel,O.&Reuter
J. 2012b. Fast Grid Based
Collision Avoidance for
VesselsusingA*SearchAlgorithm.InProc.ofthe17th
International Conference on Methods and Models in
AutomationandRobotics(MMAR)
Davis,P.V.,Dove,M.J.&Stockel,C.T.1982.Acomputer
simulation of multi‐ship encounters. Journal of
Navigation35(2):347‐352
Heiskanen, P.
1999. Decentralized method for computing
Pareto solutions in multiparty negotiations. European
JournalofOperationalResearch117(3),578‐590
Inalhan, G., Stipanovic, D. M., & Tomlin, C. J. 2002.
Decentralizedoptimization, withapplication to
multiple aircraft coordination. Proceedings of the 41st
IEEEConferenceonDecisionandControl1147‐1155
Li, X. &
Jilkov, V. 2003. Survey of maneuvering target
tracking.PartI:Dynamicmodels.InIEEETransactions
on,AerospaceandElectronicSystems39(4)
Mu,L.,Kumar,R.,&Prinz,A.2011.Anintegratedwireless
communication architecture for maritime sector.
Multiple Access Communications (pp. 193‐205).
SpringerBerlinHeidelberg
Muthoo, A. 1999. Bargaining
theory with applications.
CambridgeUniversityPress
Schuster, M., Blaich, M. & Reuter J. 2014. Collision
AvoidanceforVesselsusingaLow‐CostRadarSensor.
InProc.ofthe19thIFACWorldCongress
Smierzchalski,R.1999.Evolutionarytrajectoryplanningof
shipsinnavigationtrafficareas.JournalofMarineScience
andTechnology
4(1):1‐6
Szlapczynski, R. 2011. Evolutionary Sets Of Safe Ship
Trajectories:ANewApproachToCollisionAvoidance.
JournalofNavigation64(1):169‐181
Szlapczynski, R. 2012. Evolutionary approach to ship ’ s
trajectory planning within Traffic Separation Schemes.
PolishMaritimeResearch19(1):11‐20
Szlapczynski, R. 2013. Evolutionary Sets of
Safe Ship
TrajectoriesWithin Traffic Separation Schemes.Journal
ofNavigation66(1):65‐81
Szlapczynski, R. 2015 Evolutionary Planning of Safe Ship
Tracks in Restricted Visibility. Journal of Navigation
68(1):39‐51
Szlapczynski,R.&SzlapczynskaJ.2012a.Onevolutionary
computing in multi‐ship trajectory planning. Applied
Intelligence37(2):155‐174
Szlapczynski,R.&SzlapczynskaJ.2012b.EvolutionarySets
of Safe Ship Trajectories: Evaluation of Individuals.
International Journal on Marine Navigation and Safety of
SeaTransportation(TansNav)6(5):345‐353
Waslander, S. L. 2007. Multi‐agent systems design for
aerospace applications (Doctoral dissertation, Stanford
University)