{'fraction_non_alphanumeric': 0.023003194888178913, 'fraction_numerical': 0.0056975505857295, 'mean_word_length': 4.559798697454115, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards A COLREGs Compliant Autonomous Surface Vessel in a Constrained Channel

In this paper, we look at the role of autonomous navigation in the maritime domain. Specifically, we examine how an Autonomous Surface Vessel(ASV) can achieve obstacle avoidance based on the Convention on the International Regulations for Preventing Collisions at Sea (1972), or COLREGs, in real-world environments. Our ASV is equipped with a broadband marine radar, an Inertial Navigation System (INS), and uses official Electronic Navigational Charts (ENC). These sensors are used to provide situational awareness and, in series of well-defined steps, we can exclude land objects from the radar data, extract tracks associated with moving vessels within range of the radar, and then use a Kalman Filter to track and predict the motion of other moving vessels in the vicinity. A Constant Velocity model for the Kalman Filter allows us to solve the data association to build a consistent model between successive radar scans. We account for multiple COLREGs situations based on the predicted relative motion. Finally, an efficient path planning algorithm is presented to find a path and publish waypoints to perform real-time COLREGs compliant autonomous navigation within highly constrained environments. We demonstrate the results of our framework with operational results collected over the course of a 3.4 nautical mile mission on the Charles River in Boston in which the ASV encountered and successfully navigated multiple scenarios and encounters with other moving vessels at close quarters.


Navigation Rules (COLREGs)
The International Maritime Organization (IMO) promulgated the International Regulations for Preventing Collisions at Sea (COLREGs) ((IMO), 1972) in 1972. These are considered the "rules of the road" or the navigation rules to be followed by ships and other vessels at sea to prevent collisions between two or more vessels.
One way to attempt safe navigation for USVs is to emulate human behavior as closely as possible through COLREGs. In this paper, we consider the situations represented in Figure 1. These represent the responsibilities of power-driven vessels in sight of each other to prevent collision while passing close to each other.
A far more detailed description of responsibilities between vessels is provided in ((IMO), 1972). Figure 1: COLREGs maneuvers. The two interacting vessels are both required to follow COLREGs. We present the four fundamental scenarios, which encompass crossing, overtaking, and head-on situations between two ASVs. In covering these situations, our ASV (the Jetyak) is shown in yellow. intensity values from 0-255. The scan rate of the radar is one full rotation every 2.5 seconds (one full 360degree scan). Highly accurate heading information is delivered at 100Hz from the VN-300 INS with errors of the order of approximately 0.2 degrees RMS. All Mavlink messages are updated at 10Hz, with GPS updates at ∼2Hz.
Marine charts are required for our algorithm, and they typically provide accurate descriptions of the land, water depths, navigational aids, and features useful to safe nautical navigation. The Electronic Navigation Chart (ENC) provides a good description of the large-scale static environment. In our work, ENCs are used to overlay radar data and perform avoidance of the shoreline, other navigational hazards, and ultimately avoid dynamic and stationary obstacles. Where NOAA does not provide ENCs, as in our case on the Charles river, open-source QGIS software (QGIS, ) was used to create approximations of the land area using satellite imagery.

Binary Occupancy Grid
A binary occupancy grid is used to represent space occupied by known navigational hazards such coastlines and bridges as well as target vessels. Any black areas are considered static obstacles on the map, and any white area is considered open water space. A path planner can determine an obstacle-free path based on this map. See Fig. 3 for a representation of the Charles River binary occupancy grid.

Radar Processing
We overlay the radar data on the binary occupancy grid map of the environment. It is completed by offsetting the radar scanline angle from the Jetyak's heading and global position. The global position data is computed in Universal Transverse Mercator coordinates (UTM). After data overlay, we can extract target vessels on the river and exclude land area in the next step as illustrated in Figure 4.
There is a dead zone of returns near the radar, which appear as occupied grids but in reality are an artefact of the radar. The dead zone occupied grids can sometimes connect to real obstacles near the Jetyak.
To differentiate between these two cases, we find the lowest intensity point at the junction of the radar intensities and radar signal returns before the junction point are considered the dead zone. Other signals after the junction are treated as obstacles. We filter out all the signals that are considered to be in the dead zone. See

Target Extraction
As the first step of target tracking, the components of the radar scan corresponding to known land in the ENC map is removed. In contrast to Blaich et al. (Schuster et al., 2014) which removes objects based on whether the center point lies on land or water, we use a polygon based approach. As an offline processing step the ENC (or map from QGIS for the Charles River) is converted to polygons for fast online processing.
For each radar scan, nearby radar intensities are first grouped by connected component labeling. These connected components become separate polygons in the binary occupancy grid map. If the radar polygons are verified to intersect the land polygons that we extracted, we consider them to be stationary land objects  Figure 6: Processed radar data. The red polygon is the potential target, and the gray polygons on land are considered stationary land objects. The green rectangle is the Jetyak itself. We note that the radar returns often encompass parts of the river which we conservatively classify as land. and merge these radar polygons with the land area polygons. Otherwise, the radar polygon is considered a potential target in the water. All the potential targets are kept for the further processing. Figure 6, shows an example with the red target polygons we extracted as a candidate target and the gray polygons on land that we classified as stationary land objects. Our ASV is represented as a green rectangle. We take the center of all the target polygons and track them individually with a Kalman Filter.

Target Tracking
Although tracking targets by Automatic Identification System (AIS) is available on some marine radars, and used for ASV applications by Kazimierski et al. (Kazimierski and Stateczny, 2015) and Tetreault et al. (Tetreault, 2005), our tracking algorithm when integrated with an ENC is simpler, open-source and available for any radar platform.

Kalman Filter
A Kalman Filter is implemented to determine a given target's position in x and y, and its velocity along x and y. In our case, only x and y can be measured for the target, which are derived in the previous step described above. A constant velocity model is applied to track the target's motion.
The state vector is given by (1) p x : distance to the east in UTM p y : distance to the north in UTM v x : speed along the x (east) axis v y : speed along the y (north) axis The initial state noise covariance matrix P is defined as: Prediction stage: We predict the vessel's motion based on a constant velocity model where the process model is given by Because the target's motion does not always follow a constant velocity model, we add the noise term ν representing the additional acceleration.
We can decompose the noise term ν: Q is the process noise covariance matrix, which is the expectation of νν T As G does not contain any random variable we can rewrite this as As a x and a y have no correlation, which means σ axy = 0, we can simplify Q ν Thus, the Q matrix becomes So that we can compute the prediction state covariance as P = F P F T + Q Update stage: We update the vessel's position and velocity based on the radar measurement.
The radar measurement z includes position p x and p y : The measurement noise covariance matrix R can be defined as: We also define matrix H which is used to transform state x to measurement z:

Data Association
We run a separate Kalman Filter for each target that is identified in the radar scans. We assume that any object creates only one single measurement (one polygon in the binary occupancy grid), and one measurement can be created only by a single object. To disambiguate multiple targets we use a data association algorithm.
The Kalman Filter calculates a predicted state estimation for each target for the next time step, including a predicted position and its covariance. We use the elliptical shape of the covariance as a gate. If a target in a succeeding frame is in the gate associated with a target's predicted state in the current frame, then these two targets are considered to be the same. If there are multiple targets in the same gate in the next frame, we compute the likelihood of every target in this gate associated with the corresponding target in the original frame. The probability density function given by the Kalman Filter can be applied to get the probability, which corresponds to the likelihood in this case can be use for data association. We aim to maximize the sum of all the likelihoods for all the associations. The associations with the highest probability are selected.
In practise this method works extremely well as illustrated in Figure 7. If a new target shows up in a frame, then it would be associated with a "null" target in the previous frame, which leads to a likelihood of zero, so that the new target can be recognized and initialized. If a target disappears in a succeeding frame, the target in the current frame would be associated with a "null" target.
Associations of targets are checked in two ways to prevent highly improbable results. As a first check, we use the maximum distance we believe any given target could travel in the time between measurements, range = v · t meas . In our case, since t meas ≈ 2.5s for each radar scan and we are highly unlikely to encounter any vessels on the Charles with a v > 10m/s, we use range = 25m. In environments where we do expect to see faster vessels, range can be increased accordingly. Another check is implemented by restricting the size of the gate. The likelihood computed by the probability density function (pdf) has a threshold that restricts the size of the covariance ellipse. In our case, we use a threshold of 10 −6 . Figure 8 shows the results of our data association algorithm for multiple targets across multiple frames. The red lines in the figure are the trajectories of those targets. Figure 8: The Result of Data association. There are three target vessels near the Jetyak. We detect each target separately and associate their trajectories across multiple frames.
After the data association, measurements can be input to the Kalman Filter to run the update functions.
Then the posterior probability of each target is retrieved as the current state of the Kalman Filter, including UTM coordinates p x and p y , velocity along each axis v x and v y , and corresponding state covariance P .
Sometimes the target disappears for a single frame but then reappears. Typically, this happens when the target is too close to the coastline and gets lumped as a land object. Two frames are cached to avoid losing track of such targets in such a situation. As there is no measurement in the frame where the target disappears, only the Kalman Filter's prediction step is run.
(a) COLREGs situations (b) COLREGs projections. We pad the additional blue projections onto the target polygons according to the COLREGs situation, ensuring that the Jetyak modifies its behavior to follow COLREGs.

COLREGs Projection
In order to avoid other target vessels in accordance with COLREGs, a virtual forbidden polygon is applied to each vessel in accordance with the active COLREGs rule.
To do this, first, a check is performed to see whether the target vessel is in front of the Jetyak. Only if the target vessel is in front of our ASV do we take action to enforce COLREGs on the Jetyak.
If the target vessel is determined to be in front of us, we need to decide what actions have to be taken according to the COLREGs situation. The COLREGs situation is determined by computing the difference between the Jetyak's heading θ a and the target's heading θ b where dif f = θ a − θ b . Figure 9a shows the relationship between the heading difference and how that translates to vessel interactions under COLREGs.
After considering the difference, the applicable COLREGs projection is applied as an forbidden area in the binary occupancy grid. Figure 9b shows the different COLREGs projections corresponding to the COLREGs situations. We can see the yellow line (planed path) successfully avoids the target vessel while following COLREGs in each case. Figure 10 shows the results of applying COLREGs velocity obstacles in different situations while running our algorithm for real world situations associated with our test deployments.
(a) Head on: COLREGs require the Jetyak to pass on the right side of the target vessel.
(b) Overtaking: COLREGs require the Jetyak to overtake the target vessel from the right side.
(c) Crossing from the right: COLREGs require that the Jetyak not block the target vessel when it is crossing from the right to the left.
(d) Crossing from the left: COLREGs requires the Jetyak to hold course and not give way to the target vessel when the target is crossing from the left to the right. Finally, we can account for the COLREGs projections by using a reactive motion planning algorithm based on elements of the one proposed by Kuwata et al. (Kuwata et al., 2014). Rather than evaluating an optimal trajectory for the USV as Kuwata does, the velocity obstacles are represented as polygons in the binary occupancy grid of the environment. When the risk of collision is deemed to exist for the Jetyak's current set of waypoints, a new set of waypoints is created through the use of Visibility Graph Inspired Path Planning (VGIPP). These waypoints modify the global path for the Jetyak and are executed to avoid collisions related to COLREGs. Using VGIPP is computationally very efficient for our application.
VGIPP is based on the binary occupancy grid map. All the stationary and dynamic obstacles with their COLREGs projections are represented as occupied polygons on the map. The part of the grid that is not occupied is considered safe for traversal.
First, we pre-define a global path for the entire trip. As our river transit involves sections that are relatively narrow in parts, we choose a path that keeps us in the center of the river. This is not the shortest path, but avoids getting the vessel very close to shore. Figure 11: The Path Planning algorithm. We predefine a safe path (step 1) independent of any obstacles. We then set the shorter contour of obstacle polygons as the temporary safe path (step 2). We continue to refine the path by checking each point from the end point to the start point, to see whether this point can directly connect to the start point. If a shorter path is detected, we take that as the new path. After checking all the points after the start point, we repeat the procedure with the second point as the start point, and check all the points after it. After all the points are checked in this way, the final path is selected (steps 3 and 4).
While transiting down the river we are continually running VGIPP as illustrated in Figure 11. The predefined path may intersect with some obstacle polygons, and we find the contours of these polygons. These contours can, in turn, be split into two sets of polylines. We use the shorter polyline as our temporary optimal path.
We then check each point from the end point to the start point, to see whether the point under consideration (c) We then get the shorter contour of obstacle polygons as the temporary safe path.
(d) Finally, we optimize the temporary path by checking to see whether there is a shorter path in the route. can directly connect to the start point. If a shorter path is detected, we use the path as our new optimal path. After checking all the points after the start point, we repeat the procedure using the second point as our start point, and checking all the points after it. After all the points have been checked in this way, the final path emerges. Figure 12 shows how VGIPP is implemented.
If the Jetyak is already in an unsafe area, such as the COLREGs projection of a target, it tries to escape that area first. The algorithm finds the nearest safe point and creates a path to it, and then continues to find a safe path to the destination.
This algorithm is not guaranteed to yield an optimal result, but it is very efficient in the binary occupancy grid. In our case, the size of the binary occupancy grid map is 4000 2 . A traditional algorithm could take orders of magnitude longer to calculate the shortest path in such a huge and detailed map for each scan.
The VGIPP works efficiently in this case, which takes only around 0.2s to get the result with Python. In most cases, VGIPP does yield the optimal path. In complex environments, it also guarantees that the safe path can be detected if one exists. We note that if no acceptable path is found, the Jetyak can slow down and come to a complete stop.

Conclusions and Future Work
In this paper we have presented an end-to-end system that is capable of navigating in constrained waters while respecting the constraints associated with COLREGs. Our minimal sensor suite consists of GPS, IMU and Radar measurements.
Currently, we can collect data from radar, GPS, IMU, and compass sensors with ROS and replay the data to calculate obstacle-free waypoints that comply with COLREGs. While those waypoints are not executed live on the Jetyak due to safety and permitting concerns, they are calculated in real-time with real data and can be used to avoid collision with both dynamic and static obstacles in a complicated environment.
The processing time of the whole algorithm in Python is around 0.3s per radar scan on an i7-10750H CPU (2.60GHz with 6 cores).
We continue to work on extending our algorithm to include sensors such as cameras and lidars to allow us to work in more diverse areas, such as coming up and crossing under a bridge where our algorithm would fail due to shortcomings in the radar. We would also like to extend our work to areas that are GPS denied such as rivers that are narrow and covered by trees.