Computer Science Engineering
Computer Science-2021.gz:143173
Computer Science
856b0e007300278260793853394a4a9c4178b6b5
Grounding-aware RRT* for Path Planning and Safe Navigation of Marine Crafts in Confined Waters

The paper presents a path planning algorithm based on RRT* that addresses the risk of grounding during evasive manoeuvres to avoid collision. The planner achieves this objective by integrating a collective navigation experience with the systematic use of water depth information from the electronic navigational chart. Multivariate kernel density estimation is applied to historical AIS data to generate a probabilistic model describing seafarer's best practices while sailing in confined waters. This knowledge is then encoded into the RRT* cost function to penalize path deviations that would lead own ship to sail in shallow waters. Depth contours satisfying the own ship draught define the actual navigable area, and triangulation of this non-convex region is adopted to enable uniform sampling. This ensures the optimal path deviation.


INTRODUCTION
According to a report by the European Maritime Safety Agency, incidents rooted within human error, such as collision, contact and grounding, account for 44% of the total, with specifically grounding accounting for 13% (EMSA, 2020). Ugurlu et al. (2015) investigated grounding incidents caused by human error, and found that poor usage of the available equipment and poor assessment of the situation are key triggers. Decision support systems for collision and grounding avoidance can significantly improve the safety of navigation, by providing the human navigator with path alterations that are optimal with respect to the collision scenario and surrounding environment. Navigation in confined waters is challenging since collision avoidance must be weighed against the risk of grounding, possibly overestimated by navigators in search for more comfortable, deeper waters. Nonetheless, the collective navigation experience of seafarers across years of sailing may enable the creation of "good seamanship" models to inform the collision and grounding avoidance algorithms about best sailing practices. This paper researches a method to harvest such collective navigation experience and encode it into a probabilistic model describing seafarers' sailing behaviour in confined waters. Further, the paper specializes the RRT* path planning copyright 2021 the authors. This work has been accepted to IFAC for publication under a Creative Commons Licence CC-BY-NC-ND algorithm by integrating this probabilistic model with water depths information retrieved from the electronic navigational chart (ENC) to compute optimal path deviations to deconflict collision scenarios.

Related work
Methods for quantifying and including relevant environmental information for safe navigation and collision avoidance within confined waters has been widely investigated. The review by Huang et al. (2020) provides a broad insight into the typical components required for collision avoidance methods, with a distinction between motion prediction, conflict detection and resolution. Vagale et al. (2021a,b) presented a detailed review of the path planning aspect of collision avoidance, discussing the potential advantages and challenges for autonomous surface vessels, as well as presenting various planning schemes. Chen et al. (2020) used a binary occupancy grid along with the Fast Marching Method, and Singh et al. (2018) similarly with the A* algorithm. Bitar et al. (2020) detailed a two-stage trajectory planner, where the initial step uses a discretized polygonal representation of the configuration space, such that a hybrid A* algorithm can compute an initial dynamically feasible trajectory. Xue et al. (2011) generated potential functions from arbitrary polygons, as well as satellite images, for use with an Artificial Potential Fields algorithm. Both Candeloro et al. (2017) and Niu et al. (2018) combine the use of Voronoi diagrams with real spatial data. Martinsen et al. (2020) detailed the use of Constrained Delaunay Triangulation on land contours, to obtain an adjacency graph for trajectory refinement. Tsou (2016) formed obstacles and Predicted Areas of Danger (PADs) by utilizing information from the Electronic Chart Display and Information System (ECDIS) and AIS, in order to plan using a genetic algorithm. Reed and Schmidt (2016) and Otterholm (2019) both detailed the use S-57 charts in the context of collision avoidance, and presented various approximations for the obstacles.
Sampling-based planning strategies are prime-candidates for computing both feasible and optimal paths within the space such as those defined by the non-convex depth contours. Since its inception, the Rapidly-exploring Random Trees (RRT) algorithm (LaValle, 1998) has played an important role in sampling-based strategies, with Karaman and Frazzoli (2011) introducing the asymptotically optimal RRT*. Within sampling-based collision avoidance schemes for marine crafts, Chiang and Tapia (2018) detailed the use of a non-holonomic RRT, modelling the land masses as arbitrary polygons. Zaccone (2021) presented a COLREGs compliant RRT*, which minimized path length, curvature and repulsion from objects. Enevoldsen et al. (2021) presented the COLREGs-Informed RRT*, which directly samples COLREGs compliant trajectories for single vessel encounters in open-waters.

