1 Introduction

With the development of modern technology, the maritime autonomous surface ship (MASS) has become a new trend of ship development. One of the advantages of implementing MASS is its potential in improving navigational safety by reducing the influence of human errors [34]. Trajectory planning is one of the key technologies for MASS to navigate safely and reliably. The important part of trajectory planning is to avoid collision.

At present, there are many trajectory planning algorithms, such as the artificial neural network (ANN), genetic algorithm (GA), Ant Colony Optimization algorithm (ACO), artificial potential field (APF), and so on. Moreover, it has a good application effect on the unmanned ship (Tam et al) [29]. The detailed literature review is elaborated in Sect. 2.

However, since the development of MASS is still at an early age, it is reasonable to expect that there would be a transition period where conventional manned ship and MASS would co-exist in the waterways. This stage is also called the human–machine interaction stage [9]. Under such a scenario, the trajectory planning of unmanned ship should also conform to the Convention on the International Regulations for Preventing Collisions at Sea (COLREGS) in the human–machine interaction stage to avoid the possible misunderstanding of collision avoidance intentions between the encountered ships. COLREGS mandates due regard to the observance of good seamanship at all times. Good seamanship comprises skills that are specific for seafaring, and there are manuals of seamanship [12]. For the present, good seamanship can be defined as a blend of professional knowledge, professional pride, and experience-based common sense [8, 12]. Good seamanship is the basis of all rules as well as the fundamental rule of the COLREGS to fill the gaps for any missing or unclear statement [6, 41]. The major difficulties of collision avoidance were the incorporation of COLREGS and good seamanship [8]. Few studies consider both ship maneuverability, COLREGS, and good seamanship for trajectory planning or studies narrowed into a two-ship encounter situation.

In this work, we proposed a dynamic trajectory planning method for unmanned ships, which integrates COLREGS, good seamanship, and ship maneuverability. Our main contributions are as follows: (1) considering COLREGS and good seamanship into trajectory planning; and (2) integrating ship maneuverability into the Morphin search tree algorithm.

The outline of this paper is as follows: Sect. 2 presents brief literature review concerning local trajectory planning methods; Sect. 3 illustrates the research methodology for trajectory planning; Sect. 4 elaborates case study of trajectory planning using the proposed method; in Sect. 5, a discussion among the methods and the simulation is presented. Conclusions and future studies are given in Sect. 6.

2 Literature review

Compared with the path planning works in the field of robots, manipulators, vehicles on lands, there are only a limited number of studies on the ship at sea [1]. Path planning can be divided into global path planning and local trajectory planning [38]. This paper focuses on the safe navigation of ships and prefers local trajectory planning. Combined with the current theoretical research, the main local trajectory planning methods for the ship can be divided into the following categories: (1) artificial intelligence algorithm, and (2) artificial potential field method.

Artificial intelligence (AI) algorithm is used to estimate the safe and optimum trajectory to solve the problem of avoiding collisions at sea [10, 40]. It is the general term of a kind of algorithm, such as the artificial neural network (ANN), Genetic Algorithm (GA), Ant Colony Optimization Algorithm (ACO), and Evolutionary Algorithms (EA). Zeng et. al [40] also reported another attempt to compute the safe navigation trajectory in the open sea with GA. Smierzchalski and Michalewicz [23] proposed GA and EA for a ship to searching a safe trajectory. Li et al. [17] and Statheros et al. [24] summarized the applying GA and EA to maritime collision avoidance and trajectory planning of predecessors. Tsou et al. [31] present optimal methods for ship collision avoidance route planning and alerts based on GA. Szlapczynski and Szlapczynska [28] present a method that applies EA and some of the assumptions of game theory to find a near-optimal set of safe trajectories of all ships involved in an encounter. Szlapczynski [25] extended the previous research to focus on the evaluation phase of the evolutionary process and shows how fitness function is designed to compare various possible tracks as well as to assess the quality of a final solution. In addition, some approaches include trajectory optimization using genetic annealing algorithm [2] and ship collision avoidance route planning by ACO [5, 13, 30] have been tried by other researchers. With the further development of the research, Quantum-behaved Wolf Pack Algorithm (QWPA) is proposed complied to COLREGS, and then feasibility and effectiveness of which have been positively verified in laboratory conditions based on the three-degree-of-freedom ship mathematical model [18]. Meanwhile, deep learning makes ship trajectory planning more intelligent [7, 33].

