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

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.

2.1 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.

2.2 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^{Footnote 1} (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].

“The world’s first fully autonomous ferry” Falco by Finferries

Full size image

A Norwegian company, Maritime Robotics, has developed the USV Mariner [10], a multipurpose unmanned vehicle for offshore and coastal applications, and the USV Otter^{Footnote 2} (see Fig. 2) [11], an easily deployable system for seabed mapping and monitoring of sheltered waters. In addition, Maritime Robotics in cooperation with Rakuten Institute of Technology has developed a zero-emission USV Rakuten K22^{Footnote 3} (see Fig. 3) for research of unmanned cargo ships and related technologies as a logistics solution [12].

USV Otter by Maritime Robotics

Full size image

USV Rakuten K22 as a result of cooperation between Maritime Robotics and Rakuten Institute of Technology

Full size image

The Norwegian companies Yara and Kongsberg Maritime have succeeded in designing an all-electric, autonomous container ship known as Yara Birkeland^{Footnote 4} (see Fig. 4), which is expected to operate fully autonomously by 2022 [13]. Subsequently, the prominent shipping industry companies Wilhelmsen and Kongsberg Maritime decided to create the Massterly autonomous shipping company that will provide vessels’ autonomous operations, design and development, and control systems [14].

Yara Birkeland as a result of cooperation between Yara and Kongsberg Maritime

Full size image

The ReVolt by DNV GL

Full size image

At the time of preparation of this review, the classification company DNV GL is working on a project developing an unmanned, zero-emission, shortsea vessel, the ReVolt^{Footnote 5} (see Fig. 5) [15], as a solution to the growing need for transport capacity.

The Japanese companies Mitsui O.S.K. Lines and Mitsui Engineering & Shipbuilding Co. joined in a project of developing technology for autonomous ocean transport systems and are planning to have autonomous ships by 2025 [16]. The Japanese NYK and NYK Group companies MTI Co. Ltd, Keihin Dock Co. Ltd and Japan Marine Service Inc. are also working on developing an autonomous ship, focusing on the collision risk judgement and the autonomous operation of vessels [17]. This Japan’s first demonstration project for autonomous ships was presented in August 2018.

Meanwhile in Finland, according to Maritime Journal [18], company ABB has made a step forward with their research on autonomous shipping by successfully demonstrating remotely operated passenger ferry Suomenlinna II. Another Finnish project, Dimecc’s innovation ecosystem project One Sea (2017–2025) for autonomous marine transport uniting almost 80 companies, is planning to create the “world’s first autonomous marine transport system to the Baltic Sea” [19]. The ecosystem anticipates having fully autonomous ships by 2025.

Several big governmental projects draw some broad lines for accelerating the development of ASVs. The USV Master Plan [20] established for the US Navy lists objectives for improving autonomy to increase mission diversity and reduce the amount of supervisory intervention. Additionally, the Department of Defense of the US military published another report entitled Unmanned Systems Integrated Roadmap [21] that articulates a vision and strategy for the continued development, production, test, training, operation, and sustainment of unmanned systems. Resurging interest in ASVs came especially with the Defence Advanced Research Projects Agency’s (DARPA’s) announcement that it required $3 billion in fiscal 2012 for projects involving ASV development for submarine tracking.

Furthermore, a collaborative research project, co-funded by the European Commissions under its Seventh Framework Programme named Maritime Unmanned Navigation through Intelligence in Networks (MUNIN) (2012–2015), was working to develop technology for unmanned and autonomous vessels [22, 23]. The total budget of the project was 3.8 million EUR. Besides showing the technical, economic and legal feasibility of ASVs and USVs, it aimed to develop IT architecture for autonomous operation and design the individual components of the ASVs.

To summarise, it is clear that several companies worldwide are currently actively working towards the development of ASVs and USVs due to their benefits and novelty. The predictions of most of these companies state that fully autonomous ships can be expected by 2025.

2.3 Terminology

A review of the literature shows that there has been a great deal of ambiguity regarding the terms used in the field. Noticing this diversity, we aim at distinguishing the terminology used regarding the types and features of surface vessels, as well as the differences between terms used in path planning and path following, based mostly on LaValle [24], Lekkas [25], Fossen [26]. The definitions below are our attempt at harmonising and complementing the terms used.

