Path planning and collision avoidance for autonomous surface vehicles I: a review

Autonomous surface vehicles are gaining increasing attention worldwide due to the potential benefits of improving safety and efficiency. This has raised the interest in developing methods for path planning that can reduce the risk of collisions, groundings, and stranding accidents at sea, as well as costs and time expenditure. In this paper, we review guidance, and more specifically, path planning algorithms of autonomous surface vehicles and their classification. In particular, we highlight vessel autonomy, regulatory framework, guidance, navigation and control components, advances in the industry, and previous reviews in the field. In addition, we analyse the terminology used in the literature and attempt to clarify ambiguities in commonly used terms related to path planning. Finally, we summarise and discuss our findings and highlight the potential need for new regulations for autonomous surface vehicles.

Research into path planning and collision avoidance (COLAV) algorithms for autonomous surface vehicles (ASVs) is motivated by continuing efforts to optimise operations and improve operational safety and performance. The general premise is that introducing higher levels of autonomy can reduce accidents, fuel costs, and operational costs (including crew), and improve regularity by reducing the frequency and consequence of human errors. To illustrate, the Annual Overview of Marine Casualties and Incidents 2019 [1] developed by the European Maritime Safety Agency (EMSA) states that in 2011–2018, more than 54% of all casualties with ships were navigational casualties—a combination of contact (15.3%), collision (26.2%) and grounding/stranding (12.9%) accidents. Moreover, from a total of 4104 accident events analysed during the investigations, 65.8% were attributed to human erroneous actions. Statistics also show that 41.7% of all casualties took place in port areas, followed by 27.4% in the coastal areas (territorial sea). These numbers indicate an increased collision risk when navigating in congested waters with several static and dynamic obstacles. The aforementioned high percentage of navigational casualties (54.4%) and attribution to human erroneous actions (65.8%) for human-controlled ships can likely be reduced by introducing autonomy in the operation of surface vessels. In addition, autonomous vessels are well suited for missions in dangerous and rough sea environments, for example by better real-time decision-making or in the case of unmanned vessels, removing the risk of human lives. On the other side, increased autonomy is also associated with several important challenges related to operation in open, coastal, and congested waters, energy consumption, environmental abnormalities, personnel requirements, and national security issues that need to be considered.

The autonomous ship market is expected to grow at a fast rate in the near future. According to Global Autonomous Ship and Ocean Surface Robot Market: Analysis and Forecast, 2018–2028, a market intelligence report by BIS Research [2], “the autonomous ship market in terms of volume is expected to grow at the rate of 26.7% during the period 2024–2035 and cumulatively generate a revenue of $3.48 billion by 2035.” Hence, we expect to see an increased demand for the development of autonomous systems technology in the maritime industry, and for ships in particular.

To enable safer systems on waters with increased autonomy requires development of improved and reliable guidance, navigation and control (GNC) systems. The focus of this paper is on guidance systems, and more precisely on path planning and collision avoidance algorithms. Looking at the research done in the field so far, it is of our interest to address the ambiguities in the terminology, investigate the regulatory framework associated with autonomous vessels, and decompose the GNC system of an ASV to review different types of path planning algorithms. Our research aims at summarising the main components that need to be considered when developing a path planning and/or collision avoidance algorithm, based on information available up to date. Whereas much of what we present is general across vessel size, other considerations will differ whether the vessel is a small boat or a large ship. In such cases, the reader should note that larger ships are our main focus.

The three main contributions of this paper can be summarised as follows: (i) an elucidation and clarification of terminology related to surface vessels and guidance systems; (ii) an analysis of the existing regulatory framework for ASVs; and (iii) a suggestion for classifying path planning algorithms. Thus, our work should be of interest for investigators and developers of intelligent algorithms for path planning and collision avoidance for ASVs. Indeed, in an accompanying article in this journal [3], we extend the classification scheme presented here, and analyse and classify algorithms presented in 45 different peer-reviewed scientific papers.

The remainder of this paper is organised as follows: Sect. 2 presents advantages, challenges, and current development of ASVs, defines terminology used within this scope, and provides an overview of previous survey papers. Section 3 details regulatory guidelines that define autonomy and control safety of ASVs. Section 4 presents the authors’ view on the GNC modules for ASV navigation, from the perspective of path planning and collision avoidance. Section 5 provides our proposed classification of path planning algorithms. Section 6 contains a discussion, and finally, some concluding remarks are drawn in Sect. 7.

This section presents advantages and challenges of ASVs and recent advances in the industry, clarifies some of the terminology used in the literature, and provides an overview of previously published review papers in the field.

Advantages and challenges of ASVs

