341
1 INTRODUCTION
1.1 Swarmintelligenceanditsapplications
Swarm intelligence (SI) is a dynamically developing
areaofartificialintelligence,inspiredbythecollective
behaviourofanimals(ants,bees,birds,fish)orother
living organisms, such as e.g. bacteria. The first
approachesclassifiedasSImethods,ascanbeseenon
thetimelineinFigure1,startedtoemergeintheearly
1990s. From that time many methods have been
introduced.Mostofthemareinspiredbytheforaging
behaviour, as Ant Colony Optimization (ACO),
ArtificialBeeColonyalgorithm(ABC)orWolfSearch
Algorithm (WSA). Sometimes breeding, such as in
Cuckoo
Search(CS)or FlowerPollinationAlgorithm
(FPA),ormatesfinding,asinFireflyAlgorithm(FA),
constitutes an inspiration. Other shown algorithms
include: Particle Swarm Optimization (PSO),
Differential Evolution (DE), Harmony Search (HS),
Honey Bee Algorithm (HBA) and Virtual Bee
Algorithm(VBA),BatAlgorithm(BA),EagleStrategy
(ES)andKrillHerdAlgorithm
(KHA).
Figure1.Atimelinepresentingthedevelopmentofswarm
intelligenceandbio‐inspiredalgorithms
Swarm intelligence algorithms were initially
applied for solving combinatorial optimization
problems such as traveling salesmen problem or
graph colouring [1,2,3]. Over time more and more
real‐life applications have been developed, such as
e.g.ACOinbioinformaticsforDNAsequencing[4]or
A Nature Inspired Collision Avoidance Algorithm for
Ships
A.Lazarowska
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:Natureinspiredalgorithmsareregardedasapowerfultoolforsolvingreallifeproblems.Theydo
not guarantee to find the globally optimal solution, but can find a suboptimal, robust solution with an
acceptable computationalcost. The paper introducesanapproach tothedevelopmentof
collisionavoidance
algorithms for ships based on the firefly algorithm, classified to the swarm intelligence methods. Such
algorithmsareinspiredbytheswarmingbehaviourofanimals,suchase.g.birds,fish,ants,bees,fireflies.The
descriptionofthedevelopedalgorithmisfollowedbythepresentationofsimulationresults,whichshow,
thatit
might be regarded as an efficient method of solving the collision avoidance problem. Such algorithm is
intendedforuse inthe Decision Support System orin the Collision Avoidance Module of theAutonomous
NavigationSystemforMaritimeAutonomousSurfaceShips.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 17
Number 2
June 2023
DOI:10.12716/1001.17.02.10
342
GA,ACOandPSOformobilerobotpathplanning[5].
Other examples of SI applications include: PSO for
image analysis (face detection) [6], PSO for cancer
classification [7] and CS for the optimization of the
steelstructuredesignprocess[8].AreviewofSIand
bio‐inspiredmethodscanbe
foundin[9].
Examples of applications in regard to ships
include: optimization of ship course controller
parameters based on ACO [10], ship safe trajectory
planninginacollisionsituationbasedonACO[11,12]
and PSO [13], optimization of the parameters of the
shipdynamicsmodelusingACO,PSOand
ABC[14].
In [15] a survey of SI‐based algorithms for USVs
collaborationhasbeenpresented.
1.2 Shipcollisionavoidance
Ascanbeseenfromtheaboveintroducedoverviewof
SI methods, one of their applications is the ship
collisionavoidance problem. This issueisoneof the
maintasksin
theshipnavigationprocess,wherethe
main constraints are static, such as lands, shallows,
buoys, waterways and dynamic obstacles, which
change their position over time. Dynamic obstacles
arecalledtarget ships, whichareencounteredships,
thatmightconstituteacollisionrisktoanownship.
Many approaches for solving the
ship collision
avoidanceproblemwereproposedsince1950s,where
first methods for two‐ship encounters based upon
solvingthetriangleofvelocitiesappeared.Thelatest
algorithmsarebasedupongametheory[16],fuzzyset
theory [17], dynamic programming with neural
constraints [18], evolutionary multi‐objective
optimisation[19],multi‐agentreinforcementlearning
[20], deep reinforcement learning [21], modified
artificialpotentialfield[22]andprobabilisticvelocity
obstaclemethod[23].Safetrajectoriesarethenfedinto
the ship motion control system in order to steer the
ship along the determined path. Examples of recent
ship motion control methods are the Linear Matrix
Inequalities controller
[24], a path controller with
switching approach [25], the actor‐critic time‐delay
controller[26]andthebacksteppingcontroller[27].
2 FIREFLYALGORITHMFORSHIPCOLLISION
AVOIDANCE
2.1 Descriptionofconstructivevspopulationbased
approximatealgorithms
Optimizationalgorithmscanbeclassifiedintooneof
the two groups: exact or approximate approaches.
Swarmintelligencemethodsduetothepropertythat
theydonotguaranteeaglobaloptimum,butallowto
obtain a suboptimal solution at acceptable
computational cost, are classified to the group of
approximate algorithms. An approximate algorithm
can be further classified as constructive, population‐
basedorlocalsearch.Constructivealgorithms
builda
solution by iteratively adding solution components,
until a complete solution is achieved. A population‐
based algorithm starts with an initial population of
individuals (candidate solutions), which is then
evaluatedandmodifiedinordertofindthefinalbest
solution, until the moment, when the termination
condition is met. Local
search algorithms start from
some initial solution and iteratively apply local
changes in order to improve that solution. Local
changes mean the explorationof the neighbourhood
ofthecurrentsolution[28].
2.2 Descriptionofthefireflyalgorithmbackground
Figure2.Thebioluminescencebehaviourofafirefly
TheFireflyAlgorithm(FA)hasbeenintroducedby
Xin‐SheYangin2008[29].Asthenamesuggests,the
algorithm is inspired by the behaviour of fireflies,
which communicate with each other, look for prey
and find mates using bioluminescence.
Bioluminescencemeanstheproductionandemission
oflightbylivingorganisms,
asshowninFigure2.The
mainassumptionsappliedintheFA,inspiredbythe
behaviouroffirefliesinnature,are:
theattractivenessofafireflyisproportionaltoits
brightness,thevalueofbothparametersdecreases
withanincreasingdistancebetweenthefireflies;
foreverypairof
fireflies,thelessbrightfireflywill
bemovingtowardsthebrighterone;
if there is no brighter firefly, it will move
randomly.
Themovementofafireflytowardsthebrighterone
isdefinedbyEquation(1).
2
ij
γr
t1 t t t
ii0 ji
xxβexxαrand0.5
(1)
whereβ
0istheattractivenessatdistancer=0,αisa
parameterintroducingrandomness,randisarandom
numbergeneratoruniformlydistributedin[0,1],r
ijis
thedistancebetweenfirefliesiandj,andγisthelight
absorption coefficient, which determines the
variabilityofattractiveness.Thedistancebetweenany
twofirefliesiandjisdefinedbyEquation(2).
22
ij i j i j
r(xx)(yy)
(1)
343
2.3 Thefireflyalgorithmforsolvingtheshipcollision
avoidance
The flowchart of a firefly algorithm applied for
solvingtheshipcollisionavoidanceproblemisgiven
inFigure3.Theinputdataforthealgorithmarethe
valuesofparametersdescribingthecollisionsituation
atsea,suchas:thecourse
Ψj,thespeedVj,thebearing
N
jandthedistanceDjofthej‐thtargetshipfroman
ownshipandthecurrentcourseΨ
0andthespeedV0
ofanownship.Afterthattherelativecourses,speeds
and bearings of target ships are calculated based on
theinputdata.Inthenextstepdangeroustargetships
are determined by the algorithm. These are target
ships,thatintersecttheircourseswiththecourseofan
own ship and
might pose a collision risk.
Afterwards the specific parameters of a firefly
algorithmareinitialized,such asβ
0,αandγandan
initialpopulationofnfireflies,constitutingcandidate
trajectories, is generated. Light intensity for every
fireflyintheinitialpopulationisthencalculated.The
lightintensity of a firefly describes how good is the
solution defined by the current firefly for the
considered optimization problem. Next,
until the
termination criterion is not fulfilled, the following
stepsarecarriedoutiteratively:
calculation of movement of every firefly towards
thebrighterfireflyaccordingtoEquation(1),
evaluation, whether every firefly is positioned
within the solution space and does not exceed
constraints(staticanddynamicobstacles),
update light intensities of newly obtained
solutions(fireflies),
rank the fireflies and find the current best
trajectory.
Figure3. The flowchart of a firefly algorithm for ship
collisionavoidance
Theterminationcriterionisthemaximumnumber
ofiterations.
3 SIMULATIONRESULTS
Thefireflyalgorithmforshipcollisionavoidancewas
implementedinMatlabandcomparedwithanotherSI
algorithm, based on Ant Colony Optimization. The
flowchart of the ACO algorithm for ship collision
avoidance [30], used in the comparative analysis, is
giveninFigure4.TheappliedACO‐basedalgorithm
can be regarded as a constructive algorithm, as
artificial ants construct their solutions by
probabilistically choosing their next move on the
graph until they reach the final waypoint. For
comparison,appliedfireflyalgorithmisapopulation‐
based algorithm that in a
number of iterations
changes the initial population of fireflies (candidate
trajectories) in order to find the final best solution.
The values of specific parameters of the algorithms
usedinthecalculationsaregiveninTable1.Thesafe
distancebetweentheshipsinthecollisionavoidance
processisassuredbythe
shipdomainaroundtarget
ships.Ahexagondomainwasusedinthecarried‐out
simulationtests,butothershapesmightalsobeused,
dependingontheuserʹspreferences.Thedimensions
ofthetargetshipdomainusedinthecalculationsare
asfollows:distancetowardsbow:1.05nm,distanceof
amidships:0.65nm,distancetowardsstarboardside:
0.65 nm, distance towards stern: 0.4 nm, distance
towards port side: 0.4 nm. These are exemplary
dimensions,whichalsocanbechangedaccordingto
theuserʹspreferences.Tables2‐5presentinputdataof
testcaseusedasexamplesforthepresentationin
this
paper. Numerical results are listed in Table 6 and a
graphical presentation of the best trajectories
calculatedbybothalgorithmsaregiveninFigures5‐8.
Figure4. The flowchart of the Ant Colony Optimization‐
basedalgorithmforshipcollisionavoidance
344
Table1.ValuesofACOandFAparametersusedinthe
calculations
________________________________________________
AlgorithmParameters
________________________________________________
ACO α=1,β=2,ρ=0.1,τ0=1,number_of_ants=10,
max_iterations=20
FAβ
0=1,α=0.4,γ=1,number_of_fireflies=10,
max_iterations=50
________________________________________________
FA‐based algorithm calculated slightly shorter
trajectoriesforallofthepresentedtestcases.Therun
timeofthealgorithmwasalsoshorter.Fortestcases
1‐3 manoeuvres determined by both algorithms are
similar,composedofaturntostarboardsideandthen
return to the defined position. Interesting results
mightbenoticedforamorecomplextestcase4with6
encountered ships. For this test case the difference
betweenthetrajectoriescalculatedbybothalgorithms
ismoresignificant.ACO‐basedalgorithmdetermined
atrajectorycomposedofthreecoursechanges,witha
portsideturn,whileFA‐basedalgorithm
calculateda
starboard side manoeuvre, similarly as for the three
other considered scenarios. The difference in length
betweenthetwoproposedtrajectoriesis0.04nautical
mile, but the result of FA‐based algorithm might be
regardedasmorepractical.
Table2.Inputdatafortestcase1with2targetships
________________________________________________
ShipΨ[°] V[kn] N[°] D[NM]
________________________________________________
0 0 12――
1 270 12 45 5
2 270 12 40 7
________________________________________________
Table3.Inputdatafortestcase2with3targetships
________________________________________________
ShipΨ[°] V[kn] N[°] D[NM]
________________________________________________
0 0 12――
1 190 12 5 5
2 270 12 40 7
3 270 10 55 6
________________________________________________
Table4.Inputdatafortestcase3with4targetships
________________________________________________
ShipΨ[°] V[kn] N[°] D[NM]
________________________________________________
0 0 12――
1 180 12 5 5
2 270 14 40 7
3 280 12 55 6
4 220 14 20 4
________________________________________________
Table5.Inputdatafortestcase4with6targetships
________________________________________________
ShipΨ[°] V[kn] N[°] D[NM]
________________________________________________
0 0 14――
1 105 4 340 8
2 180 12 5 5
3 270 14 40 7
4 280 12 55 6
5 220 14 20 4
6 190 8 45 5
________________________________________________
Table6.Resultsofthetwoalgorithmsfortestcases1‐4
________________________________________________
Testcase AlgorithmDistance[nm] Ψ [°]Runtime[s]
________________________________________________
1 FA9.1812,349 0.27
1 ACO 9.2211,346 5.83
2 FA9.217,352 0.69
2 ACO 9.259,342 5.21
3 FA9.6124,342 0.86
3 ACO 9.8622,333 8.04
4 FA9.9328,337 3.22
4 ACO 9.97333,18,315 7.48
________________________________________________
Figure5. Comparison of safe trajectories calculated by the
twoalgorithmsfortestcase1
Figure6. Comparison of safe trajectories calculated by the
twoalgorithmsfortestcase2
Figure7. Comparison of safe trajectories calculated by the
twoalgorithmsfortestcase3
345
Figure8. Comparison of safe trajectories calculated by the
twoalgorithmsfortestcase4
4 CONCLUSIONS
The paper introduced an algorithm for solving the
ship collision avoidance problem based one of the
swarm intelligence methods – the firefly algorithm.
Simulation results proved, that the firefly algorithm
forshipcollision avoidanceiscapableofsolvingthe
task in up to a few seconds, what is a
reasonable
amount of time for that process. Results compared
withtheACO‐based algorithmshow,thatthefirefly
algorithm obtains shorter trajectories within shorter
calculation time. Therefore, the algorithm might
constitute a competitive approach in the group of
non‐deterministicmethods.Safetrajectoryplanningis
avitaltaskinthe
navigationofships.Suchalgorithms
might be applied as a decision support tool on
manned ships or as a part of an autonomous
navigationsystemofunmannedorfullyautonomous
vessels. Future research direction might concern
different algorithms applied for solving the safe
trajectory planning problem, running in parallel, in
order
to finally propose the best solution for the
consideredcollisionsituation.Futureresearchshould
alsoregardevaluationofthealgorithmswiththeuse
ofscenarioswithstaticobstaclesandotherwaterway‐
relatedconstraints.
REFERENCES
[1]M.DorigoandL.M.Gambardella,ʺAntcoloniesforthe
travelling salesman problem,ʺ Biosystems, Vol. 43 (2),
pp.73‐81,1997,doi:10.1016/S0303‐2647(97)01708‐5.
[2]H.HernándezandC.Blum,ʺDistributedgraphcoloring:
an approach based on the callingbehavior of Japanese
treefrogs,ʺSwarmIntelligence,vol.6,pp.
117–150,2012,
doi:10.1007/s11721‐012‐0067‐2.
[3]D.KarabogaandB.Gorkemli,ʺAcombinatorialArtificial
BeeColonyalgorithm fortravelingsalesmanproblem,ʺ
2011 International Symposium on Innovations in
Intelligent Systems and Applications, Istanbul, Turkey,
2011,pp.50‐53,doi:10.1109/INISTA.2011.5946125.
[4]C. Blum, M. Yabar and M. J. Blesa,ʺ
An ant colony
optimization algorithm for DNA sequencing by
hybridization,ʺComputers&OperationsResearch,Vol.
35, No. 11, pp. 3620–3635, 2008, doi:
10.1016/j.cor.2007.03.007.
[5]T.T.Mac,C.Copot,D.T.Tran,R.DeKeyser,ʺHeuristic
approachesinrobotpathplanning:Asurvey,ʺRobotics
andAutonomousSystems,Vol.86,pp.13‐28,2016,
doi:
10.1016/j.robot.2016.08.001.
[6]M.SugisakaandX.Fan,ʺAneffectivesearchmethodfor
NN‐basedfacedetectionusingPSO,ʺSICE2004Annual
Conference,Sapporo,Japan,2004,pp.2742‐2745,vol.3.
[7]R. Xu, G. C. Anagnostopoulos and D. C. Wunsch,
ʺMulticlass cancer classification using semi‐supervised
ellipsoidart‐map
andparticleswarmoptimizationwith
gene expression data,ʺ in The IEEE/ACM Transactions
onComputationalBiologyandBioinformatics,pp.65–
77,2007.
[8]A.Kaveh,T.BakhshpooriandM.Ashoory,ʺAnefficient
optimization procedure based on cuckoo search
algorithm for practical design of steel structures,ʺ
International Journal of Optimization in
Civil
Engineering,Vol.2,pp.1‐14,2012.
[9]X.‐S. Yang, Z. Cui, R. Xiao, A. H. Gandomi and M.
Karamanoglu,Eds.,SwarmIntelligenceandBio‐Inspired
Computation: Theory and Applications (1st. ed.).
Netherlands:ElsevierSciencePublishersB.V.,2013.
[10]M.Tomera,ʺAntcolonyoptimizationalgorithmapplied
to ship
steering control,ʺ Procedia Computer Science,
Vol. 35, pp. 83‐92, Proceedings of the 18th Annual
Conference on Knowledge‐Based and Intelligent
Information & Engineering Systems, KES‐2014 Gdynia,
Poland, September 15‐17, 2014, doi:
10.1016/j.procs.2014.08.087.
[11]M. C. Tsou and C. K. Hsueh,ʺThe study of ship
collision avoidance route
planning by ant colony
algorithm,ʺ Journal of Marine Science and Technology,
Vol. 18 (5), pp. 746–756, 2010, doi: 10.51400/2709‐
6998.1929.
[12]A.Lazarowska,ʺShip’strajectoryplanningforcollision
avoidance at sea based on ant colony optimisation,ʺ
Journal of Navigation, Vol. 68, pp. 291–307, 2015, doi:
10.1017/S0373463314000708.
[13]C.Li‐Jiaand
H.Li‐Wen,ʺShipCollisionAvoidancePath
Planning by PSO Based on Maneuvering Equation,ʺ in
Future Wireless Networks and Information Systems,
Lecture Notes in Electrical Engineering, Vol. 144, Y.
Zhang, Ed., Springer, Berlin, Heidelberg, 2012,
doi:10.1007/978‐3‐642‐27326‐1_87.
[14]M. Tomera,ʺSwarm intelligence applied to
identification of nonlinear
ship steering model,ʺ 2015
IEEE 2nd International Conference on Cybernetics
(CYBCONF), Gdynia, Poland, 2015, pp. 133‐139, doi:
10.1109/CYBConf.2015.7175920.
[15]G.Wu,T.Xu,Y.SunandJ.Zhang,ʺReviewofmultiple
unmanned surface vessels collaborative search and
hunting based on swarm intelligence,ʺ International
Journal of Advanced Robotic Systems, Vol. 19(2),
2022,
doi:10.1177/17298806221091885.
[16]J. Lisowski,ʺReview of Ship Collision Avoidance
GuidanceAlgorithmsUsingRemoteSensingandGame
Control,ʺ Remote Sensing, Vol. 14, pp. 4928, 2022,
doi:10.3390/rs14194928.
[17]M.Mohamed‐Seghir,K.KulaandA.Kouzou,ʺArtificial
Intelligence‐Based Methods for Decision Support to
Avoid Collisions at Sea,ʺ Electronics, Vol. 10(19),
pp.
2360,2021,doi:10.3390/electronics10192360.
[18]J.Lisowski,ʺArtificialIntelligenceMethodsinSafeShip
ControlBasedonMarineEnvironmentRemoteSensing,ʺ
Remote Sensing, Vol. 15, pp. 203, 2023,
doi:10.3390/rs15010203.
[19]R. Szłapczyński and H. Ghaemi,ʺFramework of an
Evolutionary Multi‐Objective Optimisation Method for
Planning a Safe Trajectory for a
Marine Autonomous
346
Surface Ship,ʺ Polish Maritime Research, Vol.26 (Issue
4),pp.69‐79,2019,doi:10.2478/pomr‐2019‐0068.
[20]G.WeiandW.Kuo,ʺCOLREGs‐CompliantMulti‐Ship
Collision Avoidance Based on Multi‐Agent
Reinforcement Learning Technique,ʺ Journal of Marine
Science and Engineering, Vol. 10(10), pp. 1431, 2022,
doi:10.3390/jmse10101431.
[21]L. Jiang, L. An,
X. Zhang, C. Wang and X. Wang,ʺA
human‐likecollisionavoidancemethodforautonomous
shipwithattention‐baseddeepreinforcementlearning,ʺ
Ocean Engineering, Vol. 264, pp. 112378, 2022, doi:
10.1016/j.oceaneng.2022.112378.
[22]Z.Zhu,H.Lyu,J.ZhangandY.Yin,ʺAnEfficientShip
Automatic Collision Avoidance Method Based on
Modified Artificial Potential Field,ʺ Journal of Marine
Science and Engineering, Vol. 10(1), pp. 3, 2022, doi:
10.3390/jmse10010003.
[23]Y. Cho, J. Han and J. Kim,ʺEfficient COLREG‐
CompliantCollisionAvoidanceinMulti‐ShipEncounter
Situations,ʺ in IEEE Transactions on Intelligent
Transportation Systems, vol. 23, no. 3, pp. 1899‐1911,
March2022,
doi:10.1109/TITS.2020.3029279.
[24]M.RybczakandK.Podgórski,ʺParetoEffectofLMIfor
Ship Propulsion,ʺ Applied Sciences, Vol. 11(16), pp.
7297,2021,doi:10.3390/app11167297.
[25]M. Tomera,ʺPath Controller for Ships with Switching
Approach,ʺ in Advanced, Contemporary Control.
Advances in Intelligent Systems and Computing, Vol.
1196, A. Bartoszewicz, J. Kabziński,
J. Kacprzyk, Eds.,
Springer, Cham, 2020, doi:10.1007/978‐3‐030‐50936‐
1_126.
[26]H. N. Esfahani and R. Szlapczynski,ʺRobust‐adaptive
dynamic programming‐based time‐delay control of
autonomous ships under stochastic disturbances using
an actor‐critic learning algorithm,ʺJournal of Marine
Science and Technology, Vol. 26, pp. 1262–1279, 2021,
doi:10.1007/s00773‐021
‐00813‐1.
[27]A. Witkowska and T. Rynkiewicz,ʺDynamically
Positioned Ship Steering Making Use of Backstepping
Method and Artificial Neural Networks,ʺ Polish
Maritime Research, Vol. 25(4) pp. 5‐12, 2018,
doi:10.2478/pomr‐2018‐0126.
[28]M. Dorigo and T. Stützle, Ant Colony Optimization.
Cambridge, Massachusetts,London, England: The MIT
Press,2004.
[29]XS. Yang,ʺFirefly Algorithms for Multimodal
Optimization,ʺ in Stochastic Algorithms: Foundations
and Applications, SAGA 2009, Lecture Notes in
Computer Science, Vol. 5792, O. Watanabe, T.
Zeugmann, Eds., Springer, Berlin, Heidelberg, 2009,
doi:10.1007/978‐3‐642‐04944‐6_14.
[30]A.Lazarowska,ʺShipʹsTrajectoryPlanningforCollision
Avoidance at Sea Based on
Ant Colony Optimisation,ʺ
TheJournalofNavigation,Vol.68(2),pp.291‐307,2015,
doi:10.1017/S0373463314000708.