2.3.1 Autonomous versus unmanned surface vehicles

The use of terms like ASV and USV across the literature is not always uniform and in some cases is even confusing. For example, a surface vessel may be defined as a “nonlinear underactuated kinodynamic system often with large inertia” [27] that operates in continuous contact with the surface of the water. However, many modern vessels are fully actuated and their inertia need not necessarily be large.

An autonomous surface vehicle, or ASV, on the other hand, is a vessel that can make decisions and operate on its own, without human guidance, navigation, and control. ASVs are typically used in military operations, maritime surveillance cruises, marine environmental monitoring applications, and in the near future, likely also for the transportation of goods and people.

Many papers in the field are referring to the terms ASV and unmanned surface vehicles as synonyms, and do not distinguish the methodology for these two types of vessels. A USV is an unmanned vehicle that does not have a human on board to control its operations but is typically remotely controlled by a human operator. Crucially, an ASV may also be unmanned but the important distinction, when compared with a USV, is that it operates without direct intervention from a human operator during the course of its ‘mission,’ whatever that might be. Obviously, an ASV could have crew and passengers in the same way as autonomous cars have passengers. Nevertheless, in the maritime field, the term ASV is commonly used when talking about an unmanned vessel. Finally, to be categorised as an autonomous (or semi-autonomous vessel), some key on-board technologies are required, which include: automatic route generation and path planning techniques, object detection capability, collision avoidance capability, and autonomous decision-making systems.

2.3.2 Path planning terminology

Path planning is a critical part in the development of USVs in general, and for ASVs in particular, with the aim of using algorithms to determine optimal trajectories to guide a vessel’s voyage. It can be defined as the problem of finding a route between two positions in a mobile space, considering that the route should be collision-free, physically feasible within spatial constraints, and satisfy certain optimisation criteria. Commonly used optimisation criteria for path and trajectory include minimisation of path length, time, and energy consumption, as well as measures of safety or risk. Also, path planning is typically defined within purely geometric space, whereas trajectory planning, or trajectory generation, involves geometric paths endowed with temporal properties, e.g., to incorporate dynamics. Although path planning of ASVs has been a focus of many authors, inconsistency of the corresponding terminology still occurs. Below, we attempt to elucidate some common terms related to path planning, with a visual representation of the terms shown in Fig. 6:

• Path planning aims to generate a geometric path by finding the set of waypoints to navigate through (or near) to travel from a start position to an end position.

• Trajectory generation succeeds the process of path planning and has a wider scope since it can take into account turning angle limits and velocity and acceleration constraints in order to generate a feasible trajectory that the ship can follow. In particular, trajectory generation includes assigning a temporal constraint (time law) to the geometric path.

• Path following means following a predefined path in the space which does not involve time as a constraint, and where the essential goal is to stay on the geometric path and follow it with whatever speed until the goal is reached.

• Trajectory tracking, on the other hand, has a time profile, meaning that the ship has to be at a certain point at a certain time while following the trajectory.

• Path smoothing is a process that receives a sequence of generated waypoints as input and connects them in an optimal way taking into consideration the limited curvature or turning radius of a vessel, where a smoothed path is obtained as a result.

Visual representation of the distinction of path planning terms used in literature

Full size image

A shortcoming with the above definitions, with path planning defined as being purely geometrical (spatial), is the question of how to define planning for moving obstacles and non-static wind or current forces. Thus, it may be argued that path planning should instead be defined as a spatiotemporal task, or one may adopt the term dynamic path planning for distinction.

2.4 Other literature reviews

In recent years, several survey papers have been published reviewing the path planning and collision avoidance of both ASVs and USVs and their components. The intention of the literature review presented in this paper is to further study and consolidate the current state-of-the-art of path planning and collision avoidance algorithms for ASVs. A selection of the most relevant papers for the period 2008–2020 is given in Table 1, with a corresponding timeline shown in Fig. 7. We summarise the selected papers in the following.

Timeline of other review papers

Full size image

