Innovative Optimal Control Path Planning for PMCU in Cruise Ship Construction: A Kinematic and Obstacle Avoidance Model

Abstract

In cruise ship manufacturing, it is common practice for prefabricated modular cabin units (PMCU) to be assembled in the workshop and transported to a designated installation location on board the ship. This paper proposed a Radau pseudospectral method based on a probabilistic roadmap (PRM) for PMCU path planning in complex deck environments. Firstly, a kinematic model is constructed, and the continuous-time optimal control path planning problem is established. Among them, an area-based obstacle avoidance constraint is applied to the approach. Then, the continuous-time optimal control problem is discretized into a nonlinear programming (NLP) problem using the orthogonal collocation method. For the initial value-sensitive NLP problem solving, a strategy using PRM combined with a heuristic rule is used to obtain a high-quality initial guess. Finally, experiments under two operating scenarios of PMCU pushing demonstrate that the method is capable of generating a better path while ensuring that the whole process is collision-free. The results show that the algorithm proposed in this paper can effectively solve the PMCU pushing path planning problem in the complex deck environment, and the path considering kinematic characteristics can be used for cabin installation, which has strong operability and applicability.

1. Introduction

The construction of large cruise ships involves a huge amount of work, and the requirements for on-time delivery are extremely strict. One of the difficulties of building cruise ships compared to ordinary ships is the large amount of cabin construction work [1]. To overcome the shortcomings, such as crossover of cabin installation processes, harsh construction environment on board, crowded workforce, and poor safety management [2,3], prefabricated manufactured modular cabin unit (PMCU) technology has been adopted by most cruise ship manufacturers. Unlike the traditional cabin building process, the PMCU assembly process is transferred to the workshop [4]. The assembled PMCUs are transported to the target locations for installation by workers on deck using specified devices, as shown in Figure 1 [5,6]. Usually, before the cabin pushing operation begins, workers will make a preliminary design of the route based on the drawings. However, in the complex deck construction environment, the initial design route could not fully consider all the details of the cabin pushing process. For the complex construction environment on deck, reasonable path planning can effectively improve the efficiency of the PMCU pushing. However, the lack of detailed path planning now makes it difficult for PMCUs to reach the target location smoothly, as spatial blocking and collisions often occur, which have a great impact on continuous production operations. Therefore, it is important to study the path planning problem of the cruise ship PMCU pushing operation process to ensure that the PMCU can reach the designated installation position on deck smoothly and support the continuous production of PMCU pushing. Further, it also provides support for the future application of intelligent transportation equipment in the installation process of PMCUs.

Path planning is a prerequisite for cabin pushing operations to reach the target position and perform the installation, which is to find a collision-free path from the starting point to the target point in the environment with obstacles according to some evaluation criteria [7]. The existing path planning methods primarily include: 1. Heuristic rule-based graph search algorithms, such as the Dijkstra algorithm [8] and A* algorithm [9,10,11]; 2. Probability-based path planning methods, such as the Rapidly-exploring Random Tree algorithm (RRT) [12,13], Optimal Rapidly-exploring Random Tree algorithm (RRT*) [14,15], and Probabilistic Roadmap Method (PRM) [16]; 3. Algorithms based on the assumed gravitational field, such as the Artificial Potential Field method (APF) [17,18]; 4. Meta-heuristic algorithms, such as the Grey Wolf Optimization algorithm (GWO) [19,20], Particle Swarm Optimization algorithm (PSO) [21,22], etc.; 5. Path planning algorithm based on reinforcement learning (RL) [23,24,25]. Most of the above algorithms usually treat the object as a point, considering only the position and ignoring the pose and kinematic constraints during the movement. The calculated paths are usually focused on the shortest path length and cannot be used directly for mobile execution, requiring post-trajectory optimization. The path planning method can satisfy the collision-free constraint of PMCU geometric center, but it cannot guarantee that the outer contour also satisfies the collision-free constraint. Therefore, regarding PMCUs as a point and ignoring their external contour, the algorithm is obviously unable to support the obstacle avoidance constraints in the process of cabin pushing. Also, the trajectory optimized according to the planned path cannot fully satisfy the actual kinematic constraints. Some of the improvement methods that consider the outer contour collision are mainly two methods; one is the obstacle expansion method [26] and the other is the spatial corridor method [27], which are applicable to the scenarios that have a large passable space. However, in the prefabricated cabin pushing process, the passable space is already small, using the obstacle expansion method will lead to the original passable path which cannot be passed, and the spatial corridor method cannot fully describe the attitude; the planned path is likely to be impassable. Therefore, the above conventional methods cannot be applied to the path planning of PMCU pushing. In order to take the external contour collision constraints and kinematic constraints into account in path planning, we use optimal control techniques to describe the PMCU path planning problem.

Optimal control techniques describe the path planning problem and constraints as a mathematical model to obtain a path that satisfies the state and control constraints and meets the corresponding performance indexes in continuous time [28]. The method has achieved applications in the field of path planning for intelligent robot motion [29], autonomous driving [30], UAV [31], USV [32], and carrier aircraft routing [26,33]. Generally, it is difficult to obtain the optimal solution of the optimal control problem [34]. The common methods for solving continuous-time optimal control with constraints are the direct method and the indirect method [35]. The indirect method is usually used to determine the optimal solution indirectly by using the necessary condition for obtaining the extreme value combined with the sufficiency condition. The indirect method mainly includes Pontryagin’s maximum principle as well as the variational method. Although the indirect method has relatively high accuracy, it is computationally inefficient and difficult to converge when solving complex problems [36,37]. In contrast, the direct method has stronger applicability by discretizing the time variables of the continuous optimal control problem and then transforming the NLP problem for solving. Among many methods, the pseudospectral method has been widely used in the field of path planning and trajectory optimization [38,39,40]. The method uses a global polynomial function as the basis function to interpolate the control and state over a series of discrete configuration points to approximate them, and then satisfies the path constraints and boundary conditions at each collocation point and solves for the cost function. Typically, the optimal solution obtained by this method is close to the analytical solution of the optimal control problem. Chu et al. [41] designed a vehicle fast steering obstacle avoidance planning method based on the pseudospectral method to solve the optimal control problem of intelligent vehicle obstacle avoidance, which takes obstacle avoidance time as the optimal control objective. Yazdani et al. [42] used the adaptive pseudospectral method to realize the obstacle avoidance of AUV docking operations by considering the dynamic interference factors in the AUV motion environment. Li et al. [43] proposed a pseudospectral hair-based UAV cluster path planning method for the cooperative flight path planning problem of multiple UAVs and realized the optimization of multiple performance targets for a UAV cluster flight. However, most of the obstacle collision constraints considered in the above study can be summarized as center distance constraints, which are more applicable to circular, cylindrical, or spherical obstacles but are not applicable in the cruise ship deck space with a complex multi-obstacle environment. However, most obstacles in the process of PMCU pushing are rectangular in shape. In addition, the pseudospectral method is sensitive to the initial value. In the complex deck environment of PMCU pushing, the low-quality initial value will greatly affect the path accessibility. Therefore, the existing method cannot be directly applied to the solution of the PMCU pushing path planning problem, in fact.