ASVs have the potential to outperform traditional vessels with regard to safety. An increased adoption of ASVs could lead to a reduction in accidents caused by human erroneous actions, which currently contribute to a large share of ship casualties. However, the advantages of ASVs are not limited only to the safety aspect. Below, we identify some current, and potential future, advantages of ASVs:

• Reduced, or eliminated, need for human control and hence, human errors.
• Longer duration performance and enabling more hazardous missions than manned vehicles.
• Improved reliability compared to remotely controlled unmanned surface vehicles (USVs) that demand highly reliable and secure communication means, and for which failure of communication may lead to a loss of navigation, accidents, or disaster.
• Enhanced controllability and deployability, in addition to increased flexibility in sophisticated environments, including so-called dirty, dull, harsh, and dangerous missions.
• Reduced personnel costs and improved personnel safety and security, when no crew is onboard and collision avoidance intelligence is implemented.
• Extended operational capabilities, functionality, and precision, which also make ASVs increasingly required in many fields, e.g., scientific research, environmental and hydrographic surveys, ocean resource exploration, military operations, and other applications.
• Reduced risks of piracy, including elimination or kidnapping of crew members.
• Increased available space and tonnage for cargo by eliminating the need for life support systems and crew facilities (hotel, catering, and sanitary rooms).
• Reduced design constraints from not having humans operating the vessel.
• Removed need for a traditional navigation bridge by placing sensors optimally anywhere on the vessel.

Importantly, autonomy is the means to ensure these advantages and not a goal in itself. Moreover, ASVs are still facing several challenges before global commercialisation and operations in international waters. Some of these issues are identified below:

• Regulatory framework. Legislation regulating ASVs is still unclear. Significant international cooperation is required in order to set up navigation and safety regulations as well as the design standards.
• Liability. There are many legal challenges that arise if there is no captain onboard, e.g., who is liable for the actions being made.
• Cyber-security. A big concern for all autonomous systems, cyber-security is of vital importance. A flaw in software may give unauthorised access to hackers who could take control of a ship.
• Safety in navigation. A vessel sailing in open waters faces many risks including harsh weather conditions, obstacles, especially dynamical or underwater, or even risks related to third parties. Special attention should be brought to obstacles that cannot be detected by the automatic identification system (AIS), such as people in water, recreational vessels, small water equipment, or sea animals. An autonomous ship must be able to handle such challenges by itself without human control.
• Reliability and maintenance. To operate at deep-sea for extended periods of time it is crucial to have good condition monitoring systems, maintenance plans, and redundancy. If there are no engineers onboard, the planned maintenance must take place at port. This may require longer stays in port, and vessel off-hire is expensive. Furthermore, to achieve satisfactory reliability, it may be required to redesign many of the ship systems to improve the mean time between failure (MTBF) and add redundancy.
• Connectivity. Even though there is an increasing number of satellites in orbit, there is a varying degree of coverage and bandwidth depending on vessels’ location. Areas at high latitudes have poor coverage and are particularly challenging since most satellites are geostationary above the equator. In addition, a vessel could lose connectivity due to weather, damage to crucial equipment (such as antennas), and interference.
• Piracy. Even if the ASV is unmanned, the cargo and the ship itself have a high value and is subject to hijacking. An unmanned ship may also be easier to seize.

Recent advances in the industry

Nowadays, leading shipbuilding companies already have a vision of a future with mostly autonomous vessels on waters. In what follows, we present some recent advances and future predictions among important actors in the industry.

In their €6.6 million project, Advanced Autonomous Waterborne Applications Initiative (AAWA) (2015–2017), Rolls-Royce anticipated having ocean-going autonomous ships by 2025 [4]. Moreover, in 2017, Rolls-Royce, in cooperation with Svitzer, demonstrated project Sisu—the world’s first remotely operated commercial vessel [5]. Subsequently, in 2018, Rolls-Royce in cooperation with Finferries started the collaboration project Safer Vessel with Autonomous Navigation (SVAN) to test the findings of the AAWA project [6]. The aim of the project is to develop solutions to optimise the safety and efficiency of ships. So far, they have succeeded in designing and commercialising components for automatic operations such as autocrossing systems, which resulted in “the world’s first fully autonomous ferry” Falco^Footnote1 (see Fig. 1) successfully demonstrated in 2018 [7]. Furthermore, in another joined collaboration with Intel, Rolls-Royce is trying to make autonomous ships a reality by providing new technologies, intelligent awareness systems, and other products to enhance the operational safety of ASVs [8]. Finally, it is worth mentioning that the Rolls-Royce division mainly involved with autonomous ships, Rolls-Royce Commercial Marine, recently was acquired by Kongsberg Gruppen [9].