Statheros et al. [28], 2008. The authors review the collision avoidance techniques and International Regulations for Preventing Collisions at Sea (COLREGs) [36] (see Sect. 3.2) for autonomous ships along three axes: mathematical models, soft computing (evolutionary algorithms, fuzzy logic, expert systems, and neural networks), and hybrid systems. The authors conclude that the hybrid systems look very promising for a ship’s autonomous navigation, although it is challenging to harmonically merge different artificial intelligence (AI) technologies together.

Tam et al. [29], 2009. The authors review past studies on collision avoidance and path planning of autonomous ships up until the year 2008. The reviewed papers are organised on a timeline in the sequence of their publishing date, setting focus on the evolution of algorithms. Some of these papers are also categorised according to their point of focus; earlier papers typically focus more on collision avoidance, whereas more recent papers focus more on path planning. The limitations of previously developed algorithms highlighted by the authors include: (a) the lack of environmental factors in algorithms, (b) working with only semi-dynamic obstacles (rather than true dynamic obstacles), (c) having idealised ship dynamic models, and (d) lack of compliance to COLREGs in many cases.

Campbell et al. [30], 2012. The authors focus on AI solutions for autonomous ships. The review discusses the current state of USV collision avoidance research and reveals weaknesses in obstacle detection and avoidance (ODA) systems found in the literature. The review also inspects the integration of COLREGs for the general case and for multiple unmanned vessels in cooperation within the obstacle avoidance protocols.

Zeng et al. [31], 2015. Whereas the other review papers we have selected to include in this section are related to ASVs, we have chosen to include one review by Zeng et al. [31], who present a set of recently developed AUVs and provide a detailed literature review of their operational endurance and specifications. The review paper sheds light on path planning and optimisation techniques from the angle of their performance aspects (safety, energy consumption, voyage time), aiming to highlight challenges that need to be addressed to achieve higher levels of autonomy.

Liu et al. [32], 2016. This paper reviews all three components of GNC for USVs. The authors offer a classification of existing GNC approaches using various criteria where only a part of the research is dedicated to path planning and collision avoidance. The review is accompanied by several comprehensive figures summarising common challenges and the history of the development of USVs, listing advantages and limitations of the used sensors with great focus on classifying the control methods.

Szlapczynski and Szlapczynska [33], 2017. The authors discuss a number of ship safety domain models that are a part of the autonomous ship collision avoidance system. The paper emphasises that the factors considered in different safety domain models are usually more important than the shape of the domain itself. However, to enable real-time systems operation, mostly single parameters such as the time to the closest point of approach (TCPA) and/or the distance to the closest point of approach (DCPA) are used instead of the whole ship safety domain.

Singh [34], 2018. This review paper provides an overview of components of optimal local and global path planning for USVs, considering compliance with COLREGs and different objective functions of both vessels in formations and single vessels.

Huang et al. [35], 2020. This paper reviews collision prevention techniques both for manned and unmanned ships, distinguishing three modules, namely, motion prediction, conflict detection, and conflict resolution. The paper identifies up-to-date drawbacks and trends in the field as well as reviews and compares the existing collision avoidance methods based on properties proposed by authors.

Remarks on literature reviews. The analysis of previous reviews shows that in recent years, there has been a growing interest in path planning and collision avoidance problem for ASVs. While authors of the analysed reviews are referring to both ASV and USV type of surface vessels, the algorithms used in both cases remain similar. The same applies to the reviewed algorithms for AUVs by Zeng et al. [31] that can be adapted for use for ASVs.

Increased interest in autonomous marine transport has led to the development of guidelines and safety conventions. Guidelines describe both autonomy levels and trial guidelines for maritime autonomous surface ships (MASS). To our knowledge, design standards for ASVs have not yet been developed.

3.1 Levels of autonomy

Current guidelines for autonomy levels define and clarify the concept of different levels of ship autonomy to make it understandable for all involved parties. In 2014, the Society of Automotive Engineers (SAE) first developed the guidelines that explain six levels of autonomy for cars, ranging from cars with manual control to fully autonomous cars [37]. Similarly, in 2016, Lloyd’s Register (LR) proposed six autonomy levels (ALs) for ships [38], ranging from manually navigated ships at autonomy level AL0 to fully autonomous ships at autonomy level AL6, which are summarised in Table 2. Throughout this paper, the term ASV is used to refer to both levels AL5 and AL6, whereas the term USV refers to the level AL4.

