Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Currently, economic development is putting enormous pressure on transport systems. Freight transport is likely to grow over the next decades [7]. If roads and railways are the major means of transport for handling the growth, they will face frequent congestion. Inland waterway shipping still have the capability of transporting large additional volumes. It offers an environment-friendly alternative to road and rail transport in terms of both energy consumption and gas emissions [6]. To meet the transportation demand and maintain sustainable development, many countries are aiming to promote and strengthen the competitive position of inland waterway shipping in the transport system.

Research has proposed many measures to improve the position of inland shipping, such as optimizing ship dimensions [10], removing bottlenecks [5], improving utilization of ports [8] and locks [25]. Among these measures, employing autonomous vessels has recently drawn much attention [13, 27]. Autonomous vehicles are already state-of-the-art in the land-based transport domain. There exist several examples of self-driving and automated guided vehicles in modern container terminals [26]. Consequently, applying autonomous vessels is seen as a way to improve the safety and efficiency of inland shipping.

Safety can be improved as human error is one of the main causes of ship accidents. Figure 1 shows the mains causes of ship accidents between 2005 and 2014 in Dutch inland waterways [14]. The category operation error includes alcohol/drug use, wrong estimation, fatigue, etc.; the category communication error indicates not maintaining watch on correct VHF channel, unclear explanation, etc.; the category environmental error includes disturbances caused by wind, wave and current, poor visibility, etc.; the category equipment error indicates the failure of engine, rudder or other navigation equipments. For autonomous vessels, detection of obstacles, estimation of the risk, communication between vessels and infrastructure can be done without humans. Thus, applying autonomous vessels could be an efficient measure to reduce the number of accidents.

Fig. 1.
figure 1

(based on [17]).

The causes of the shipping accidents

Full size image

Efficiency can be improved by autonomous vessels due to the intelligent path planning and better control of vessel motion. Communication and coordination with infrastructures also make it possible for autonomous vessels to minimize the waiting time at ports, locks, etc.

The overall architecture of an autonomous vessel is shown in Fig. 2. To realize autonomous navigation, a vessel controller uses sensors to get self-state information (e.g., position, speed and heading), environmental information (e.g., wind speed, current velocity) and information of obstacles. Based on the obtained information, optimal paths to follow and desired speed and heading with specified objectives and constraints can be determined. The commands are sent to actuators for autonomous navigation.

Fig. 2.
figure 2

The overall architecture of autonomous vessels.

Full size image

In Fig. 2, the module ‘Path planning’ plays an important role in autonomous navigation. It describes how the autonomous vessel make decisions regarding its course to sail. The path planning problem can be subdivided into a global and a local planning task: an approximate global planner computes paths ignoring the kinematic and dynamic constraints; an accurate local planner accounts for the constraints and generates feasible local trajectories [20]. The final path are determined on the basis of reference path provided by the global planner according to the transport mission, known stationary obstacles (e.g., islands, shallow waters) and infrastructure operation schedules, and the collision avoidance actions taking into account the regulations and the limitation of infrastructures (e.g., width and depth of waterways). Communication between vessel controllers will help the controller make better path planning decision. As a starting point, this paper focuses on the global path planning problem.

Many path planning algorithms have been developed for the navigation of unmanned surface vehicles as well as robots, such as Artificial Potential Field methods [23], Evolutionary Algorithms [12], and Heuristic Search Algorithms [4, 19]. For a detailed review of path planning and collision avoidance technologies and techniques, see [2, 21]. Among these methods, the group of heuristic search algorithms, especially A* and its extensions, are commonly used to determine the path from an origin to a destination for land-based vehicles [18, 22].

Compared with mobile robotics path planning, the static obstacles in inland waterway networks are usually larger and continuous. Clear passages (waterways) can be found in the map. Moreover, when autonomous vessels are in a hybrid environment where exist vessels operated by humans. In order to ensure safety it is necessary that autonomous vessels comply with navigation rules throughout their missions [2]. Several recent efforts have been made to integrate rules into path planning algorithms [11, 19].

In order to find a suitable global path planning algorithm for inland autonomous vessels, in this paper we carry out a comparison among A* and its extensions. We moreover propose a new algorithm called A*BG for autonomous inland vessels. Based on the existing algorithms, A*BG takes advantage of grid search and visibility check, which improves the searching and computational properties.

