Ship Collision Avoidance And COLREGS Compliance Using .
1Ship Collision Avoidance and COLREGSCompliance using Simulation-Based ControlBehavior Selection with Predictive HazardAssessmentTor A. Johansen , Tristan Perez , Andrea Cristofaro , Abstract—This paper describes a concept for a collision avoidance system for ships, based on model predictive control. A finiteset of alternative control behaviors are generated by varying twoparameters: offsets to the guidance course angle commanded tothe autopilot, and changes to the propulsion command rangingfrom nominal speed to full reverse. Using simulated predictionsof the trajectories of the obstacles and ship, the compliancewith COLREGS and collision hazards associated with eachof the alternative control behaviors are evaluated on a finiteprediction horizon, and the optimal control behavior is selected.Robustness to sensing error, predicted obstacle behavior, andenvironmental conditions can be ensured by evaluating multiplescenarios for each control behavior. The method is conceptuallyand computationally simple and yet quite versatile as it canaccount for the dynamics of the ship, the dynamics of the steeringand propulsion system, forces due to wind and ocean current,and any number of obstacles. Simulations show that the methodis effective and can manage complex scenarios with multipledynamic obstacles and uncertainty associated with sensors andpredictions.Index Terms—Autonomous Ships; Collision Avoidance; Trajectory optimization; Hazard; Safety; Control Systems.I. I NTRODUCTIONA. BackgroundRules for ship collision avoidance are given by the Convention on the International Regulations for Preventing Collisionsat Sea (COLREGS), by the International Maritime Organization (IMO), [1]. Whilst COLREGS were made for shipsoperated by a crew, their key elements are also applicablefor automatic collision avoidance systems, either as decisionsupport systems for the crew or in autonomously operated andunmanned ships [2], [3], [4]. In an autonomous system implementation, COLREGS implicitly impose requirements on theinformation that must be provided by sensor systems, and thecorrect actions that should occur in hazardous situations.Autonomous operation of a ship requires that guidance,navigation and control is performed with high reliability, faulttolerance, and safety, including real-time perception of the Center for Autonomous Marine Operations and Systems (AMOS), Department of Engineering Cybernetics, Norwegian University of Science andTechnology, Trondheim, Norway. Department of Electrical Engineering and Computer Science, QueenslandUniversity of Technology, Brisbane, Australia. Current address: School of Science and Technology (MathematicsDivision), University of Camerino, Italy.Corresponding author: tor.arne.johansen@itk.ntnu.noship’s surroundings in order to avoid grounding and collisionwith other ships, vessels, people, marine mammals or otherobstacles that may be encountered. Larger ships are expectedto carry an automatic identification system (AIS) transmittingradio signals containing position and other information aboutthe ship, that can be received by other ships and authorities. Inorder to be able to detect the wide range of potential obstacles,onboard sensors such as radar, LIDAR and camera can be usedto scan the environment of the ship, [5], [6], [7].In this paper, we address the design of the collision avoidance control algorithm, that must decide on the control actionsrequired to ensure compliance with COLREGS and minimizehazard to an acceptable level based on the available sensorinformation.B. Literature review and motivationA wide range of ship collision avoidance control algorithms,many of them implementing compliance with the main rulesof COLREGS, are reviewed in [8] and [9]. They generallydo not scale very well to manage a large number of highlydynamic obstacles in dense traffic and at the same time canaccurately take into consideration the dynamics of the ship,steering and propulsion system, as well as environmentaldisturbances such as winds and ocean currents. The systematicextension of the existing algorithms to account for suchcomplex situations does not appear to be straightforward. Thismotivates our investigation on a new approach that employsideas from optimization-based control and can directly exploitthe availability of a simulation model for predictions.Model Predictive Control (MPC) is a very general and powerful control method that can compute an optimal trajectorybased on predictions of obstacles’ motion, robustly account fortheir uncertainty, employ a nonlinear dynamic vehicle modelincluding environmental forces, and formalize risk, hazardand operational constraints and objectives as a cost functionand constraints in an optimization problem. In fact, MPC hasbeen extensively studied for collision avoidance in automotivevehicles [10], [11], aircraft and air traffic control [12], groundrobots [13] and underwater vehicles [14]. Although someelements of optimization and optimal control are used in [15],[16], [17], the authors are not aware of the use of MPC forship collision avoidance with COLREGS compliance.MPC can compute optimal trajectories using numericaloptimization methods, e.g [18]. Its main challenges are re-
2lated to the convergence and computational complexity of thenumerical optimization. It is widely recognized that complexcollision avoidance scenarios may lead to non-convex optimization formulations exhibiting local minimums, and thatshortest possible computational latencies is highly desirablefor real-time implementation. This makes it challenging to implement an MPC for collision avoidance, and the formulationof models, control trajectory parameterization, discretization,objectives, constraints, and numerical algorithms need to becarefully considered along with issues such as dependability[19].In order to reap the main benefits of MPC, and mitigate theissues related to local minimums, computational complexityand dependability, one can take a rather simple approach thatturns out to be very effective in terms of high performance andlow complexity of software implementation. In the literatureon robust MPC the concept of optimization over a finitenumber of control behaviors is well known, e.g. [20], [21],[22]. In its simplest form, it amounts to selecting among afinite number of control behaviors based on a comparison oftheir cost and feasibility, e.g. [23], [24], [25], although mostapproaches also incorporates optimization over some controlparameters.C. ContributionsIn this paper, we consider MPC with a relatively smallfinite number of control behaviors, parameterized by offsets to course and propulsion command, and merely requireevaluation of their performance by simulation. Hence, wecompletely avoid numerical optimization and the associatedcomputation of gradients that is inherent in conventional MPC.This certainly restricts the degrees of freedom available forcontrol, and the set of alternative control behaviors must becarefully crafted in order to achieve the required control performance and effectiveness of the collision avoidance systemand COLREGS compliance.We propose to implement collision avoidance functionalitythrough a finite horizon and finite scenario hazard minimization problem over a finite number of control behaviors. TheMPC optimization problem is solved in a receding horizon implementation with a re-optimization based on updatedinformation at regular intervals, e.g. every 5 seconds. Thehazard associated with the ship trajectory resulting from agiven control behavior is evaluated using a ship simulatorto make predictions that takes into account the dynamics ofthe ship, steering and propulsion system, the current positionand velocity, the control behavior, as well as wind and oceancurrent. Robustness can be enhanced by considering additionalscenarios resulting from perturbation of the input data. AnMPC cost function considers the constraints and objectives ofcollision avoidance and compliance with the rules of COLREGS, using velocity and line-of-sight vectors to express theCOLREGS rules. The constraints are implemented as penaltiesin order to ensure that the best possible control behavior canbe chosen also when collision with at least one obstacle seemsunavoidable.II. S YSTEM OVERVIEWFigure 1 illustrates the overall concept with its main subsystems and the information flow between them. The nominalinput to the ship’s Autopilot from the Mission Planner isassumed to be the propulsion or speed-over-ground command,and the desired path given as a sequence of way-points. TheCollision Avoidance System (CAS) searches for COLREGScompliant and collision-free trajectories close to the ship’snominal trajectory, given the measured positions and predictedtrajectories of obstacles. The CAS outputs a course angleoffset and a modified propulsion command that are givento the autopilot. We notice that the CAS needs to considertrajectories (with explicit representation of time) while inthe autopilot there is a decoupling of position and time intopath guidance (steering) and propulsion control. The speedis normally kept close to a nominal cruise speed, but maybe reduced, set to zero, or reversed, upon command from theCollision Avoidance System (CAS). The CAS can also providealarms such as sound and light signals. In-depth descriptionsof the CAS functionality are given in section III. The ship’son-board navigation system provides measurements (usuallyfrom a global navigation satellite system (GNSS)) of positionand velocity. The accuracy of GNSS position measurementsis typically 10 meters or better, which is sufficient for thisapplication. However, the integrity of the GNSS measurementsshould be analyzed for larger errors such as multi-path, jamming and spoofing. In new systems such as GALILEO this isbetter handled than in GPS.In order to support the collision avoidance we assume thefollowing information and capacities are available: List of obstacle’s positions and velocities, from radar,lidar, AIS, camera or infrared thermal imager, or similarsensors and tracking systems. A detailed description andsurvey of such systems is beyond the scope of the paper,and we refer to [26], [5], [6], [7] as well as recent resultsfrom automotive industry [27], [28].Mapped hazards from an electronic map.A desired nominal path to the target destination.Mathematical model of ship for prediction of futuretrajectory in order to evaluate the effect of steeringand propulsion commands, as well as winds and oceancurrents.Real-time measurement of the ship’s position, velocity,heading and yaw rate.Estimates of wind and ocean current forces on the ship.The proposed architecture implies that the collision avoidance functionality is separated from the mission planningfunctionality, and the commands from both these systems areexecuted by the ship’s autopilot. This leads to a highly modulararchitecture that admit the collision avoidance system to beadded on top of existing functionality, and such that reliabilityand safety can be ensured through additional independent andredundancy systems and functions.A brief overview of the main rules of COLREGS are givenin Appendix A.
3Fig. 1. Block diagram illustrating the information flow between the main modules in the system.III. C OLLISION AVOIDANCE SYSTEM (CAS)An overview of the proposed CAS control algorithm is givenin Fig. 2. The collision avoidance functionality is realized by afinite horizon and finite scenario hazard minimization problemdefined over a finite number of control behaviors in combination with multiple scenarios resulting from uncertainties inpredicted obstacle trajectories and weather. The optimizationproblem is solved in a receding horizon implementation witha re-optimization based on updated information at regularintervals, e.g. every 5 seconds. The hazard associated withthe ship trajectory resulting from a given control behavior isevaluated using a ship simulator to make predictions that takesinto account the dynamics of the ship, steering and propulsionsystem, the current position and velocity, the control behavior,as well as wind and ocean current. Robustness is attained bysetting an appropriate safety margin and possibly by evaluatingadditional scenarios resulting from perturbation of the inputdata to represent uncertainty in obstacle’s future trajectories.A cost function measures the predicted grounding and collisionhazards, and compliance with the rules of COLREGS, usingvelocity and line-of-sight vectors to express the COLREGSrules. The proposed optimization is deterministic and guarantees that the global minimum is found after a known finitenumber of cost function evaluations.In this section we describe in some detail the main components of the CAS, and their interactions.A. Obstacle trajectory predictionThe collision avoidance problem is linked with considerableuncertainty, as the obstacles’ future motions must be predicted.The simplest short-term predictions of the obstacles’ trajectories are perhaps straight line trajectoriesFig. 2. Summary of the collision avoidnace control algorithm.η lati (t)longη i (t) η̂ilat klat v̂iN (t τi )(1)η̂ilong(2) klong v̂iE (t τi )where klat and klong are constants that convert from metersto degrees in the given area, t is a future point in time, andτi is the time of last observation.
4B. Control behaviors and scenariosWhilst COLREGS define a set of traffic rules that leads toexpected behaviors, one must also be prepared for the factthat some vessels will not be able, or choose not, to complywith these rules. Based on this, we make some choices andassumptions.The CAS decides its control behavior by evaluating a finitenumber of alternative control behaviors in some scenariosusing a ship simulator that operates much faster than realtime. Each scenario is defined by the current state of the ship,the predicted trajectories of the observed obstacles, a controlbehavior that is either assumed to be fixed on the predictionhorizon or by a sequences of control behaviors that are used indifferent parts of the prediction horizon. The nominal scenario(guidance along the nominal path with no course offset and atnominal speed) is accepted if the hazard is sufficiently low. Ifnot, the least hazardous control behavior is selected among thealternatives that represent a finite number of evasive controlbehaviors. The predictive simulation should include effects ofwinds and currents that may have a significant effect on theship, in particular if the decided control action is to stop. Thehazard minimization criterion is based on an evaluation ofcollision hazard, grounding hazard and COLREGS compliance. The strategy recognizes that there may be conflictingobjectives and constraints, such that a sound compromise mustbe made to determine minimum hazard.The set of alternative control behaviors should be as extensive as computation time allows, since this will increase theperformance of the system. The following set of alternativecontrol behaviors is to be considered as a minimum in a typicalimplementation: Course offset at -90, -75, -60, -45, -30, -15, 0, 15, 30,45, 60, 75, 90 degreesKeep speed (nominal propulsion), slow forward, stop andfull reverse propulsion commands.and all the combinations of the above leading to 13 · 4 52control behaviors. Assuming the control behavior is keptfixed on the entire prediction horizon, this corresponds to 51possible evasive maneuvers in addition to the nominal controlbehavior with zero course offset, and nominal forward propulsion. Clearly, considering the possibility to change controlbehavior on the horizon may lead to a ship trajectory withless hazard. However, with one planned change in controlbehavior on the horizon this leads to a much larger numberof 522 2704 scenarios. From a safety point of view it isclearly desirable to evaluate as many alternative scenarios aspossible, while from a computational point of view the numberof scenarios needs to be kept smaller than the computationalcapacity. There is clearly also a trade-off between the numberof scenarios and the computational complexity of the simulations in terms of high-fidelity time-discretization, lengthof prediction horizon, detail of ship model, control updateinterval and computational latency. Robustness to uncertaintyin the prediction of the obstacle’s trajectories may also berepresented by additional scenarios being perturbations of theobstacles’ predicted trajectories, see Section IV-A.C. Prediction of own ship trajectoryIn order to predict the ship’s motion in response to thedifferent control behaviors as well as wind and ocean currentdisturbances, we propose to employ the standard 3-degrees offreedom horizontal plane ship dynamics model, neglecting theroll, pitch and heave motions [29]η̇ R(ψ)v vcM v̇ C(v)v D(v)v τ R(ψ)T τw(3)where η (x, y, ψ) represents position and heading in theearth-fixed frame, v [vx , vy , r] includes surge and swayrelative velocities and yaw rate decomposed in the bodyfixed frame, M is the vessel inertia matrix, C(·) and D(·)model, respectively, Coriolis and damping terms, R(ψ) is therotation matrix from body-fixed to earth-fixed frame, the inputτ represents the commanded thrust and moments, and vc is theocean current velocity and τw is the wind force, both expressedin the earth-fixed frame.The simulation should account for the dynamics of thepropulsion and steering system, an autopilot that accept acourse command to implement the steering control. We assumethe autopilot is executing a LOS guidance control with apre-defined look-ahead distance, [29]. This leads to a coursecommand χLOS that guides the ship towards the straight pathbetween the previous and the current selected way-points. TheCAS can provide a course angle offset χca such that theactual course command is χc χLOS χca . A PI controllerfor the course steering is then implemented to compute thecommanded rudder angleZ tδ Kp (χc χ) Ki(χc χ)dt(4)0where Kp and Ki are controller gains. The autopilot operateswith a constant propulsion command P [ 1, 1] where 1 is(nominal) forward propulsion, 0 is stop, and -1 is full reverse.A highly useful property of these control behaviors is thatthey represent meaningful actions when the control behavior iskept constant on the whole prediction horizon. Another usefulproperty is that since the course offset comes in addition tothe LOS guidance, then simply setting the course offset tozero will recover the LOS guidance control and the ship willgo back to the nominal path without any further planning orguidance.D. COLREGS complianceAn important factor in the evaluation of collision hazardsis the prediction horizon used to evaluate the result of thesimulation scenarios described in Section III-B. COLREGSrules 8 and 16 demand that early action is taken, so theprediction horizon should be significantly larger than the timeneeded to make a substantial change of course and speed.The main information used to evaluate COLREGS compliance and collision hazard at a given future point in time, ona predicted ship trajectory generated by a candidate controlbehavior, is illustrated in Figure 3, and detailed as follows: The blue curve illustrates the own ship’s predicted trajectory, which is a function of the current position, velocity
5speed vi (t) is not close to zero and v0k (t) · vi (t) cos(22.5 ) v0k (t) vi (t) ki (t) cos(φahead ) v0k (t) v0k (t) · L (6)(7)where φahead is an angle to be selected.The obstacle with index i is said to be CROSSED at timet in scenario k if it is close to own ship and v0k (t) · vi (t) cos(68.5 ) v0k (t) vi (t) (8)where 68.5 could be replaced by a more suitable angledepending on the velocity and type of obstacle.E. Hazard evaluation criterionFig. 3. The main information used for hazard evaluation at a given futuretime t in scenario k, where the blue dot denotes the predicted position of theown vehicle, and the red dot d
collision avoidance and compliance with the rules of COL-REGS, using velocity and line-of-sight vectors to express the COLREGS rules. The constraints are implemented as penalties in order to ensure that the best possible control behavior can be chosen also when collision with at least one obstacle seems unavoidable. II. SYSTEM OVERVIEW
collisions in the networks such as ALOHA, CSMA, MACA and MACAW. MACAW Protocol Multiple Access with Collision Avoidance for Wireless (MACAW) is a widely used MAC sub layer protocol. MACAW is useful for mobile ad-hoc networks. It contains new collision avoidance mechanisms. By these me-chanisms data transmission is completed in five steps.
With more than 10,000 TCAS II/ACAS II installations on more than 325 aircraft types, Honeywell is the overwhelming choice in collision avoidance for airline and corporate pilots. Honeywell now combines the unmatched flexibility of Integrated Hazard Avoidance System with
Reciprocal n-body Collision Avoidance Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha Abstract In this paper,we present a formal approachto reciprocal n-bodycollision avoidance, where multiple mobile robots need to avoid collisions with each other while movingin a commonworkspace.In our formulation,each robotacts fully in-
5 1. Collision Physics – An Overview. 1.1 Outline. Collision physics includes ANY collision of a quantum particle with a target. Collision Particles may be: PHOTONS (eg from a Laser, Synchrotron source or FEL) ELECTRONS (usually of well defined momentum from an electron gun) IONS (usually from an ion source of well defin
Holes - examples-a protruding fragment of ice ripped a hole in the ship's hull-The collision tore a hole in the warship's waterline, flooding the ship’shold-The MV „ ." has been cut in two; - During collision in 1965 of the dry-cargo ship „ " with a supertanker the former has developed a hole depth up to 2/3 B;-Due to explosion on the tanker „ ", the depth of damage had reached 21 m.
avoidance, two ethical standards were applied: the Utilitarianism approach and the Deontology approach. The former approach states that ethics of tax avoidance cannot be determined theoretically because this evaluation depends, ultimately, on the quality of the government. The latter approach states that tax avoidance is an .
This paper examines the relative valuation of alternative methods of tax avoidance. Prior studies find that firm value is positively associated with overall measures of tax avoidance; I extend this research by providing evidence that investors distinguish between methods of tax reduction in their valuation of tax avoidance.
Designation: C 1116/C 1116M – 06 Standard Specification for Fiber-Reinforced Concrete1 This standard is issued under the fixed designation C 1116/C 1116M; the number immediately following the designation indicates the year of original adoption or, in the case of revision, the year of last revision. A number in parentheses indicates the year of last reapproval. A superscript epsilon (e .