Novelty and contribution
This paper proposes a novel marine-oriented RRT* path planning algorithm for collision and grounding avoidance of vessels sailing in confined waters. Current samplingbased algorithms adopted within the marine domain, such as RRT*, consider simplified or artificial representations of the environment. In contrast this contribution operates directly on environment information (e.g. depth contours) extracted from the real electronic navigational chart. We introduce the concept of collective navigation experience to describe the best practices of seafarers while sailing in a given restricted sea region. We propose to use multivariate kernel density estimation on historical AIS data to generate probabilistic models that describe the seafarers' behaviour in steering vessels of different draught. We define the planning region by extracting from the ENC depth contours satisfying the vessel's draught requirements, and we propose triangulation of such non-convex polygons as a mean to achieve uniform sampling of the space. This ensures optimality of the sought path deviation. The probabilistic model is exploited in the RRT* cost function to sway the path planner towards deconflicting path alterations that favor comfortable navigation, as seen from the eyes of human navigator, while still exploring the whole navigable area as described by the ENC.

Vessel assumptions
Own ship This study concerns path planning for large vessels with maneuvering restrictions due to their draught and minimum required turning radius, such as ro-ro vessels, container feeders, bulk carriers, etc. It is assumed that a track control system is responsible to steer the vessel based on a sequence of waypoints W i = (N i , E i , R i ), where N i is the North position, E i is the East position, and R i is the radius of acceptance. The manoeuvring capabilities (e.g. minimal turning radius) of own ship are accounted for when generating a feasible waypoint sequence. overtaking, head-on and crossing scenarios. The solid coloured vessel is in a give-way situation.
Target vessels Target vessels are characterized by means of a comfort zone described by an ellipse whose dimensions are related to the ship length L, with 8L and 3.2L defining major and minor axis, respectively (Hansen et al., 2013).

COLREGs description and compliance
Any collision avoidance system must adhere to the "rulesof-the-road", namely the COLREGs. The most frequently considered rules are Rules 13-15, which deal with overtaking, head-on and crossing scenarios, respectively. The rules are defined for single-vessel encounters, assuming both vessels are power-driven. Figure 1 visualizes the beforementioned rules, where the vessel in give-away situation must yield for the stand-on vessel. For Rules 14 and 15, the give-way vessel must pass on the starboard side of the stand-on vessel, whereas both a port and starboard passing for Rule 13 is valid. The relative bearing between own ship and target vessel determines the collision scenario at hand. For further details regarding the relevant COLREGs, interpretation of the relative bearing, and assessment of the collision scenario see (Enevoldsen et al., 2021).

Electronic Navigational Charts
The electronic chart display and information system is a compliant, digital alternative to paper nautical charts. The ECDIS serves the navigator with important information, typically contained within the conventional paper charts, as well as information from RADAR and AIS. The Electronic Navigational Charts (ENCs) must conform to the S-57 standard in order to be used with the ECDIS. Within the S-57 charts various information layers exist, containing data about land and depth contours, buoys identifiers and placement, recommended navigational tracks, dredges, restricted areas, etc. The information contained within the ENC is fundamental for navigating in confined waters, since it directly encodes geographical areas which are feasible with respect to the draught of a given vessel. Therefore, the information layer of the ENC utilized for this particular study is that one containing the depth contours, namely DEPARE. For visualization purposes the land masses contained within LNDARE are also extracted. Through software, all depth contours intersecting with a geofilter are selected and subsequently cropped (Fig. 2a), resulting in a collection of polygons described by their geodetic coordinates, minimum and maximum water depths. Figure 2b visualizes the cropped depth contours with minimum water depth greater than 6m (white areas are waters shallower than 6m).  Extracting data from the S-57 ENCs using a pre-defined geofilter (black square in Fig. 2a), and subsequently manipulating the polygons in order to extract contours with a specified minimum water depth (Fig. 2b).