The artificial potential field (APF) method is widely used for ship automatic collision avoidance [15, 19, 21, 35]. Xue et al. [35] developed a simple and practical method of automatic trajectory planning and collision avoidance based on APF. The developed APF method combined with ship domain and the target ships’ motion to ship collision avoidance [32]. Lyu and Yin [20] present a COLREGS-constrained real-time and deterministic trajectory planning method for autonomous ships or Unmanned Surface Vehicles (USV) using modified APF in complex and dynamic navigation environments. Lazarowska [14] proposed the APF method by considering COLREGS to quickly plan a deterministic collision-free trajectory in the presence of a variety of static obstacles with arbitrary shapes and multiple dynamic ships with variable headings.

Above all, the planning trajectory of the ship may cause misunderstanding of the target ship without considering COLREGS and good seamanship. In addition, the ship’s trajectory may be completed by a succession of small alterations of course and/or speed, ignoring the maneuverability of the ship, which does not meet the requirements of rule 8 of COLREGS. In the meantime, some researches consider COLREGS [13, 15, 19, 22] or ship maneuverability [9, 26, 27] to trajectory planning. In addition, there are also some methods that combine COLREGS and ship maneuverability for trajectory planning [3, 16].

There are two important points in trajectory planning, one is the algorithm of trajectory planning, and the other is the factors that need to be considered in trajectory planning. From the trajectory planning algorithm analysis, the above research through different algorithms to solve the problem of ship local trajectory planning, to a certain extent, the algorithm has been mature. But the performance of different trajectory planning algorithms is completely different. In addition to the above-mentioned algorithms, Morphin algorithm has been applied in the field of robot trajectory planning and has the advantages of small computation and high efficiency [37, 39]. Considering the factors of trajectory planning, although COLREGS and ship maneuverability are taken into account, it is not mature to consider rules, good ship skills, and maneuverability at the same time. However, there are still many research prospects for full integration of ship maneuverability, COLREGS, and good seamanship.

To further develop a local trajectory planning method that can make the search trajectory consistent with the ship’s navigation trajectory, the Morphin search tree algorithm is combined with ship maneuverability and is constrained by COLREGS and good seamanship.

3 Methodology

In dynamic trajectory planning of the unmanned ship, it is necessary to fully consider the constraints of the restrictions such as the characteristics of the maritime traffic environment, ship maneuverability, COLREGS, and good seamanship. In this paper, we propose a trajectory planning model for the unmanned ship under a multi-object environment at sea, based on a multi-layer Morphin adaptive search tree.

The process of trajectory searching in the multi-object environment is illustrated in Fig. 1. Based on the environmental and local traffic information, the own ship would design several path candidates (OA-OD) considering its own maneuverability. The inflection point in the red box indicates the stage that the ship performs a collision avoidance maneuver. The number in the red box indicates the number of course alterations in this planned trajectory. As shown in the Fig. 1, the trajectory OC changes to the left, which does not meet the constraints of COLREGS and good seamanship. The trajectory OA does not return to the original course, so it does not meet the requirements of this trajectory planning. From the perspective of COLREGS and good seamanship constraints, OB and OD are the required trajectories. Finally, the optimal trajectory can be determined according to the different optimization objectives of the trajectory evaluation function. When the evaluation function is biased towards economy, the trajectory OB is the optimal trajectory; when the evaluation function is the deviation between the planning trajectory and the original trajectory is small, the trajectory OD is the optimal trajectory.

Fig. 1
figure 1

Trajectory search in the multi-object environment

Full size image

With the integration of the COLREGS and good seamanship, the rule-compliant path (OD) can be proposed for the safe control of the unmanned ship, which is also compatible with the interpretation of other manned ships in the vicinity. To achieve such an objective, several critical components of the path planner of the unmanned ship should be included, which are as follows: (1) environment model; (2) feasible avoidance range calculation model; (3) path optimization model considering COLREGS and seamanship.

The environmental model is to extract and integrate the location, speed, size, and other information of obstacles through modern navigation equipment in the rolling window, and finally form the local obstacle information map. A rolling window is used to limit the scope of the local obstacle information map. Once the environmental obstacle map is constructed, a feasible avoidance range, which is a set of own ship trajectories that can avoid all obstacles in the rolling window, would be proposed via the velocity obstacle (VO) method [8]; Finally, planning trajectory can be determined by multi-layer Morphin adaptive search tree, and evaluated by the trajectory evaluation function. The research framework of the methodology is shown in Fig. 2.

Fig. 2
figure 2

Research framework

Full size image

4 Model design

4.1 Environment model

The environmental model is built according to the known information in the rolling window: the actual environment for the ship to perform the task is converted to the map feature information matrix, which can be stored conveniently. The construction of the environment model is divided into the following two steps: (1) determine the size of the rolling window, and (2) convert the known information in the rolling window into the environment map feature information.