The common pseudospectral methods can be further classified into the Chebyshev pseudospectral method (CPM) [44], Legendre pseudospectral method (LPM) [45], Gauss pseudospectral method (GPM) [46], and Radau pseudospectral method (RPM) [40], depending on the collation points picking method. Among them, RPM satisfies the principle of co-state mapping, and the approximation accuracy and convergence speed are better than other pseudospectral methods. To achieve rational planning of PMCU paths while satisfying kinematic and dynamical constraints as well as known global path information, this paper novelty proposes an RPM path planning method based on the probabilistic roadmap and heuristic rule (PH-RPM), which can be used for the path planning of cabin pushing operation process in the complex deck environment. The proposed PH-RPM uses probabilistic path diagrams to construct passable space and designs a path-pruning heuristic rule with reverse search. The combination of the two methods generates high-quality passable paths as initial solutions and inputs them into RPM for solving. In addition, in the process of RPM solving, the determination method based on geometric area constraints is applied to convert obstacle avoidance constraints into process constraints so as to avoid the introduction of 0–1 decision variables affecting the solution.

The remainder of this paper is organized as follows: The PMCU pushing path planning model considering dynamics constraints, state and control constraints, and process obstacle constraints is constructed in Section 2. Section 3 proposes an improved RPM algorithm to solve the optimal control problem, discretizes the continuous optimal control problem into an NLP problem to solve, and designs an initial solution generation strategy based on PRM and the heuristic rule. Section 4 designs simulation experiments based on cruise ship PMCU pushing operation environment to verify the applicability and effectiveness of the algorithm proposed in this paper. Finally, the conclusions of this paper are summarized in Section 5.

2. Optimal Control Model for PMCU Path Planning

In order to solve the PMCU pushing path planning problem using optimal control techniques, the path planning problem of PMCU pushing must be modeled. This section first introduces the basis of optimal control and then gives a specific description of the PMCU path planning optimal control model.

2.1. Optimal Control Model

The PMCU path planning problem refers to finding a path between a start state and an end state that meets the constraints of the transport process. Typically, the constraints involved in this problem are time-dependent. To provide a complete and direct description of the PMCU path planning problem, we use optimal control for modeling.

The optimal control model can be described as follows: for a controlled system, finding the optimal change of control variables to minimize the optimization objective following the state of the system while satisfying the constraints. Generally, for a common optimal control problem, it consists of the following parts:

$$J=\mathsf{\Psi }\left(x\left(t_0\right),t_0,x\left(t_f\right),t_f\right)+{\int }_0^{t_f}L(x\left(t\right),u\left(t\right),t)dt$$

(1)

$$\dot{x}\left(t\right)=f\left(x\left(t\right),u\left(t\right),t\right),t\in \left[t_0, t_f\right]$$

(2)

$$\Phi \left(x\left(t_0\right),t_0,x\left(t_f\right),t_f\right)=0$$

(3)

$$h (x\left(t\right),u\left(t\right),t)\le 0$$

(4)

Equations (1)–(4) represent a common optimal control problem, where $x\left(t\right)$ denotes the state variables, $u\left(t\right)$ denotes the control variables, $t_0$ denotes the initial time, and $t_f$ denotes the terminal time. Equation (1) represents the optimization objective of the optimal control problem, which usually consists of two parts: system terminal state objective and system process objectives, respectively. Equation (2) represents the differential equation constraint of the controlled system, describing the change of state variables and control variables of the controlled system. Equation (3) shows the boundary conditions of the controlled system, which are used to describe the range of states at a point in time within the control time. Equation (4) represents the path constraints, indicating the constraints imposed on the state and control of the system throughout the controlled time.

We can completely define an optimal control problem by Equations (1)–(4). This means that when we model the optimal control of the PMCU path planning problem, we need to define Equations (1)–(4) separately.

In general path planning problems, the optimization objective of path planning methods is usually the shortest moving path. However, in actual production, the time of the cabin pushing process is a key factor affecting the installation of PMCU, and the shortest path does not necessarily meet the requirements of optimal production efficiency. So, this paper considers using the cabin pushing operation time as the optimization objective, which is:

$$J={\int }_{t_0}^{t_f}dt=t_f$$

(5)

Equation (5) represents the optimization objective function, $t_0$ is the starting time and $t_0=0, t_f$ is the required time for cabin pushing to the target, and $J$ represents the optimization objective. Compared with Equation (1), we do not require the optimization of the terminal state of PMCU path planning, so we only consider the process objective to minimize the terminal time to achieve maximum efficiency.

The differential equation constraints of the PMCU path planning optimal control model correspond to its kinematic model. The boundary conditions correspond to the range of state and control variations of the PMCU pushing process. The path constraints need to restrict the PMCU pushing process from colliding with obstacles. The above three parts will be introduced in Section 2.2, Section 2.3, Section 2.4, respectively.

2.2. Kinematic Model of PMCU

The construction space on the deck of the cruise ship is narrow and complex, so it is difficult for traditional heavy-duty trucks to directly enter the deck space for construction work. At present, PMCU is often transported by workers using special transfer devices. The device shown in Figure 1 is often used to push the cabin during the transportation of prefabricated cabins on board by fixing two devices on opposite sides of the prefabricated cabin. Then, the workers can move the cabin in any direction during the pushing process [6].