Multivariate Kernel Density Estimation
Kernel density estimation belongs to the family of nonparametric methods for estimating an unknown probability density function based on a finite data sample.
. . , n, be a sequence of independent and identically distributed p-variate random variables drawn from an unknown density f . Then, the general form of the p-dimensional multivariate kernel density estimator is (Gramacki, 2018) f where H = H > 0 is the non-random p × p bandwidth matrix, and K(·) is the unscaled kernel.
The bandwidth matrix and the kernel determines the degree of smoothness of the estimated density, which in fact inherits all the smoothness properties of the underlying kernel. Probability density functions are generally adopted as kernel functions. This implies that the area under the kernel must be equal to one, and that the kernel function is always positive. A commonly adopted kernel is the multivariate normal density The bandwidth matrix H determines both the amount and orientation of the smoothing. In the most general case of an unconstrained bandwidth, there are n(n + 1)/2 parameters to be determined in order to achieve the desired level of smoothing. Due to the complexity of solving the unconstrained case, it is common to constrain the bandwidth matrix such that H = h 2 I p with h > 0 or H = diag{h 2 1 , h 2 2 . . . , h 2 p } with h i > 0. In these cases there is a wide array of methods that can be applied to estimate the values of the parameters h i from the available data (Gramacki, 2018, Chapter 4). Estimation problems addressing large data sets with high dimensionality show a computational complexity as high as O(n 2 ), if a naive evaluation of the kernel function K(·) is performed. Several methods have been developed to accelerate the computation of the kernel functions (Raykar et al., 2010), and one of the most effective applies the Fast Fourier Transform (FFT) (Silverman, 1982;Gramacki and Gramacki, 2017).

Automatic Identification System (AIS)
The overall collection of historical AIS data is represented as the set A, whose elements are messages m containing the following data entries: the Maritime Mobile Service Identity MMSI i , the timestamp t i , the speed-overground SOG i , the vessel draught D i , the vessel position in geodetic coordinates (latitude λ i and longitude φ i ). The generation of the collective navigation experience for a specific geographical region is based on a subset of A, which contains data pertaining to vessels sailing in such region. Let introduce the geodetic region of interest Then the set containing the data relevant to the estimation of the collective navigation experience for vessels with draught larger than or equal to a given draughtD is defined as The set V guarantees that only AIS messages from marine vessels are considered, leaving out from the set ND data referring to drifting buoys and fast moving rescue vehicles.

Learning navigators' best practices in confined waters
Navigating within confined waters presents a plethora of new variables for navigators to consider, including the trade-off between voyage duration and safe passage. Safe navigation in complex waters is heavily dependant on the traffic within said waters, and the constraints presented by shallow waters. These trade-offs occurring within Danish waters have been documented through a national database of AIS messages. By computing multivariate KDEs using the past positions of vessels within the region of interest, the collective navigation experience can be quantified in a probabilistic sense.
The top left corner of Fig. 3 shows an example of AIS data for the region of interest .72 • }, corresponding to the Little Belt area in Denmark. The data refers to vessels navigating in the speed range of interest V = {SOG i | 0.5kn < SOG i < 50kn}. Different KDEs can then be estimated by creating the set ND for different values ofD. For the estimation process we utilized the multivariate normal density as kernel function, and the constrained bandwidth model H = h 2 I p where h was hand-tuned. The actual estimation of the kernel density was performed leveraging the Python toolbox KDEpy (Odland, 2018); specifically the FFT-based KDE scheme was utilized for its superior computational speed on the large AIS data set. Figure 3 details the resulting KDEs estimated on three sets ND for increasing value ofD, and the underlying ENC data corresponds to waters whose minimal depth is greater than the specified draught. By excluding parts of the data set based on draught restrictions, the overall encoded behaviour from previous navigators changes. An important thing to note in this particular study-case is that, despite there is a direct northbound path, the majority of density moves North-West, before continuing North-East. This indicates that through past experiences, the navigators deem the passage directed North less safe, due to the heavily restricted waters, compared to prolonging the journey and increasing the overall safety margin. This shows that the probabilistic representation contains valuable information regarding the safe navigation of confined water areas. As observed, past navigators consistently practice navigational safety, which is evident within the historical data, where the majority of the density maintains a safe distance from shallow waters and other waters which are associated with higher navigational risks.

