{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T13:15:38Z","timestamp":1779196538007,"version":"3.51.4"},"reference-count":52,"publisher":"MDPI AG","issue":"15","license":[{"start":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T00:00:00Z","timestamp":1595548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100005033","name":"Politechnika Bialostocka","doi-asserted-by":"publisher","award":["WZ\/WI\/1\/19"],"award-info":[{"award-number":["WZ\/WI\/1\/19"]}],"id":[{"id":"10.13039\/501100005033","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Akademia Morska w Szczecinie","award":["1\/S\/ITM\/16"],"award-info":[{"award-number":["1\/S\/ITM\/16"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>A single anti-collision trajectory generation problem for an \u201cown\u201d vessel only is significantly different from the challenge of generating a whole set of safe trajectories for multi-surface vehicle encounter situations in the open sea. Effective solutions for such problems are needed these days, as we are entering the era of autonomous ships. The article specifies the problem of anti-collision trajectory planning in many-to-many encounter situations. The proposed original multi-surface vehicle beam search algorithm (MBSA), based on the beam search strategy, solves the problem. The general idea of the MBSA involves the application of a solution for one-to-many encounter situations (using the beam search algorithm, BSA), which was tested on real automated radar plotting aid (ARPA) and automatic identification system (AIS) data. The test results for the MBSA were from simulated data, which are discussed in the final part. The article specifies the problem of anti-collision trajectory planning in many-to-many encounter situations involving moving autonomous surface vehicles, excluding Collision Regulations (COLREGs) and vehicle dynamics.<\/jats:p>","DOI":"10.3390\/s20154115","type":"journal-article","created":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T09:06:09Z","timestamp":1595581569000},"page":"4115","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Beam Search Algorithm for Anti-Collision Trajectory Planning for Many-to-Many Encounter Situations with Autonomous Surface Vehicles"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1315-8926","authenticated-orcid":false,"given":"Jolanta","family":"Koszelew","sequence":"first","affiliation":[{"name":"Faculty of Computer Science, Bialystok University of Technology, 15-351 Bialystok, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5241-7930","authenticated-orcid":false,"given":"Joanna","family":"Karbowska-Chilinska","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":"Kuczy\u0144ski","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":"Wo\u0142ejsza","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":[[2020,7,24]]},"reference":[{"key":"ref_1","first-page":"269","article-title":"On the future of maritime transport \u00e2 discussing terminology and timeframes","volume":"13","author":"Hult","year":"2019","journal-title":"TransNav Int. J. Mar. Navig. Saf. Sea Transp."},{"key":"ref_2","unstructured":"(2020, April 04). MUNIN-Concept Study for Unmanned Bulk Ship. Available online: http:\/\/www.unmanned-ship.org\/munin\/."},{"key":"ref_3","unstructured":"(2020, April 04). Milli-Ampere: Autonomous Passenger Ferry. Available online: https:\/\/www.nrk.no\/trondelag\/foreslar-forerlos-passasjerferge-i-trondheim-1.12990523."},{"key":"ref_4","unstructured":"(2020, April 04). Concept Development Autonomous Passengzer Ferry Ballstad. Available online: https:\/\/www.lofotenmatpark.no\/portefoljer\/53-forstudium-autonom-ferge-ballstadlandet-ballstadoya."},{"key":"ref_5","unstructured":"(2020, April 04). ASTAT-Autonomous Ship Transport at Trondheimsfjorden. Available online: http:\/\/astat.autonomous-ship.org\/."},{"key":"ref_6","unstructured":"(2020, April 04). Enable Autonomous Navigation in Close Proximity. Available online: https:\/\/www.kongsberg.com\/maritime\/about-us\/news-and-media\/news-archive\/2018\/kongsberg-coordinates-eu-funded-project-to-enable-autonomous-navigation-in-close?OpenDocument."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"012020","DOI":"10.1088\/1742-6596\/1357\/1\/012020","article-title":"The Autosea project: Developing closed-loop target tracking and collision avoidance systems","volume":"1357","author":"Brekke","year":"2019","journal-title":"J. Phys. Conf. Ser."},{"key":"ref_8","unstructured":"(2020, April 04). Yara Birkeland. Available online: https:\/\/www.yara.com\/news-and-media\/press-kits\/yara-birkeland-press-kit\/."},{"key":"ref_9","unstructured":"(2020, April 04). AAWA-The Advanced Autonomous Waterborne Applications. Available online: https:\/\/www.rolls-royce.com\/media\/press-releases\/2016\/21-06-2016-rr-publishes-vision-of-the-future-of-remote-and-autonomous-shipping.aspx."},{"key":"ref_10","unstructured":"(2020, April 04). AVA\u2013Autonomous Vessel with an Air Look. Available online: https:\/\/www.avalproject.pl."},{"key":"ref_11","unstructured":"(2020, April 04). HYDRO DRONE-Marine Technology sp. z o.o., Poland. Available online: http:\/\/www.marinetechnology.pl\/hydrodron.html."},{"key":"ref_12","unstructured":"(2020, April 04). Albatros-Autonomous Underwater Vehicle, Gda\u0144sk University of Technology. Available online: https:\/\/oio.pg.edu.pl\/documents\/213057\/104cb930-9567-415b-9441-faa73f972874."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Karbowska-Chilinska, J., Koszelew, J., Ostrowski, K., Kuczynski, P., Kulbiej, E., and Wolejsza, P. (2019). Beam search Algorithm for ship anti-collision trajectory planning. Sens. Spec. Issue Sens. Syst. Veh. Navig., 19.","DOI":"10.3390\/s19245338"},{"key":"ref_14","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_15","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_16","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_17","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_18","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_19","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_20","first-page":"31","article-title":"Multi-criteria ACO-based algorithm for the ship\u2019s trajectory planning","volume":"11","author":"Lazarowska","year":"2017","journal-title":"TransNav Int. J. Mar. Navig. Saf. Sea Transp."},{"key":"ref_21","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_22","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_23","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_24","first-page":"207","article-title":"A reactive COLREGs-compliant navigation strategy for autonomous maritime navigation","volume":"49","author":"Naeem","year":"2016","journal-title":"IFAC Pap."},{"key":"ref_25","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_26","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_27","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_28","doi-asserted-by":"crossref","unstructured":"Lyu, H., and Yin, Y. (2018). Fast path planning for autonomous ships in restricted waters. Appl. Sci., 8.","DOI":"10.3390\/app8122592"},{"key":"ref_29","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_30","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_31","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1017\/S0373463300022384","article-title":"Traffic capacity","volume":"24","author":"Fujii","year":"1971","journal-title":"J. Navig."},{"key":"ref_32","first-page":"97","article-title":"The combination of analytical and statistical method to define polygonal ship domain and reflect human experiences in estimating dangerous area","volume":"4","author":"Dinh","year":"2016","journal-title":"Int. J. E-Navig. Marit. Econ."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1017\/S0373463315000533","article-title":"An empirically-calibrated ship domain as a safety criterion for navigation in confined waters","volume":"69","author":"Wang","year":"2016","journal-title":"J. Navig."},{"key":"ref_34","first-page":"223","article-title":"Evolutionary sets of safe ship trajectories: The method\u2019s development and selected research results","volume":"XXIII","year":"2011","journal-title":"Arch. Transp."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1017\/S0373463312000422","article-title":"Evolutionary sets of safe ship trajectories within traffic separation schemes","volume":"66","year":"2013","journal-title":"J. Navig."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"69","DOI":"10.2478\/pomr-2019-0068","article-title":"Framework of an evolutionary multi-objective optimisation method for planning a safe trajectory for a marine autonomous surface ship","volume":"26","author":"Ghaemi","year":"2019","journal-title":"Pol. Marit. Res."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"106436","DOI":"10.1016\/j.oceaneng.2019.106436","article-title":"COLREGs-compliant multi-ship collision avoidance based on deep reinforcement learning","volume":"191","author":"Zhao","year":"2019","journal-title":"Ocean Eng."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"30","DOI":"10.2478\/pomr-2019-0004","article-title":"Universal autonomous control and management system for multipurpose unmanned surface vessel","volume":"26","author":"Stateczny","year":"2019","journal-title":"Pol. Marit. Res."},{"key":"ref_39","unstructured":"(2020, April 04). Navigation Decision Support System-NAVDEC. Available online: https:\/\/www.navdec.com."},{"key":"ref_40","unstructured":"(2020, April 04). W\u00e4rtsil\u00e4 Vessel Traffic Services. Available online: https:\/\/www.wartsila.com\/marine\/optimise\/ship-traffic-control-solutions\/vessel-traffic-services."},{"key":"ref_41","first-page":"1","article-title":"Autonomous unmanned merchant vessel and its contribution towards the e-navigation","volume":"1","author":"Burmeister","year":"2014","journal-title":"Int. J. E-Navig. Marit. Econ."},{"key":"ref_42","unstructured":"Chong, J.C. (2018). Impact of maritime autonomous surface ships (MASS) on VTS operations. [Master\u2019s Thesis, World Maritime University]."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"(2019). Ulku Ozturk; Kadir Cicek, Individual collision risk assessment in ship navigation: A systematic literature review. Ocean Eng., 180, 130\u2013143.","DOI":"10.1016\/j.oceaneng.2019.03.042"},{"key":"ref_44","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, Gdynia, Poland.","DOI":"10.1201\/9781315099132-23"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1513","DOI":"10.1016\/j.cor.2008.02.003","article-title":"A beam search algorithm for the circular packing problem","volume":"36","author":"Akeb","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/S0377-2217(98)00319-1","article-title":"Job shop scheduling with beam search","volume":"114","author":"Sabuncuoglu","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_47","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_48","unstructured":"(2020, May 27). Simulation Results repository. Available online: https:\/\/chilan.com\/mbsaships20.mp4."},{"key":"ref_49","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_50","unstructured":"(2020, May 27). Polsteam. Available online: https:\/\/www.polsteam.com."},{"key":"ref_51","unstructured":"(2020, May 27). Foundation for Safety of Navigation and Environment Protection in I\u0142awa. Available online: www.ilawashiphandling.com.pl."},{"key":"ref_52","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, Olsztyn, Poland.","DOI":"10.1109\/BGC-Geomatics.2018.00025"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/15\/4115\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:51:21Z","timestamp":1760176281000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/15\/4115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,24]]},"references-count":52,"journal-issue":{"issue":"15","published-online":{"date-parts":[[2020,8]]}},"alternative-id":["s20154115"],"URL":"https:\/\/doi.org\/10.3390\/s20154115","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,24]]}}}