{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:07:47Z","timestamp":1760710067714,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"24","license":[{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wy\u017cszego","doi-asserted-by":"publisher","award":["WZ\/WI\/1\/19 and 1\/S\/ITM\/16"],"award-info":[{"award-number":["WZ\/WI\/1\/19 and 1\/S\/ITM\/16"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>The biggest challenges in the maritime environment are accidents and excessive fuel consumption. In order to improve the safety of navigation at sea and to reduce fuel consumption, the strategy of anti-collision, shortest trajectory planning is proposed. The strategy described in this paper is based on the beam search method. The beam search algorithm (BSA) takes into account many safe trajectories for the present ship and chooses the best in terms of length and other criteria. The risk of collision of present ship with any target ships is detected when the closest point of approach (CPA) of the present ship is violated by the target ship\u2019s planned trajectory. Only course alteration of the present ship is applied, and not speed alteration. The algorithm has been implemented in the decision support system NAVDEC and tested in a real navigation environment on the m\/f Wolin, a Polish ferry. Almost all BSA trajectories calculated were shorter in comparison to the standard NAVDEC-calculated algorithm.<\/jats:p>","DOI":"10.3390\/s19245338","type":"journal-article","created":{"date-parts":[[2019,12,5]],"date-time":"2019-12-05T03:16:36Z","timestamp":1575515796000},"page":"5338","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Beam Search Algorithm for Ship Anti-Collision Trajectory Planning"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5241-7930","authenticated-orcid":false,"given":"Joanna","family":"Karbowska-Chilinska","sequence":"first","affiliation":[{"name":"Faculty of Computer Science, Bialystok University of Technology, 15-351 Bialystok, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jolanta","family":"Koszelew","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Bialystok University of Technology, 15-351 Bialystok, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof","family":"Ostrowski","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Bialystok University of Technology, 15-351 Bialystok, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Kuczynski","sequence":"additional","affiliation":[{"name":"Unity Developer, The Dust; 50-043 Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Kulbiej","sequence":"additional","affiliation":[{"name":"R&amp;D Department, Sup4Nav sp. z o.o.; 71-602 Szczecin, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Wolejsza","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science and Telecommunication, Maritime University of Szczecin, 70-500 Szczecin, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,4]]},"reference":[{"key":"ref_1","unstructured":"EMSA\u2014European Maritime Safety Agency (2019, September 24). Annual Overview of Marine Casualties and Incidents 2018. Available online: http:\/\/www.emsa.europa.eu\/emsa-documents\/latest\/item\/3406-annual-overview-of-marine-casualties-and-incidents-2018.html."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1017\/S0373463308005134","article-title":"Review of collision avoidance and path planning methods for ships in close range encounters","volume":"62","author":"Tam","year":"2009","journal-title":"J. Navig."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Melhaoui, Y., Allal, A.A., Kamil, A., Mansouri, K., and Rachik, M. (2019, January 25\u201326). Toward an overview of ship collision avoidance maneuvers approaches in compliance with COLREG convention. Proceedings of the 5th International Conference on Optimization and Applications, Kenitra, Morocco.","DOI":"10.1109\/ICOA.2019.8727687"},{"key":"ref_4","unstructured":"(2019, September 24). Convention on the International Regulations for Preventing Collisions at Sea. Available online: http:\/\/www.imo.org\/en\/OurWork\/Safety\/Navigation\/Pages\/Preventing-Collisions.aspx."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.oceaneng.2018.03.073","article-title":"Towards a decision support system for maritime navigation on heavily trafficked basins","volume":"159","author":"Montewka","year":"2018","journal-title":"Ocean Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1017\/S0373463316000746","article-title":"Decision Support in Collision Situations at Sea","volume":"70","author":"Pietrzykowski","year":"2017","journal-title":"J. Navig."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1016\/j.eswa.2016.11.005","article-title":"A New Deterministic Approach in a Decision Support System for Ship\u2019s Trajectory Planning","volume":"71","author":"Lazarowska","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.oceaneng.2012.09.003","article-title":"Cooperative Path Planning Algorithm for Marine Surface Vessels","volume":"57","author":"Tam","year":"2013","journal-title":"Ocean Eng."},{"key":"ref_9","first-page":"1","article-title":"Multiobjective Optimization Based Vessel Collision Avoidance Strategy Optimization","volume":"2014","author":"Xu","year":"2014","journal-title":"Math Probl. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10489-011-0319-7","article-title":"On evolutionary computing in multi-ship trajectory planning","volume":"37","author":"Szlapczynski","year":"2014","journal-title":"Appl. Intell."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.oceaneng.2016.05.040","article-title":"Multi-Target collision avoidance route planning under ECDIS framework","volume":"121","author":"Tsou","year":"2016","journal-title":"Ocean Eng."},{"key":"ref_12","first-page":"746","article-title":"The study of ship collision avoidance route planning by ant colony algorithm","volume":"18","author":"Tsau","year":"2010","journal-title":"J. Mar. Sci. Tech."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.12716\/1001.11.01.02","article-title":"Multi-criteria ACO-based algorithm for the ship\u2019s trajectory planning","volume":"11","author":"Lazarowska","year":"2017","journal-title":"TransNav J."},{"key":"ref_14","first-page":"777","article-title":"Collision avoidance path planning for ships by particle swarm optimization","volume":"26","author":"Kang","year":"2018","journal-title":"J. Mar. Sci. Tech."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Borkowski, P. (2018). The Ship Movement Trajectory Prediction Algorithm Using Navigational Data Fusion. Sensors, 17.","DOI":"10.3390\/s17061432"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Lisowski, J. (2019). Sensitivity of Safe Trajectory in a Game Environment on Inaccuracy of Radar Data in Autonomous Navigation. Sensors, 19.","DOI":"10.3390\/s19081816"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.ifacol.2016.10.344","article-title":"A Reactive COLREGs-Compliant Navigation Strategy for Autonomous Maritime Navigation","volume":"49","author":"Naeem","year":"2016","journal-title":"IFAC-PapersOnline"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kulbiej, E. (2018, January 21\u201323). Autonomous Vessels\u2019 Pathfinding Using Visibility Graph. Proceedings of the 2018 Baltic Geodetic Congress (BGC Geomatics), Olsztyn, Poland.","DOI":"10.1109\/BGC-Geomatics.2018.00026"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.oceaneng.2019.05.017","article-title":"A multilayer path planner for a USV under complex marine environments","volume":"184","author":"Wang","year":"2019","journal-title":"Ocean Eng."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1017\/S0373463318000796","article-title":"COLREGS-constrained real-time path planning for autonomous ships using modified artificial potential fields","volume":"72","author":"Lyu","year":"2018","journal-title":"J. Navig."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1017\/S0373463312000483","article-title":"A novel analytical framework for dynamic quaternion ship domains","volume":"66","author":"Wang","year":"2013","journal-title":"J. Navig."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.oceaneng.2017.09.020","article-title":"Review of ship safety domains: Models and applications","volume":"145","author":"Szlapczynski","year":"2017","journal-title":"Ocean Eng."},{"key":"ref_23","unstructured":"Zhang, W. (1999). State-Space Search: Algorithms, Complexity, Extensions, and Applications, Springer."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Wo\u0142ejsza, P. (2015, January 13\u201316). Implementation of Decision Support System on m\/f Wolin. Proceedings of the Federated Conference on Computer Science and Information Systems, Lodz, Poland.","DOI":"10.15439\/2015F153"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kulbiej, E., and Wo\u0142ejsza, P. (2016). An analysis of possibilities how the collision between m\/v \u2018Baltic Ace\u2019 and m\/v \u2018Corvus J\u2019 could have been avoided. Annu. Navig., 121\u2013134.","DOI":"10.1515\/aon-2016-0008"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wo\u0142ejsza, P., and Kulbiej, E. (2017, January 21\u201323). Model Research of Navigational Support System Cooperation in Collision Scenario, Marine Navigation. Proceedings of the 12th International Conference on Marine Navigation and Safety of Sea Transportation (TransNav 2017), Gdynia, Poland.","DOI":"10.1201\/9781315099132-23"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kulbiej, E., and Wo\u0142ejsza, P. (2017, January 21\u201323). Naval Artificial Intelligence, Marine Navigation. Proceedings of the 12th International Conference on Marine Navigation and Safety of Sea Transportation (TransNav 2017), Gdynia, Poland.","DOI":"10.1201\/9781315099132-36"},{"key":"ref_28","first-page":"90","article-title":"Fundamental principles of passage planning for autonomous vessels","volume":"52","author":"Kulbiej","year":"2017","journal-title":"Sci. J. Marit. Univ. Szczec."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Koszelew, J., Wolejsza, P., and Oldziej, D. (2018, January 21\u201323). Autonomous Vessel with an Air Look. Proceedings of the 2018 Baltic Geodetic Congress (Geomatics), University of Warmia and Mazury in Olsztyn, Olsztyn, Poland.","DOI":"10.1109\/BGC-Geomatics.2018.00025"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1515\/aon-2017-0022","article-title":"Determination of the Last Moment Manoeuvre for Collision Avoidance Using Standards for Ships Manoeuvrability","volume":"24","author":"Koszelew","year":"2017","journal-title":"Annu. Navig."},{"key":"ref_31","unstructured":"(2019, September 24). Project Semi-Autonomous Coaster. Available online: http:\/\/stocznia-szczecinska.pl\/en\/semi-autonomous-coaster\/."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1017\/S0373463315000223","article-title":"Analysis of Collision Threat Parameters and Criteria","volume":"68","author":"Lenart","year":"2015","journal-title":"J. Navig."},{"key":"ref_33","unstructured":"Cain, F., and Turner, M. (2019, September 24). New Ships, Old Rules: Updating IMO Rules to Cover Autonomous Ships. Available online: http:\/\/www.roboticslawjournal.com\/analysis\/new-ships-old-rules-updating-imo-rules-to-cover-autonomous-ships-56804504."},{"key":"ref_34","unstructured":"Noma, T. (2016). Existing conventions and unmanned ships\u2013need for changes?. [Master\u2019s Thesis, World Maritime University]."},{"key":"ref_35","unstructured":"Baldauf, M., Mehdi, R.A., Fonseca, T., and Kitada, M. (2019, September 24). Conventional Vessels and Marine Autonomous Surface Ships\u2013A Love Marriage? Autonomous Shipping in Inland Navigation. Available online: https:\/\/www.unece.org\/fileadmin\/DAM\/trans\/doc\/2018\/sc3wp3\/10._WMU.pdf."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1222","DOI":"10.1002\/rob.21900","article-title":"The branching-course MPC algorithm for maritime collision avoidance","volume":"36","author":"Eriksen","year":"2019","journal-title":"J. Field Robot."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Brekke, E.F., Wilthil, E.F., Eriksen, B.-O.H., Kufoalor, D.K.M., Helgesen, K., Hagen, I.B., Breivik, M., and Johansen, T.A. (2019). The Autosea project: Developing closed-loop target tracking and collision avoidance systems. J. Phys. Conf. Ser., 1357.","DOI":"10.1088\/1742-6596\/1357\/1\/012020"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/24\/5338\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:39:59Z","timestamp":1760189999000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/24\/5338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":37,"journal-issue":{"issue":"24","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["s19245338"],"URL":"https:\/\/doi.org\/10.3390\/s19245338","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2019,12,4]]}}}