The rolling window size is mainly affected by the onboard detection equipment; the calculation method is shown in the following equation:

$$W\left({p}_{ship}\left(t\right)\right)=\left\{{p}_{ship}\left(t\right) |d\left({p}_{0},{p}_{ship}\left(t\right)\right)\le {R}_{win}\right\}$$
(1)

where \({p}_{0}\) is the initial position of the ship in the current rolling window, \({p}_{ship}\left(t\right)\) is the position of the ship at t time, \(d\left({p}_{0},{p}_{ship}\left(t\right)\right)\) is the Euclidean distance between the initial ship position and the position at t time, and \({R}_{win}\) is the sensing radius of the ship onboard detection equipment.

After determining the rolling window, the environment information in the window should be processed. Based on the Electronic Chart Display Information System (ECDIS), this paper extracts static obstacle information such as wreak, aids to navigation, and other obstacles, which include the location and size of obstacles. Then, according to the ship Automatic Identification System (AIS) data, the dynamic and static information of the target ship can be extracted. According to navigation practice, the target ship is regarded as a point obstacle, islands, reefs, and shipwrecks, etc. are regarded as strip obstacles, circular obstacles, etc. [8]. Object information is shown in the following equation:

$$Object=\left[\begin{array}{ll}\begin{array}{l}\begin{array}{ll}{x}_{1}& {y}_{1}\end{array}\\ \begin{array}{cc}\dots & \dots \end{array}\\ \begin{array}{cc}{x}_{n}& {y}_{n}\end{array}\end{array}& \begin{array}{c}\begin{array}{cc}{v}_{1}& {R}_{1}\end{array}\\ \begin{array}{cc}\dots & \dots \end{array}\\ \begin{array}{cc}{v}_{n}& {R}_{N}\end{array}\end{array}\end{array}\right]$$
(2)

where \(x\) and \(y\) are the abscissa and ordinate of the object’s position; \(v\) is the speed of objects; \(R\) is the size of obstacles.

4.2 Feasible avoidance range calculation model

Feasible avoidance range refers to sets of own ship trajectories that the ship can avoid all obstacles in the rolling window. According to the 8th rule of the COLREGS, under most circumstances, alteration, of course, is the most effective action to avoid a close-quarters situation, especially at the open sea when ample sea room is available. Hence, the output of this model is a feasible course alteration range.

The proposed feasible avoidance range calculation model is to calculate a feasible course alteration range based on the velocity obstacle (VO) method. First, the coordinate system is established, and the location of all environment data will be transformed; second, the ship motion model is established to simulate the motion of the ship after taking avoidance action. Finally, according to the VO algorithm, we can judge whether the ship avoidance action is feasible.

4.2.1 Ship domain and coordinate system

This study adopts a center offset ellipse shape for the Own Ship (OS) domain, as shown in Fig. 3. In this paper, two coordinate systems are introduced, which are ship following coordinate system o-x–y and geodetic coordinate system O-X–Y. The O-X–Y coordinate system was fixed to the Earth, the X-axis pointing toward the East, the Y-axis to North. The o-x–y coordinate system was fixed to the OS, the x-axis pointing toward the starboard, the y-axis to bow.

Fig. 3
figure 3

Ship domain model and coordinate system

Full size image

The real ship being fixed by a distance and an angle (199° relative to real ship’s bow, 19° relative to real ship’s stern in Fig. 3.) from the phantom ship (Davis et.al) [4]. The relation of the phantom ship and the real ship can be expressed in the following equation based on O-X–Y coordinate system:

$$\left\{\begin{array}{c}{X}_{o}^{^{\prime}}={X}_{o}-{R}_{d}\mathrm{cos}\left(C+{19}^{^\circ }\right)/4\\ {Y}_{o}^{^{\prime}}={Y}_{o}-{R}_{d}\mathrm{sin}\left(C+{19}^{^\circ }\right)/4\\ {R}_{d}=ab/\sqrt{{\left(a\mathrm{sin}{199}^{^\circ }\right)}^{2}+{\left(b\mathrm{cos}{199}^{^\circ }\right)}^{2}}\end{array}\right.$$
(3)

where \(\left({X}_{o},{Y}_{o}\right)\) denotes the coordinates of the real OS, and \(({X}_{o}^{^{\prime}},{Y}_{o}^{^{\prime}})\) is the coordinates of the phantom ship. The variables a and b are the lengths of the semi-major and semi-minor axes of the ellipse, respectively. \(C\) is the true course of the OS. \({R}_{d}\) is the distance from the position of the phantom ship to the border of the ellipse along the direction of the real OS.

All obstacle coordinates are based on O-X–Y coordinate system. The ship domain is an eccentric ellipse. To facilitate the calculation, all subsequent calculations are carried out in the o-x–y coordinate system. The obstacle coordinates are transformed from the O-X–Y coordinate system to the o-x–y coordinate system, and the conversion formula is shown in the following equation:

$$\left\{\begin{array}{l}{x}_{r}=\left({X}_{R}-{X}_{o}^{^{\prime}}\right)\mathrm{cos}C-\left({Y}_{R}-{Y}_{o}^{^{\prime}}\right)\mathrm{sin}C\\ {y}_{r}=\left({X}_{R}-{X}_{o}^{^{\prime}}\right)\mathrm{sin}C+\left({Y}_{R}-{Y}_{o}^{^{\prime}}\right)\mathrm{cos}C\end{array}\right.$$
(4)

where \(({\mathrm{x}}_{\mathrm{r}},{\mathrm{y}}_{\mathrm{r}})\) is the objects coordinates in the o-x–y ship-fixed coordinate system; \(({\mathrm{X}}_{\mathrm{R}}, {\mathrm{Y}}_{\mathrm{R}})\) is the coordinates of the object in the O-X–Y Earth-fixed coordinate system.

4.2.2 Ship motion model

OS will experience a non-linear motion process (see Fig. 4) during course alteration. Therefore, it is necessary to establish a ship motion model to describe the non-linear motion. In this study, three degrees of freedom of ship motion (surge, sway, and yaw) are modeled to predict and simulate the ship motion based on MMG:

Fig. 4
figure 4

Infeasible course alteration range

Full size image
$$\left\{\begin{array}{l}\left(m+{m}_{x}\right)\dot{u}-\left(m+{m}_{y}\right)vr={X}_{H}+{X}_{P}+{X}_{R}\\ \left(m+{m}_{y}\right)\dot{v}-\left(m+{m}_{x}\right)ur={Y}_{H}+{Y}_{P}+{Y}_{R}\\ \left({I}_{ZZ}+{J}_{ZZ}\right)\dot{r}={N}_{H}+{N}_{P}+{N}_{R}\end{array}\right.$$
(5)

where \(m\), \({m}_{x}\), \({m}_{y}\), \({I}_{ZZ}\) and \({J}_{ZZ}\) are mass of the ship, added mass in x and y directions, inertia moment and additional inertia moment, respectively; subscript H, P, R are bare hull, propeller, and rudder, respectively; u, v, and r denote surge, sway velocity and yaw rate, respectively; X, Y, N are the external forces and moments in different directions, respectively.

4.2.3 Feasible course alteration range algorithm

In this paper, the non-linear VO method is used to calculate the feasible avoidance range. After the above coordinate transforming and ship motion modeling, the next step is to use the VO method to solve the feasible avoidance range. According to the ship motion model, judge whether the velocity of OS belongs to the velocity obstacle area when the initial course needs to be changed to an angle and stabilized at this angle. If not, it belongs to the feasible avoidance range. For instance, when the redirection interval is within \([{\alpha }_{1},\left.{\alpha }_{2}\right]\), it belongs to the infeasible course alteration range; otherwise, it belongs to the feasible course alteration range.

4.3 Multi-layer Morphin adaptive search tree

After solving the feasible avoidance range, the next step is to search the path within the range of feasible avoidance range, which satisfies the COLREGS and seamanship. The Morphin algorithm would be generating feasible path candidates that are in line with the ship’s maneuverability. In this section, multi-layer Morphin adaptive search tree is applied as the methodological framework.

Morphin algorithm is a local trajectory planning algorithm based on ground analysis [11], which is also a local obstacle avoidance algorithm based on grid local terrain. This algorithm generates a set of discrete navigating trajectories in the movement direction of a ship based on ship maneuverability. The search tree has two important parameters: the number of search layers and the length of the search arcs. The number of search layers means the search times of a trajectory, and the search arc length means the trajectory length of a search. Normally such parameters have to be pre-set arbitrarily or based on the iteration of the experiment. In our work, we improved the algorithm to realize the adaptive number of search layers and the length of the search arc.

4.3.1 Adaptive number of search tree layers

When the multi-layer Morphin search tree is used for dynamic trajectory planning, the more layers of the search tree, the more flexible the generated trajectory is. The time cost of constructing and evaluating the search arc, however, is inversely proportional to the number of layers of the search tree. According to the previous research [37], the search effect is relatively good when the number of search tree layers is within three layers. At the same time, the ship shall follow as few maneuvers as possible in the process of collision avoidance. Too much maneuvering may not only damage the ship’s power and control system, and but also increases the difficulty to target ship (TS) to understand the collision avoidance intention of own ship (OS) to achieve the coordinated collision avoidance of the two ships under such a scenario. Therefore, the algorithm will adaptively adopt three layers or two layers of search trees for trajectory planning in the actual search process to improve the utilization rate of feasible space and the flexibility of search.

After setting the range of ship redirection angle and the interval of search arc, the range of search arc in a single execution cycle is determined, so as to the number of search arc generated by each node.

4.3.2 Search arc adaption

The multi-layer Morphin search tree is constructed in the rolling window. The radius of the rolling window limits the maximum search distance of the search arc. The ship motion control system limits the minimum search distance of the search arc. That is, the minimum search distance for each search is the ship’s motion distance when the course is stable after the ship changes a certain angle. Moreover, the maximum search distance is not greater than the radius of the rolling window. Therefore, the search arc length meets the following requirements:

$$ \begin{array}{*{20}l} {\left\{ {\begin{array}{*{20}l} {l_{arc}^{i} \ge d_{e} } \hfill \\ {l_{arc}^{1} + l_{arc}^{2} + \cdots + l_{arc}^{i} \le R_{win} } \hfill \\ \end{array} } \right.} & {i = 1,2,3 \cdots } \\ \end{array} $$
(6)

where \(l_{arc}^{i}\) is the length of the search arc of each layer; \(d_{e}\) is the ship motion distance when the course is stable after the ship changes a certain angle.

4.4 Trajectory evaluation

Trajectory evaluation is based on the evaluation function to evaluate every trajectory which conforms to the COLREGS, good seamanship, and ship maneuverability. Therefore, the key point of trajectory evaluation is the establishment of a trajectory evaluation function based on certain optimization criteria. According to navigation practice, the avoidance urgency and the economy of trajectory are determined as the trajectory evaluation indexes [38]. By weighting the urgency and economic indicators of planning trajectory, it is the trajectory evaluation function. The urgency is expressed by the collision risk of the waypoint \(({T}_{{u}_{tT}})\). The economy is evaluated by the combination of ship maneuvering amplitude \(({T}_{a})\), trajectory execution time \(({T}_{t})\) and trajectory yaw \({(T}_{Disv})\).

4.4.1 Urgency index

The collision risk index is a good indicator to measure the urgency of risk between two ships. In some researches, the collision risk index is divided into space collision risk and time collision risk [36]. This paper adopts this definition to express the urgency of waypoint with collision risk. If both ships maintain their present speed and course, the potential risk of collision exists when TS enters the ship domain of the OS regardless of the present distance. In other words, the risk of space collision between two ships reaches 1 in this situation. In addition, the time collision risk can represent the urgency of collision avoidance. The ship urgency index \(({T}_{{u}_{tT}})\) can be obtained as follows [36]:

$${T}_{{u}_{tT}}=\left\{\begin{array}{ll}1& {t}_{CS}\le 0\\ {\left(1-\frac{{t}_{CS}}{{t}_{0}}\right)}^{3.03}& 0<{t}_{CS}<{t}_{0}\\ 0& {t}_{CS}\ge {t}_{0}\end{array}\right.$$
(7)

where \({t}_{CS}\) is the time from the current time of the ship to the latest rudder application point; \({t}_{0}\) is the time from the first time-in-point of collision risk to the latest rudder application point.

4.4.2 Economy index

On the premise of ensuring the safety of the planned trajectory, the economy of the planned dynamic avoidance trajectory can be improved through the following three aspects: (1) controlling the number and amplitude of ship maneuvers; (2) shortening the execution time of the planned trajectory, i.e., shortening the avoidance distance; (3) reducing the deviation range from the original route when restoring the original course.

Therefore, in the economic evaluation, there are three indexes as follows: (1) the evaluation indexes of ship maneuvering amplitude \({T}_{a}\), trajectory execution time \({T}_{t}\) and trajectory yaw \({T}_{Disv}\). \({T}_{a}\) is the amplitude of ship maneuvers, \({T}_{t}\) is the time consumed by the planned trajectory, and \({T}_{Disv}\) is shown in the following equation:

$$ T_{Disv} = Disv = \left| {\sqrt {\left( {x_{f} - x_{0} } \right)^{2} + \left( {y_{f} - y_{0} } \right)^{2} } * \sin \left( {TB - TC} \right)} \right| $$
(8)

where \(\left( {x_{f} ,y_{f} } \right)\) is the position when the ship recovers the original heading, \(\left( {x_{0} ,y_{0} } \right)\) is the initial position coordinate when the ship takes avoidance action, TB is the true bearing between two positions, and TC is the true course in the position \(\left( {x_{0} ,y_{0} } \right)\).

4.4.3 Comprehensive evaluation function

The search trajectory in the local environment information map is evaluated by the comprehensive evaluation function, and the urgency of waypoint and the trajectory economy are the main indexes of trajectory evaluation.

Since these evaluation indexes are not in the same dimension or order of magnitude, such as angle, length, and time, the indexes should be standardized before comprehensive evaluation. To retain the potential weight relationship reflected by the standard deviation in the original data, the min–max standardization method [38] is used in this paper:

$$ x^{^{\prime}} = \frac{{x - x_{\min } }}{{x_{\max } - x_{\min } }} $$
(9)

where \({x}^{^{\prime}}\) represents the standardization process of the original data. \({x}_{min}\) is the minimum value of the indicator, and \({x}_{max}\) is the maximum value of the indicator.

After standardizing the data of indexes, the comprehensive evaluation indexes of \({T}_{{u}_{tT}}^{^{\prime}}\) and \({T}_{a}^{^{\prime}}\) are calculated as follows:

$$ T^{^{\prime}} = \frac{1}{2}\left( {\frac{1}{n}\sum\limits_{i = 1}^{n} {x_{i}^{^{\prime}} } + \max (x_{i}^{^{\prime}} )} \right) $$
(10)

where \({x}_{i}^{^{\prime}}\) is a standardized indicator value.

Finally, each index is weighted to establish a comprehensive evaluation function, and the evaluation value of each search trajectory is calculated as the following equation:

$$ E = c_{1} \times T_{{u_{tT} }}^{^{\prime}} + c_{2} \times T_{a}^{^{\prime}} + c_{3} \times T_{t}^{^{\prime}} + c_{4} \times T_{Dis}^{^{\prime}} $$
(11)

where the variables \({c}_{1}\),\({c}_{2}\),\({c}_{3}\), and \({c}_{4}\) are the parameter weights.

The smaller the E value is, the better the path. The variables \({c}_{1},{c}_{2}\),\({c}_{3}\), and \({c}_{4}\) can be set according to the optimization objectives. If the \({c}_{1}\) weight is increased, the optimal trajectory is inclined to the trajectory with weak urgency; if the \({c}_{2}\),\({c}_{3}\), and \({c}_{4}\) weights are increased, the planned trajectory is inclined to the economy.

4.5 Algorithm design

According to the research framework of Chapter 3, first, we build an environmental model. Second, according to the environmental information, the feasible avoidance range can be calculated. Finally, we search and evaluate the trajectory within the feasible avoidance range and output the optimal trajectory. The specific calculation process is as follows:

  • Step 1. Determine the rolling window based on the initial position of the ship and built environment model to obtain a local obstacle information map;

  • Step 2. Calculate the feasible avoidance range can be calculated by the model based on local obstacle information map;

  • Step 3. Start the first layer (avoidance) trajectory search, and the search starting point is the initial location of the OS.

  • Step 4. The end of the first search trajectory is taken as the starting position of the second search tree;

  • Step 5. Determine the rolling window based on the starting position of the second search tree and built environment model to obtain a local obstacle information map;

  • Step 6. Calculate the feasible avoidance range can be calculated by the model based on local obstacle information map;

  • Step 7. Start the second layer (avoidance or resume navigation) trajectory search, if the second level search has a resuming course, the resuming trajectory search is preferred;

  • Step 8. The end of the second search trajectory is taken as the starting position of the third search tree;

  • Step 9. Determine the rolling window based on the starting position of the third search tree and built environment model to obtain a local obstacle information map;

  • Step 10. Calculate the feasible avoidance range can be calculated by the model based on local obstacle information map;

  • Step 11. Start the third layer (resume navigation) trajectory search.

  • Step 12. If the third layer has a resume navigation trajectory, output trajectory; otherwise, adjust the second search trajectory length and go to step 9.

  • Step 13. Evaluate all output trajectories and select the optimal trajectory, end the algorithm.

5 Case study

To demonstrate and test the proposed trajectory planning model, two simulations are conducted. In practical application, different ships will adjust the weight of the trajectory evaluation function according to the needs of trajectory planning. In this simulation, to make the results representative, the weight of the evaluation function index is set to the same.

5.1 Setup

In this simulation, a 3DOF MMG model of a Panamax bulk carrier, MV HUAYANG DREAM, is used [8]. The related parameters are shown in Table 1.

Table 1 Parameter settings of simulation
Full size table

5.1.1 (1) Setting of OS

The initial motion parameters of OS are uniformly set as follows: position coordinate is (0,0) n mile in O-X–Y coordinate system with heading 000˚ at speed is 13 kn; possible course alteration range is \(\left[-9{0}^{\circ },9{0}^{\circ }\right]\); the long axis of the own ship domain is 8 times the length, the short axis is 4 times the length, and the eccentricity angle of the elliptical ship domain is 199°.

5.1.2 (2) Setting of objects

The objective of the simulation is to verify the effectiveness and applicability of the proposed model under the various encounter scenarios. To achieve this, in the simulation, we have set up six target ships and three static objects to simulate the classic encounter situations and environment. The object information is shown in Table 2.

Table 2 Dynamic and static object information
Full size table

5.2 Feasible avoidance range

According to the model in Sect. 4.2, the feasible avoidance ranges at different timesteps are calculated. The results are shown in Fig. 5.

Fig. 5
figure 5

Feasible avoidance range in multi-object environment

Full size image

As shown in Fig. 5, the green line is the feasible trajectory of the OS, and its range is the feasible avoidance interval; the black line is the infeasible trajectory of the ship, and its range is the infeasible avoidance range. Under the influence of the space barrier of each object, the range of feasible avoidance space corresponding to the ship at different times is different, and the specific values are shown in Table 3. In 0 s and 282 s, there is collision risk with obstacles. According to the COLREGS and good seamanship, the ship should turn to starboard, and the maximum change course shall not exceed 90°. According to rule 8 in COLREGS, any alteration of course and/or speed to avoid collision shall, if the circumstances of the case admit, be large enough to be readily apparent to another vessel observing visually or by radar; a succession of small alterations of course and/or speed should be avoided. Hence, the minimum change angle should be greater than 5°. At 1466 s and 2110 s, there is no collision risk between the ship and the obstacles, so the ship can take action at will.

Table 3 Feasible avoidance range
Full size table

5.3 Results of dynamic trajectory planning

According to the feasible avoidance range calculated in Sect. 5.2, trajectory search will be carried out in this range. The optimal dynamic trajectory planning of OS is shown in Fig. 6, and the information of each waypoint is shown in Table 4

Fig. 6
figure 6

Dynamic trajectory planning simulation result

Full size image
Table 4 Critical way point of optimal trajectory
Full size table

In Fig. 6, the green trajectory is the optimal dynamic collision avoidance trajectory in the local environment, and the solid blue line is the motion trajectory of target ships. Figure 6 can clearly show the relative position of the OS and other objects.

According to Table 4, the navigation time of the planned trajectory is 2394 s, the total alters course amplitude of ship maneuvers is 60˚, the yaw distance is 32 m when the original heading is restored, and the collision risk index is 0. The planned route can be divided into four stages: the first stage is from the initial position of own ship to the waypoint 1, the second stage is from the waypoint 1 to the waypoint 2, the third stage is from the waypoint 2 to the waypoint 3, and the fourth stage is from the waypoint 3 to the recovery of the original heading point.

Under the premise of ensuring the navigation safety, the planned trajectory has a small amplitude of ship maneuvers at each waypoint, and avoidance action and time of taking avoidance meet the requirements of COLREGS and good seamanship. In addition, the execution time of the planned trajectory and yaw distance is small, which ensures the economy of the planned trajectory.

6 Discussion

6.1 Comparison with the APF algorithm

To verify the effectiveness of the proposed model, the model will be compared with the traditional APF model. In addition, the planning trajectory results of the two models are shown in Fig. 7. The green line is the planning trajectory by the proposed model, and the red line is the planning trajectory by the APF model.

Fig. 7
figure 7

Planning trajectory results of two models

Full size image

According to the meeting situation of the ship’s initial position and the navigation practice, the ship shall turn to starboard. The trajectory proposed in this model can pass all objects after the first altering course. Therefore, in the second altering course, the ship resumes navigation. Therefore, the trajectory proposed by this method is in line with COLREGS and good seamanship. Planning trajectory by APF method can pass all objects through three turns, and finally resume navigation. It is also acceptable from the perspective of navigation practice. From the perspective of the economy, the planned trajectory of the APF model is longer than that of the proposed model. The difference in consumption time between them is 596 s (Table 5). Therefore, the planning trajectory planned by the proposed model is more economical. From the number of waypoints, the difference between the two is 1, which is not very big. From the point of view of rationality, there are unsmooth waypoints in the planning trajectory of the APF model, and the ship cannot sail along the planning trajectory strictly, because the planning trajectory of the APF model does not consider the maneuverability of the ship; while another planning trajectory integrates the ship maneuverability in Morphin search three algorithms, and the search trajectory is consistent with the trajectory of ship actual navigation. Therefore, the planning trajectory by the proposed model is more practical. In conclusion, the planning trajectory of the proposed model is more in line with navigation practice than that of the APF model.

Table 5 Planning trajectory parameter comparison
Full size table

6.2 Advantages and limitations of the model

The traditional method of local trajectory planning for the ship is often to search a trajectory that does not collide with obstacles. But these methods are not suitable for the unmanned ship in the human–machine interaction stage. This is due to the following characteristics of the ship as the main collision avoidance body: (1) the ship has the characteristics of large inertia, and its course of change has obvious time delay effect; (2) the motion control has the characteristics of nonholonomic constraint and underdrive, and the course of change is non-linear; (3) the avoidance action shall conform to the practice of collision avoidance at sea, requirements of COLREGS and good seamanship.

The proposed model in this paper not only considers the constraint of ship maneuverability, but also combines COLREGS and good seamanship based on multi-layer Morphin adaptive search tree model. In addition, the model can be applied to search trajectory in the multi-object environment. According to the simulation results, the collision avoidance trajectory provided by this model is in line with the navigation practice, and it is a safe, economical, and operable collision avoidance trajectory. In addition, OS actions will not cause misunderstanding of TSs. The simulation results verify the validity and applicability of the dynamic trajectory planning model in multi-object dynamic trajectory planning.

This method offers a new perspective to trajectory planning, which not only can be used for collision avoidance for the manned or unmanned ship but also can be applied to vessel traffic management.

For manned ships, the model can provide a local planning trajectory to Officers on Watch (OOW), and OOW can avoid collision and resume navigation according to the trajectory provided.

For unmanned ships, the model can provide a local planning trajectory to unmanned ships. In addition, unmanned ships can navigate directly along the trajectory provided. When the unmanned ship and the manned ship co-exist, the risk measurement of the unmanned ship can be harmonized by the presented method and will not cause misunderstanding between them.

From the perspective of traffic management, the model can also be used in Vessel Traffic Services (VTS). The method can be integrated into the VTS and guide any checked ship for safe navigation.

However, the current method is suitable/applicable for ships navigating in open waters since the consideration of alteration of course as the only collision avoidance maneuver. With the extension on the collision avoidance maneuver, such as change of speed, the proposed model is promising is also implementing in a complicated environment. Then, the ship motion control model in this model does not consider factors such as wind, wave, and current. In future research, the determination of index weight has certain subjectivity in the trajectory evaluation function. Further research can reduce the impact of human factors and find a group of index weights that can be recognized by the public.

7 Conclusion

Trajectory planning is an important part of MASS to navigate safely and reliably. At present, there are many methods of trajectory planning. However, the dynamic trajectory planning for the unmanned ship is a complex problem of trajectory search and optimization in the context of co-existing manned and unmanned ships. To achieve safe navigation for MASS, the trajectory planning algorithm that can integrate COLREGS and good seamanship, maneuverability would be of significant value for the development of MASS. To achieve this goal, this paper uses a Morphin adaptive search tree algorithm to planning trajectory, which fully considers the influence of ship maneuverability, COLREGS, and good seamanship to restrain the length and direction of the search tree.

A case study is set up in this paper. The results show that the ship can avoid obstacles and resume navigation through three maneuvers. The planned trajectory meets the requirements of COLREGS and good seamanship. This paper also set up a comparative experiment with the traditional APF model, which shows that the trajectory of the proposed model is shorter and smoother.

The main contributions of this paper are as follows:

(1) It is suitable for dynamic trajectory planning in a multi-objective environment;

(2) Ship maneuverability, COLREGS, and good seamanship are considered in the path planning process;

(3) Applicability and potential of the method are verified via case study and comparison with other models;

(4) Morphin search tree-based trajectory planning method is proposed;

(5) For the co-existence of the unmanned and manned ship, harmonized path planning is essential.

This method has more application potential and can ensure the safe navigation of ships, even the traffic safety of the whole water area. It is suitable for the unmanned ship, especially in the co-existence environment of the unmanned ship and manned ship. When the model is used on the manned ship, the crew can be provided with the position of the waypoint and the course alteration amplitude; when the model is used on the unmanned ship, the planned trajectory can be input and executed through the automatic control system on the unmanned ship. When the model is applied to the environment with only unmanned ships, it needs to be modified according to the collision avoidance rules of unmanned ships at that time.

Future research should focus on the following aspects. First, the accuracy of the ship motion control model directly affects the accuracy of avoidance trajectory planning, so it can further improve the accuracy of the ship control model. Second, the influence of the environment (such as wind, wave, and current) can be added to the ship’s motion model. Third, the impact of human factors on the multi-layer Morphin adaptive search tree model can be reduced.