The remainder of this paper is organized as follows. In Sect. 2, a brief introduction of the inland waterway transport system is provided. A* and its extensions are elaborated on in Sect. 3. Based on this, the new algorithm A*BG is proposed in Sect. 4. Simulation experiments are carried out to assess the performance of the algorithms in Sect. 5. Conclusions and future research are presented in Section 6.

2 Inland Waterway System

The main function of an inland waterway system is to fulfill the transport demand, i.e., to transport goods or people from one place to another. As shown in Fig. 3, two main components in waterway systems are vessels and infrastructures. Vessels are the means of transport. Infrastructures are necessary to guarantee a sound navigation: waterways provide navigable waters; locks create stepped navigational pools with reliable depths; bridges balance the road traffic and the waterborne traffic.

Fig. 3.
figure 3

Inland waterway system.

Full size image

Rules and regulations provide suggestions to the skippers. These “rules of the road” specify the types of maneuvers that should be taken in situations where there is a risk of collision. Vessels navigating in waterways are also influenced by the external environment (e.g., wind, current and waves).

The architecture of an autonomous vessel in Fig. 2 can be regarded as the detail explanation of the relation of a vessel controller and a vessel in Fig. 3. When vessels navigating between the origins and destinations, controllers control the propeller and rudder to let the vessel move to desired position. The sensors measure the practical speed and headings of the vessel and provide them to the controllers as feedbacks. Vessel controller can obtain the position and direction of other vessels via sensors. When there is a risk of collision, actions that should be taken to avoid the collision are decided by the controllers. The communication between vessel controllers can help controllers to cooperate with each other.

Infrastructure controllers making schedules with the predicted time of arrival reported by vessel controllers and also keep an eye on the state of the infra-structures (e.g., availability, waiting time and length of the line). In return, the operation schedules also have impacts on vessel controllers decision making on the route, departure time and speed choices.

3 Existing Path Planning Algorithms

In this section, A* and its improved extensions and their characteristics are introduced. The method to apply the algorithms to inland autonomous vessels considering rules and regulations is explained as well.

3.1 A*

A* is the most widely used path planning algorithm, which can be applied on metric or topological map [4]. This algorithm uses a combination of heuristic searching and searching based on the shortest path. A* is defined as best-first algorithm, because each node in the map is evaluated by the function:

$$\begin{aligned} f(s_\mathrm {start}, s, s_\mathrm {goal})=g(s_\mathrm {start},s)+h(s, s_\mathrm {goal}) \end{aligned}$$
(1)

where \(g(s_\mathrm {start},s)\) provides the length of the shortest path from a start node \(s_\mathrm {start}\) to node s found so far, \(h(s, s_\mathrm {goal})\) provides an estimate of the distance from node s to goal node \( s_\mathrm {goal}\), \(f(s_\mathrm {start}, s, s_\mathrm {goal})\) provides an estimate of the length of a shortest path from the start node \(s_\mathrm {start}\) via node s to the goal node \(s_\mathrm {goal}\).

