Article Search
닫기

Original Article

Split Viewer

International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(4): 378-390

Published online December 25, 2021

https://doi.org/10.5391/IJFIS.2021.21.4.378

© The Korean Institute of Intelligent Systems

Improved Collision Avoidance Method for Autonomous Surface Vessels Based on Model Predictive Control Using Particle Swarm Optimization

Jinwan Park

Department of Maritime Transportation System, Mokpo National Maritime University, Mokpo, Korea

Correspondence to :
Jinwan Park (pjinwan2@gmail.com)
*These authors contributed equally to this work.

Received: November 10, 2021; Revised: December 11, 2021; Accepted: December 17, 2021

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Most collision accidents are caused by human errors in an encounter situation between vessels. Autonomous operations have received much interest among researchers to reduce human errors resulting from improper vessel maneuvering actions. In this paper, an intelligent collision avoidance method that considers not only the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) but also complex encounter situations with multiple obstacle vessels was proposed for autonomous surface vessels (ASVs). The results were verified by comparing the performance with that of existing methods. To take timely maneuvering actions to prevent the collision of vessels involved in an encounter, fuzzy comprehensive evaluation, and model predictive control using particle swarm were applied to path planning. As a result, ASVs can take proper action to avoid collisions in compliance with COLREGs based on the proposed method. The improved collision avoidance method exhibits better performance than existing methods.

Keywords: Autonomous surface vessels, Path planning, Collision avoidance, Model predictive control, Particle swarm optimization

The European Maritime Safety Agency (EMSA) reported that navigation accidents over the years 2014–2019 make up 44% of total vessel accidents [1]. In particular, 54% of vessel accidents are caused by improper human actions in encounter situations among vessels. Despite the various real-time information on vessel movements provided by advanced navigation equipment such as RADAR, electronic chart display and information systems (ECDIS), and automatic identification system (AIS), vessel accident records show that subsequent actions taken to avoid vessel collisions based on risk assessment are not performed properly. With the advent of digitalization in the maritime industry, autonomous operations are expected to decrease human errors through intelligent collision risk assessment and collision avoidance algorithms.

This paper proposes a collision avoidance algorithm for autonomous surface vessels (ASVs) which require intelligent and automatic operations. Smierzchalski and Michalewicz [2] proposed an evolutionary algorithm-based decision-support system for path planning in collision situations; however, the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) [3] were not considered. Lee and Rhee [4] developed a collision avoidance system using fuzzy theory and the A-star algorithm, which is a graph-based method for searching the shortest path. However, a rule-based collision avoidance system using fuzzy theory may have difficulty in responding appropriately to unexpected situations [5]. Fahimi [6] proposed a method for controlling multiple ASVs by applying the nonlinear model predictive control (NMPC) method. The experimental results of Fahimi’s method, however, require additional validation to determine compliance with COLREGs. Perera et al. [7] proposed a collision avoidance method based on fuzzy logic and Bayesian network and validated it through experiments involving multiple target vessels. Their method failed to comply with COLREGs in unexpected situations where the target vessels corresponding to the stand-on vessel did not take evasive action. Zaccone et al. [8] and Enevoldsen et al. [9] proposed collision avoidance methods for vessels based on a rapidly-exploring random tree algorithm (RRT*). Although compliant with COLREGs, they did not consider multiple obstacles in a complex situation. Johansen et al. [10] introduced the simulation-based model predictive control (SBMPC) method for collision avoidance by evaluating collision risk and COLREGs compliance for each predetermined finite number of scenarios.

In addressing the challenge of collision avoidance for the safety of vessel traffic, compliance with COLREGs should be considered in situations where multiple obstacle vessels are encountered. Therefore, methods based on model predictive control (MPC) that predict the future path of a vessel within a finite time horizon and control the vessel according to predefined constraints are suitable for collision avoidance systems. A mathematical optimization method can be used to derive an optimal input to the control system based on the MPC formulation. To improve the methodology proposed in [10], the particle swarm optimization (PSO) algorithm is incorporated into MPC to find an optimal path. The PSO algorithm is a fast and simple method for searching the global minimum and is suitable for real-time path planning. Tan et al. [11] and Thomas [12] applied MPC and PSO in real-time control systems and subsequently proved the performance. Yao et al. [13] proposed an MPC method to improve the grey wolf optimizer (GWO) to plan the optimal trajectories of multiple unmanned aerial vehicles for target tracking in the urban environment. However, Kraiem et al. [14] and Rabie [15] proved that PSO tends to outperform GWO. In the field of autonomous underwater vehicles (AUVs), the PSO algorithm has already been applied to collision avoidance and path planning, and the effectiveness of its performance has been verified in [16]. Kang et al. [17] also used the PSO algorithm for path planning of vessels. They considered only single obstacle vessels for the path planning. Therefore, it is necessary to consider not only compliance with COLREGs, but also multiple obstacle vessels. In this study, to verify performance, the proposed method was compared with the existing SBMPC [10], in a case simulation.

The remainder of this paper is organized as follows: in Section 2, the main rules of COLREGs are described as applied to collision avoidance systems; in Section 3, a methodology for path planning and collision avoidance for ASVs based on the MPC and PSO algorithms is proposed. In Section 4, the results of the case simulations and verification are presented. Finally, in Section 5, along with the conclusion future directions are suggested.

Path planning with collision avoidance requires compliance with COLREG rules. The steering and sailing rules of COLREGs are classified according to visibility conditions. The definition of an encounter situation when the vessels are in sight of one another is shown in Figure 1. In Figure 1, the vessel is represented by the red triangle. Overtaking is defined as a situation in which an obstacle vessel overtakes another vessel at a position where the relative bearing range is 112.5°–247.5°. Starboard crossing is a situation in which an obstacle vessel crosses another vessel ahead at a position where the relative bearing range is 006°–112.5°. Port crossing is a situation in which an obstacle vessel crosses another vessel ahead at a position where the relative bearing range is 247.5°–354°. In head-on situations, on the other hand, vessels have courses within approximately 6°, in opposite directions [18].

The steering and sailing rules of COLREGs depicting different situations are shown in Figure 2. In each situation, the give-way vessel is supposed to keep out of the way of another ship, so far as possible, taking early and substantial action to keep it clear. The stand-on vessel should maintain its course and speed.

If there is a risk of collision while the vessel is navigating, proactive action is required to avoid collisions in compliance with COLREGs. An assessment of collision risk is important for finding a safe path to avoid the collision. However, it is difficult for a navigator to accurately determine the existence of collision risk because the navigation of a ship involves uncertainty. The fuzzy comprehensive evaluation (FCE) method was applied to address this uncertainty problem. FCE can reflect on various factors affecting the collision risk of vessels and can be evaluated both subjectively and objectively by experts. The distance at closest point approach (DCPA), time to closest point approach (TCPA), distance, relative bearing, and velocity ratio are determined as the target factors affecting the risk of ship collision whereby AIS data can provide navigation information on a ship’s own vessel as well as the obstacle vessels during navigation. However, it is difficult to determine the existence of collision risk using only quantitative assessments. Therefore, the collision risk detection algorithm [1921] is applied to automatically inform ASVs of the existence of collision risk. This algorithm detects collision risk by applying “time to safe distance”, which indicates the time it takes for the distance between two vessels to reach a safe distance. The path planning algorithm proposed in this study starts to search for a safe path for collision avoidance based on MPC and PSO when a risk of collision is detected. In the closed loop of the MPC, the three degree of freedom (DOF) vessel dynamics model was applied to predict the path of the vessel and process the optimized control input. In the optimization stage, the PSO algorithm, which is a simple and powerful optimization method, was applied. Compliance with COLREGs is considered a constraint for finding a collision-free path. A flowchart of the proposed collision-avoidance method is shown in Figure 3.

3.1 Collision Risk Assessment

To assess the risk of collision between two vessels quantitatively, the FCE method was applied. The FCE method combines the subjective evaluation of experts with objective evaluation using a database for each factor that affects the target [19,20]. In this study, DCPA, TCPA, distance (D), relative bearing (B), and velocity ratio (K) were selected as the target factors to calculate the collision risk using the FCE method. In the Cartesian coordinate system, the origin is the position of the ASV; (X, Y ) denotes the relative position of the obstacle vessel; Vo denotes the true velocity of the ASV; Vt denotes the true velocity of the obstacle vessel; Vr denotes the relative velocity of the obstacle vessel with respect to ASV; and Vrx, Vry denote the components of Vr in the x and y directions, respectively. Consequently, the DCPA, TCPA, D, and K can be obtained as follows [1921]:

DCPA=|XVry-YVrxVr|,TCPA=-XVrx+YVryVr2,D=X2+Y2,K=Vt/Vo.

According to the FCE method, the collision risk index (CRI) can be calculated by the dot product of the weight vector and membership vector, as follows [19,20,22,23]:

CRI=W·U=WDCPA·UDCPA+WTCPA·UTCPA+WD·UD+WB·UB+WK·UK,

where W and U represent the weight and membership vector of the target factors, respectively. The membership value for each target factor can be calculated using the membership function [19,20,22,24,25], which can be stated for DCPA as follows:

UDCPA={1,DCPA<d1,(d2-DCPAd2-d1)2,d1DCPAd2,0,DCPA>d2,

where d1 is the minimum safety distance between encountered vessels and d2 is the absolute safety distance, which is equal to twice the value of d1. The value of d1 is calculated as follows:

d1={1.1,355°<B67.5°,1,67.5°<B112.5°,0.6,112.5°<B247.5°,0.9,247.5°<B355°.

The membership function of TCPA is given by

UTCPA={1,0TCPAt1,(t2-TCPAt2-t1)2,t1TCPAt2,0,TCPA>t2,

where t1 is the time remaining until collision, and t2 is the collision avoidance time; t1 and t2 are calculated as follows:

t1={d12-DCPA2VR,DCPAd1,0,DCPA>d1,t2={d22-DCPA2VR,DCPAd2,0,DCPA>d2.

The membership function of D given by

UD={1,0<D<D1,(D2-DD2-D1)2,D1DD2,0,D>D2,

where D1 is the critical safety distance and is equal to 12 times the overall length of ASV, and D2 is the distance required to take a last action. D2 can be calculated as follows:

D2=1.7cos(B-19°)+4.4+2.89cos2(B-19°),

where the membership function of B is expressed as

UB=12[cos(B-19°)+440289+cos2(B-19°)]-517,

and the membership function of K is

UK=11+2KK2+1+2KsinC.

3.2 Path Planning and Collision Avoidance

Based on the collision risk assessment of the vessel, if there is a risk of collision, the path should be planned to avoid the risk of collision in compliance with the COLREGs. To avoid the risk of collision of ASVs, their course or speed can be adjusted using a controller. Therefore, the collision avoidance system is designed such that ASVs can navigate along a safe path through predictive control using the model of ship dynamics.

3.2.1 Ship dynamics

When designing control systems for ship collision avoidance, three DOF horizontal plane models (surge, sway, and yaw) are used, as described in [19]. The models are generally used in dynamic positioning systems, trajectory-tracking control systems, and path-following systems for ships, semi-submersibles, and underwater vehicles because most crafts do not have actuation in DOF [26]. The nonlinear maneuvering equations based on the rigid-body force and hydrodynamic forces can be written as follows:

η˙=[cos(ψ)-sin(ψ)0sin(ψ)cos(ψ)0001]ν,Mν˙+C(ν)ν+D(ν)ν=τ,

where denotes the position and course defined on the interval ; ν = [u, v, r]∈ ℝ3 represents the relative velocities in surge, sway and yaw; M denotes the vessel inertia matrix; C(·) is the Coriolis-centripetal term; D(·) is the damping term; and τ represents the vector of control inputs.

To control vessel behavior, the steering system and propulsion were considered, as described in [10]. It is assumed that the steering system utilizes line-of-sight (LOS) guidance which is based on the principle of lookahead steering [10,26]. This guidance computes the desired course angle χd so that the vessel proceeds according to the preplanned path. The actual course command for the steering system can be obtained as follows [10,26]:

χ=χd+χca,

where χca denotes the course angle offset provided by the collision avoidance system. Vessel propulsion can be controlled by a constant propulsion command P ∈ [−1, 1] where 1 is ahead propulsion, 0 is stop, and −1 is full astern propulsion.

3.2.2 Model predictive control

MPC is an advanced feedback control method that has a noticeable impact on process industries. This algorithm predicts the future outputs of a process to determine the control actions to optimize in the current time step. The main advantage of MPC is that it can handle multivariable control problems and directly handle constraints. In discrete-time space, a plant model is assumed to have the following form [27,28]:

x(t+1)=f(x(t),u(t),t),y(t)=g(x(t),t),

where f and g are known nonlinear functions; x denotes an n-dimensional state vector; u denotes an m-dimensional input vector; y denotes an l-dimensional vector of the measured outputs; and t is the time instant. Letting k be the current timestep, any control sequence u(t | k) with prediction horizon Hp and prediction outputs ŷ(t | k) can be obtained by minimizing the function J as follows [27,28]:

J=i=1Hpγe(tk+i)2+i=1Hpλu(tk+i)2+i=1HcμΔu(tk+i)2,

where

Δu(tk)=u(tk)-u(tk-1),

e denotes the error between reference r and the predicted output ŷ; Hc denotes the control horizon; || · || denotes the Euclidean norm; and γ, λ, μ are weighting parameters for the control penalization. The procedure is illustrated in Figure 4 [27].

At each time step, an iterative online optimization is conducted to obtain the new input over the predictions generated by the plant model. The process control method is called the receding horizon strategy because the prediction horizon moves along with one sampling interval [27].

3.2.3 Particle swarm optimization

The PSO algorithm utilizes the idea that particles belonging to a certain swarm share information with each other to establish an optimal destination. This algorithm was introduced by Kennedy and Eberhart [29] and improved by Mezura-Montes and Coello [30] and Pedersen [31]. Each particle belonging to a certain swarm has a position vector p∈ℝn and a velocity vector v∈ℝn in the corresponding search space, as a candidate solution to the optimization problem. The algorithm, upon start, creates particles and initializes the position vector, velocity vector, and objective function value corresponding to each particle. Subsequently, each particle position is evaluated by the objective function, and the particle with the minimum value of the objective function determines the best position hbest. The global best position gbest is determined by iteratively updating the velocity and position vectors of each particle in the swarm. The equation for this algorithm can be written as follows:

pj(i+1)=pj(i)+vj(+1),vj(i+1)=ωvj(i)+φhrh(hjbest(i)-pi(i))+φgrg(gbest(i)-pj(i)),

where j denotes the particle index; i denotes the iteration index; ω denotes an inertia coefficient; φh and φg are acceleration coefficients; rh and rg are random vectors that are uniformly distributed.

3.2.4 Proposed MPC-PSO method

To control the ASV behavior in the risk of collision, the constant propulsion command P and course angle offset χca are utilized as the particle’s position vectors of the PSO algorithm in the MPC controller. When the state vector of the obstacle vessel and waypoint information are input into the MPC-PSO controller, the optimized P and χca are delivered to the vessel. Simultaneously, the desired course angle χd and the desired velocity νd, which are calculated by guidance, are also input to the vessel. The structure of the collision-avoidance system is shown in Figure 5.

The objective function for the MPC-PSO controller is expressed as

J(tk)=WC(maxomax1iHpCo(tk+i))+Wo=1Noi=1Hpo(tk+i)+WP(1-P)+Wχχca+WΔPL-Llast+WΔχDHU(Tr,Trlast),={1,0<B112.5°,0,otherwise,

where , W, Wχ, WΔP, and WΔχ are weighting parameters for the control penalization; o is the index of the obstacle vessels; No is the number of obstacle vessels; is the collision risk index; Tr is the predicted path of the vessel of interest with input in the current time step; Trlast is the predicted path of the vessel based on the last output of the controller; L is the length of Tr; Llast is the length of Trlast; and DHU(·) denotes the HU distance [32], which is computed as the average Euclidean distance between points in two trajectories. In the objective function, the first term calculates the collision risk index of the predicted path to enable the vessel to find a path free of collision risk. The second term penalizes the situation in which the obstacle vessel is located on the starboard side of the vessel of interest so that the latter can comply with COLREGs. The third and fourth terms adjust the priority of altering the course and reducing the speed when the vessel takes action to avoid the risk of collision. The remaining terms are included to ensure stability of vessel maneuvering.

Simulations were carried out for an encounter situation defined according to COLREGs, to verify that ASV can avoid the risk of collision in compliance with COLREGs for obstacle vessels that do not take evasive actions, except in the port crossing situation. In addition, the performance of the proposed method was verified by comparing it with that of SBMPC in a situation of sequentially encountering multiple obstacle vessels. The parameters used in the simulations for each scenario are summarized in Table 1.

In Table 1, Tc is the time step interval in the simulation; Tp is the time step interval for prediction; Te is the end time of the simulation; LOA1 is the overall length of the vessel; LOA2 is the overall length of the obstacle vessel. In the PSO algorithm, SWsize is the swarm size, and Maxi is the maximum number of iterations. Moreover, the boundary of the propulsion command P and the course angle offset χca are denoted by the position variables of the PSO algorithm, and set to [0.5, 1] and [−90, 90], respectively. Different values of Te and were applied depending on the number of obstacles in the encounter situation, that is, a single obstacle or multiple obstacles.

4.1 Head-on Situation

Path planning simulation for the head-on situation in which the ASV has a collision risk with one obstacle vessel was carried out according to Table 2, where the initial settings of the scenario are displayed. Based on the simulation results displayed in Figure 6, ASV altered its course to starboard in compliance with COLREGs rule 14 to avoid the obstacle encountered. The results illustrate the vessel altering her course to return to port according to the planned path after passing the obstacle vessel on the port side. The minimum distance between the ASV and obstacle vessel was found to be 0.8729 nm, and only course alteration was performed without reducing the speed to avoid collision.

4.2 Starboard Crossing Situation

The simulation of path planning for the crossing situation in which the ASV has a collision risk with one obstacle vessel located on the starboard side was carried out according to Table 3, where the initial settings are displayed for this scenario. According to the simulation results shown in Figure 7, ASV altered its course to starboard in compliance with COLREGs rule 15 to avoid the obstacle vessel encountered. Figure 7 illustrates the vessel altering her course to return to port along the planned path after passing the obstacle vessel on the port side. The minimum distance between the ASV and obstacle vessel was found to be 0.5532 nm, and only course alteration was performed without reducing the speed to avoid collision.

4.3 Port Crossing Situation

The path planning was simulated for the crossing situation in which the ASV has a collision risk with one obstacle vessel located on the port side. The initial settings for this scenario are displayed in Table 4. Because the obstacle vessel corresponds to the give-way vessel according to the COLREGs rule 15, the scenario was designed such that the obstacle vessel altered its course to starboard to avoid collision. According to the simulation results shown in Figure 8, ASV maintained her course and speed in compliance with COLREG rules 15 and 17. The minimum distance between the ASV and the obstacle vessel was 0.2794 nm.

4.4 Overtaking

Path planning simulation for the overtaking situation in which the ASV has a collision risk with one obstacle vessel was carried out with the initial settings for the scenario displayed in Table 5. Based on the simulation results displayed in Figure 9, the ASV altered its course to starboard in compliance with COLREGs rule 13 to avoid the obstacle vessel in returning to port along the planned path after passing the obstacle vessel on the port side. The minimum distance between the ASV and the obstacle vessel was 0.4662 nm, and only course alteration was performed without reducing the speed to avoid collision.

4.5 Comparison with SBMPC

In the standard encounter situations defined by COLREGs, the behavior of the ASV in avoiding collisions while complying with regulations was verified. In addition, to verify the effectiveness of the proposed method (MPC-PSO), the proposed method was applied jointly with the existing SBMPC to a possible encounter situation, and the results were compared. The parameters used for the objective function in the SBMPC method are as follows:

Kcoll=0.02;dsafe=1,025;dcl=2,500;κ=25;kP=33;ΔP=13;kχ-port=0.65;kχ-starboard=0.3;Δχ-port=0.55;Δχ-starboard=0.2.

Path planning simulation for the situation where the ASV has a collision risk with five obstacle vessels was carried out with the initial settings of the scenario displayed in Table 6. The results of the simulation using the proposed method are shown in Figure 10 for an ASV with Obstacle1. The ASV kept its course and speed as Obstacle1 took action to avoid collision. To compare the performance of the SBMPC method, the ASV and Obstacle1 scenarios were designed as in Section 4.3 to compare the performance of the SBMPC method. ASV then altered its course to starboard to keep out of the way of Obstacle2 and Obstacle3 passing Obstacle1 on the port side. In the situation of ASV with Obstacle4 and Obstacle5, ASV continued to alter its course to starboard to pass through the stern of the obstacles in compliance with COLREG rule 15.

The results of the simulation applying the SBMPC method are shown in Figure 11 for the situation of ASV with Obstacle1. ASV altered its course to starboard even though Obstacle1 took evasive action. When the ASV was placed in a head-on situation with Obstacle2 and Obstacle3, ASV altered its course to port in non-compliance with COLREGs rule 14. Moreover, when ASV encountered Obstacle4 and Obstacle5 in a crossing situation, the ASV altered its course to starboard and passed ahead of the others in non-compliance with COLREGs rule 15. Table 7 lists the minimum distance passed on the way to each obstacle for each methodology. According to Table 7, the results of the route planning using the proposed method were found to be safer than those of SBMPC.

In this study, the MPC and PSO algorithms were utilized for path planning and collision avoidance of ASVs. In the closed loop of MPC, the collision risk of the predicted path was evaluated based on the FCE method to determine the safest path. The behavior of ASVs violating COLREGs was penalized to ensure that ASV complies with COLREGs in encounter situations. Through simulations, the proposed method was verified as the ASV properly avoided collisions while complying with COLREGs in standard encounter situations. To verify the effectiveness of the proposed method, it was applied alongside the existing SBMPC method to evaluate possible encounter situations, and the results were compared. The performance of the proposed method was better than that of the SBMPC method. However, considering that there are diverse encounter situations among vessels, real complicated situations should be studied in further work. Furthermore, external factors, such as the visibility of the sea and tidal currents, should be considered. The proposed method is expected to contribute to intelligent collision avoidance by ASVs, and to assist in decision-making when the shore controller or navigators determine the risk of a collision necessitating action to avoid collisions at sea.

No potential conflict of interest relevant to this article was reported.

Fig. 1.

Definition of encounter situation.


Fig. 2.

Steering and sailing rules in each encounter situation defined by COLREGs: (a) overtaking, (b) head-on situation, and (c) crossing situation.


Fig. 3.

Flowchart of collision avoidance for ASVs.


Fig. 4.

Basic idea of the model predictive control.


Fig. 5.

Structure of collision avoidance system based on MPC-PSO.


Fig. 6.

Simulation results for head-on situation. (a) Trajectory plot until the distance between the ASV and the obstacle vessel are closest. (b) Full trajectory plot of the ASV and obstacle vessel. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.


Fig. 7.

Simulation results for starboard crossing situation. (a) Trajectory plot until the distance between the ASV and the obstacle vessel is closest. (b) Full trajectory plot of the ASV and obstacle vessel. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.


Fig. 8.

Simulation results for port crossing situation. (a) Trajectory plot to minimize the distance between the ASV and the obstacle vessel.


Fig. 9.

Simulation results for overtaking. (a) Trajectory plot to minimize the distance between the ASV and the obstacle vessel. (b) Full trajectory plot of the ASV and obstacle vessel. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.


Fig. 10.

Simulation results for an encounter situation with multiple obstacle vessels based on MPC-PSO. (a) Full trajectory plot of the ASV and each obstacle vessel. (b) Trajectory plot up to the point where the distance between the ASV and each obstacle vessel are the closest. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.


Fig. 11.

Simulation results for an encounter situation with multiple obstacle vessels based on SBMPC. (a) Full trajectory plot of the ASV and each obstacle vessel. (b) Trajectory plot up to the point where the distance between the ASV and each obstacle vessel is the closest. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.


Table. 1.

Table 1. Parameters for simulation.

ParameterValueParameterValue
Tc5 sec5.5, 10
Tp5 secW3
Te1,700 sec, 3,500 secWP30
Hc25 secWχ0.9
Hp600 secWΔP10
Ts10 minWΔχ0.6
LOA1120 mSWsize20
LOA2100 mMaxi15

Table. 2.

Table 2. Initial navigation parameters for head-on situation.

ObjectPosition (x, y)Speed (knot)Course (°)
ASV(0, 0)100
Obstacle(0, 10,000)8180

Table. 3.

Table 3. Initial navigation parameters for crossing situation.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle(4000, 4000)10270

Table. 4.

Table 4. Initial navigation parameters for crossing situation.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle(−3000, 6000)690

Table. 5.

Table 5. Initial navigation parameters for overtaking.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle(0, 3000)30

Table. 6.

Table 6. Initial navigation parameters for an encounter situation with multiple obstacles.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle1(−3000, 6000)690
Obstacle2(10000,19000)6247
Obstacle3(10000,18000)5252
Obstacle4(300,20000)7180
Obstacle5(500, 20000)6182

Table. 7.

Table 7. The closest distance between ASV and each Obstacle in the validation simulation (measure of distance: nm).

MethodObstacle1Obstacle2Obstacle3Obstacle4Obstacle5Ave. value
MPC-PSO1.04271.45850.81381.96692.00421.4572
SBMPC0.51630.80501.33150.43710.30190.6784

  1. European Maritime Safety Agency (2021). Annual Overview of Marine Casualties and Incidents 2021. Lisbon, Portugal: European Maritime Safety Agency
  2. Smierzchalski, R, and Michalewicz, Z (2000). Modeling of ship trajectory in collision situations by an evolutionary algorithm. IEEE Transactions on Evolutionary Computation. 4, 227-241. https://doi.org/10.1109/4235.873234
    CrossRef
  3. International Maritime Organization (1972). Convention on the International Regulations for Preventing Collisions at Sea (COLREGs). London, UK: International Maritime Organization
  4. Lee, HJ, and Rhee, KP (2001). Development of collision avoidance system by using expert system and search algorithm. International Shipbuilding Progress. 48, 197-212.
  5. Huang, S, Teo, RSH, and Tan, KK (2019). Collision avoidance of multi unmanned aerial vehicles: a review. Annual Reviews in Control. 48, 147-164. https://doi.org/10.1016/j.arcontrol.2019.10.001
    CrossRef
  6. Fahimi, F (2007). Non-linear model predictive formation control for groups of autonomous surface vessels. International Journal of Control. 80, 1248-1259. https://doi.org/10.1080/00207170701280911
    CrossRef
  7. Perera, LP, Carvalho, JP, and Soares, CG (2012). Intelligent ocean navigation and fuzzy-Bayesian decision/action formulation. IEEE Journal of Oceanic Engineering. 37, 204-219. https://doi.org/10.1109/JOE.2012.2184949
    CrossRef
  8. Zaccone, R, Martelli, M, and Figari, M . A COLREG-compliant ship collision avoidance algorithm., Proceedings of 2019 18th European Control Conference (ECC), 2019, Naples, Italy, Array, pp.2530-2535. https://doi.org/10.23919/ECC.2019.8796207
  9. Enevoldsen, TT, Reinartz, C, and Galeazzi, R (2021). COLREGs-Informed RRT* for collision avoidance of marine crafts. Available: https://arxiv.org/abs/2103.14426
  10. Johansen, TA, Perez, T, and Cristofaro, A (2016). Ship collision avoidance and COLREGS compliance using simulation-based control behavior selection with predictive hazard assessment. IEEE Transactions on Intelligent Transportation Systems. 17, 3407-3422. https://doi.org/10.1109/TITS.2016.2551780
    CrossRef
  11. Tan, Q, Dai, P, Zhang, Z, and Katupitiya, J (2018). MPC and PSO based control methodology for path tracking of 4WS4WD vehicles. Applied Sciences. 8. article no 1000
    CrossRef
  12. Thomas, J . Integrating particle swarm optimization with analytical nonlinear model predictive control for nonlinear hybrid systems., Proceedings of 2015 12th International Conference on Informatics in Control, Automation and Robotics (ICINCO), 2015, Colmar, France, pp.294-301.
  13. Yao, P, Wang, H, and Ji, H (2016). Multi-UAVs tracking target in urban environment by model predictive control and Improved Grey Wolf Optimizer. Aerospace Science and Technology. 55, 131-143. https://doi.org/10.1016/j.ast.2016.05.016
    CrossRef
  14. Kraiem, H, Aymen, F, Yahya, L, Trivino, A, Alharthi, M, and Ghoneim, SS (2021). A comparison between particle swarm and grey wolf optimization algorithms for improving the battery autonomy in a photovoltaic system. Applied Sciences. 11. article no 7732
    CrossRef
  15. Rabie, HM . Particle swarm optimization and grey wolf optimizer to solve continuous p-median location problems., Proceedings of the International Conference on Advanced Intelligent Systems and Informatics, 2019, Cairo, Egypt, pp.136-146.
  16. Aghababa, MP, Amrollahi, MH, and Borjkhani, M (2012). Application of GA, PSO, and ACO algorithms to path planning of autonomous underwater vehicles. Journal of Marine Science and Application. 11, 378-386. https://doi.org/10.1007/s11804-012-1146-x
    CrossRef
  17. Kang, YT, Chen, WJ, Zhu, DQ, Wang, JH, and Xie, QM (2018). Collision avoidance path planning for ships by particle swarm optimization. Journal of Marine Science and Technology. 26. article no 3
  18. Cockcroft, AN, and Lameijer, JNF (2003). Guide to the Collision Avoidance Rules. Jordan Hill, Oxford: Elsevier
  19. Park, J, and Jeong, J (2020). Assessment of ship collision risk in coastal waters by fuzzy comprehensive evaluation. Journal of Korean Institute of Intelligent Systems. 30, 325-330. https://doi.org/10.5391/jkiis.2020.30.4.325
    CrossRef
  20. Park, J, and Jeong, JS (2021). An estimation of ship collision risk based on relevance vector machine. Journal of Marine Science and Engineering. 9. article no 538
    CrossRef
  21. Lenart, AS (2015). Analysis of collision threat parameters and criteria. The Journal of Navigation. 68, 887-896. https://doi.org/10.1017/S0373463315000223
    CrossRef
  22. Gang, L, Wang, Y, Sun, Y, Zhou, L, and Zhang, M (2016). Estimation of vessel collision risk index based on support vector machine. Advances in Mechanical Engineering. https://doi.org/10.1177/1687814016671250
    CrossRef
  23. Xu, Q, Meng, X, and Wang, N (2009). Intelligent evaluation system of ship management. Marine Navigation and Safety of Sea Transportation. Boca Raton, FL: CRC Press, pp. 787-790
  24. Li, B, and Pang, FW (2013). An approach of vessel collision risk assessment based on the D–S evidence theory. Ocean Engineering. 74, 16-21. https://doi.org/10.1016/j.oceaneng.2013.09.016
    CrossRef
  25. Nguyen, M, Zhang, S, and Wang, X (2018). A novel method for risk assessment and simulation of collision avoidance for vessels based on AIS. Algorithms. 11. article no 204
    CrossRef
  26. Fossen, TI (2011). Handbook of Marine Craft Hydrodynamics and Motion Control. Chichester, UK: John Wiley & Sons
    CrossRef
  27. Maciejowski, JM (2001). Predictive Control: With Constraints. Harlow, UK: Pearson Education
  28. Grune, L, and Pannek, J (2017). Nonlinear model predictive control. Nonlinear Model Predictive Control. Cham, Switzerland: Springer, pp. 45-69 https://doi.org/10.1007/978-3-319-46024-6_3
    CrossRef
  29. Kennedy, J, and Eberhart, R . Particle swarm optimization., Proceedings of International Conference on Neural Networks (ICNN), 1995, Perth, Australia, Array, pp.1942-1948. https://doi.org/10.1109/ICNN.1995.488968
  30. Mezura-Montes, E, and Coello, CAC (2011). Constraint-handling in nature-inspired numerical optimization: past, present and future. Swarm and Evolutionary Computation. 1, 173-194. https://doi.org/10.1016/j.swevo.2011.10.001
    CrossRef
  31. Pedersen, MEH (2010). Good parameters for particle swarm optimization. Copenhagen, Denmark: Hvass Laboratories Technical Report No. HL1001
  32. Morris, BT (2010). Understanding Activity from Trajectory Patterns. San Diego, CA: University of California

Jinwan Park received his Ph.D. degree in Maritime Information Systems from Mokpo National Maritime University, Korea. His research interests include maritime safety, vessel traffic theory, ASV control, optimization method, and intelligent navigation systems.

E-mail: pjinwan2@gmail.com


Article

Original Article

International Journal of Fuzzy Logic and Intelligent Systems 2021; 21(4): 378-390

Published online December 25, 2021 https://doi.org/10.5391/IJFIS.2021.21.4.378

Copyright © The Korean Institute of Intelligent Systems.

Improved Collision Avoidance Method for Autonomous Surface Vessels Based on Model Predictive Control Using Particle Swarm Optimization

Jinwan Park

Department of Maritime Transportation System, Mokpo National Maritime University, Mokpo, Korea

Correspondence to:Jinwan Park (pjinwan2@gmail.com)
*These authors contributed equally to this work.

Received: November 10, 2021; Revised: December 11, 2021; Accepted: December 17, 2021

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Most collision accidents are caused by human errors in an encounter situation between vessels. Autonomous operations have received much interest among researchers to reduce human errors resulting from improper vessel maneuvering actions. In this paper, an intelligent collision avoidance method that considers not only the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) but also complex encounter situations with multiple obstacle vessels was proposed for autonomous surface vessels (ASVs). The results were verified by comparing the performance with that of existing methods. To take timely maneuvering actions to prevent the collision of vessels involved in an encounter, fuzzy comprehensive evaluation, and model predictive control using particle swarm were applied to path planning. As a result, ASVs can take proper action to avoid collisions in compliance with COLREGs based on the proposed method. The improved collision avoidance method exhibits better performance than existing methods.

Keywords: Autonomous surface vessels, Path planning, Collision avoidance, Model predictive control, Particle swarm optimization

1. Introduction

The European Maritime Safety Agency (EMSA) reported that navigation accidents over the years 2014–2019 make up 44% of total vessel accidents [1]. In particular, 54% of vessel accidents are caused by improper human actions in encounter situations among vessels. Despite the various real-time information on vessel movements provided by advanced navigation equipment such as RADAR, electronic chart display and information systems (ECDIS), and automatic identification system (AIS), vessel accident records show that subsequent actions taken to avoid vessel collisions based on risk assessment are not performed properly. With the advent of digitalization in the maritime industry, autonomous operations are expected to decrease human errors through intelligent collision risk assessment and collision avoidance algorithms.

This paper proposes a collision avoidance algorithm for autonomous surface vessels (ASVs) which require intelligent and automatic operations. Smierzchalski and Michalewicz [2] proposed an evolutionary algorithm-based decision-support system for path planning in collision situations; however, the Convention on the International Regulations for Preventing Collisions at Sea (COLREGs) [3] were not considered. Lee and Rhee [4] developed a collision avoidance system using fuzzy theory and the A-star algorithm, which is a graph-based method for searching the shortest path. However, a rule-based collision avoidance system using fuzzy theory may have difficulty in responding appropriately to unexpected situations [5]. Fahimi [6] proposed a method for controlling multiple ASVs by applying the nonlinear model predictive control (NMPC) method. The experimental results of Fahimi’s method, however, require additional validation to determine compliance with COLREGs. Perera et al. [7] proposed a collision avoidance method based on fuzzy logic and Bayesian network and validated it through experiments involving multiple target vessels. Their method failed to comply with COLREGs in unexpected situations where the target vessels corresponding to the stand-on vessel did not take evasive action. Zaccone et al. [8] and Enevoldsen et al. [9] proposed collision avoidance methods for vessels based on a rapidly-exploring random tree algorithm (RRT*). Although compliant with COLREGs, they did not consider multiple obstacles in a complex situation. Johansen et al. [10] introduced the simulation-based model predictive control (SBMPC) method for collision avoidance by evaluating collision risk and COLREGs compliance for each predetermined finite number of scenarios.

In addressing the challenge of collision avoidance for the safety of vessel traffic, compliance with COLREGs should be considered in situations where multiple obstacle vessels are encountered. Therefore, methods based on model predictive control (MPC) that predict the future path of a vessel within a finite time horizon and control the vessel according to predefined constraints are suitable for collision avoidance systems. A mathematical optimization method can be used to derive an optimal input to the control system based on the MPC formulation. To improve the methodology proposed in [10], the particle swarm optimization (PSO) algorithm is incorporated into MPC to find an optimal path. The PSO algorithm is a fast and simple method for searching the global minimum and is suitable for real-time path planning. Tan et al. [11] and Thomas [12] applied MPC and PSO in real-time control systems and subsequently proved the performance. Yao et al. [13] proposed an MPC method to improve the grey wolf optimizer (GWO) to plan the optimal trajectories of multiple unmanned aerial vehicles for target tracking in the urban environment. However, Kraiem et al. [14] and Rabie [15] proved that PSO tends to outperform GWO. In the field of autonomous underwater vehicles (AUVs), the PSO algorithm has already been applied to collision avoidance and path planning, and the effectiveness of its performance has been verified in [16]. Kang et al. [17] also used the PSO algorithm for path planning of vessels. They considered only single obstacle vessels for the path planning. Therefore, it is necessary to consider not only compliance with COLREGs, but also multiple obstacle vessels. In this study, to verify performance, the proposed method was compared with the existing SBMPC [10], in a case simulation.

The remainder of this paper is organized as follows: in Section 2, the main rules of COLREGs are described as applied to collision avoidance systems; in Section 3, a methodology for path planning and collision avoidance for ASVs based on the MPC and PSO algorithms is proposed. In Section 4, the results of the case simulations and verification are presented. Finally, in Section 5, along with the conclusion future directions are suggested.

2. COLREGs

Path planning with collision avoidance requires compliance with COLREG rules. The steering and sailing rules of COLREGs are classified according to visibility conditions. The definition of an encounter situation when the vessels are in sight of one another is shown in Figure 1. In Figure 1, the vessel is represented by the red triangle. Overtaking is defined as a situation in which an obstacle vessel overtakes another vessel at a position where the relative bearing range is 112.5°–247.5°. Starboard crossing is a situation in which an obstacle vessel crosses another vessel ahead at a position where the relative bearing range is 006°–112.5°. Port crossing is a situation in which an obstacle vessel crosses another vessel ahead at a position where the relative bearing range is 247.5°–354°. In head-on situations, on the other hand, vessels have courses within approximately 6°, in opposite directions [18].

The steering and sailing rules of COLREGs depicting different situations are shown in Figure 2. In each situation, the give-way vessel is supposed to keep out of the way of another ship, so far as possible, taking early and substantial action to keep it clear. The stand-on vessel should maintain its course and speed.

3. Methodology

If there is a risk of collision while the vessel is navigating, proactive action is required to avoid collisions in compliance with COLREGs. An assessment of collision risk is important for finding a safe path to avoid the collision. However, it is difficult for a navigator to accurately determine the existence of collision risk because the navigation of a ship involves uncertainty. The fuzzy comprehensive evaluation (FCE) method was applied to address this uncertainty problem. FCE can reflect on various factors affecting the collision risk of vessels and can be evaluated both subjectively and objectively by experts. The distance at closest point approach (DCPA), time to closest point approach (TCPA), distance, relative bearing, and velocity ratio are determined as the target factors affecting the risk of ship collision whereby AIS data can provide navigation information on a ship’s own vessel as well as the obstacle vessels during navigation. However, it is difficult to determine the existence of collision risk using only quantitative assessments. Therefore, the collision risk detection algorithm [1921] is applied to automatically inform ASVs of the existence of collision risk. This algorithm detects collision risk by applying “time to safe distance”, which indicates the time it takes for the distance between two vessels to reach a safe distance. The path planning algorithm proposed in this study starts to search for a safe path for collision avoidance based on MPC and PSO when a risk of collision is detected. In the closed loop of the MPC, the three degree of freedom (DOF) vessel dynamics model was applied to predict the path of the vessel and process the optimized control input. In the optimization stage, the PSO algorithm, which is a simple and powerful optimization method, was applied. Compliance with COLREGs is considered a constraint for finding a collision-free path. A flowchart of the proposed collision-avoidance method is shown in Figure 3.

3.1 Collision Risk Assessment

To assess the risk of collision between two vessels quantitatively, the FCE method was applied. The FCE method combines the subjective evaluation of experts with objective evaluation using a database for each factor that affects the target [19,20]. In this study, DCPA, TCPA, distance (D), relative bearing (B), and velocity ratio (K) were selected as the target factors to calculate the collision risk using the FCE method. In the Cartesian coordinate system, the origin is the position of the ASV; (X, Y ) denotes the relative position of the obstacle vessel; Vo denotes the true velocity of the ASV; Vt denotes the true velocity of the obstacle vessel; Vr denotes the relative velocity of the obstacle vessel with respect to ASV; and Vrx, Vry denote the components of Vr in the x and y directions, respectively. Consequently, the DCPA, TCPA, D, and K can be obtained as follows [1921]:

DCPA=|XVry-YVrxVr|,TCPA=-XVrx+YVryVr2,D=X2+Y2,K=Vt/Vo.

According to the FCE method, the collision risk index (CRI) can be calculated by the dot product of the weight vector and membership vector, as follows [19,20,22,23]:

CRI=W·U=WDCPA·UDCPA+WTCPA·UTCPA+WD·UD+WB·UB+WK·UK,

where W and U represent the weight and membership vector of the target factors, respectively. The membership value for each target factor can be calculated using the membership function [19,20,22,24,25], which can be stated for DCPA as follows:

UDCPA={1,DCPA<d1,(d2-DCPAd2-d1)2,d1DCPAd2,0,DCPA>d2,

where d1 is the minimum safety distance between encountered vessels and d2 is the absolute safety distance, which is equal to twice the value of d1. The value of d1 is calculated as follows:

d1={1.1,355°<B67.5°,1,67.5°<B112.5°,0.6,112.5°<B247.5°,0.9,247.5°<B355°.

The membership function of TCPA is given by

UTCPA={1,0TCPAt1,(t2-TCPAt2-t1)2,t1TCPAt2,0,TCPA>t2,

where t1 is the time remaining until collision, and t2 is the collision avoidance time; t1 and t2 are calculated as follows:

t1={d12-DCPA2VR,DCPAd1,0,DCPA>d1,t2={d22-DCPA2VR,DCPAd2,0,DCPA>d2.

The membership function of D given by

UD={1,0<D<D1,(D2-DD2-D1)2,D1DD2,0,D>D2,

where D1 is the critical safety distance and is equal to 12 times the overall length of ASV, and D2 is the distance required to take a last action. D2 can be calculated as follows:

D2=1.7cos(B-19°)+4.4+2.89cos2(B-19°),

where the membership function of B is expressed as

UB=12[cos(B-19°)+440289+cos2(B-19°)]-517,

and the membership function of K is

UK=11+2KK2+1+2KsinC.

3.2 Path Planning and Collision Avoidance

Based on the collision risk assessment of the vessel, if there is a risk of collision, the path should be planned to avoid the risk of collision in compliance with the COLREGs. To avoid the risk of collision of ASVs, their course or speed can be adjusted using a controller. Therefore, the collision avoidance system is designed such that ASVs can navigate along a safe path through predictive control using the model of ship dynamics.

3.2.1 Ship dynamics

When designing control systems for ship collision avoidance, three DOF horizontal plane models (surge, sway, and yaw) are used, as described in [19]. The models are generally used in dynamic positioning systems, trajectory-tracking control systems, and path-following systems for ships, semi-submersibles, and underwater vehicles because most crafts do not have actuation in DOF [26]. The nonlinear maneuvering equations based on the rigid-body force and hydrodynamic forces can be written as follows:

η˙=[cos(ψ)-sin(ψ)0sin(ψ)cos(ψ)0001]ν,Mν˙+C(ν)ν+D(ν)ν=τ,

where denotes the position and course defined on the interval ; ν = [u, v, r]∈ ℝ3 represents the relative velocities in surge, sway and yaw; M denotes the vessel inertia matrix; C(·) is the Coriolis-centripetal term; D(·) is the damping term; and τ represents the vector of control inputs.

To control vessel behavior, the steering system and propulsion were considered, as described in [10]. It is assumed that the steering system utilizes line-of-sight (LOS) guidance which is based on the principle of lookahead steering [10,26]. This guidance computes the desired course angle χd so that the vessel proceeds according to the preplanned path. The actual course command for the steering system can be obtained as follows [10,26]:

χ=χd+χca,

where χca denotes the course angle offset provided by the collision avoidance system. Vessel propulsion can be controlled by a constant propulsion command P ∈ [−1, 1] where 1 is ahead propulsion, 0 is stop, and −1 is full astern propulsion.

3.2.2 Model predictive control

MPC is an advanced feedback control method that has a noticeable impact on process industries. This algorithm predicts the future outputs of a process to determine the control actions to optimize in the current time step. The main advantage of MPC is that it can handle multivariable control problems and directly handle constraints. In discrete-time space, a plant model is assumed to have the following form [27,28]:

x(t+1)=f(x(t),u(t),t),y(t)=g(x(t),t),

where f and g are known nonlinear functions; x denotes an n-dimensional state vector; u denotes an m-dimensional input vector; y denotes an l-dimensional vector of the measured outputs; and t is the time instant. Letting k be the current timestep, any control sequence u(t | k) with prediction horizon Hp and prediction outputs ŷ(t | k) can be obtained by minimizing the function J as follows [27,28]:

J=i=1Hpγe(tk+i)2+i=1Hpλu(tk+i)2+i=1HcμΔu(tk+i)2,

where

Δu(tk)=u(tk)-u(tk-1),

e denotes the error between reference r and the predicted output ŷ; Hc denotes the control horizon; || · || denotes the Euclidean norm; and γ, λ, μ are weighting parameters for the control penalization. The procedure is illustrated in Figure 4 [27].

At each time step, an iterative online optimization is conducted to obtain the new input over the predictions generated by the plant model. The process control method is called the receding horizon strategy because the prediction horizon moves along with one sampling interval [27].

3.2.3 Particle swarm optimization

The PSO algorithm utilizes the idea that particles belonging to a certain swarm share information with each other to establish an optimal destination. This algorithm was introduced by Kennedy and Eberhart [29] and improved by Mezura-Montes and Coello [30] and Pedersen [31]. Each particle belonging to a certain swarm has a position vector p∈ℝn and a velocity vector v∈ℝn in the corresponding search space, as a candidate solution to the optimization problem. The algorithm, upon start, creates particles and initializes the position vector, velocity vector, and objective function value corresponding to each particle. Subsequently, each particle position is evaluated by the objective function, and the particle with the minimum value of the objective function determines the best position hbest. The global best position gbest is determined by iteratively updating the velocity and position vectors of each particle in the swarm. The equation for this algorithm can be written as follows:

pj(i+1)=pj(i)+vj(+1),vj(i+1)=ωvj(i)+φhrh(hjbest(i)-pi(i))+φgrg(gbest(i)-pj(i)),

where j denotes the particle index; i denotes the iteration index; ω denotes an inertia coefficient; φh and φg are acceleration coefficients; rh and rg are random vectors that are uniformly distributed.

3.2.4 Proposed MPC-PSO method

To control the ASV behavior in the risk of collision, the constant propulsion command P and course angle offset χca are utilized as the particle’s position vectors of the PSO algorithm in the MPC controller. When the state vector of the obstacle vessel and waypoint information are input into the MPC-PSO controller, the optimized P and χca are delivered to the vessel. Simultaneously, the desired course angle χd and the desired velocity νd, which are calculated by guidance, are also input to the vessel. The structure of the collision-avoidance system is shown in Figure 5.

The objective function for the MPC-PSO controller is expressed as

J(tk)=WC(maxomax1iHpCo(tk+i))+Wo=1Noi=1Hpo(tk+i)+WP(1-P)+Wχχca+WΔPL-Llast+WΔχDHU(Tr,Trlast),={1,0<B112.5°,0,otherwise,

where , W, Wχ, WΔP, and WΔχ are weighting parameters for the control penalization; o is the index of the obstacle vessels; No is the number of obstacle vessels; is the collision risk index; Tr is the predicted path of the vessel of interest with input in the current time step; Trlast is the predicted path of the vessel based on the last output of the controller; L is the length of Tr; Llast is the length of Trlast; and DHU(·) denotes the HU distance [32], which is computed as the average Euclidean distance between points in two trajectories. In the objective function, the first term calculates the collision risk index of the predicted path to enable the vessel to find a path free of collision risk. The second term penalizes the situation in which the obstacle vessel is located on the starboard side of the vessel of interest so that the latter can comply with COLREGs. The third and fourth terms adjust the priority of altering the course and reducing the speed when the vessel takes action to avoid the risk of collision. The remaining terms are included to ensure stability of vessel maneuvering.

4. Simulations

Simulations were carried out for an encounter situation defined according to COLREGs, to verify that ASV can avoid the risk of collision in compliance with COLREGs for obstacle vessels that do not take evasive actions, except in the port crossing situation. In addition, the performance of the proposed method was verified by comparing it with that of SBMPC in a situation of sequentially encountering multiple obstacle vessels. The parameters used in the simulations for each scenario are summarized in Table 1.

In Table 1, Tc is the time step interval in the simulation; Tp is the time step interval for prediction; Te is the end time of the simulation; LOA1 is the overall length of the vessel; LOA2 is the overall length of the obstacle vessel. In the PSO algorithm, SWsize is the swarm size, and Maxi is the maximum number of iterations. Moreover, the boundary of the propulsion command P and the course angle offset χca are denoted by the position variables of the PSO algorithm, and set to [0.5, 1] and [−90, 90], respectively. Different values of Te and were applied depending on the number of obstacles in the encounter situation, that is, a single obstacle or multiple obstacles.

4.1 Head-on Situation

Path planning simulation for the head-on situation in which the ASV has a collision risk with one obstacle vessel was carried out according to Table 2, where the initial settings of the scenario are displayed. Based on the simulation results displayed in Figure 6, ASV altered its course to starboard in compliance with COLREGs rule 14 to avoid the obstacle encountered. The results illustrate the vessel altering her course to return to port according to the planned path after passing the obstacle vessel on the port side. The minimum distance between the ASV and obstacle vessel was found to be 0.8729 nm, and only course alteration was performed without reducing the speed to avoid collision.

4.2 Starboard Crossing Situation

The simulation of path planning for the crossing situation in which the ASV has a collision risk with one obstacle vessel located on the starboard side was carried out according to Table 3, where the initial settings are displayed for this scenario. According to the simulation results shown in Figure 7, ASV altered its course to starboard in compliance with COLREGs rule 15 to avoid the obstacle vessel encountered. Figure 7 illustrates the vessel altering her course to return to port along the planned path after passing the obstacle vessel on the port side. The minimum distance between the ASV and obstacle vessel was found to be 0.5532 nm, and only course alteration was performed without reducing the speed to avoid collision.

4.3 Port Crossing Situation

The path planning was simulated for the crossing situation in which the ASV has a collision risk with one obstacle vessel located on the port side. The initial settings for this scenario are displayed in Table 4. Because the obstacle vessel corresponds to the give-way vessel according to the COLREGs rule 15, the scenario was designed such that the obstacle vessel altered its course to starboard to avoid collision. According to the simulation results shown in Figure 8, ASV maintained her course and speed in compliance with COLREG rules 15 and 17. The minimum distance between the ASV and the obstacle vessel was 0.2794 nm.

4.4 Overtaking

Path planning simulation for the overtaking situation in which the ASV has a collision risk with one obstacle vessel was carried out with the initial settings for the scenario displayed in Table 5. Based on the simulation results displayed in Figure 9, the ASV altered its course to starboard in compliance with COLREGs rule 13 to avoid the obstacle vessel in returning to port along the planned path after passing the obstacle vessel on the port side. The minimum distance between the ASV and the obstacle vessel was 0.4662 nm, and only course alteration was performed without reducing the speed to avoid collision.

4.5 Comparison with SBMPC

In the standard encounter situations defined by COLREGs, the behavior of the ASV in avoiding collisions while complying with regulations was verified. In addition, to verify the effectiveness of the proposed method (MPC-PSO), the proposed method was applied jointly with the existing SBMPC to a possible encounter situation, and the results were compared. The parameters used for the objective function in the SBMPC method are as follows:

Kcoll=0.02;dsafe=1,025;dcl=2,500;κ=25;kP=33;ΔP=13;kχ-port=0.65;kχ-starboard=0.3;Δχ-port=0.55;Δχ-starboard=0.2.

Path planning simulation for the situation where the ASV has a collision risk with five obstacle vessels was carried out with the initial settings of the scenario displayed in Table 6. The results of the simulation using the proposed method are shown in Figure 10 for an ASV with Obstacle1. The ASV kept its course and speed as Obstacle1 took action to avoid collision. To compare the performance of the SBMPC method, the ASV and Obstacle1 scenarios were designed as in Section 4.3 to compare the performance of the SBMPC method. ASV then altered its course to starboard to keep out of the way of Obstacle2 and Obstacle3 passing Obstacle1 on the port side. In the situation of ASV with Obstacle4 and Obstacle5, ASV continued to alter its course to starboard to pass through the stern of the obstacles in compliance with COLREG rule 15.

The results of the simulation applying the SBMPC method are shown in Figure 11 for the situation of ASV with Obstacle1. ASV altered its course to starboard even though Obstacle1 took evasive action. When the ASV was placed in a head-on situation with Obstacle2 and Obstacle3, ASV altered its course to port in non-compliance with COLREGs rule 14. Moreover, when ASV encountered Obstacle4 and Obstacle5 in a crossing situation, the ASV altered its course to starboard and passed ahead of the others in non-compliance with COLREGs rule 15. Table 7 lists the minimum distance passed on the way to each obstacle for each methodology. According to Table 7, the results of the route planning using the proposed method were found to be safer than those of SBMPC.

5. Conclusion

In this study, the MPC and PSO algorithms were utilized for path planning and collision avoidance of ASVs. In the closed loop of MPC, the collision risk of the predicted path was evaluated based on the FCE method to determine the safest path. The behavior of ASVs violating COLREGs was penalized to ensure that ASV complies with COLREGs in encounter situations. Through simulations, the proposed method was verified as the ASV properly avoided collisions while complying with COLREGs in standard encounter situations. To verify the effectiveness of the proposed method, it was applied alongside the existing SBMPC method to evaluate possible encounter situations, and the results were compared. The performance of the proposed method was better than that of the SBMPC method. However, considering that there are diverse encounter situations among vessels, real complicated situations should be studied in further work. Furthermore, external factors, such as the visibility of the sea and tidal currents, should be considered. The proposed method is expected to contribute to intelligent collision avoidance by ASVs, and to assist in decision-making when the shore controller or navigators determine the risk of a collision necessitating action to avoid collisions at sea.

Fig 1.

Figure 1.

Definition of encounter situation.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 2.

Figure 2.

Steering and sailing rules in each encounter situation defined by COLREGs: (a) overtaking, (b) head-on situation, and (c) crossing situation.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 3.

Figure 3.

Flowchart of collision avoidance for ASVs.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 4.

Figure 4.

Basic idea of the model predictive control.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 5.

Figure 5.

Structure of collision avoidance system based on MPC-PSO.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 6.

Figure 6.

Simulation results for head-on situation. (a) Trajectory plot until the distance between the ASV and the obstacle vessel are closest. (b) Full trajectory plot of the ASV and obstacle vessel. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 7.

Figure 7.

Simulation results for starboard crossing situation. (a) Trajectory plot until the distance between the ASV and the obstacle vessel is closest. (b) Full trajectory plot of the ASV and obstacle vessel. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 8.

Figure 8.

Simulation results for port crossing situation. (a) Trajectory plot to minimize the distance between the ASV and the obstacle vessel.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 9.

Figure 9.

Simulation results for overtaking. (a) Trajectory plot to minimize the distance between the ASV and the obstacle vessel. (b) Full trajectory plot of the ASV and obstacle vessel. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 10.

Figure 10.

Simulation results for an encounter situation with multiple obstacle vessels based on MPC-PSO. (a) Full trajectory plot of the ASV and each obstacle vessel. (b) Trajectory plot up to the point where the distance between the ASV and each obstacle vessel are the closest. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Fig 11.

Figure 11.

Simulation results for an encounter situation with multiple obstacle vessels based on SBMPC. (a) Full trajectory plot of the ASV and each obstacle vessel. (b) Trajectory plot up to the point where the distance between the ASV and each obstacle vessel is the closest. (c) The course offset angle χca and the propulsion P of the ASV for collision avoidance. (d) Actual course command χ of the ASV.

The International Journal of Fuzzy Logic and Intelligent Systems 2021; 21: 378-390https://doi.org/10.5391/IJFIS.2021.21.4.378

Table 1 . Parameters for simulation.

ParameterValueParameterValue
Tc5 sec5.5, 10
Tp5 secW3
Te1,700 sec, 3,500 secWP30
Hc25 secWχ0.9
Hp600 secWΔP10
Ts10 minWΔχ0.6
LOA1120 mSWsize20
LOA2100 mMaxi15

Table 2 . Initial navigation parameters for head-on situation.

ObjectPosition (x, y)Speed (knot)Course (°)
ASV(0, 0)100
Obstacle(0, 10,000)8180

Table 3 . Initial navigation parameters for crossing situation.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle(4000, 4000)10270

Table 4 . Initial navigation parameters for crossing situation.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle(−3000, 6000)690

Table 5 . Initial navigation parameters for overtaking.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle(0, 3000)30

Table 6 . Initial navigation parameters for an encounter situation with multiple obstacles.

ObjectInitial position (x, y)Speed (knot)Initial course (°)
ASV(0, 0)100
Obstacle1(−3000, 6000)690
Obstacle2(10000,19000)6247
Obstacle3(10000,18000)5252
Obstacle4(300,20000)7180
Obstacle5(500, 20000)6182

Table 7 . The closest distance between ASV and each Obstacle in the validation simulation (measure of distance: nm).

MethodObstacle1Obstacle2Obstacle3Obstacle4Obstacle5Ave. value
MPC-PSO1.04271.45850.81381.96692.00421.4572
SBMPC0.51630.80501.33150.43710.30190.6784

References

  1. European Maritime Safety Agency (2021). Annual Overview of Marine Casualties and Incidents 2021. Lisbon, Portugal: European Maritime Safety Agency
  2. Smierzchalski, R, and Michalewicz, Z (2000). Modeling of ship trajectory in collision situations by an evolutionary algorithm. IEEE Transactions on Evolutionary Computation. 4, 227-241. https://doi.org/10.1109/4235.873234
    CrossRef
  3. International Maritime Organization (1972). Convention on the International Regulations for Preventing Collisions at Sea (COLREGs). London, UK: International Maritime Organization
  4. Lee, HJ, and Rhee, KP (2001). Development of collision avoidance system by using expert system and search algorithm. International Shipbuilding Progress. 48, 197-212.
  5. Huang, S, Teo, RSH, and Tan, KK (2019). Collision avoidance of multi unmanned aerial vehicles: a review. Annual Reviews in Control. 48, 147-164. https://doi.org/10.1016/j.arcontrol.2019.10.001
    CrossRef
  6. Fahimi, F (2007). Non-linear model predictive formation control for groups of autonomous surface vessels. International Journal of Control. 80, 1248-1259. https://doi.org/10.1080/00207170701280911
    CrossRef
  7. Perera, LP, Carvalho, JP, and Soares, CG (2012). Intelligent ocean navigation and fuzzy-Bayesian decision/action formulation. IEEE Journal of Oceanic Engineering. 37, 204-219. https://doi.org/10.1109/JOE.2012.2184949
    CrossRef
  8. Zaccone, R, Martelli, M, and Figari, M . A COLREG-compliant ship collision avoidance algorithm., Proceedings of 2019 18th European Control Conference (ECC), 2019, Naples, Italy, Array, pp.2530-2535. https://doi.org/10.23919/ECC.2019.8796207
  9. Enevoldsen, TT, Reinartz, C, and Galeazzi, R (2021). COLREGs-Informed RRT* for collision avoidance of marine crafts. Available: https://arxiv.org/abs/2103.14426
  10. Johansen, TA, Perez, T, and Cristofaro, A (2016). Ship collision avoidance and COLREGS compliance using simulation-based control behavior selection with predictive hazard assessment. IEEE Transactions on Intelligent Transportation Systems. 17, 3407-3422. https://doi.org/10.1109/TITS.2016.2551780
    CrossRef
  11. Tan, Q, Dai, P, Zhang, Z, and Katupitiya, J (2018). MPC and PSO based control methodology for path tracking of 4WS4WD vehicles. Applied Sciences. 8. article no 1000
    CrossRef
  12. Thomas, J . Integrating particle swarm optimization with analytical nonlinear model predictive control for nonlinear hybrid systems., Proceedings of 2015 12th International Conference on Informatics in Control, Automation and Robotics (ICINCO), 2015, Colmar, France, pp.294-301.
  13. Yao, P, Wang, H, and Ji, H (2016). Multi-UAVs tracking target in urban environment by model predictive control and Improved Grey Wolf Optimizer. Aerospace Science and Technology. 55, 131-143. https://doi.org/10.1016/j.ast.2016.05.016
    CrossRef
  14. Kraiem, H, Aymen, F, Yahya, L, Trivino, A, Alharthi, M, and Ghoneim, SS (2021). A comparison between particle swarm and grey wolf optimization algorithms for improving the battery autonomy in a photovoltaic system. Applied Sciences. 11. article no 7732
    CrossRef
  15. Rabie, HM . Particle swarm optimization and grey wolf optimizer to solve continuous p-median location problems., Proceedings of the International Conference on Advanced Intelligent Systems and Informatics, 2019, Cairo, Egypt, pp.136-146.
  16. Aghababa, MP, Amrollahi, MH, and Borjkhani, M (2012). Application of GA, PSO, and ACO algorithms to path planning of autonomous underwater vehicles. Journal of Marine Science and Application. 11, 378-386. https://doi.org/10.1007/s11804-012-1146-x
    CrossRef
  17. Kang, YT, Chen, WJ, Zhu, DQ, Wang, JH, and Xie, QM (2018). Collision avoidance path planning for ships by particle swarm optimization. Journal of Marine Science and Technology. 26. article no 3
  18. Cockcroft, AN, and Lameijer, JNF (2003). Guide to the Collision Avoidance Rules. Jordan Hill, Oxford: Elsevier
  19. Park, J, and Jeong, J (2020). Assessment of ship collision risk in coastal waters by fuzzy comprehensive evaluation. Journal of Korean Institute of Intelligent Systems. 30, 325-330. https://doi.org/10.5391/jkiis.2020.30.4.325
    CrossRef
  20. Park, J, and Jeong, JS (2021). An estimation of ship collision risk based on relevance vector machine. Journal of Marine Science and Engineering. 9. article no 538
    CrossRef
  21. Lenart, AS (2015). Analysis of collision threat parameters and criteria. The Journal of Navigation. 68, 887-896. https://doi.org/10.1017/S0373463315000223
    CrossRef
  22. Gang, L, Wang, Y, Sun, Y, Zhou, L, and Zhang, M (2016). Estimation of vessel collision risk index based on support vector machine. Advances in Mechanical Engineering. https://doi.org/10.1177/1687814016671250
    CrossRef
  23. Xu, Q, Meng, X, and Wang, N (2009). Intelligent evaluation system of ship management. Marine Navigation and Safety of Sea Transportation. Boca Raton, FL: CRC Press, pp. 787-790
  24. Li, B, and Pang, FW (2013). An approach of vessel collision risk assessment based on the D–S evidence theory. Ocean Engineering. 74, 16-21. https://doi.org/10.1016/j.oceaneng.2013.09.016
    CrossRef
  25. Nguyen, M, Zhang, S, and Wang, X (2018). A novel method for risk assessment and simulation of collision avoidance for vessels based on AIS. Algorithms. 11. article no 204
    CrossRef
  26. Fossen, TI (2011). Handbook of Marine Craft Hydrodynamics and Motion Control. Chichester, UK: John Wiley & Sons
    CrossRef
  27. Maciejowski, JM (2001). Predictive Control: With Constraints. Harlow, UK: Pearson Education
  28. Grune, L, and Pannek, J (2017). Nonlinear model predictive control. Nonlinear Model Predictive Control. Cham, Switzerland: Springer, pp. 45-69 https://doi.org/10.1007/978-3-319-46024-6_3
    CrossRef
  29. Kennedy, J, and Eberhart, R . Particle swarm optimization., Proceedings of International Conference on Neural Networks (ICNN), 1995, Perth, Australia, Array, pp.1942-1948. https://doi.org/10.1109/ICNN.1995.488968
  30. Mezura-Montes, E, and Coello, CAC (2011). Constraint-handling in nature-inspired numerical optimization: past, present and future. Swarm and Evolutionary Computation. 1, 173-194. https://doi.org/10.1016/j.swevo.2011.10.001
    CrossRef
  31. Pedersen, MEH (2010). Good parameters for particle swarm optimization. Copenhagen, Denmark: Hvass Laboratories Technical Report No. HL1001
  32. Morris, BT (2010). Understanding Activity from Trajectory Patterns. San Diego, CA: University of California

Share this article on :

Related articles in IJFIS

Most KeyWord