This article introduces an automatic collision avoidance (ACA) system for ship integrated by three parts, combining stage discrimination module, a module to determine feasible collision avoidance action according to International Regulations for Preventing Collisions at Sea (COLREG) and a tracking module for keeping the own ship on the desired route. The paper attempts to discriminate the differently dangerous stages for encounters of ships by determining ship’s domain model and analyzing COLREG. The new ship domain model defining the most dangerous area around target ship is shaped based on ship maneuverability information and good seamanship, within which statistical method is performed. one hundred commercial vessels and 60 experienced officers are surveyed in order to determine parameters employed for ship domain construction. The concept of ACA is adopted by mutually flexible application between PID controller and complexity rules of algorithm named consecutive waypoint generation (CWPG) algorithm. Many simulation scenarios are then, utilized to validate the effectiveness and feasibility of the suggested system accompanying with the evaluation on saving energy and smoothness of the performance. A novel ACA system is presented in this research the effectiveness of which is convincing. The new ship domain model can be widely applied in general cases instead of certain restriction areas implementing surveys in previous studies. There is no fulfilled acceptance solution to the major until now, however, new approaching development of this research will promote a positive result for an application of ACA system in deploy in the future.
Close range collision avoidance for ship has never been an easy task in view of many problems faced by mariners. Numerous disasters occurred which was traced to human errors and neglect without navigational advising equipment available on the bridge. A sensible solution for maritime navigation, which is making decision assistance system seemed to be the effectively forwarded step in the future to decrease the risk of collision. A system is estimated to have optimum application only if it has certain criterions, such as determining the shortest route, the safest route, minimum figure for actions, observe the regulations, etc. However, the work including all of the mentioned factors is not easy the previous attempts have been lacking some of them. The impressing studies combined effectively between two importance criterions: shortest route and following international collision avoidance regulations. This major is categorized by three fields depending on the area of study. There are collision risk assessment, collision avoidance for ships and optimal route planning.
Study of collision risk assessment is witnessed as the early field of the major. The first concepts depended on the closest point of approach (CPA), time of closest point of approach (TCPA) or distance to closest point of approach (DCPA). This method is deemed to be adequate by many studies published and its effect in deploy. The research of [1] uses investigation parameters, including TCPA and DCPA as the input source to obtain the value of collision risk (CR) implemented by a fuzzy system. The evaluation of CR employing two parameters (TCPA, DCPA) is not a new method, nevertheless, it is effective in long range and all areas. Recently, the safety domain around ships is deemed the newly and effectively popular method employed in route planning algorithms due to the convenient application for separate purposes. The proposition of [2] was the first concept of ship domain marking an important role in assessing collision risk by the geometrical model. The domain introduced is an ellipse with the OS at the center shaped by the investigation of marine traffic in Japanese channels. Furthermore, [3] suggested three segments of the circles created by different radius, not to mention the fact that either domain has been widely applied since the 1970s in marine traffic engineering. The existing domains have presented various shapes and size computing from different factors, that is proved by numerous domain published in next three decades [4–8]. In general, the previous studies are divided into two kinds based on the function of domain, the first one has just required danger area without estimating CR and the second is the incorporation of both functions. Previous domains identified by AIS data are highly reliable in the survey area while outside is not.
While “collision risk assessment” has reached more benefit outcomes, the studies of “collision avoidance for ship” and “optimal route planning” have been implementing to find an adequate conclusion for practical application. The first published research of “collision avoidance for ship” carried out by Calvert [9] introduced a concept of starboard maneuvers during close-quarter. The next steps could be illustrated briefly by [10, 11]. On the whole, most publications focus on offering advice for a navigator in the case of facing the most dangerous encounter without multi-approach. However, they have some restrictions, such as:
COLREG is not combined into the [10] and [11]. Other studies of route planning using heuristic algorithms typically face that problem.
The actions encouraged is limited in its effectiveness, due to someone still required the new heading or velocity for avoiding the collision without optimization.
The geometries are too many to display for navigators, this issue makes some confusing feeling for mariners when the traffic is heavy, for instance in Pedersen’s anti-collision indicators [11].
The field of “route planning” has been started studying at the late of the 1990s and categorized into two groups, knowing as deterministic and heuristic approach. While heuristic approach commonly searches the empty or safe space for drawing a newly shortest route, heuristic approach constructs a set of rule defining steps of avoiding action, drawing a new route following different purpose of designer. The common features of ACAS applying heuristic approach are always finding the approximately shortest path, saving energy and smoothness performance while the deterministic focus on special purpose, such as following COLREG regulations, flexibility in special approach. The impression studies of the deterministic group are the propositions [12–14]. The second group is witnessed by studies [15–18].
Overall, under the literature review of close range collision avoidance for ship, this article suggested:
The new stage discrimination model is structured and a novel ship domain proposed plays an important role in such model. While previous domains identified by AIS data are highly reliable in the survey area instead of general areas, the ship domain in this study can be applied in general cases without in a certain area.
An effective domain will be identified by a new approach. The criteria of this domain are minimal and safe and it is deemed a flexible method for creating the shortest route and saving energy.
The appropriate automatic collision aviodance (ACA) algorithm is introduced in a combination with the proposed domain named consecutive waypoint generation (CWPG) algorithm. The validation is performed by simulation scenarios in order to prove the effectiveness of CWPG with previous studies.
This paper is structured into five sections including the introduction.
This study attempts to discriminate the differently dangerous stage for encounters of ships by determining ship’s domain model and analyzing COLREG. Officers process evaluating collision risk based on COLREG [19] rules and good seamanship; however, according to COLREG, the CR are not contained in clear descriptions. In the views of previous studies, this article will provide an appropriate method for identifying the scale of collision risk.
In COLREG, Rule 22 defined the visibility of the masthead light, stern light and sidelight for vessels over 50 m in length, 6, 3 and 3 miles, respectively. To this regulation, the distance between vessels, less than 6 miles are applied for appearance of CR in head-on situation. Similarly, 3 miles for overtaking situation and crossing situation. However, when two vessels are approaching at low speed, nobody can seriously contend that the required distances mentioned are applicable to them. It is necessary to generate another limitation requiring that TCPA be below a critical value. Dinh and Im introduced a novel concept of ship domain for target ship (TS) constructed by two parts, Action area and Blocking area (Figure 1) with the limited distance carried out by average TCPA in different situations [6].
Action area (ATA): A circle is determined by a radius defined by appropriate distance for making avoidance action. If the distance between two vessels is shorter than the radius of Action area, the safe passing distance cannot be ensured if only one ship fully maneuvers.
Blocking area (BLA): A quadrilateral defined by ship’s maneuverability and good seamanship. If own ship (OS) infringes TS’s Blocking area, the collision cannot be avoided if only OS fully alter her course.
Many studies presented the terms of stage model, [20, 21] attempted to this field. The four stages introduced, including no CR, CR, CS and ID. This article suggests different stages of encounter shown in Figure 2.
Stage 1 is defined obeying COLREG (Rule 22), the distance between two vessels over 6 miles do not exist. Stage 2 is defined when CR first appears, OS has to evaluate the CR for substantial action according to COLREG part B. Stage 3 is defined by when OS navigates inside ATA, the OS needs to alter her course to avoid BLA or collision. Stage 4 is defined by BLA of ship domain, this is the most dangerous area that all TS need to keep outside.
BLA deemed ship domain defining the most dangerous area around TS, the method for domain definition is illustrated in Figure 3.
In head-on situation, the shortest distance accepted for a passing of OS and TS is a sum of advance distance of turning circle of TS (Adv_{t}) and OS (Adv_{o}), such work is illustrated in Figure 3(a). This distance is sufficient for two ships to avoid each other in an emergency situation with her rudder is steered hard to port side or starboard (so D_{f} = Adv_{t} + Adv_{o}), the remaining edges (D_{a}, D_{p}, D_{s}) is the minimum distance for a safe passing (MinPD). In order to determine MinPD, the statistical method will be employed. In overtaking and crossing situation, the method for defining BLA is presented in Figures 3(a) and (c). For a sample, the equation to determine BLA in head-on situation:
where D_{f}, D_{a}, D_{p}, D_{s} are axis constructed BLA; Adv_{t} and Adv_{o} are advance distances of turning circle of TS and OS, respectively; ErrGPS is maximum user range error of GPS recorded, Δ is a maximum error of regression implements. Because Adv_{t} cannot be obtained in assistance device equipped on board. In order to determine such parameter, linear regression method is applied. One hundred commercial vessels are collected, including container and cargo ship (Figure 4). The final equation of Adv_{t} determined is expressed below,
where L_{t} is the length of ship.
The maximum error of regression implements (Δ) can be calculated by prediction value of Adv_{t} (known as ŷ_{i}) and actual value (y_{i}) in regression performance.
The maximum error of regression implements (Δ) calculated is approximately 134.1614 m.
In order to determine MinPD, the survey is implemented by 60 officers divided into two groups, operational officers and management officers. Officer’s experience is illustrated in Figure 5.
The conclusion computed is shown below:
The final suggested formula of BLA is shown in
The parameter of GPS error (ErrGPS) is 25.495 m adopted in the Report #86 at the William J. Hughes Technical Centre [22].
In evidence, an experienced seafarer frequently evaluates the velocity, angle of approach, kind of approach and distance between two vessels to provide the distance of avoiding action. Such distance can be understood as the radius of ATA illustrated in Figure 1.
In the fact that officers estimate the distance to come to CPA and choose a reasonable distance to take an action. However, reasonable distance (d_{i}) mentioned depends on each mariner. The survey is implemented by the questionnaires sent to 45 experienced officers and 15 masters who are Vietnamese working on board to determine d_{i}. When d_{i} is defined, TCPA value can be calculated at that time named reasonable time (t_{i} = d_{i}/V_{relative}). The equation determines t_{i} can be expressed below,
If the survey is implemented to n subjects, the reasonable time of head-on (t_{Av}_{−}_{H}), crossing (t_{AV}_{−}_{C}) and overtaking (t_{AV}_{−}_{O}) situation calculated on average can be determined by
Moreover, in this research, the reasonable time needed to determine is to make the action before OS come to F (t_{Av}_{−}_{H}) or P (t_{Av}_{−}_{C}) or A (t_{Av}_{−}_{O}) in head-on or crossing or overtaking situation, respectively. DCPA is assumed, DCPA is 0 and the angle coordinated by two vectors of TS and OS’ speed is 90° (in crossing situation). t_{Av}_{−}_{H}, t_{Av}_{−}_{C} and t_{Av}_{−}_{O} can be computed (
where D_{f}_{−}_{s}, D_{p}_{−}_{s} and D_{a}_{−}_{s} are D_{f}, D_{p} and D_{a} of TS domain in survey.
When
In head-on situation:
In crossing situation:
In overtaking situation:
The work determining the radius of “Action area” (R_{CAA}) is processed by questionnaire method sent to 45 officers and 15 masters. They are experienced mariner working on board in various shipping companies.
The assumption conditions are good weather (the effect of wind and flow is not too significant); TS is referred to a bulk carrier PANAMAX vessel, 60,000 dwt, length 210 m, DCPA = 0 and two vessels are navigating on the open sea. The question is “What distance between two vessels should be chosen for taking an avoiding action?” in four cases of approach, including:
Head-on situation, the velocity of OS and TS are both from 7.5 (kn);
Head-on situation, the velocity of OS and TS are both from 12.5 (kn);
Crossing situation, the velocity of OS and TS are both from 7.5 (kn);
Crossing situation, the velocity of OS and TS are both from 12.5 (kn).
The results of the four situations are shown in Figure 6. The survey in overtaking is not performed in this article. The final equation for determination of ATA can be shown below,
In head-on situation:
In crossing situation:
The section focus on definition of stage discrimination model, 4 stages are defined by the analysis of COLREG and a new suggestion of ship domain.
In this study, a new method of ACA will be introduced, which is a consecutive waypoint generation algorithm. CWPG algorithm is actually an effective combination between domain, track-keeping (PID) and rules of COLREG.
The CWPG algorithm makes a new route by perpetually adding subsidiary waypoint (SubWP) waypoint into the current route for avoiding TS when current route overlaps BLA. The principle of CWPG algorithm is illustrated in Figure 7.
The proposed method can be classified in deterministic approaches, within which many rules are integrated into for determining the freshly optimal route. The deterministic approach obeys a set of complexly constructed steps to generate the solution, whereas the heuristic approach only searches inside a subspace of the searching space for an approximately best solution rather than the best solution. The actions raised by CWPG algorithm is optimal turn which has the combined advantages of both approaches, including the approximately minimum cost of energy, smoothness performance and following COLREG.
The flowchart of CWPG algorithm is shown in Figure 8. Firstly, TS’s information maneuvering around OS are collected by equipment on board. If TS is inside Stage 2 determined by stage discrimination model in Section 2, TS’s collision risk will be calculated. The system compares the values of CR for identifying the most dangerous TS, such TS chosen will be prepared for the making of OS’s avoiding action. The value of CR is calculated by a fuzzy set, the inputs are values of TCPA and DCPA and output is CR (Figure 9). The fuzzy rules set is shown in Table 1.
Fuzzy set theory adopted is introduced by Hasegawa and Kouzuki [1] however, the membership functions and the range of value set are adjusted for making an evaluation with more suitable distance.
Target ship’s heading, velocity and position are collected for computing TCPA and DCPA, after that two values will be used as input variables in a fuzzy system in order to calculate the final of CR. Generally, the value of CR is set between −1 and +1 and the value less than zero means there is no CR. Additionally, the value in the range of 0 to 0.5 in head-on situation or 0 to 0.6 in crossing situation is the significant hazard level of CR.
The approaching situation discrimination can be illustrated in Figure 10.
The general principle of such algorithm is to be started when a dangerous target is identified. The avoiding actions are stopped when the state between two ships is improved satisfying the conditions for branching out the loop. When the loop is stopped, original waypoint will be added after.
Ship route planning can be categorized into two main groups, namely the deterministic and the heuristic approach. The common features of ACA system applying heuristic approach are always finding the approximately shortest path, saving energy and smoothness performance while the deterministic focus on special purpose, such as following COLREG regulations, flexibility in special approach. This research follows the deterministic approach, however, the new route generated is the nearly shortest route, saving energy and smoothness performance, a validation, therefore, is performed in the comparison between this study and a representative algorithm of heuristic approach.
For applying algorithms of heuristic approach to ACA system, a matrix waypoint is frequently constructed with a huge number of waypoints known as a graph or net involving many corners used in the researches of [17] and [18]. The representative algorithm will delete the waypoints in a dangerous area, some of the remaining waypoints in net will be used for connectivity for a possibly shortest route. The Floyd is an algorithm in the heuristic approach so it has the ability to create new paths that satisfy the criteria of saving energy, shortest route and smoothness performance. Furthermore, Floyd algorithm is better in applying for a bigger graph than other algorithms of heuristic approach. As the consequence, Floyd algorithm is chosen.
Ship motions are defined by the six degrees of freedom, including two kinds of motion linear motions (Heave, Sway, Surge) and rotation motions (Pitch, Roll, Yaw). Admittedly, only motions of the surge, sway and yaw are concerned in almost study shown in Figure 11 under two coordinate systems. Ox_{o}y_{o}z_{o} is earth-fixed coordinate and Gxyz is the body-fixed coordinate which is origin at the center of gravity.
Ship maneuverability has been typically estimated depend on numerous mathematical model by consisting various hydrodynamic forces acting on ship’s hull, rudder, propeller and other considerable external forces and moments, whereas the expression is not so simple by virtue of the existence of unsteady elements. Hence, such phrase “quasi-steady approach” is always existed, the fact that some contributions, not importance can be denied as assumptions. In last decades, many kinds of mathematical models have been introduced for evaluation of ship motion. In order to assess the movement of OS, MMG mathematical model will be applied to the simulation implement in this article.
Three-DOF formula originally introduced by MMG (Mathematical Models of Maneuvering Motion Group) which was established by the second section of the Japan Towing Tank Committee in March 1976. Three-DOF mathematical model includes of motion equations showed in
The external forces and moment can be expressed as:
X_{H}, Y_{H} and N_{H} have many kinds of polynomials by following non-dimensional polynomials of β and r′ as the total force model. The simulation of this article use this expression:
X_{P}, Y_{P} and N_{P} are expressed as the equation below:
where K_{T} is the thrust coefficient of the propeller, J is an advanced constant of propeller J.
X_{R}, Y_{R} and N_{R} are judged on interactions between hull and rudder:
F_{N} is rudder normal force:
The term “own ship” is used to refer to a modern training ship named SAE NURI such as a model whose parameters are employed to forecast the hydrodynamic coefficients. The ship’s principle particular is shown in Table 2.
In simulation or practice, tracking module is designed to maintain the desired ship heading. The disturbances creating rolling affect the course-keeping ability of such module. Moreover, if the course-keeping ability of tracking module is not significant, rolling will appear in the ship motion, even so, the influence is small. In this article, environmental disturbance factors affecting on ship are refused such as the wind, flow and wave. That absolutely does not affect the results of avoiding a collision in the same conditions in practice (good weather), in as much as a safe turning point is always calculated for tracking module toward. The avoiding plan is only failed when the influence of environmental disturbances is too adverse that tracking module is out of the function. However, in practice, officers do not use automated systems in bad situations. The area for ship collision avoidance assumptions is empty without any other obstacles rather than one which is the most dangerous TS.
The simulation scenarios are performed in 11 times, divided into two types of situation, head-on and crossing situation (Table 3). In each simulation, the value of the direction, speed and location of OS and TS is changed to ensure that the algorithm can take flexible action in various cases. Two algorithms described are CWPG and Floyd algorithm. This work will point out the algorithm, which is more effective than remaining one.
The criteria chosen to evaluate the benefit of two algorithms are Mean Integral Absolute (MIA) and the Mean Total Variation (MTV) introduced by Zhang et al. [23]. MIA and MTV estimate the changing performance of rudder angle (δ) to measure the energy cost and the smoothness of the corresponding algorithm. MIA and MTV can be computed by
where
u(t) Rudder angle for the control plan.
t and t − 1 Current sampling time and past time.
The data recorded shows that both algorithms (CWPG and Floyd) help OS pass TS in all simulations (Figure 12). One of the first things to note is that MIA value of CWPG algorithm gets wins in all simulations. CWPG proves its ability in avoiding performance with a minimum cost of energy. It is the greatly impressive result because of a huge gap compares with Floyd algorithm. The decreases of MIA value from Floyd algorithm to CWPG algorithm are 38.5%, 50%, 24.7%, 49.35% and 56.93% in first, second, third, fourth and fifth simulation, respectively.
Meanwhile, MTV data show a smaller gap between two algorithms, in such criterion CWPG wins in three simulations (first, second and fifth). The reduces of MTV value from Floyd algorithm to CWPG algorithm are 5.05%, 19.05% and 44.7% in first, second and fifth simulation, separately. Two sudden wins come from Floyd algorithm in MTV value when the simulation is implemented in third and fourth simulation, the reduces of MTV value from CWPG to Floyd algorithm are 14.73% and 16.55% in the third and fourth simulation. In the fact, although Floyd algorithm becomes a winner in MTV in the third and fourth test, however, it chooses a longer route than CWPG algorithm. Therefore, MIA values of Floyd algorithm in third and fourth tests are much higher than CWPG.
Overall, Figure 12 indicate that CWPG is proved as a better choice for application in head-on approach due to the win of almost criteria mentioned. On average, the decrease of MIA and MTV average value from Floyd algorithm to CWPG algorithm are 43.52% and 5.95%, respectively.
Similarly, 6 typical tests will be given for pointing out the general view of two algorithms. Figure 13 illustrates remarkable MIA and MTV of two algorithms.
The total recorded number of all species of CWPG algorithm in crossing simulation gives the first view of a next win. Obviously, MIA value of CWPG algorithm is frequently less than MIA recorded from Floyd algorithm. The decreases of MIA value from Floyd algorithm to CWPG algorithm are 21.74%, 47.51%, 9.07%, 41.23%, 31.67%, 55.45% in first, second, third, fourth, fifth, sixth simulation respectively. CWPG proves its ability in saving energy.
In spite of MTV, Floyd algorithm has only one win in the first simulation. In remaining simulations, MTV values of CWPG are always less than Floyd algorithm. The decrease of MTV values from Floyd algorithm to CWPG algorithm are 1.7%, 11.9%, 60.68%, 34.05%, 19.35% in second, third, fourth, fifth, sixth simulation respectively. On the whole, CWPG is also better in smoothness performance.
Overall, in crossing simulation, CWPG algorithm receives an impressive victory over the criteria requirements. In average, the decreases of MIA and MTV value from Floyd algorithm to CWPG algorithm are 34.44% and 6.09%, respectively in the whole crossing simulations. The winner in crossing situation is CWPG algorithm.
This article introduces an approximately completed system for ACA with the aim of providing the best possible assistance to officers at sea. The contributions of this article can be summarized by four issues. Firstly, four distinct stages in the entire approaching process are identified to ensure effective scale for application of ACA at sea. Secondly, the computing models for ship domain is introduced and the number and quality of objects are upgraded in the survey compared with the previous attempts [6]. Thirdly, the concept of an appropriate ACA algorithm is introduced, the new course produced for avoiding collision performance collects both important criterions, saving energy and smoothness trajectory. Finally, the article expresses the results of validation for proving the efficiency of the proposed algorithm. The average results over 11 simulation scenarios, CWPG algorithm saves 38.98% energy and its trajectory recoded smoother than Floyd algorithm, 6.02%. Further studies on stage model and route planning are yet implemented for a fulfilling system.
This research was a part of the project titled ‘Development of Ship-handling and Passenger Evacuation Support System’, funded by the Ministry of Oceans and Fisheries, Korea.
The novel ship domain and constructed parameters.
Stages of approaching situations.
The concept for calculating
Ship’s size of the survey according to length (a) and breadth (b).
Navigator’s experience in
Questionnaire results of ATA.
Principle of CWPG algorithm.
Flowchart of CWPG algorithm.
Fuzzy memberships for calculating CR.
Encounter situation discrimination model.
Coordinate system.
Comparisons of MIA (a) and MTV (b) in head-on situation.
Comparisons of MIA (a) and MTV (b) in crossing situation.
Evolved fuzzy rules set
TCPA | SAN | MEN | DAN | VDP | DAP | MEP | SAP | VSP |
---|---|---|---|---|---|---|---|---|
DCPA | ||||||||
SAN | SAN | SAN | SAN | SAP | SAP | VSP | VSP | VSP |
MEN | SAN | MEN | DAN | DAP | MEP SAP | VSP | VSP | |
DAN | SAN | MEN | DAN | VDP | DAP | MEP | SAP | VSP |
MEP | SAN | MEN | DAN | DAP | MEP | SAP | VSP | VSP |
SAP | SAN | SAN | SAN | SAP | SAP | VSP | VSP | VSP |
SAN: Safe Negative, MEN: Medium Negative, DAN: Dangerous Negative, VDP: Very Dangerous Positive, DAP: Dangerous Positive, MEP: Medium Positive, SAP: Safe Positive, VSP: Very Safe Positive.
Principle particular of the ship
Type | Training ship |
---|---|
Length overall (m) | 103 |
Length between perpendicular (m) | 94 |
Breadth (m) | 15.6 |
Draft (m) | 5.4 |
Thruster (Bow) (N) | 49,000 |
Transverse projected area (m^{2}) | 183.3 |
Lateral projected area (m^{2}) | 1053.7 |
Simulation scenarios
Head-on situation | Crossing situation |
---|---|
E-mail: namkyun.im@mmu.ac.kr
E-mail: dinhgiahuy@vimaru.edu.vn