LR is not the only organisation that has defined levels of autonomy for surface vessels. Norwegian Forum for Autonomous Ships (NFAS) categorises surface vessels into four groups according to their level of autonomy [39], as shown in Table 3. More detailed descriptions of the division of ships based on both autonomy and manning levels can be found in Rødseth and Nordahl [39].

We note that although one might think that simple remote control could be the first step towards autonomy, the above indicates that increasing the level of automation is the appropriate way forward. In the case of simple remote control, the need for high and expensive communication bandwidth (cameras and radar) and risk of loss of communications are good arguments against remote control before the vessel has reached a high level of autonomy. Likewise, simple remote control would probably not reduce the amount of staff, just moving them to shore.

3.2 Safety regulations

A crucial aspect of ASVs is safety and the ability to safely navigate in open waters, coastal areas, and congested waters like harbours. Clearly, the safety issue is the most challenging when avoiding collisions with other dynamic vessels or land in high-traffic congested waters.

There are several regulations that consider the safety of surface vessels. One of them is the International Convention for the Safety of Life at Sea (SOLAS) [40], proposed by the International Maritime Organization (IMO) in 1974, that sets safety standards in the construction, equipment and operation of merchant ships. Another regulation, COLREGs, was proposed by IMO in 1972 in an attempt to define how vessels should act in various situations when meeting other vessels to navigate through waters safely and without collisions [36]. These regulations, which were developed for manned surface vessels, need to be taken into account when developing path planning and collision avoidance systems for ASVs even though there might be some exceptional cases.

COLREGs consist of 38 rules that are categorised into 5 parts. Part B “Steering and Sailing rules,” which contains 16 rules, is responsible for handling collision avoidance situations. When evaluating risk of collision, it is necessary to follow Rule 7 using on-board measurement devices (compass, radar) to ensure safe navigation. In situations when the risk of collision exists, proper actions to avoid collisions are determined by Rule 8. Four different two-vessel encounter situations of power-driven vessels—overtaking, head-on situation, and crossing from the port side or starboard side—are described by COLREG rules, as illustrated in Fig. 8. These actions are true in the encounter situations when both vessels are in sight of one other and a risk of collision (Rule 7) is formed. In these situations, alteration of course is chosen over alteration of speed. To have a better understanding of the actions taken by give-way and stand-on vessels in the encounter situations, it is also important to consider Rule 16, explaining actions taken by give-way vessel, and Rule 17, explaining actions of stand-on vessel Deciding when to take which action from the own vessel’s perspective depends on the relative bearing of the approaching target vessel, which must be avoided, as illustrated in Fig. 9. However, an exceptional situation may occur, defined by Rule 17, when it is apparent that the give-way vessel does not take the necessary collision avoidance actions. In this case, the stand-on vessel, instead of keeping its course and speed, must take actions to avoid possible danger situations.

Four encounter situations of power-driven vessels according to the COLREGs rules 13–15: (a) head-on, (b) overtaking, (c) crossing from the right (starboard) and (d) crossing from the left (port). The bottom (blue) vessel is the own vessel and the top (orange) is the target vessel. Solid (dashed) line indicates stay-on (give-way) action

Full size image

Categorisation of collision avoidance actions based on COLREGs that need to be taken depending on the angle of the approaching target ship (TS) in relation to own ship (OS)

Full size image

However, there are also a few special cases of collision avoidance: when at least one of the vessels at the encounter is a sailing vessel (Rule 12), and when there is a situation of restricted visibility (Rule 19). Responsibilities between different types of vessels while navigating are covered by Rule 18. The implementation of this rule requires a good situational awareness, for being able to differ between vessels engaged in fishing, sailing vessels, and vessels not under command. COLREGs also acknowledge situations when it is allowed to violate the collision avoidance rules (Rule 2(b)). The rule states that, in immediate danger situations, it is necessary to follow ordinary practice of seamen to take required precautions to avoid fatalities. While performing manoeuvre, limitations of both vessels must be considered.