Problem definition
The generalized optimal planning problem considered in this paper is defined in a similar fashion to (Gammell et al., 2014). Let X ⊆ R n be the state space, which is divided into two subsets, X free and X obs , with X free = X \X obs . The states within X free contain all states that are feasible with respect to maneuvering constraints, COLREGs compliance, collision and grounding. Let x start ∈ X free be the initial state at t = 0 and x goal ∈ X free be the desired final state. Let σ : [0, 1] → X be a sequence of states constituting a found path and Σ be the set of all nontrivial and feasible paths. The objective is then to find the optimal path σ * , which minimizes a cost function while connecting x start to x goal through X free , σ * = arg min σ∈Σ c(σ) | σ(0) = x start , σ(1) = x goal , ∀s ∈ [0, 1], σ(s) ∈ X free } .

(5)
We propose a cost function that trades off between two performance indexes: the path length and the grounding risk. The latter is defined as the complementary of the normalized kernel density estimate, and represents the discomfort of fellow navigators when manoeuvring vessels too close to shallow waters. The cost function reads as c(σ) = w 1 (1 −F (σ)) + w 2 l(σ) (6) with scalar weights w i , the over all path length l(σ), and is the normalized kernel density along the path σ. Remark 1. The simple structure of the cost function (6) aims at emphasizing the role of the collective navigation experience encoded in the estimated kernel density towards the generation of the path deviation during a potential collision scenario. However, the RRT* offers a general framework where the cost function can include an arbitrary number of performance indexes focusing on e.g., speed loss, energy consumption, fuel consumption, etc.

RRT*
The underlying RRT* algorithm is a marine-oriented variant of the general algorithm presented by Karaman and Frazzoli (2011). Algorithm 1 describes the main structure of the general RRT* planner. The routine consists of growing a tree T = (V, E), where V and E represent the sets of nodes and edges, respectively. A given node x represents a particular state at time t, containing the North-East position of the vessel, with the connecting edges containing cost and constraint information. The algorithm is modified to incorporate the cost function (6). Feasible(x nearest , x new ) ensures that only feasible nodes are added to the tree, and therefore rejects node sequences that are either non-COLREGs compliant, outside the bounds of X free or violates the remaining constraints (such as the minimum turning radius). Due to availability of depth contours within the ENC, which directly encode a draught dependant representation of X free , the proposed sampling strategy is tailored in order to leverage the nonconvex polygons that describe the navigable regions. The following section, details the proposed uniform sampling scheme of general non-convex depth contours.

Sampling non-convex depth contours
The depth contours extracted from the ENC are represented by arbitrary non-convex polygons. To achieve the uniform sampling of this space, thereby ensuring optimality of the sought path, the Constrained Delaunay Triangulation (CDT) (Chew, 1989) is applied to decompose the non-convex polygon into a finite set of triangles. CDT guarantees that all the obtained triangles are contained within the perimeter of the polygon. Figure 2c shows CDT applied to the polygon data obtained from the depth contours in Fig. 2b. The uniform sampling of the obtained triangles is a two-step procedure: first there is the uniform selection of a triangle, weighted by area; then the uniform sampling of the selected triangle takes place. Given any triangle composed by vertices (A, B, C), a uniformly sampled point P within the triangle is then described by P = 1 − √ r 1 A + √ r 1 (1 − r 2 ) B + √ r 1 r 2 C (8) where r 1 ∼ U(0, 1) and r 2 ∼ U(0, 1) (Osada et al., 2002).The polygon geometries contained within the ENC are represented at a very a high resolution. Hence it is recommended to simplify the polygons using a line simplification method, such as the Douglas-Peucker algorithm (Douglas and Peucker, 1973). Remark 2. The standard RRT* algorithm performs sampling in a rectangular region surrounding the space where the path needs to be planned. For navigation in confined waters, the sampling of such space is highly inefficient with respect to finding the optimal path. This is because many samples are likely to fall in correspondence of land masses and shallow waters. Rejection sampling is therefore applied to retain only the valuable samples. On the contrary, sampling the triangular regions within the perimeter of the depth contours is highly efficient since all the samples in such region contributes to improve the found solution.