The forces during the pushing process of the PMCU are complicated, including pushing forces of workers, gravity, and device friction. This paper focuses on the path planning problem, focusing on the planning of the movement path and position and pose of the cabin pushing process. Also, because of the low speed of cabin pushing and the flat cruise deck, factors such as lateral sliding as well as inertia forces can be ignored. Combined with the characteristics that the cabin pushing process can move in any direction, the simplified kinematic model of the PMCU pushing (Figure 2) can be expressed as:

$$\left\{\begin{array}{l}{\dot{x}}_i=v_i\cdot \mathit{cos}\theta \\ {\dot{y}}_i=v_i\cdot \mathit{sin}\theta \\ {\dot{v}}_i={u_i}_1\\ {\theta }_i={u_i}_2\end{array}\right.$$

(6)

Equation (6) is the state variables of the PMCU pushing process, $x_i,y_i$ is the position of the ith PMCU in the 2D space of deck, $\dot{x_i},\dot{y_i}$ is the first-order derivatives of $x_i,y_i$, i.e., the velocity components in $x,y$ direction, ${\theta }_i$ is the orientation angle of PMCU pushing process, $v_i$ is the velocity of the PMCU pushing process, and $[u_{i1},u_{i2}]$ are the control variables of the PMCU pushing process.

2.3. Boundary Conditions

The state variables constraints mainly refer to the constraints imposed on each state variable during PMCU pushing, which can be expressed as:

$$\left\{\begin{array}{c}{x}_{min}\le x_i\left(t\right)\le x_{max}\\ y_{min}\le y_i\left(t\right)\le y_{max}\\ v_{min}\le v_i\left(t\right)\le v_{max}\\ {\theta }_{min}\le {\theta }_i\left(t\right)\le {\theta }_{max}\end{array}\right.$$

(7)

In Equation (7), $x_{min}, x_{max},{ y}_{min},{ y}_{max}$, etc., are the constraints of each state variable during PMCU pushing. In addition to path state variables constraints, PMCU pushing is also constrained by the initial state and the end state. The initial state of the PMCU pushing into the deck via the port side opening can be expressed as:

$$\left\{\begin{array}{l}{x}_i\left(t_0\right)={x_i}_0\\ y_i\left(t_0\right)={y_i}_0\\ v_i\left(t_0\right)=0\\ {\theta }_i\left(t_0\right)=0\end{array}\right.$$

(8)

$x_{i0},y_{i0}$, etc., in Equation (8) are the initial state constraints for the ith PMCU. The endpoint of PMCU pushing is the target installation location of the different cabins and must satisfy the required pose constraints for the installation, which can be expressed as:

$$\left\{\begin{array}{l}{x}_i\left(t_f\right)=x_{if}\\ y_i\left(t_f\right)=y_{if}\\ v_i\left(t_f\right)=0\\ {\theta }_i\left(t_f\right)={\theta }_{if}\end{array}\right.$$

(9)

$x_{if},{ y}_{if}$ etc., in Equation (9) are the end state constraints for the ith PMCU. In addition, the boundary conditions of the control variables are shown in Equation (10).

$$\left\{\begin{array}{c}{u}_{1min}{\le u}_{i1}\left(t\right)\le u_{1max}\\ u_{2min}{\le u}_{i2}\left(t\right)\le u_{2max}\end{array}\right.$$

(10)

2.4. Path Obstacles Avoidance Constraints

Currently, most path-planning studies based on optimal control use circles or spheres to model obstacles [38,43,47] when such methods result in a large amount of space occupied by the obstacles in the model. This method of describing obstacles is not acceptable for the narrow and complex cruise deck environment during PMCU pushing. The main obstacle on the deck of a cruise ship is mainly the steel structures, which are usually relatively regular in shape and can usually be directly regarded as rectangular obstacles. Some areas need to be reserved for subsequent construction, which can also be rectangular obstacles according to the construction scribing. Compared to circular obstacle description methods, rectangular obstacles occupy less space [32], which is better for PMCU pushing path planning.

For rectangular obstacle avoidance constraints, most of the current studies use the P-norm form for the constraint description, i.e., the P-norm analytic is used to represent the rectangular obstacle contour [26,48]. However, this method requires that $p\to \infty$ when representing a rectangle, which often produces invalid solutions in the computation process.

Therefore, this paper adopts the area relationship of contour vertices to express the obstacle avoidance constraints of PMCU pushing [49]. Whether a collision with an obstacle is determined by comparing the size of the sum of the triangle area produced by the points on the planned path and the four vertices of the rectangular obstacle with the area of the rectangle, as shown in Figure 3. The scenario shown in Figure 3A is that the vertex E collides with the obstacle, so the sum of the four triangle areas is equal to the area of the obstacle rectangle. The scenario shown in Figure 3B does not collide; the sum of the areas of the four triangles is greater than the area of the rectangle.

Thus, the obstacle avoidance constraint for the cabin pushing process can be described as:

$$S_{△AEB}+S_{△BEC}+S_{△CED}+S_{△DEA}-S_{▭ABCD}>0$$

(11)

In Equation (11), $S_{△AEB},{ S}_{△BEC},{ S}_{△CED},{ \mathrm{and} S}_{△DEA}$ are the areas of triangles $AEB, BEC, CED, DEA$, respectively. $S_{▭ ABCD}$ is the area of rectangle $ABCD$. Point $E$ is the PMCU outer contour vertex, and the entire cabin pushing process should ensure that all four vertices of the PMCU rectangular outer contour satisfy the obstacle avoidance constraints.

3. RPM Path Planning Method Based on Probabilistic Roadmap and Heuristic Rule

In Section 2, we construct the complete optimal control model of PMCU pushing path planning. In order to solve this model, this section proposes an RPM path planning method based on a probabilistic roadmap and heuristic rule. Firstly, the optimal control model was constructed based on the PMCU process kinematics model, and the RPM algorithm was used to solve the problem. Aiming at the initial value sensitivity of the RPM, the probabilistic roadmap (PRM) algorithm is used to construct the passable path, and a path pruning heuristic rule with reverse search is proposed to further optimize the passable path generated by the PRM. Thus, high-quality initial value guesses are generated and input into the RPM algorithm to improve the quality of RPM path planning.

3.1. RPM for Solving the Optimal Control Path Planning Problem

To solve the optimal control problem corresponding to Equations (5)–(11), the Radau pseudospectral method is used to discretize the continuous-time optimal path planning problem into a finite-dimensional NLP problem to solve for the optimal time of the cabin pushing control.

First, the time interval of the problem needs to be normalized, i.e., the time interval $[t_0,t_f]$ is transformed into $(-\mathrm{1,1}]$ that can be solved by pseudospectral, as in Equation (12).

$$\tau =\frac{2t}{t_f-t_0}-\frac{t_f+t_0}{t_f-t_0}=\frac{2t-t_f-t_0}{t_f-t_0}$$

(12)

In Equation (12), $\tau$ is the normalized time, $t\in [t_0,t_f]$.

In order to solve the problem, the state variables, control variables, constraint functions, optimization objective functions, etc., need to be discretely varied. Solving with the RPM requires dividing the time interval. However, the collocation point taken by the RPM is the Legendre Gauss Radau (LGR) point, which takes the value interval $(-\mathrm{1,1}]$, excluding the left endpoint of the interval. To be consistent with the time interval required by the RPM, a discrete point is added, i.e., the total number of discrete points is $N+1$ and the interval is $[-\mathrm{1,1}]$.

The LGR point of order $N$ is the solution of the polynomial $P_N\left(\tau \right)+P_{N-1}\left(\tau \right)=0$, where $P_N\left(\tau \right)$ denotes the Legendre polynomial of order $N$:

$$P_N\left(\tau \right)=\frac{1}{2^{N}N!}\cdot \frac{d^N}{d{\tau }^N}\left({\left({\tau }^2-1\right)}^N\right)$$

(13)

The set of LGR collocation points using Equation (13) is $\{{\tau }_1,{\tau }_2,\dots ,{\tau }_N\}$. Further, the state variables $\{X_1,X_2,\dots ,X_N\}$ and the control variables $\{U_1,U_2,\dots ,U_N\}$ at the LGR collocation points can be obtained. Then, the state variable $x\left(\tau \right)$ and control variable $u\left(\tau \right)$ can be expressed using Lagrange polynomials:

$$x\left(\tau \right)\approx X\left(\tau \right)=\sum _{i=0}^N{L}_i\left(\tau \right)X\left({\tau }_i\right)$$

(14)

$$u\left(\tau \right)\approx U\left(\tau \right)=\sum _{i=1}^N{L}_i\left(\tau \right)U\left({\tau }_i\right)$$

(15)

Since the point ${\tau }_0=-1$ is added at the interval $(-\mathrm{1,1}]$, in the state variable approximation in Equation (14), $i=0$. The control variable approximation uses only LGR points for approximation, excluding the −1 point, so $i=1$ in Equation (15). In Equations (14) and (15), $L_i\left(\tau \right)$ represents the Lagrange interpolation basis function, expressed as:

$$L_i\left(\tau \right)=\prod _{j\ne i,i=1}^N\frac{\tau -{\tau }_j}{{\tau }_i-{\tau }_j}$$

(16)

in which,

$$L_i\left({\tau }_j\right)=\left\{\begin{array}{l}1, i=j\\ 0,i\ne j\end{array}\right.$$

(17)

Further, the constraints are transformed. The derivative of the approximate state variable is obtained by deriving the derivative of the approximate state variable obtained from the Lagrange interpolation polynomial:

$$\dot{x}\left({\tau }_i\right)\approx X\left({\tau }_i\right)=\sum _{j=0}^N{\dot{L}}_j\left({\tau }_i\right)X_j=\sum _{j=0}^N{D}_{ij}{X}_j$$

(18)

where $D_{ij}$ is the differential matrix and the expression is:

$$D_{ij}=\left\{\begin{array}{l}\frac{\dot{g}\left({\tau }_i\right)}{\left({\tau }_i-{\tau }_j\right)\dot{g}\left({\tau }_j\right)},if i\ne j\\ \frac{\ddot{g}\left({\tau }_i\right)}{2\dot{g}\left({\tau }_j\right)} ,if i=j\end{array}\right.$$

(19)

In Equation (19), $g\left({\tau }_i\right)=\left(1+{\tau }_i\right)[P_N\left({\tau }_i\right)-P_{N-1}({\tau }_i\left)\right]$, $\dot{g}\left({\tau }_i\right)$ is the first-order derivative and $\ddot{g}\left({\tau }_i\right)$ is the second-order derivative. The differential equation constraint can be transformed into:

$$\sum _{i=0}^N{D}_{ij}X\left({\tau }_j\right)=\frac{t_f-t_0}{2}f\left(X\left({\tau }_i\right),U\left({\tau }_i\right),{\tau }_i\right)$$

(20)

In addition, for the path planning problem, it is necessary to determine the terminal state $x\left({\tau }_f\right)$ of the PMCU at the target location. Then, the terminal state can be expressed as follows:

$$x\left({\tau }_f\right)\approx X\left({\tau }_N\right)=X\left({\tau }_0\right)+\frac{t_f-t_0}{2}\sum _{i=1}^N{\omega }_{i}f\left(X\left({\tau }_i\right),U\left({\tau }_i\right),{\tau }_i\right)$$

(21)

where ${\omega }_i$ is the Gaussian integral weight, ${\omega }_i=\frac{2}{1-{\tau }_i^2}{\left[{\dot{P}}_N\left({\tau }_i\right)\right]}^2$.

Similarly, the boundary constraints and process constraints can be discretized as:

$$\Phi \left(X\left({\tau }_0\right),t_0,X\left({\tau }_N\right),t_f\right)=0$$

(22)

$$h\left(X\left({\tau }_i\right),U\left({\tau }_i\right),{\tau }_i,t_0,t_f\right)\le 0$$

(23)

Overall, the optimal control problem of PMCU pushing path planning can be transformed into a NLP problem and solved by sequential quadratic programming (SQP).

3.2. NLP Problem Solving and Initial Value Generation

Section 2 and Section 3.1 construct the optimal control problem and discretize the continuous optimal control problem into a finite-dimensional NLP problem using the RPM. For a NLP problem, the SQP method is one of the effective solution methods [50]. However, for the optimal control problem in Section 2, its practical path planning environment is complex, the problem size is large, and there are more constraints to be satisfied, leading to an increase in the computational time for solving the problem. In addition, the SQP method is sensitive to the initial values. If the initial solution quality is not high enough, the iterative solution process may diverge. Therefore, this section will investigate how to ensure the speed of solving while improving the quality of the initial solution.

3.2.1. Probabilistic Roadmap Method

When solving the path planning problem, the first element to focus on is whether the path is passable or not, and how to build a collision-free passable space in a complex environment is an effective means to improve the quality of the initial solution. The Probabilistic Roadmap (PRM) method is a probabilistic sampling-based algorithm, which is probabilistic complete, practical, and a very effective passable path planning algorithm [51].

The PRM algorithm can be divided into two phases: the offline learning phase and the online query phase. In the learning phase, the roadmap of the passable space is constructed based on probabilities and can be represented as an undirected graph $G=\{V,E\}$, where the set of nodes $V$ represents the set of collision-free nodes. The connected set $E$ represents the collision-free paths connecting neighboring nodes, and the sets $V$ and $E$ are both empty sets in the initial state. The PRM randomly constructs multiple collision-free nodes and adds them to the node set $V.$ It also defines a distance $\rho$. For a node in the node-set $V$, if the distance of the node from a node is less than $\rho$, it is considered a neighbor node. Connect all neighbor nodes and determine whether the connection $\tau$ collides with the obstacle; if there is no collision, then $\tau$ is added to the connection set $E$. The pseudo-code of the Roadmap Construction Algorithm is shown in

Table 1. Roadmap construction algorithm pseudocode.

Roadmap Construction Algorithm

Input: $N_v=number of vertices to complete the graph$ $N_k=number of neighbors to examine for each vertex$ Output: $G=\{V,E\}$ 1: $\mathit{b}\mathit{e}\mathit{g}\mathit{i}\mathit{n}$ 2: $V\leftarrow \mathrm{\varnothing };$ 3: $E\leftarrow \mathrm{\varnothing };$ 4: $i=0;$ 5: $\mathit{f}\mathit{o}\mathit{r} \left(i\le N_v\right) \mathit{d}\mathit{o}$ 6:      $\mathit{i}\mathit{f}\left(v\leftarrow the random sampling vertex is in free space\right),\mathit{t}\mathit{h}\mathit{e}\mathit{n}$ 7:          $V\leftarrow V\cup \left\{v\right\}$ 8:      $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 9:          $\mathit{r}\mathit{e}\mathit{p}\mathit{e}\mathit{a}\mathit{t};$ 10: $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 11: $\mathit{f}\mathit{o}\mathit{r} \mathit{a}\mathit{l}\mathit{l} v\in V \mathit{d}\mathit{o}$ 12:      $N_n\leftarrow the N_k closest neighbors of v chosen from V according to distance$ 13:      $\mathit{f}\mathit{o}\mathit{r} \mathit{a}\mathit{l}\mathit{l} v^{\prime } \in N_n \mathit{d}\mathit{o}$ 14:          $\mathit{i}\mathit{f} \left(v,v^{\prime }\right) \notin E \mathit{a}\mathit{n}\mathit{d} ∆\left(v,v^{\prime }\right) \ne NIL \mathit{t}\mathit{h}\mathit{e}\mathit{n}$ // Perform inclusion and collision detection for $(v,v\prime )$ 15:              $E\leftarrow E\cup \left\{\right(v,v^{\prime }\left)\right\}$ //Put $(v,v\prime )$ into set $E$. 16:          $\mathit{e}\mathit{n}\mathit{d} \mathit{i}\mathit{f}$ 17:      $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$ 18: $\mathit{e}\mathit{n}\mathit{d} \mathit{f}\mathit{o}\mathit{r}$

.

After completing the roadmap construction and entering the query phase, the PRM algorithm starts to solve the path planning problem, which uses the Dijkstra algorithm to search a passable path from the starting node to the target node from the undirected graph $G=\{V,E\}$ according to the starting node, target node, and environment information of the problem.

3.2.2. Path Pruning Heuristic Rule with Reverse Search

In Section 3.2.1 we obtained a passable path using the PRM, but the computed passable path usually has more redundant points and more turning points. In fact, the quality of this path is still not high enough, and directly using it as the initial solution to the NLP problem may increase the computational effort or even affect the generation of optimal or sub-optimal paths. To optimize this problem, this paper proposes path pruning heuristic rules with a reverse search to reduce the number of redundant points in the path to improve the quality of the planned path, as shown in Figure 4.

On the base of the path planned by the Dijkstra algorithm, the nodes in the path are connected from the target point to the starting point in turn, and if the connection between the $n$-th node and the target point does not pass through the obstacle while the connection between the $(n+1)$-th node and the target point passes through the obstacle, the node between the target point and the nth node in the path is removed. Once again, the connections between other nodes in the path are verified, and finally, the remaining nodes are extracted and connected in the order from the starting point to the endpoint to form a suboptimal path. The path pruning heuristic method flow is shown in Figure 5.

3.3. PH-RPM Design

In the PH-RPM proposed in this paper, the optimal control model for PMCU pushing path planning is first discretely solved using the RPM method to transform it into a finite-dimensional NLP problem. The PRM algorithm pre-plans the passable space and solves the effective PMCU pushing suboptimal path by combining the path pruning heuristic method, which can effectively improve the quality of the initial value guess while ensuring the speed of the solution. The initial solution is used as the initial value guess of the NLP problem. In order to solve the NLP problem, SQP is adopted in this paper. Compared with other methods, the SQP has good convergence, high computational efficiency, and strong boundary search capability and has been widely valued and applied by scholars once it was proposed [52,53,54]. The basic principle is that at the current iteration point $x^k$, taking the Taylor second-order expansion of the Lagrange function $L(x,\lambda )$ of the NLP model at $(x^k,{\lambda }^k)$ for the variable $x$ as the objective function. Using the Taylor first-order expansion with the constraint at $x^k$ as the constraint, a quadratic programming subproblem is constructed to obtain the search direction $d^k$, and the process is repeated iteratively to find the optimal solution for the problem.

Overall, the summary composition of the proposed optimal control-based path planning algorithm, which we called the PH-RPM, is shown in Figure 6:

4. Simulation Experiment and Results

In Section 4, we will evaluate the performance of the PH-RPM proposed in this paper through simulation experiments, which will be modeled using a real production environment on the eighth deck of a large cruise ship. We use some well-known path planning algorithms to compare with the PH-RPM of this paper in two scenarios, respectively.

4.1. Definition of Simulation Cases

In this paper, the A* algorithm, RRT* algorithm, and PRM algorithm, which are commonly used in path planning problems, are selected and compared with the PH-RPM algorithm proposed in this paper. Among them, the A* algorithm has a more direct path search, while the RRT* and PRM algorithms are efficient and fast, and all of them have good path planning performance. In addition, the traditional RPM algorithm is also applied in the examples, and the results of the algorithm are compared with those of other algorithms. Some of the intelligent optimization algorithms, such as the genetic algorithm (GA) popular in path planning, are not selected as comparison algorithms because the parameter configurations of such algorithms have some uncertainty. Generally, such methods require optimization of parameter configurations and algorithmic strategies according to the problem environment to achieve the application and performance improvement of the algorithms; directly adopting the parameter configurations and algorithmic strategies from other studies in this paper’s problem does not guarantee that a reliable solution can be obtained.

The experiments were conducted in the construction environment of the first to third main vertical zone (MVZ) on deck 8 of a large cruise ship. This environment is mainly occupied by passenger cabins, and most of the cabin types are prefabricated cabins that need to be pushed and transferred from the reversed side opening to the target positions for installation. The experiments are designed with two scenarios. Case 1 is a simple scenario that corresponds to the cabin-pushing process of the first prefabricated cabin in the region. The path planning problem in this scenario mainly needs to consider the fixed structural obstacles on the deck environment and part of the reserved installation space. Case 2 is a complex scenario; in addition to the obstacles in Case 1, we also need to pay attention to the impact of the prefabricated cabin that has been installed on the path. Both cases need to ensure that the speed of the prefabricated cabin is $0 \mathrm{m}/\mathrm{s}$ when it reaches the target position and the angle meets the process requirements for subsequent connection and installation, which means that the prefabricated cabin needs to stay at the target position according to the specified position. In both cases, the length and width of the PMCU are 6.2 m and 2.8 m.

All experiments were run on a computer with an AMD Ryzen5 4600H 3.00 GHz processor and 16 GB RAM and were solved using the well-established solver SNOPT. The relevant parameters used are shown in

Table 2. Parameter description.

Parameter	Description	Setting
$(x_0,y_0)$	Initial position of PMCU	(106.2, 44.8)
${\theta }_0$	Angle at initial position	$-\frac{\pi }{2}$
$v_0$	Velocity at the initial position	0
$t_0$	Time to leave the initial position	0
$[v_{min},v_{max}]$	The range of velocity changes $(\mathrm{m}/\mathrm{s})$	[−0.5, 0.5]
$[{\theta }_{min},{\theta }_{max}]$	The range of angle changes $\left(\mathrm{r}\mathrm{a}\mathrm{d}\right)$	$[-\pi , \pi ]$
$[u_{1min},u_{1max}]$	The range of acceleration changes $(\mathrm{m}/{\mathrm{s}}^2)$	[−0.1, 0.1]
$[u_{2min},u_{2max}]$	The range of angular acceleration changes $(\mathrm{r}\mathrm{a}\mathrm{d}/\mathrm{s})$	$[-\frac{\pi }{4}, \frac{\pi }{4}]$
$\left[x_{min},x_{max}\right]$	Horizontal boundary	[0, 180]
$\left[y_{min},y_{max}\right]$	Vertical boundary	[0, 50]
$N$	Number of collocation points	40

.

4.2. Case 1: Simple Scenario

In the simple scenario, the target point coordinates of the PMCU are ${\left[x_f,y_f\right]}_{case1}=[27.2, 39.2]$, the velocity of target point $v_{fcase1}=0$, and the orientation angle ${\theta }_{fcase1}=-\frac{\pi }{2}$. Among them, since the traditional RPM algorithm uses random initial value guesses, it often converges to different solutions and, in some cases, even fails to converge within the maximum number of iterations. Therefore, the results of the traditional RPM algorithm are compared with the PH-RPM using the optimal results of all experiments.

4.2.1. Simulation Results

The calculation results of the five algorithms for the Case 1 simple scenario are shown in

Table 3. Results of simple scenarios planned by different algorithms.

Algorithm	${\mathit{t}}_{\mathit{c}\mathit{p}\mathit{u}}/\mathit{s}$	${\mathit{t}}_{\mathit{f}}/\mathit{s}$	$\mathit{L}/\mathit{m}$
A*	2.921	-	70.74
RRT*	7.679	-	82.99
PRM	1.206	-	84.12
RPM	6.160	174.88	68.51
PH-RPM	1.884	154.43	70.25

. In Table 3, $t_{cpu}$ is the CPU running time for different algorithms computation. As can be seen, the PRM algorithm requires the shortest computation time, which is only 1.206 s. The PH-RPM proposed in this paper can also be efficiently carried out in simple scenarios for paths to carry out planning, and the computation time required is only 1.884 s, which is slightly longer than that of the PRM but is still shorter than that of other path planning methods. $t_f$ is the time of the cabin pushing from the starting point to the endpoint under kinematic constraints, where the A*, RRT*, and PRM algorithms do not take the characteristics such as the velocity of the PMCU pushing into account in the planning, so the corresponding results are null. Compared with the conventional RPM algorithm, the PH-RPM algorithm solves the simple scenario with 154.43 s for the pushing, which is 20.45 s less than the time solved by the conventional RPM algorithm.

Regarding the path planning results of different algorithms, we need to combine the path length and path diagram for comparison, as shown in Figure 7 and Figure 8. As shown in Figure 7, the RPM achieves the shortest path with a length of only 68.51 m. The path length planned by the PH-RPM proposed in this paper is 70.25 m, which is slightly longer than RPM but still shorter than A*, RRT*, and PRM. Although the traditional RPM algorithm finds the shortest path length, it can be seen in the rectangular areas (A) and (B) in Figure 8. This is because the RPM only satisfies the process constraints at the collation points, but the paths between the collocation points may still not satisfy the path constraints, resulting in collisions. Although the path length of the PH-RPM method is slightly longer than that of the RPM, it can be seen from Figure 8 that no collision occurs along the entire length of the path, which ensures the path is passable. The other algorithms (A*, RRT*, and PRM) are also able to plan the resulting paths, but the lengths of the generated paths are all longer than PH-RPM, and the kinematic constraints are not fully taken into account in the planning process.

The variation curves of the velocity and orientation angle of the cabin pushing process by the PH-RPM algorithm and the RPM algorithm are shown in Figure 9. From an overall perspective, the variation of velocity and orientation angle of the results planned by the PH-RPM are within the set constraints, and the rate of change is acceptable. From Figure 9A, it can be seen that the velocity variation during the motion of the cabin pushing in the simple scenario can be divided into three stages: acceleration, maximum velocity motion, and deceleration, conforming to the actual motion situation and more stable than the results of RPM planning. From Figure 9B, the 0~25 s orientation angle changes rapidly to adjust the movement direction, fine-tune the angle to avoid obstacles during the maximum velocity motion, and gradually adjust to the specified direction to meet the target pose requirements when approaching the target position, which is more in compliance with the actual situation compared with the RPM planning results.

4.2.2. Discussion

From the simulation of the simple scenario, it can be seen that the PH-RPM proposed in this paper can achieve better results in terms of computational efficiency and path computation results in this scenario. In terms of computational efficiency, the PH-RPM method takes only 1.884 s for path planning under the simple scenario, which is slightly longer than the time taken by the PRM, but it is still the second most efficient algorithm. The time cost of A* is related to the search range; the span from the starting point to the target point is smaller in the simple scenario, so A* has a smaller search range and consumes less time. RRT* is characterized by a reconnection step that tries to change existing connections to find a better path and, therefore, consumes more time. The initial value input to the RPM uses a random strategy, and poor quality of the initial values can lead to the method taking more time. The. PH-RPM uses a probabilistic roadmap and heuristic rules for the initial solution construction, and kinematic characteristics are taken into account in the computation process, so the computation time is slightly longer compared to the PRM. Compared with the RPM, we can find that the initial solution generation strategy proposed in this paper can effectively reduce the computation time of the pseudospectral method.

Combining the path lengths, passing times, path diagrams, and speed and angle variations, it can be seen that the paths planned by the PH-RPM method proposed in this paper have the shortest passable paths and take less time. Usually, in path planning problems, we consider the path planned by the A* algorithm to be the theoretical optimal path because the A* algorithm will consider the object as a point using a grid map for planning. But in the simple scenario shown in Figure 8, since the A* algorithm uses an eight-direction move strategy, which considers that each move needs to pass through the center of the grid, the calculated path may not be the shortest path when the number of grids passed is small. Moreover, since the paths generated by the A*, RRT*, and PRM methods do not consider kinematic constraints, their paths are not directly applicable to PMCU pushing. Although the RPM takes kinematic constraints into account, the algorithm is not fully applicable to this problem as it satisfies path constraints only at collocation points, resulting in collisions of the computed paths between neighboring collocation points.

Compared with the RPM, the velocity and orientation angle changes of the PH-RPM in the PMCU pushing process in the simple scenario are more in line with the actual movement, and the velocity and angle change rates are within a reasonable range. And the angle will be fine-tuned when approaching certain key obstacle nodes to avoid them. In the actual PMCU pushing process of cruise ship production, similar to the simple scenario, the current state and speed will be adjusted in advance according to the simulation results at critical path nodes before encountering obstacles, avoiding the wide range of state adjustments after the cabin is close to the obstacles.

In summary, compared with other path-planning algorithms, the PH-RPM algorithm can plan shorter motion paths with no collisions while considering kinematic constraints in the simple scenario.

4.3. Case 2: Complex Scenario

In the complex scenario, the number of structural obstacles and reserved areas through which the cabin pushing may pass becomes more numerous, and the immovable PMCUs can also be regarded as obstacles. All these obstacles can have some influence on the position & pose of the PMCU during the pushing process. In this scenario, the coordinates of the PMCU target point ${\left(x_f,y_f\right)}_{case2}=(152.8,10.1)$, the velocity $v_{fcase2}=0$, and the orientation angle ${\theta }_{fcase1}=\frac{\pi }{2}$.

4.3.1. Simulation Results

The simulation results of the five algorithms in the complex scenario are shown in

Table 4. Results of the complex scenario planned by different algorithms.

Algorithm	${\mathit{t}}_{\mathit{c}\mathit{p}\mathit{u}}/\mathit{s}$	${\mathit{t}}_{\mathit{f}}/\mathit{s}$	$\mathit{L}/\mathit{m}$
A*	12.531	-	93.89
RRT*	10.396	-	123.73
PRM	3.843	-	129.57
RPM	10.867	136.35 (Invalid)	54.77 (Invalid)
PH-RPM	4.528	239.78	106.96

and Figure 10. The detailed path diagram is shown in Figure 11.

According to Table 4, it can be seen that similar to the simple scenario, the smallest $t_{cpu}$ among the five algorithms is the PRM with only 3.843 s. The PH-RPM proposed in this paper is still in the second position, slightly longer than the PRM, with a time of 4.528 s. The longest computation time for the five algorithms is the A* algorithm, which is due to the increased time cost caused by the wider search range. Combining Table 4 and Figure 10, from the comparison of path length, the path length of the RPM is the shortest, only 54.77 m, followed by the A* algorithm with a path length of 93.86 m. The path length of the PH-RPM in this paper is 106.96 m, which is 13.92% longer than the path length of the A* algorithm. The planned paths calculated by the RRT* and PRM methods are longer, 123.73 m and 129.57 m, respectively. As can be seen in Figure 11, the paths planned by the RPM are invalid and do not result in collision-free paths from the start to the endpoint. That is, in complex scenarios, all algorithms except the RPM can obtain valid solutions, and A* calculates the shortest path length among all valid solutions.

Figure 12 shows the velocity and orientation angle variation curves of the PH-RPM algorithm in the path-planning process of the complex scenario. Since the RPM algorithm is not able to find the effective path in the complex scenario, the velocity and directional angle changes obtained by the RPM algorithm are not discussed. From Figure 12A, it can be seen that the whole moving process is similar to the simple scenario and can still be divided into three stages. Although there is a certain fluctuation of velocity during the maximum velocity motion, the fluctuation range is acceptable and satisfies the boundary range constraint of velocity, which is consistent with the actual motion. From Figure 12B, the overall change of orientation angle is relatively flat, which meets the boundary constraint of angle change, and the angle change at the end stage meets the practical requirements, i.e., the angle first reaches near the target position according to a certain angle, and then gradually adjusts the angle to meet the target pose constraint.

4.3.2. Discussion

In terms of computational efficiency, the results of the complex scenario are similar to the results of the simple scenario, with the PRM having the shortest computation time and PH-RPM being in second place, taking less time than the RPM. This is due to the effect produced by the introduction of the initial value strategy proposed in this paper. The computation time consumed by the A* algorithm becomes the longest due to the increase in the search range required for the complex scenario. RRT* is more efficient in searching in the complex scenario compared to A*, but still not comparable to the PRM and the PH-RPM with efficient probabilistic roadmap construction strategies.

Combining the path lengths, passing times, path diagrams, and speed and angle variations, the results in the complex scenario are different from the results in the simple scenario; the A* algorithm has the shortest path in the complex scenario. This is because the number of grids explored by the A* algorithm in the complex scenario is large enough so that the path length is minimized, but it cannot be applied to the PMCU pushing path planning directly because the shape constraints and kinematic constraints of the PMCU are not considered. Although the traditional RPM algorithm for complex scenario planning successfully solves and obtains the result of $t_f=136.35 \mathrm{s}, L=54.77 \mathrm{m}$, the planned path passes through multiple obstacles, and no valid solution is obtained at all. As for the path planned by the PH-RPM, the path of the whole process of cabin motion is collision-free so that the path planning can be realized under the condition that the outer contour of the cabin does not collide with the obstacles and the obtained motion time is $t_f=239.78 \mathrm{s}$, which is in the acceptable range. The path length is shorter compared with the RRT* and PRM algorithms. However, there is a 13.9% gap in path length compared to the A* algorithm. This part of the gap is due to the way the A* algorithm searches for a path. This is because A* will only search and judge the eight adjacent grids of the current node, which means that the path of the A* algorithm will be infinitely close to the obstacles when they exist nearby. It’s also more indicative of the advantage in length of the paths planned by A* considering the object as a point. Therefore, the path of A* is usually regarded as the theoretical shortest path without considering the outer contour and kinematic constraints. The path planned by the PH-RPM proposed in this paper ensures the outer contour of the PMCU does not collide with obstacles because of the constraints imposed by the path constraints of the optimal control model. The gap in path length is acceptable compared to the path planned by A*. For production applications, it is more important to get a path to pass through obstacles than to get the shortest path. RRT* and PRM can plan paths, but the optimality and practicality of the planned paths are not high, and they do not take kinematic constraints into account either. Therefore, they cannot be used as PMCU path planning as well. The path planned by PH-RPM can be considered as the optimal path under the complex scenario, which satisfies the kinematic constraints.

In summary, the PH-RPM algorithm in this paper can be used to solve the PMCU pushing path planning problem in the complex scenario, and the algorithm has stronger applicability to complex scenarios compared with the traditional RPM algorithm. Compared with other path planning algorithms, it can realize the planning of accessible paths in complex scenarios with careful consideration of kinematic constraints, and the planned paths have shorter path lengths.

5. Enterprise Applications of the PH-RPM

Currently, the PH-RPM proposed in this paper is mainly applied to the testing and production guidance of the PMCU pushing process. Usually, before an enterprise conducts PMCU pushing, the production department will first carry out a process simulation using an actual model frame of the same size as the actual cabin to test whether the cabin can pass near certain key obstacles. However, this test session cannot test all PMCUs and takes up a lot of time, manpower, equipment, and other costs for the enterprise. Through the PH-RPM method proposed in this paper, the PMCU pushing route can be effectively planned to ensure that the whole process path is collision-free, which effectively reduces the cost of the enterprise and improves the overall efficiency of the project.

In addition, the paths calculated by the PH-RPM are used to guide the PMCU PUSHING process by being sent down to the field, providing efficient pushing paths for the production environment. According to the enterprise single-day data estimation, the average effective transport time of a PMCU is about 4–8 min (excluding preparation work as well as process adjustment). Through the application of the method in this paper, it is possible to plan the pushing paths in advance, effectively guide the motion attitude of the push cabin process, reduce the narrow aisle passing time, and reduce the effective motion time of the actual PMCU by an average of 38–45%.

6. Conclusions

This paper is oriented to the PMCU pushing installation process of the cruise ship and mainly solves the path planning problem of the cabin pushing process. Based on the kinematic model of the pushing cabin process, a PH-RPM for solving the path planning under complex space is proposed. The main contributions of this paper can be summarized as follows:

(1)

In this paper, the kinematic modeling of the PMCU pushing installation process for cruise ships is carried out, and the continuous-time optimal control model for PMCU pushing path planning is constructed based on the kinematic characteristics.

(2)

To solve this optimal control problem, we use the Radau pseudospectral method for discretization to a NLP and solution. For the characteristics of the NLP problem sensitive to the initial value, an initialization strategy based on a probabilistic roadmap and heuristic rule is proposed to quickly generate high-quality initial solutions and achieve fast planning of optimal paths.

(3)

The performance of the PH-RPM proposed in this paper is evaluated through simulation experiments and compared with well-known path planning algorithms, including A*, RRT*, and PRM, while the traditional RPM is also used for comparison. The experimental results show that the PH-RPM generates optimal or sub-optimal passable path lengths compared to other methods. Combining kinematic constraints and outer contour collision constraints, the PH-RPM generates higher-quality paths and can effectively solve the PMCU pushing path planning problem.

In this paper, the RPM with initial value strategy (PH-RPM) is proposed and used to solve the PMCU pushing path planning problem. The method may also be used for other complex spatial path planning or motion planning problems that require consideration of kinematic constraints, like path planning for robot indoor environments, unmanned vehicles, etc. In addition to this, the RPM can be improved in the collocation points configuration strategy, and higher initial solution generation strategies may exist to further improve the initial value quality. In future research, PMCU pushing dynamic path planning with real-time environmental information and application of AI, such as reinforcement learning on cruise ship construction, will be our main research content. Since there is a temporary construction situation on the deck of the cruise ship, the real-time environmental information is likely to affect the PMCU path planning decisions. This is specifically important, considering that real-time environmental information can lead to a path that is more capable of guiding the production process, which in turn promotes the application of intelligent devices in the cruise ship construction process.