Finally, the latest newcomer to the set of regulations is Interim Guidelines for MASS Trials [41] proposed by IMO in June 2019. These guidelines have been developed with the goal to ensure that the trials of autonomous ships are “conducted safely, securely and with due regard for protection of the environment.” Although these guidelines might be general, without going very deep into details, and be in their first stage of the development, they are a good starting point to regulate trials of ASVs in the future.

4.1 GNC architecture

According to Fossen [42], a marine vessel’s control system consists of three main modules—the GNC components. These are generally constituted by onboard computers and software, which together are responsible for managing the entire ASV system, which is why they are considered as some of the most vital components of the ASV. An alternative way of organising the architecture of the control system is proposed by Lekkas [25], who defines a path planning module separately from the guidance layer in the GNC system, hence having four main modules.

In an attempt of reconciliation, we propose an architecture that includes many components from several of these variations (see Fig. 10):

Proposed GNC architecture

Full size image

The guidance module. This module generates a path that the vessel will follow to accomplish its mission starting from the vehicle’s current position to a designated end position. The guidance module receives information about the environment and the own vessel’s state as an input from the navigation module. It is then responsible for continuously generating and updating desirable paths (feasible, safe, optimal, and smooth are common criteria) to the control system according to the information provided by the navigation system, assigned missions, vehicle’s capability, and environmental conditions. The resultant path that is transmitted to the control module can be represented as a set of waypoints. In the case of applying a path smoothing technique on the set of the resulting waypoints, the output that is transmitted to the control layer is a smoothed path that needs to be followed.

The navigation module. This module is responsible, first, for estimating the own vessel’s state, e.g., determining the location of the vessel and state parameters like position, velocity, and attitude. Second, it includes perceiving information about the environment and surroundings. The obtained data can be fused to provide the vessel with necessary information about situational awareness and for providing the guidance system with the necessary inputs.

The control module. This module determines the necessary control forces for a vessel to follow the path that is set by the guidance system, considering the current state of the vessel determined by the navigation system. The input of the control module can vary from an already smoothed path to a simple set of waypoints that need to be followed. The control module needs to make sure that the resulting path is feasible with regards to the vessel’s control limitations. One of its main responsibilities is the minimised-error trajectory tracking by setting the correct control commands to the actuators (e.g., propeller speed and rudder angle).

Remarks on GNC modules. The architecture proposed above is not strictly defined as the ultimate and ‘one and only’ architecture of control systems for ASVs. Rather, it represents our preferred means for studying path planning and collision avoidance within GNC. Contrary to Lekkas and Fossen [43], we define the role of path planning and collision avoidance to be a part of the guidance module (layer). The following subsection extensively describes path planning and collision avoidance components and their role in the guidance module.

4.2 Path planning and collision avoidance

The literature review shows that in most of the papers the two distinguished types of path planning are global path planning and local path planning, e.g., Polvara et al. [44], Wang et al. [45], Xie et al. [46]. Global (deliberative) path planning finds a safe path from the initial state to the goal state considering known obstacles and assuming that a complete model of the environment is available. On the other hand, local (reactive) path planning, uses the information about the local environment around the vessel taking into consideration information from the sensors for situational awareness and putting emphasis on avoiding the dynamic obstacles in the vicinity to generate a feasible and safe path. The actions of a local path planner can result in a deviation from the previously planned path or a change in speed. For local path planning, in particular, it is important to follow COLREGs, unless exceptional situations occur, in order to safely avoid all of the obstacles. However, when an ASV should follow COLREGs and when it should not, remains an open question. Also, both local and global path planning modules might not be necessarily separate components; some of the algorithms are performing overlapping tasks.

On the other hand, there is also a different variation of suggested planning levels, used by some authors [47,48,49]: high-level global path planning, which creates paths avoiding known static obstacles; mid-level protocol-based COLAV, which follows a set of rules (like COLREGs); and low-level reactive COLAV, which avoids immediate collisions in close range, without considering COLREGs.