RESULTS
The grounding-aware RRT* planner is evaluated on two confined water scenarios. Each scenario includes a singlevessel encounter, where own ship must perform an evasive manoeuvre to avoid collision. The planning scheme receives the position of own ship as the starting configuration, and selects a point along the nominal trajectory as the goal configuration. The resulting trajectories for both scenarios are visualized in Fig. 4. Two different deviations,  with differing objectives, were computed for each scenario. For the first objective, the weights of the cost function (6) were selected to emphasise the value provided by the learned behaviour from the AIS data, and for the second the weights were selected to only consider the minimization of the path elongation (i.e. w 1 = 0).
In the first scenario, Fig. 4a, own ship is travelling northbound through the Little Belt area when it encounters a target vessel also northbound, but travelling at a lower speed. The encounter with the target vessel is identified as an overtaking scenario, using the relative bearing. The second scenario, Fig. 4b, features own ship heading South down a narrow channel at the Great Belt area. The grounding-aware RRT* planner is initiated due to an incoming target vessel that, based on the relative bearings, is identified as a head-on encounter. This implies that own ship must yield.
In both study-cases, the grounding-aware RRT* path planner computes a COLREGs compliant path alteration, which ensures both the collision avoidance and the safe navigation across confined waters. The computed path alterations clearly show how the planner negotiates between the collective navigation experience embodied by the KDE and the water depth information provided by the ENC. The former attracts the path of own ship to traverse waters that have been heavily navigated in the past by other vessels of equal draught; the latter pushes the path to cross deep enough waters closer to shore to ensure that the comfort zone of the target vessel is never violated during the evasive manoeuvre. The combined effect is a path deviation that concomitantly achieves collision and grounding avoidance while safeguarding the navigation comfort of both own ship and target vessel. The two additionally computed deviations which seek to minimize the path length, also provide COLREGs complaint path alterations, however both disregard the risks associated with traversing possibly too shallow waters. This results in a more risky passage due to both potential grounding risks and the limited space for maneuvers given additional incoming vessels. The paper proposed using triangulation of the depth contours for computing valid samples in scenarios with confined waters. Its performance is compared against a standard sampling approach based on a rectangular region and rejection sampling. The comparison is performed using Monte Carlo simulations. Figure 5 illustrates the computational time in seconds as the number of valid samples increases: it is evident that the proposed triangulation scheme outperforms the baseline rejection sampler. Additionally, the performance related to configuring the sampling spaces is provided in Table 1.
For both scenarios, the triangulation scheme is initially at a disadvantage, since on average it takes longer to extract the contours and compute the triangles, compared to simply extracting the depth contours as required by the rejection sampler. It should be noted, that due to variations in the polygonal data between the two scenarios, the preprocessing duration differs between the two presented scenarios. However, once the configuration of the sampling spaces is finalized, the proposed triangulation based sampling scheme significantly outperforms the rejection sampling scheme at higher sample quantities. The ability to rapidly compute valid samples is key for optimal samplingbased algorithms and the speed in which they converge to the respective optimal solution (Gammell et al., 2014;Enevoldsen et al., 2021). Noteworthy that the performance of the rejection sampling heavily depends on the area ratio between the surface inside the depth contours and the total surface within the bounding box. As the area ratio decreases, the probability of successfully computing a valid sample also decreases, leading to slower sampling performance. This is clearly shown in Fig. 5 where an area ratio difference of about 14% between the Great Belt and Little Belt study-cases produces a change of about 40% in computational time. This issue is mitigated by utilizing the computed triangulation, since it directly represents the valid sampling space, guaranteeing that any computed sample is valid, resulting in no wasted sampling effort.

CONCLUSION
The paper presented a grounding-aware RRT* path planning algorithm for collision avoidance in confined waters. The proposed algorithm combines the navigation experience of seafarers with the water depth information available through the ENC, to achieve optimal path alterations that trade off between comfortable navigation (not too close to shallow waters) and feasible navigation (crossing navigable areas for the current draught). The paper proposed the use of multivariate kernel density estimation on historical AIS data to generate a probabilistic model that describes the best sailing practices of seafarers in a given restricted sea region. This model is then used as cost factor in the performance index of a COLREGs compliant RRT* collision avoidance scheme. This enables the planner to compute safe path deviations, which are aware of both collision and grounding risks. Furthermore, compared to existing marine-oriented RRT* implementations, the presented scheme directly utilizes the complex geometries present within the chart data. Through triangulation the sampling scheme has increased probability of improving the computed solution. The augmented planning scheme was successfully demonstrated in simulation for two separate confined water collision scenarios, where the results clearly show the value provided by taking advantage of the prior navigational experiences.