A* uses a priority queue Open to perform the repeated selection of minimum \(f(s_\mathrm {start}, s, s_\mathrm {goal})\) nodes to expand (expanding a node means this node is a candidate in the shortest path). At each step, the node s with the minimum \(f(s_\mathrm {start}, s, s_\mathrm {goal})\) is removed from Open. The unblocked neighbor nodes which are in the line-of-sight of node s are recorded in the set \(nbr_{los}(s)\). For each \(s'\) in \(nbr_{los}(s)\), its related values are updated: \(parent(s')=s\), \(g(s_\mathrm {start},s')= g(s_\mathrm {start},s)+distance(s,s')\). If \(s'\) is already included in Open, A* compares the two \(g(s_\mathrm {start},s')\) in \(nbr_{los}(s)\) and Open, and updates the \(s'\) with lower \(g(s_\mathrm {start},s')\). If not, \(s'\) is added to Open. The algorithm then repeats this procedure until s is \(s_\mathrm {goal}\). The length of the path that A* finds is then \(f(s_\mathrm {start},s_\mathrm {goal},s_\mathrm {goal})\).

The basic A* is restricted to a so-called 8-connectivity grid. This means that the path it finds is based on the connection between the closest possible nodes. The turning angle of each movement is restricted to multiples of \(45^\circ \), which makes the path linked in a zigzag style. Consequently, the path A* finds is not guaranteed to be the optimal path.

3.2 A* with Larger Neighborhood

The length and smoothness of the paths A* finds are influenced by the connectivity of possible nodes which is determined by so-called ‘neighborhood’. The term ‘neighborhood’ indicates the area that A* algorithm explores in a single step, which determines the successor nodes that can be reached from a source node.

One method to improve A* is to enlarge the neighborhood. As shown in Fig. 4, when \(neighborhood=1\) is considered, the algorithm can search 8 successor nodes. This is the most frequently used A*. 8 directions are possible to move into in a single step. When the neighborhood increases to 2, 16 more grids and 8 more directions can be searched in each step. Thus, the larger the neighborhood is, the more successor nodes the algorithm can reach, and the more directions are possible to be explored in a single step.

Fig. 4.
figure 4

Neighborhood in A* algorithm.

Full size image

It is considered that a larger neighborhood results in the discovery of a shorter path due to the increased fineness of possible directions. However, the computation time will also increase since more nodes need to be explored at each step. The trade-off must be made between the optimality of the path and the computation time in terms of requirements during for implementation.

3.3 A* with Post-smoothing

A* with Post-smoothing (A*PS) runs A* on grids and then smooths the resulting path, which often shortens it at the cost of an increase in computation time. Denote by \([s_0, s_1, . . . , s_n]\) the path that A* finds on grids, with \(s_{0} = s_\mathrm {start}\) and \(s_{n} = s_\mathrm {goal}\). A*PS firstly uses \(s_{0}\) as the current node. It then find out the farthest node \(s_{i}\) that is in line-of-sight with \(s_{0}\) on the path from \(s_n\) to \(s_1\). Then, A*PS removes the intermediate nodes \(s_1\) to \(s_{i-1}\) from the path, thus shortening it. Then \(s_{i}\) becomes the current node and A*PS repeats this procedure until it reaches the end of the path.

A*PS typically finds shorter paths than A* on grids, but is not guaranteed to find the optimal path [3, 22]. The reason for this is that it only considers resulting paths and thus cannot make informed decisions regarding other paths during the A* search, which motivates the idea of interleaving smoothing [3].

3.4 Theta*

Theta* is an extension of the A*, which resides in the visibility test between successor nodes and the parent nodes. The main difference between A* and Theta* is that Theta* considers the path from the parent(s) to node \(s'\). In each step, when s (the node with the lowest \(f(s_\mathrm {start}, s, s_\mathrm {goal})\) in Open) expanding its successors \(s'\) in \(nbr_{los}(s)\), the visibility between \(s'\) and parent(s) is checked. If parent(s) is visible to \(s'\), \(parent(s')\) becomes parent(s), and \(g(s', s_\mathrm {start})\), \(h(s',s_\mathrm {goal})\) and \(f(s_\mathrm {start},s',s_\mathrm {goal})\) are updated correspondingly. Thus, parent(s) and \(s'\) are directly connected. A detailed description of Theta* can be found in [3].

Theta* reduces some unnecessary heading changes taking advantage of the visibility test. Since Theta* carry out line-of-sight checks between a source node and its neighbor nodes, the computation time of Theta* is longer than A* and A*PS. However, Theta* is not guaranteed to find optimal paths. The parent of a node should be a visible neighbor of the node or a parent of a visible neighbor, which lead to a limitation of expanding nodes [3, 22].

3.5 A* Adaptation Considering Navigation Regulations

As mentioned, it is necessary to take the navigation rules and regulations into account when planning paths for inland autonomous vessels. Thus, adaption should be made when applying A* and its extensions to inland vessels.

The main regulations in Dutch inland waterways are the RPR (Rijnvaartpolitiereglement, Rhine Navigation Police Regulations) and the BPR (Binnenvaartpolitiereglement, Inland Waterways Police Regulations). One important item related to global path planning in these two regulations is: ‘if two vessels encounter each other with the risk of collision, the vessel not following the starboard side of the waterway must give way to the ship following the starboard side’ [15]. Accordingly, vessel controllers generally choose the path on the starboard side of the waterway as preferred path. To reflect this circumstance, the middle line of a waterway is applied to separate the vessel traffic from different directions when implementing the path planning algorithms for autonomous inland vessels.

The paths that the planning algorithms compute are usually close to the border of obstacles. Because of ship-bank interaction, sailing closer to the obstacles will increase the risk of collision [20, 24]. For the sake of safety, vessels usually keep a certain distance from the obstacles. Therefore, buffer areas are set around the obstacles. When planning the path, the paths via the buffer areas are still available to vessels with a penalty in path length. In this way, when implementing A* and its extensions, \(f(s_\mathrm {start}, s, s_\mathrm {goal})\) of a grid in a buffer area is larger than its original value when there is no buffer areas.

4 A* on Border Grids

The algorithms presented in Sect. 3 are not guaranteed to find the optimal paths. An algorithm named A* on Visibility Graphs (A*VG) has been proven to be able to find the optimal paths on a map with disjoint polygonal obstacles [1, 3]. In A*VG, visibility graphs are constructed before the A* search. If two locations do not pass through any obstacle, an edge is drawn between them to represent the visibility connection. The paths A*VG finds are along the edge and have heading changes only at the border of obstacles. However, A*VG can be slow. Visibility checks need to be performed for every pair of blocked nodes to determine whether or not there should be a visibility edge between them.

The above mentioned algorithms have different advantages and disadvantages. The characteristics of each algorithm are concluded in Table 1. A* on grid maps are simple and with relatively low computation time. However, the path it calculates is usually the longest. Theta* and A*VG take the advantage of the visibility check, and the paths these two algorithm find are relatively shorter. At the same time, their computation times are longer. Based on the comparison, a new algorithm for inland autonomous vessels is proposed next.

Table 1. Summary of the characteristics of the algorithms.
Full size table

Inspired by A*VG, in the new algorithm, the border of the obstacles are decomposed into grids. The grids in the line-of-sight of a source node are its successor nodes. This algorithm is represented as A* on Border Grids (A*BG).

Algorithm 1 shows the pseudo code of A*BG. s is the node with the lowest \(f(s_\mathrm {start}, s, s_\mathrm {goal})\) in Open. Line-of-sight checks are carried out between the source node s and all border grids. The nodes visible to s are included in the set Candidates as the candidate successors to be expanded. For each node \(s'\) in Candidates, if it is visible to parent(s), its \(parent(s')\) and other related values will be updated. Then, the node with lowest \(f(s_\mathrm {start}, s, s_\mathrm {goal})\) in Open is assigned to s again. This procedure is repeated until s is \(s_\mathrm {goal}\).

Inspired by Theta* and A*VG, A*BG considers the connection of parent(s) and \(s'\), and the paths A*BG calculated only have heading changes at where line-of-sight is blocked, which reduces unnecessary heading changes and the path length. Applying border grids instead of visibility graph can greatly reduce the number of visibility test. Using border grids instead of transferring the whole map into grids reduces the amount of nodes the algorithm need to search, which makes the algorithm faster. Moreover, regarding all visible border grids as candidates when expanding successors, A*BG does not influenced by the size of neighborhood and it is able to search in every direction.

figure a

5 Simulation Experiments

To test the performance of the algorithms, in this section, we compare A*, A*PS, Theta* and A*BG with respect to their path length and computation time.

Fig. 5.
figure 5

(maps taken from [9]).

Location of ship accidents [16] and case study areas

Full size image
Table 2. Experimental results.
Full size table

5.1 Case Study Areas

Safety is one of the main factors that should be kept in mind when planning for autonomous vessels. Consequently, we choose for our experimental areas inland waterway regions where relatively many accidents have taken place in the past.

The locations of ship accidents occurred in Dutch inland waterways during 2008–2015 are shown in Fig. 5. The places where accidents frequently occur are ports and intersections. Accordingly, we choose an intersection and a port area for carrying out the experiments. Case Study 1 is the area of the Oude Maas. It is an intersection near the Port of Rotterdam, where is the convergent place of river Noord, Benede-Merwede, Dordsche Kil and Oude Maas. Case Study 2 is Port of Rotterdam. It is the largest port in Europe and the place accidents most frequently occurred.

Fig. 6.
figure 6

Experiment results (Ngb: Neighborhood of the algorithms).

Full size image

5.2 Setup

All algorithms tested in our experiments are grid-based. Thus, the maps of our case study areas are transfered into \(500 \times 250\) grids. The length of 1 grid is 1 unit. The buffer area in Case study 1 is two grids near the obstacles and in Case study 2 is 1 grid. Vessels can sail in the buffer area, but with a penalty length. We use middle lines to take the regulations into consideration. To study the influence of the size of neighborhood, the algorithms are carried out with increasing neighborhood (from \(neighborhood=1\) to \(neighborhood=10\)).

The algorithms tested in our experiments maintain three values for every node: \(g(s_\mathrm {start},s)\) is the length of the path from \(s_\mathrm {start}\) to s; \(h(s,s_\mathrm {goal})\) is the straight-line distance of s and \(s_\mathrm {goal}\); \(f(s_\mathrm {start},s,s_\mathrm {goal}\) is the sum of \(g(s_\mathrm {start},s)\) and \(h(s,s_\mathrm {goal})\). We use the Euclidean distance in the experiments. The distance between two nodes N(x, y) and \(N'(x',y')\) is \(\sqrt{(x-x')^2+(y-y')^2}\). That is, the distance from one grid to an adjacent left\right\up\down node is 1 unit, and to an adjacent diagonal node is \(\sqrt{2}\) units.

The experiments are run on a PC with a dual-core 3.2GHz Intel(R) Core(TM) i5-3470U CPU and 8GB of RAM. Each case has been repeated for 5 times.

5.3 Experiment Results

The results of the simulation experiments are shown in Table 2 and Fig. 6. The path length and average computation time over 5 repetitions are provided.

Fig. 7.
figure 7

Paths found in Case study 1.

Full size image

As shown in Table 2, two case studies show similar relations between the path length, computation time and the size of neighborhood. For A*, A*PS and Theta*, with the increase of neighborhood, the length of the paths becomes shorter, but the computation time increase dramatically as well. When the neighborhood is small, the length of the paths that the three algorithms found differs greatly. The difference decreases when the neighborhood is enlarged (Fig. 6). The path length of the three algorithms then approaches to a certain value.

With respect to A*BG, the size of neighborhood does not influence the results of A*BG. In the two case studies, A*BG shows the best performance. The path it computed is shorter than the shortest path the other three algorithms find, and the computation time is much shorter. Similar to other three algorithms, when the planning area becomes larger, the computation time of A*BG increases.

Figure 7 shows the path found in Case study 1. The paths calculated by A* with different size of neighborhood are shown in Fig. 7(a) as an example to show the impacts of the neighborhood size. Because the length of paths that the tested algorithms find differs greatly when \(neighborhood=1\), this situation is chosen as an example to present the difference of the paths found by different algorithms in Fig. 7(b). The main difference among the paths lies in the bend segments. The algorithms which find the shorter paths, A* when \(neighborhood=10\) and A*BG, find smoother paths at the bend segments.

6 Conclusions and Future Research

Autonomy is seen as a possibility for maritime transport to meet today’s and tomorrow’s challenges. In realizing autonomous navigation, path planning plays an important role. As a starting point of path planning for inland autonomous vessels, a modified A* algorithm (A*GB) is proposed to solve the global path planning problem. In this paper, we carry out experiments to compare the performance of A*, A*PS, Theta* and A*GB. Two places where ship accidents frequently occurred in the past are chosen as case study areas. The path length and computation time of each algorithms is analyzed. Trading off the path length and computation time, the performance of A*GB is more satisfying for inland autonomous vessels’path planning.

There are several directions in which this research will be extended. Firstly, when the planning area is larger, the computation time increases and the fineness of the grids also decreases, which affect the performance of the algorithm. The principle of Model Predictive Control can then be used to solve this problem. Long voyages are divided into smaller segments, after which a vessel updates its path at subsequence decision steps. Secondly, in this paper, the impact of infrastructures is not included. As important components in inland waterway system, infrastructures such as locks and bridges have great impact on inland shipping. Most delays are caused by operation of locks and bridges. Global path planning should also consider these influences. Finally, real-time information should also be taken into account. If preplanned paths are blocked due to accidents, or if there is a long waiting time at a certain lock, it is important that the vessel can replan its path according to real-time information.

Moreover, the global path planner considered here only provides reference paths considering static obstacles for an autonomous vessel. Algorithms for local path planning, i.e., collision avoidance, are needed to deal with the moving obstacles. These moving obstacles not only include other autonomous vessels, but also vessels operated by humans. With different obstacles, the information available is different. Besides, the actions controllers take and the resulting trajectories of the vessels operated by humans are uncertain. How the autonomous vessel communicates and coordinates with others using different sources of information and deals with uncertainties are future research problems.