COLREGs  UNI NORWAY, TRONDHEIM  COLAV
Please use our AZ INDEX to navigate this site or return HOME


COLREGS  Humans could be the weak link in future navigation by autonomous ships. Systems should be designed to be robust and upgradeable, at low cost. So that everyone can enjoy the safety of a robot at the helm. Remember when electronic calculators and computers were expensive!
This paper presents a threelayered hybrid Collision Avoidance (COLAV) system for autonomous surface vehicles, compliant with rules 8 and 13–17 of the International Regulations for Preventing Collisions at Sea (COLREGs). The COLAV system consists of a highlevel planner producing an energyoptimized trajectory, a modelpredictive, controlbased, midlevel COLAV algorithm considering moving obstacles and the COLREGs, and the branchingcourse model predictive control algorithm for shortterm COLAV handling emergency situations in accordance with the COLREGs.
Previously developed algorithms by the authors are used for the highlevel planner and shortterm COLAV, while we in this paper further develop the midlevel algorithm to make it comply with COLREGs rules 13–17. This includes developing a state machine for classifying obstacle vessels using a combination of the geometrical situation, the distance and time to the closest point of approach (CPA) and a new CPAlike measure.
The performance of the hybrid COLAV system is tested through numerical simulations for three scenarios representing a range of different challenges, including multiobstacle situations with multiple simultaneously active COLREGs rules, and also obstacles ignoring the COLREGs. The COLAV system avoids collision in all the scenarios, and follows the energyoptimized trajectory when the obstacles do not interfere with it.
Motivated by the potential for reduced costs and increased safety, the maritime industry is rapidly moving toward autonomous operations. Following groundbreaking advances in the automotive industry, many sectors within the maritime industry are considering the benefits of autonomy, which includes more environmentally friendly operations. For instance, the agricultural chemical company Yara together with the maritime technology supplier Kongsberg Maritime are developing the electrical autonomous container vessel Yara Birkeland, which aims to replace 40,000 yearly truck journeys in urban eastern Norway1.
Another example is the world's first autonomous car ferry, Falco, developed by
RollsRoyce (recently bought by Kongsberg Maritime) and Finferries. In 2018, Falco navigated autonomously between two ports in Finland2. Reports state that in excess of 75 % of maritime accidents are due to human errors (Chauvin, 2011; Levander, 2017), indicating that there is also a potential for increased safety in addition to the economical and environmental benefits.
Since the rules are written for humans, with few quantitative figures, a challenge for autonomous operation is to quantify them into behaviors that can be executed algorithmically. The focus of the work in this paper is to do that, and to design a hybrid COLAV system that performs motion planning and generates maneuvers in compliance to rules 8 and 13–17 of the COLREGs.
The reason for this is that many gradientbased algorithms are not sufficiently numerically robust, not allowing a COLAV system to solely rely on such an algorithm. This issue can be handled in hybrid architectures, constrained by the bottomlevel algorithm being numerically robust and able to handle extraordinary situations where the other algorithms fail. Hence, hybrid architectures also allows using gradientbased algorithms, which are able to solve problems with large search spaces more efficiently than samplebased algorithms.
The works by Loe (2008) and Švec et al. (2013) are examples of twolayered hybrid COLAV architectures. The top layers perform trajectory planning among static obstacles, while the bottom layers perform moving obstacle avoidance in compliance with COLREGs rules 13–16. Casalino et al. (2009) presents a threelayered hybrid COLAV system where the top layer also performs trajectory planning amongst static obstacles. The middle layer avoids moving obstacles, while the bottom layer implements safety functions for handling cases where the two other layers fail. This approach does, however, not consider the
COLREGs.
It considers static obstacles, which may include bathymetric constraints. Since the highlevel planner only considers static information, it is intended to be run offline, but it can also be run online, for instance if new static obstacles are detected. The midlevel algorithm attempts to follow the nominal trajectory, while performing COLAV of static and moving obstacles in compliance with COLREGs rules 8, 13–16, and the first part of Rule 17.
The midlevel algorithm is run periodically with a shorter temporal horizon than the highlevel algorithm, and produces a modified trajectory which is passed to the shortterm layer. Both the highlevel and midlevel algorithms use gradientbased optimization. The shortterm algorithm attempts to follow the modified trajectory, while it in compliance with the second part of Rule 17 handles situations where obstacles ignore the COLREGs. This algorithm also handles other emergency situations, and uses samplebased optimization to achieve a high level of robustness, ensuring safe operation if the midlevel algorithm fails to find a solution. The following list summarizes our contributions:
The vessel of interest in this article is the Telemetron ASV, which is owned and operated by the Norwegian company Maritime Robotics and shown in Figure 2. The Telemetron ASV is a highspeed dualuse vessel propelled by a steerable outboard engine, capable of speeds up to 18 m/s.
FIGURE 2. The Telemetron ASV, designed for both manned and unmanned operations. Courtesy of Maritime Robotics.
Eriksen and Breivik (2017a) presents a model of the Telemetron ASV, which is extended to include ocean currents in Bitar et al. (2019a). The model has the form M(xr)x˙r+σ(xr)=τ, (1)
where η = [x, y, ψ]⊤ ∈ ℝ2 × S is the vessel pose and Vc=[Vx,Vy]⊤
describes the ocean current, both in the Earthfixed NorthEastDown frame {n}. The vector xr=[ur,r]⊤∈Xr⊂R2 is the vessel velocity under the assumption of zero relative sway motion (Bitar et al., 2019a), where the set ��r describes the vesselfeasible steadystate velocities where (1) is valid. The transformation matrix R(ψ) is given by the heading ψ ∈ S as
while r ∈ ℝ describes the vessel yawrate. The matrix M(xr) is a statedependent inertia matrix, while σ(xr) and τ=[τm,τδ]⊤∈U⊂R2 describe the vessel damping and control input, respectively. The set �� describes the control inputs where (1) is valid.
To plan the ASV's nominal trajectory, we use a highlevel trajectory planner developed in Bitar et al. (2019b). This trajectory planner uses the ASV model described in section 2 to generate an energyoptimized trajectory between the start and goal positions. The planning algorithm combines an A⋆ implementation and an optimal control problem (OCP) solver to generate a feasible and optimized trajectory.
The elliptical boundaries are described with the inequality:
where xc and yc is the ellipsis center, and xa, ya > 0 are the ellipsis major and minor axes, respectively. To allow for angled obstacles, the ellipses are rotated clockwise by an angle α. We add a small constant ϵ > 0 to each side of the inequality, and take the logarithm to arrive at the following obstacle representation: +(−(x−xc) sin α+(y−yc) cos αya)2+ϵ]+log(1+ϵ)≤0. (4)
The logarithm operation is applied to reduce the numerical range of the inequality, which helps with numerical stability of the subsequently described solver, and the constant ϵ is included to avoid singularities when (4) is evaluated for (x, y) → (xc, yc) (Bitar et al., 2019a).
From a scenario consisting of static obstacles, as mentioned in section 3.1, we find the piecewise linear shortest path by performing an A⋆ search on a uniformly decomposed grid. The resulting path is converted to a timeparameterized fullstate trajectory by assuming a constant forward velocity, and connecting the shortest path with straight segments and circle arcs. The constant forward velocity is
where Lpath is the length of the connected path, and tmax is the maximum allowed time to complete the trajectory. This fullstate trajectory is then used as an initial guess to solve the OCP that gives the energyoptimized trajectory:
The solution of this OCP is a trajectory of states z(·) and inputs τ(·) that minimizes the cost functional in (6a).
The ASV model from section 2 is rewritten as z∙=f(z,τ), where z=[η⊤,x⊤r]⊤ and f(z, τ) represents (1).
with tuning parameters Ke, Kδ > 0. The first term consists of a function that is proportional to mechanical work performed by the ASV:
The function n: ℝ+ → ℝ+ maps the control input τm to propeller angular velocity. The function δ: ℝ → S maps the control input τδ to outboard motor angle. The second term in (8) is a quadratic cost to yaw control, included to avoid issues with singularity when solving the OCP.
The midlevel algorithm, initially presented in Eriksen and Breivik (2017b) and further developed in Bitar et al. (2019a), is a model predictive control (MPC)based algorithm intended for longterm COLAV. The algorithm utilizes gradientbased optimization, and takes both static and moving obstacles into account while attempting to follow an energyoptimized nominal trajectory from the highlevel planner. The algorithm produces maneuvers complying with Rule 8 of the COLREGs, which requires maneuvers to be made in ample time and be readily observable for other vessels. The optimization problem is formulated as a NLP, which gives flexibility in designing the optimization problem.
The COLREGs consists of a total of 37 rules and is divided into five parts (Cockcroft and Lameijer, 2004), where part B (rules 4–19) contains relevant rules on the conduct of vessels in proximity of each other. The most relevant rules for designing COLAV systems in part B are rules 8 and 13–17:
In the hybrid architecture illustrated in Figure 1, the midlevel algorithm is given the task of strictly enforcing COLREGs rules 13–16 and the standon requirement of Rule 17, while also complying with Rule 8.
A commonly used concept for interpreting obstacles in COLAV algorithms is to assign a spatial region to obstacles, which the ownship should not enter. This approach is commonly referred to as a domainbased approach. Specially designed ship domains are commonly used for interpreting the COLREGs in COLAV algorithms, where the required clearance to an obstacle is significantly larger if the maneuver violates the COLREGs (Szlapczynski and Szlapczynska, 2017; Eriksen et al., 2019).
This approach is attractive since it continuously captures multiple COLREGs rules, and does not require logic or discrete decisions. However, such an approach does not strictly enforce the COLREGs rules, since it will allow maneuvers violating the rules if they are large enough. In addition, a shipdomain approach will not be able to strictly enforce the standon requirement of Rule 17, since a domainbased approach will avoid collision with all obstacles. One could ignore obstacles with giveway obligations, but this would require an explicit COLREGs interpretation which conflicts with domainbased approaches' core idea of implicit COLREGs interpretation. Therefore, we pursue an alternative approach to handling the COLREGs in the midlevel algorithm.
For instance, an obstacle approaching from head on, but far enough away to not be considered as a danger may be put in a safe state. Hence, the midlevel algorithm will (for the current iteration) act like no COLREGs rule applies to this vessel for the entire prediction horizon, while the obstacle may get close enough during the prediction horizon to be considered as a headon situation. An MPC scheme of only implementing a small part of the prediction horizon will reduce the implications of this, since the situation is reassessed each time midlevel algorithm is run, which justifies the assumption of considering the COLREGs from a static perspective. Investigating the possibilities for dynamically predicted future COLREGs situations as part of the MPC prediction will be considered as future work.
We propose to utilize a state machine in order to decide which COLREGs rule is active with respect to each obstacle in the vicinity of the ownship. The state machine contains the states:
As shown in Figure 4, all transitions have to go either from or to the safe state.
FIGURE 3. Illustration of headon (A) and crossing (B) situations, and how they should be resolved.
FIGURE 4. COLREGs state machine. The abbreviations “GSF,” “GSO,” “GOT,” “GGW,” and “GHO” denote geometrical situations, while “entryxx” and “exitxx” denote additional statedependent entry and exit criterias.
This implies that when the state machine decides that a COLREGs (or emergency) situation exists with respect to an obstacle, it will not allow switching to another state without the situation being considered as safe first. One could argue that it should be able to transition between specific states, like e.g., from headon, giveway and overtaking to emergency. This is an interesting topic, which should receive attention in the future. To control the transitions between the different states, we combine the time to and distance at the CPA, a CPAlike measure of the time until a critical point and a geometrical interpretation of the situation.
CPA is a common concept in maritime risk assessment. Given the current speed and course of the ownship and an obstacle, CPA describes the time to the point where the two vessels are the closest, and the distance to the obstacle at this point. Given the position and velocity vector of the ownship p, v and an obstacle po, vo, the time to CPA is calculated as (Kufoalor et al., 2018)
where ϵ > 0 is a small constant in order to avoid division by zero in the case where the relative velocity between the ownship and obstacle is zero. Given tCPA, we calculate the distance between the vessels at CPA as
While the CPA is the point where the distance to an obstacle is at its minimum, the critical point is where the distance to an obstacle crosses underneath a critical distance dcrit. This critical distance describes a minimum obstacle distance that the midlevel algorithm is designed for. The time to the critical point tcrit can be calculated by solving the equation
In the cases where the distance between the ships does not fall below dcrit, tcrit is undefined. Otherwise, there are generally two solutions. The interesting solution is the one with the lowest tcrit value, as this is when the obstacle enters the dcrit boundary.
where d¯i,enterCPA,t–i,enterCPA, and t¯i,enterCPA for i ∈ {SO, OT, GW, HO} are tuning parameters denoting thresholds on dCPA and tCPA in order to satisfy the entry criteria for the standon, overtaking, giveway and headon states. The tuning parameter t¯EM,entercrit denotes an upper limit on tcrit in order to enter the emergency state.
The idea behind the standon, overtaking, giveway and headon entry criterias are that in order for the obstacle to represent a risk, both tCPA and dCPA need to be within some tunable thresholds. Situations with a very low dCPA, but with a high tCPA, will not trigger the entry criteria, since the situations will not occur in the near future. Similarly, if tCPA is within the thresholds, but dCPA is large, this indicates a safe passing where risk of collision does not exist. The lower bound on tCPA will typically be selected as zero, and is useful to distinguish between obstacles moving toward of away from the ownship.
For the emergency state, the entry criteria is based on the critical point, at which we are so close that the midlevel algorithm may struggle with providing meaningful maneuvers. In addition to tcrit being under the threshold t¯EM,entercrit, we require that tCPA is positive, indicating that we are getting closer to the obstacle. Currently, we only allow entering the emergency state if the situation is a geometrical giveway or headon, since an overtaking situation represents a smaller danger and has less requirement for special consideration.
where d−−i,exitCPA,t–i,exitCPA, and t¯i,exitCPA for i ∈ {SO, OT, GW, HO} are tuning parameters denoting thresholds on dCPA and tCPA in order to satisfy the exit criteria for the standon, overtaking, giveway and headon states.
The exit criteria for the emergency state is satisfied if tcrit is larger than the tuning parameter t¯EM,enterexit, or tCPA is negative, implying that the obstacle is moving further away from the ownship. Note that the exit criterias are obtained by negating the entry criterias, but with other thresholds in order to implement hysteresis to avoid shattering. In general, we allow for different tuning parameters for the different states, but in our simulations we see that selecting the same tuning parameters for all states provides good results. Therefore, we define:
Tam and Bucknall (2010) present a geometrical interpretation scheme for deciding COLREGs situations based on the relative position, bearing and course of the obstacle with respect to the ownship. We base our geometrical interpretation on a slightly modified version of this scheme, where we include the sign of tCPA to distinguish between situations where the obstacle moves closer toward or farther away from the ownship. The geometrical interpretation is shown in Figure 5, where the geometrical situation is obtained by finding which region the obstacle position and course resides in.
The geometrical situations are colorcoded and denoted as Gi, i ∈ {SF, SO, OT, GW, HO} for safe, standon, overtaking, giveway and headon situations, respectively. When two situations are given, like e.g., GSF/SO, we use the former (SF) if tCPA < 0 and the latter (SO) if tCPA ≥ 0, analogous to the obstacle moving away or toward the ownship. To decide the geometrical situation, we first find which relative bearing region the obstacle resides in, before finding which obstacle region the obstacle's course resides in. The figure is inspired by Tam and Bucknall (2010).
The highlevel planner produces an energyoptimized nominal trajectory for the ownship to follow. However, since the highlevel planner does not consider moving obstacles, the speed is the only timerelevant factor of the desired trajectory. In a case where the ownship for some reason, e.g., avoiding moving obstacles, lag behind the nominal trajectory, following the nominal trajectory in absolute time would cause a speed increase in order to catch up with it. Therefore, the midlevel algorithm performs relative trajectory tracking, where it tracks the nominal trajectory with a time offset tb ∈ ℝ. This results in a relative nominal trajectory for the midlevel algorithm:
where
pd=[Nd(t),Ed(t)]⊤ is the nominal trajectory from the highlevel planner. The time offset tb is calculated each time the midlevel algorithm is run by solving a separate optimization problem, and is selected such that p̄ d(t0) is the point on the nominal trajectory closest to the ownship. See Bitar et al. (2019a) for a detailed description of this concept.
The midlevel algorithm is formalized as an OCP:
subject to
where Th > 0 is the prediction horizon, ϕ(·, ·) is the objective functional, (17b) contains a kinematic vessel model, (17c) contains inequality constraints and (17d) contains boundary constraints.
subject to
g(w,η(t0))=0h(w,ξ)≤0h¯¯k(ηk,ωk,μk,p¯¯d,k)≤0∀k∈{1,…,Np}ξ≥0, (18)
The objective function contains four functions, where ϕp(w, ω, μ) introduces cost on deviating from the relative nominal trajectory p̄ d(t), ϕc(w) introduces cost on using control input, ϕCOLREGs(w) is a COLREGsspecific function and ϕξ(ξ) introduces slack variable cost.
The Huber loss function has a discontinuous gradient, making it slightly complicated to implement in gradientbased optimization problems. It can, however, be implemented in a continuous fashion by utilizing lifting, where slack variables are introduced to create a problem of a higher dimensionality which is easier to solve. Using this technique, ϕ̄ p(w,ω,μ) is defined as
where Kp > 0 is a tuning parameter, and ωk∈R2 and μk∈R2 are slack variables constrained by
where pk is the predicted vessel position at time step k, i.e., ηk=[p⊤k,ψk]⊤. See Bitar et al. (2019a) for more details.
where KU∙,Kχ∙>0 are tuning parameters, while qU∙(U∙k) and qχ∙(χ∙k) are the nonlinear cost functions. Notice that neither the speed over ground (SOG) U nor the course χ are elements of the search space, but they can be computed as U=u2+v2−−−−−−√ and χ=ψ+arcsinvU. Their derivatives are then calculated by finite differencing. See Eriksen and Breivik (2017a) and Bitar et al. (2019a) for more details on the control cost function.
where OHO,OGW,OSO, and OEM contain obstacles which are in the headon, giveway, standon and emergency states, respectively, and KHO, KGW, KSO, KEM > 0 are tuning parameters. The functions VHO, i, k(pk), VGW, i, k(pk), VSO, k(w), and VEM, k(w) describe functions capturing headon, giveway, standon and emergency behavior with respect to obstacle i, respectively. Notice that the headon and giveway functions vary with both the obstacle number and time step number, which is due to the functions depending on the given obstacles position and course at time step k.
where αx, HO, αy, HO > 0 are tuning parameters controlling the steepness of the headon potential function and x̄ 0,HO>0 is a tuning parameter controlling the influence of the attenuating potential. The coordinate (x{i, k}, y{i, k}) is p given in obstacles i's coursefixed frame (in which the xaxis points along the obstacle's course) at time step k, computed as
where po, k, i and χi, k are the position and course of obstacle i at time step k. The headon potential function with parameters αx, HO = 1/500, αy, HO = 1/400 and x0, HO = 1, 000 m is shown in Figure 6A.
where αx, GW, αy, GW > 0 control the steepness of the giveway potential function and ȳ0, GW < 0 control the attenuation on the port side of an obstacle.
The giveway potential function with parameters αx, GW = 1/400, αy, GW = 1/500 and y0, GW = −500 m is shown in Figure 6B.
If an obstacle is in an emergency state, the obstacle is disregarded in the midlevel algorithm and left for the shortterm algorithm to handle. In such a situation, it is important that the midlevel algorithm behaves predictable, and we therefore use the same cost function as for standon situations:
The slack variable ξ is used in a homotopy scheme, which we introduce to avoid getting trapped in local minima around moving obstacles. The homotopy scheme is described in further detail in section 4.5. The homotopy cost function ϕξ(ξ) introduces slack cost on ξ:
where Kξ > 0 is iteratively increased as part of the homotopy scheme.
The inequality constraint h(w, ξ) ≤ 0 ensures COLAV and steadystate feasibility with respect to actuator limitations.
ho(x1,y1,xc,i,yc,i,xa,i,ya,i,αi)ho(x2,y2,xc,i,yc,i,xa,i,ya,i,αi)⋮ho(xNp,yNp,xc,i,yc,i,xa,i,ya,i,αi)≤0. (30)
Moving obstacles are handled in a similar fashion, but letting the ellipsis center position and angle be time varying. Obstacles in standon situations should, however, not be included in the constraints, since the midlevel algorithm is supposed to stand on in such situations. Moreover, if an obstacle has entered an emergency state, the obstacle is so close and behaving unpredictably that the midlevel algorithm should disregard it and leave it for the shortterm layer. Hence, for the ith moving obstacle not in a standon or an emergency situation, we define the constraint
⎡⎣⎢⎢ho(x1,y1,xc,i,1,yc,i,1,xa,i,ya,i,αi,1)⋮ho(xNp,yNp,xc,i,Np,yc,i,Np,xa,i,ya,i,αi,Np)⎤⎦⎥⎥≤0, (31)
where xc, i, k, yc, i, k, and αi, k denote the position and course of the ith moving obstacle at time step k.
where we include slack variables ξ ≥ 0 on the moving obstacle constraints as part of a homotopy scheme. The reason for using homotopy is that NLP solvers in general only finds local minima, and can have issues with moving an initial guess “through” obstacles. Normally, this is not an issue, but for the midlevel algorithm the optimal solution can change drastically from one iteration to another. This can for instance happen if an obstacle enters a headon or giveway state, where the solution can be trapped on the wrong side of an obstacle.
In general, homotopy describes introducing an extra parameter which is iteratively adjusted in order to iteratively move a local solution toward a global solution (Deuflhard, 2011). In our homotopy scheme, we introduce slack variables on the moving obstacle constraints, which will allow solutions to travel through obstacles at the cost of a homotopy cost (29) scaled by the homotopy parameter Kξ. Initially, this is selected as a low value to have a high amount of slack on the moving obstacles, while it is iteratively increased toward Kξ → ∞, which results in ξ = 0 and hence no slack on moving obstacles. Currently, we only introduce slack on moving obstacles, but slack should also be introduced to static obstacles if they are small enough for the algorithm to be able to pass on both sides, like e.g., rocks, navigational marks, etc.
Finally, the inequality constraints are combined as.
5. ShortTerm COLAV
For the shortterm layer, the branchingcourse model predictive control (BCMPC) algorithm is used, which is a samplebased MPC algorithm intended for shortterm ASV COLAV. The BCMPC algorithm was initially developed in Eriksen et al. (2019), extended to also consider static obstacles in Eriksen and Breivik (2019) and is experimentally validated in several fullscale experiments using a radarbased system for detecting and tracking obstacles.
The algorithm complies with COLREGs rules 8, 13, and the second part of Rule 17, while favoring maneuvers complying with the maneuvering aspects of rules 14 and 15. Notice that Rule 17 allows a ship to ignore the maneuvering aspects of rules 14 and 15 in situations where the giveway vessel does not maneuver. The obstacle clearance will be larger if the algorithm ignores the maneuvering aspects of rules 14 and 15, like e.g., passing in front of an obstacle in a crossing situation where the ownship is the giveway vessel.
Moving obstacles are in general handled by the midlevel algorithm, making this applicable only in emergency situations and for obstacles detected so late that the midlevel algorithm is unable to avoid them.
where U∙i,i∈[1,NU] and χ¨i,i∈[1,Nχ] denote NU ∈ ℕ and Nχ ∈ ℕ vesselfeasible speed and course accelerations.
Given the acceleration samples (35) and motion primitives for each maneuver in a trajectory, we create a set of desired SOG and course trajectories Ud. These trajectories have continuous acceleration, and is designed in an openloop fashion by using the current reference tracked by the vessel controller for initialization, rather than the current vessel SOG and course. The reason for this is that the reference to the vessel controller should be continuous in order to avoid jumps in the actuator commands. To include feedback in the trajectory prediction, a set of feedbackcorrected SOG and course trajectories Ū d is predicted using a simplified error model of the vessel and vessel controller. Finally, the feedbackcorrected SOG and course trajectories are used to compute a set of feedbackcorrected pose trajectories:
where η̄ (⋅) denotes a kinematic simulation procedure that given SOG and course trajectories, Ū(·) and χ̄ (⋅), in Ū d computes the vessel pose.
See Eriksen and Breivik (2019) and Eriksen et al. (2019) for more details on the trajectory generation procedure.
A problem with this, is that when operating at high speeds, the possible acceleration may not be symmetric, resulting in that zero acceleration (hence keeping a constant speed and course), may not be part of the search space. This can cause undesirable behavior, since the BCMPC algorithm will be unable to keep the speed and course constant, which can cause oscillatory behavior.
In this paper, we therefore propose to move the acceleration samples closest to zero, and adding the desired acceleration as a separate sample, given that it is vessel feasible. This will make sure that keeping a constant speed and course, as well as a trajectory converging toward the desired trajectory is included in the search space. +wav,mavoidm(η¯¯(⋅))+wav,savoids(η¯¯(⋅)) +wt,UtranU(ud(⋅))+wt,χtranχ(ud(⋅)). (38)
The variables wal, wav, m, wav, s, wt, U, wt, χ > 0 are tuning parameters, while align(η̄ (⋅);pmidd(⋅)) measures the alignment between a candidate trajectory η̄ (⋅) and the desired trajectory from the midlevel algorithm pmidd(⋅). The function avoidm(η̄ (⋅)) ensures COLAV of moving obstacles by penalizing trajectories close to obstacles, using a nonsymmetric obstacle ship domain designed with the COLREGs in mind. The function avoids(η̄ (⋅)) ensures COLAV of static obstacles by introducing an occupancy grid, while tranU(ud(·)) and tranχ(ud(·)) introduces transitional costs to avoid shattering. The transitional terms penalize deviations from the planned trajectory of the previous iteration, unless changing to the trajectory corresponding by the desired acceleration.
See Eriksen and Breivik (2019) and Eriksen et al. (2019) for more details and descriptions of the terms.
The hybrid COLAV system is verified through simulations, which are present in this section. The simulations include ocean current and both static and moving obstacles. We include moving obstacles both acting in compliance with the COLREGs, and violating the COLREGs.
The simulations are performed in MATLAB on a computer with an 2.8 GHz Intel Core i7 processor running macOS Mojave, using CasADi (Andersson et al., 2019) and IPOPT (Wächter and Biegler, 2005) for implementing the highlevel and midlevel algorithms. The simulator is built upon the mathematical model of the Telemetron ASV described in section 2, and the modelbased speed and course controller in Eriksen and Breivik (2018) is used as the vessel controller.
To reduce the computational load and increase the predictability of the midlevel algorithm, we utilize six steps of each planned midlevel trajectory, only running the midlevel algorithm every 60 s. This implies that six steps of the predicted solution will be implemented before computing a new solution, which further implies that the state machine is also only run every 60 s. If the midlevel algorithm fails in finding a feasible solution, the algorithm will reuse the solution from the last iteration.
This may for instance happen if the algorithm tries to compute a solution while being inside a moving obstacle ellipse, which sometimes can be the case when an obstacle is exiting an emergency or standon state. The BCMPC algorithm is run every 5 s, with parameters as described in Eriksen and Breivik (2019). An update rate of 5 s is considered sufficient due the typically large maneuvering margins at sea. It is also worth noting that the detection and tracking system can represent a significant time delay, especially for radarbased systems (Eriksen et al., 2019).
For confined and congested areas the BCMPC algorithm may need to be run at a higher rate, which also imposes requirements for highbandwidth obstacle estimates. Static obstacles are padded with a safety margin of 150 m for the highlevel and midlevel algorithms, while the BCMPC algorithm uses a safety margin of 100 m for static obstacles. The reason for having a smaller static obstacle safety margin for the BCMPC algorithm is that it tends to struggle with following trajectories on the static obstacle boundaries. The BCMPC algorithm would hence not be able to follow the nominal trajectory if the static obstacle safety margin was the same as for the midlevel and highlevel algorithms.
Scenario 1 contains two static obstacles, four moving obstacles, an ocean current of [−2, 0]⊤ m/s and is shown in Figure 7. The highlevel planner plans a nominal trajectory between the initial and goal positions at [7000, 200]⊤ m and [0, 7900]⊤ m, respectively. The first obstacle is in a standon situation, where it is required to maneuver in order to avoid collision with the ownship, which is required to stand on. As shown in Figure 7B, the first obstacle is quickly considered as a standon situation, at which the midlevel algorithm disregards the obstacle and continues with the current speed and course.
Following this, the obstacle maneuvers in accordance to the COLREGs, and we avoid collision. After the first static obstacle, we encounter two crossing vessels where the ownship is deemed the giveway vessel. In accordance with the COLREGs, we maneuver to starboard in order to pass behind both obstacles. Notice that the second giveway obstacle is detected as a giveway situation later than the first, since the entry criteria in the state machine includes the time to CPA, which is higher for the second giveway obstacle.
After avoiding the two giveway obstacles, we converge toward the nominal trajectory and encounter a headon situation. This is correctly identified by the state machine as head on, and we maneuver to starboard in order to avoid collision. Notice that even though the obstacle maneuvers, we keep the obstacle in the headon state until we have passed it.
Figure 7. Scenario 1: trajectory and COLREGs interpretation. The text marks denote the time steps [150, 600, 1100] s. (A) Trajectory plot. The initial position of the ownship and obstacles are shown with circles, with the blue ellipses illustrating the moving obstacle ellipse size. The vessel patches, which are overexaggerated for visualization, mark the ownship and obstacle poses at given time stamps. The static obstacles are shown in yellow, with the BCMPC and midlevel safety margins enclosed around. The black arrow indicates the ocean current direction. (B) Output from the state machine for each obstacle. The asterisks mark time stamps, and the colors correspond to the obstacle patch colors in the trajectory plot.
After passing the two crossing obstacles, the midlevel algorithm increases the speed in order to get back to the nominal trajectory, which is due to the algorithm attempting to keep the speed projected on the nominal trajectory equal as the desired nominal speed. Furthermore, notice that the midlevel algorithm actively controls the relative surge speed in order achieve the desired SOG, which is clearly seen when passing the first static obstacle.
Figure 8. Scenario 1: speed and angular trajectories. The asterisks mark the same time samples as in Figure 7. (A) Speed trajectories. (B) Angular trajectories.
Scenario 2, shown in Figure 9, is more complex than Scenario 1, with a total of five moving obstacles, and has an ocean current of [−1, 1]⊤ m/s. The highlevel planner plans a nominal trajectory between the initial and goal positions at [200, 200]⊤ m and [5500, 7000]⊤ m, respectively. The first obstacle is a crossing vessel, which similarly as in Scenario 1 is deemed to give way for the ownship, which should keep the current speed and course. However, in this scenario, the obstacle violates the COLREGs by not maneuvering in order to avoid collision. Therefore, the BCMPC algorithm maneuvers to avoid collision when the obstacle gets so close that the safety margins of the BCMPC algorithms is violated. The BCMPC algorithm maneuvers to port, as advised by COLREGs Rule 17 for crossing situations where the standon vessel has to maneuver, and safely avoid the first obstacle.
The second obstacle is overtaken by the ownship, and correctly considered as an overtaking situation by the state machine. For such an situation, there is no requirement on how the ownship should maneuver, except keeping clear from the overtaken vessel. After passing the second obstacle, we encounter a complex situation with simultaneous headon, giveway and standon obligations. In this situation, each vessel, including the ownship, finds itself in a situation where a headon and a giveway situation require starboard maneuvers, while a standon situation requires the vessel to keep the current speed and course. However, headon and giveway obligations should be prioritized higher than standon situations, and the situation is quite easily solved by each vessel maneuvering to starboard and passing behind the vessel crossing from starboard. The midlevel algorithm solves this situation with the desirable behavior, and converges toward the nominal trajectory after the situation is resolved. As shown in Figure 9B, the state machine interprets the situations correctly.
With respect to the COLREGs, the ownship is required to give way to both obstacles since they are crossing from the ownship's starboard side. One can, however, argue that the maneuvers displayed by the obstacles are dangerous and displays poor seamanship, such that the ownship should not be held accountable if a collision occurred. Nevertheless, the hybrid COLAV system manages to avoid both obstacles. As seen in Figure 11B, the first obstacle is sufficiently far away from the ownship to be considered as a giveway situation when the state machine interprets the situation, and the midlevel algorithm plans a trajectory passing behind the first obstacle. The second obstacle maneuvers to port even closer to the ownship, resulting in the distance to the critical point being within the threshold for entering the emergency situation when the state machine interprets the situation. In this situation, the midlevel algorithm disregards the obstacle and leaves it to the BCMPC algorithm to avoid collision.
The simulation results show that the hybrid COLAV system is able to handle a wide range of situations, while also behaving in an energyoptimal way when moving obstacles are not interfering with the ownship trajectory. Table 3 shows the minimum distance to static and moving obstacles for the scenarios.
The minimum distance to moving obstacles is a bit difficult to interpret, since the obstacle ship domains are noncircular, implying that the required clearance depends on relative position of the ownship with respect to the moving obstacles. However, we see that we have a larger clearance in headon, giveway and standon situations where the obstacles comply with the COLREGs, and do not perform dangerous maneuvers (as in Scenario 3), compared to overtaking situations. The reason for this is that when overtaking (obstacle 2 in Scenario 2), we pass the obstacle on a parallel course, resulting in the minor axis of the moving obstacle ellipsis indicating the required clearance. Furthermore, we see that obstacle 1 in Scenario 2, which ignores its giveway obligation, comes significantly closer than other crossing obstacles except for those in Scenario 3.
The reason for this is that the BCMPC algorithm, which handles this situation, has a lower clearance requirement than the midlevel algorithm, which still should be considered as safe. In Scenario 3, the two obstacles display poor seamanship, and behave dangerously. Obstacle 1 is handled by the midlevel algorithm and passed with a clearance lower than the major axis of the midlevel algorithm, which is caused by the BCMPC algorithm “cutting the corner.” The clearance should still be considered safe since we are behind the obstacle, and the clearance requirements of the BCMPC algorithm is enforced. Obstacle 2, which is placed in the emergency state and handled by the BCMPC algorithm, is passed with a clearance of only 106.6 m. This is lower than the clearance to Obstacle 1 in Scenario 2 (which violated its standon requirement), and is due to the BCMPC algorithm having a nonsymmetric obstacle ship domain function allowing for a smaller clearance when passing behind an obstacle than in front.
In this paper, we have presented a threelayered hybrid COLAV system, compliant with COLREGs rules 8 and 13–17. As part of this, we have further developed the MPCbased midlevel COLAV algorithm in Eriksen and Breivik (2017b) and Bitar et al. (2019a) to comply with COLREGs rules 13–16 and parts of Rule 17, which includes developing a state machine for COLREGs interpretation. The hybrid COLAV system has a welldefined division of labor, including an inherent understanding of COLREGs Rule 17, where the midlevel algorithm obeys standon situations, while the BCMPC algorithm handles situations where giveway vessels do not maneuver.
The work in this article was the result of a collaboration between BOE and GB, supervised by MB and AL. The contributions to the midlevel and shortterm algorithms are made by BOE, while the COLREGs interpreter was developed in collaboration between GB and BOE. GB has implemented the highlevel planner, and prepared this for integration with the developed simulator. BOE has taken lead on writing the paper, in collaboration with GB. MB and AL have provided valuable feedback in the writing process.
This work was supported by the Research Council of Norway through project number 269116, project number 244116, as well as the Centers of Excellence funding scheme with project number 223254.
The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.
1.
https://www.wsj.com/articles/norwaytakesleadinracetobuildautonomouscargoships1500721202
(accessed May 22, 2019).
(accessed April 11, 2019).
Andersson, J. A. E., Gillis, J., Horn, G., Rawlings, J. B., and Diehl, M. (2019). CasADi: a software framework for nonlinear optimization and optimal control. Math. Program. Comput. 11, 1–36. doi: 10.1007/s1253201801394
CrossRef Full Text  Google Scholar
ORIGINAL RESEARCH ARTICLE
...
....
Part A  General (Rules 13) & Part B Steering and Sailing Section 1  Conduct of vessels in any condition of visibility (Rules 410)
Rule
1 states that the rules apply to all vessels on
the high seas and connected waters. Rule
7 risk assumptions shall not be made on scanty
(radar) information.
Sections II & III Conduct of Vessels in Sight of one another
Part C  LIGHTS & SHAPES (Rules 2031) Part D  SOUND AND LIGHT SIGNALS  DEFINITIONS (Rules 3237) Part E  EXEMPTIONS  Rule 38 Part F  Convention compliance verification provisions Rules 39  41
Annex I  Positioning and technical details of lights and shapes Annex
II  Additional signals for fishing vessels fishing in
close proximity
LINKS & REFERENCE
https://www.frontiersin.org/articles/10.3389/frobt.2020.00011/full


Please use our AZ INDEX to navigate this site
This website is Copyright © 2021 Jameson Hunter Ltd