In some cases, to ensure the feasibility of a path and reproduce the manned vessel’s behaviour, it is necessary to apply path smoothing methods over the generated linearly connected path. According to Lekkas et al. [50], there are two main categories of paths resulting from connecting waypoints: (1) a combination of straight line and arc segments, and (2) splines. A comprehensive description of these path categories can be found in LaValle [24], and Lekkas and Fossen [51].

Emerging from robotics, path planning is a developing research field applied to ground vehicles, underwater vehicles, surface vessels, and drones, with many algorithms being reused and adapted for each of these contexts. There are clearly similarities between autonomous vehicles navigating on unstructured roads without driving lanes (parking, intersections, diversions, complete road blockage, unorganised traffic, etc.) and open sea manoeuvring of ASVs. However, finding an optimal safe path while driving in a lane can often be simpler than on unstructured roads or open areas where the distribution of obstacles is irregular. The complexity of the environment and kinodynamics makes path planning of surface vessels more challenging and different from ground vehicles.

Collision avoidance includes multiple issues that have to be solved, such as dealing with external disturbances (wind, waves, current); modelling the own ship dynamics; predicting the behaviour of target vessels (vessels that must be avoided); avoiding close-range collisions, grounding, and stranding; docking; and safety.

For collision-free path planning, in addition to the above, finding the optimal path, smoothing the followed path, evaluating the path efficiency, ensuring path following, and so on must be solved.

In this section, we present and categorise path planning algorithms used for ASVs.

5.1 Path planning algorithms

We have adopted a general categorisation of path planning algorithms based on Souissi et al. [52], and suggest that such algorithms can take a classical approach, an advanced approach, or a hybrid approach (see Fig. 11).

Path planning approaches

Full size image

The classical approach. This approach is a two-step process consisting of (1) environment modelling to prepare for the search; and (2) performing the search of the optimal path in this environment. These methods are most commonly used for global off-line path planning with static obstacles where there is no need for path replanning or local collision avoidance [34, 52].

First, for the environment modelling, there are two main approaches used, based on [52] (see Figure 12):

Methods used for environment modelling in the classical approach

Full size image

• Roadmap-based methods which attempt to capture the free-space connectivity with a graph. Their main goal is to reduce the N-dimensional configuration space to a set of one-dimensional paths, which are then searched, e.g., visibility graphs and Voronoi diagrams [53].

• Cell decomposition methods that decompose the configuration space of the problem into nonoverlapping convex regions referred to as cells [54]. After the decomposition has been performed, a connectivity graph, representing the adjacency relationships of the cells, is created. The decomposition components can be both regular and irregular grids as well as a navigation mesh [52].

We note, however, that these two main approaches may imply static environmental conditions, and as such may require further refinement to capture the time-varying nature of the environment, effectively adding another dimension to the state space.

After modelling of the environment, the roadmap or connectivity graph is searched for a collision-free path between the initial and the goal positions.

Advanced approach. These algorithms are commonly used to deal with dynamic obstacles, path re-planning and local collision avoidance in real time. Most often, they do not require environmental modelling beforehand. Based on the literature review, we propose the following classification of the advanced approaches used in the path planning for surface vessels’ (see Fig. 13):

Classification of the algorithms using an advanced approach

Full size image

• Machine learning algorithms, which has attracted the attention of some researchers. In Cheng and Zhang [55], the authors proposed a concise deep reinforcement learning obstacle avoidance (CDRLOA) algorithm using an avoidance reward function and decision-making module. This algorithm proves its efficiency in complex navigation situations and unknown environment disturbances.

• Directional approaches, which include three kinds of methods [56]:

  • potential field methods, which are most often used due to low computational load requirement for trajectory generation. An attractive field is assigned to the target, whilst negative fields represent obstacles and so the vessel is repelled at these locations. In general, the trajectory can be generated effectively in real time and planning and control are merged into one function, however, a disadvantage is the risk of being trapped in local minima [57].

  • velocity space methods, for which, we define three sub-categories: velocity obstacles [58], dynamic window [45] and curvature velocity.

  • vector field histogram methods, which use histogram grids to plan motion in real time, taking into account the dynamics and shape of the vessel, e.g. a polar histogram [29].

• Evolutionary algorithms (EAs), which represent AI by mimicking the evolutionary behaviour of biological systems. They address the problem of multi-objective optimization where traditional optimization methods such as gradient descent become too complex or computationally demanding. However, the disadvantage of some of them is once again the potential of getting trapped in local minima, finding at best a near-optimal solution (as the global optimum is never guaranteed) or even failing to find a solution at all in some instances. EAs such as particle swarm optimization (PSO) [59], ant colony optimization (ACO) [60], genetic algorithm (GA) [61], wolf colony algorithm (WCA) [62], bio-inspired neural networks, and other algorithms have all been used and implemented for solving the path planning problem of ASVs.

• Sampling-based algorithms have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness [63]. The probabilistic roadmap (PRM) and rapidly exploring random tree (RRT) [64] algorithms and their variations are some of the most often used algorithms.

Hybrid approach. In this context, these algorithms are ones that combine several path planning algorithms to ensure safe and feasible navigation both globally and locally. Whilst these algorithms are often more complicated, the result is often better than when the combined methods are applied separately, as in many cases they overcome each other’s drawbacks. Some good examples are presented by Zhou et al. [65], Wang et al. [45], Xiong et al. [66], Blaich et al. [67].

The increased popularity of ASVs is clearly evidenced by the several attempts of shipbuilding companies to introduce autonomy at sea and the success of these projects. Based on the industry’s predictions, fully autonomous surface vehicles are expected by 2025. A positive reinforcement here is the multiple collaboration projects between companies that lead to knowledge sharing and faster development of the technology.

Although we have tried to elucidate the terminology of the path planning and types of surface vessels in this paper, the confusion of terms used in the literature still remains and should be addressed also in the future. The confusion of the terms ‘ASV’ and ‘USV’ can be partially explained by the vague and unclear boundary between the levels of autonomy and manning onboard. It needs to be emphasised that even fully autonomous operational surface vessels might have passengers and/or staff working onboard and therefore should be categorised as manned. Additionally, the issue that is not raised in most of the papers up to date is whether remote control is the right first step towards full autonomy of surface vessels. As we already discussed in Sect. 3, a remotely controlled USV that does not have full operational autonomy as a back-up plan is at high risk due to the potential of loss of communication, which could be disastrous and lead to total loss of control of the ship.

Another topic for discussion is safety conventions like COLREGs. These regulations, first developed in 1972, were clearly developed for human-controlled manned vessels. Thus, in an era where control over vessels is deliberately transferred to computers, the open question is how well are ASVs going to follow rules written for human beings. Furthermore, it is possible to envision exceptional situations when an ASV should not follow the defined collision avoidance rules to avoid last-minute collision. Therefore, it is clear that the COLREGs Rule 2(b) should be implemented in the GNC system of an ASV. The question of when to follow regulations and when not to is a topic of future research. Alternatively, an improved version of these regulations should be developed to account for both USVs, ASVs and traditionally manned surface vessels on waters.

To summarise research about path planning algorithms for ASVs, there is a wide variety of different methods for path planning that have already been successfully applied for USV or ASV applications. Moreover, some of the non-applied path planning algorithms that have been implemented for ground vehicles navigating on the unstructured roads or AUVs can likely be adapted for ASVs too.

From a path planning and collision avoidance perspective, we have proposed just one scheme for classification of path planning algorithms and models of GNC, hopefully positively complementing other schemes and views in the literature. Several elements of our study could have been analysed further in-depth, including collision avoidance methods, path following, and path smoothing methods but have been left out to limit the scope of this paper. We do, however, cover these topics in our accompanying paper [3].

We have given an overview of the current situation in the field of path planning and collision avoidance of ASVs by explaining important aspects such as autonomy, safety, and GNC system architecture from a path planning and collision avoidance point of view. Some inconsistencies within terminology in the literature have been highlighted, and regulations related to path planning and collision avoidance of ASVs have been analysed and discussed. Our review paper contributes to a rapidly growing field that still contains many unanswered questions. We acknowledge that ASVs have not only great potential but also a number of challenges that must be considered and treated with caution in the years to come.