# Research on Path and Sequence Planning for Multi-Cabin Onboard Transportation of Large Cruise Ships
## 3 Improved A-Star Algorithm Designing
### A-Star Algorithm Principle  
The core idea of the A-Star algorithm is to simultaneously consider both the actual cost from the current node to the starting point, and the estimated cost from the current node to the destination. The sum of these two costs is used to evaluate the priority of the node. During the search, nodes are expanded sequentially according to their priority, until the destination is found or it is determined that the destination is unreachable.  
In the A-Star algorithm, the estimated cost is typically calculated using a heuristic function, such as the Manhattan distance or Euclidean distance. The algorithm uses an open list and a closed list to track the nodes that have been discovered, and records the parent node of each node to trace the found path. The evaluation function is used to assess the priority of each node during the search process. It evaluates based on the distance from the node to the target node and the actual distance from the node to the starting node, in order to determine the next node to expand [22]. The choice of the evaluation function depends on the nature of the specific problem and the practical application scenario. A good evaluation function should have the following properties:  
The estimate should be accurate, meaning it should be as close as possible to the actual distance.  
The computational cost should be minimized, as the evaluation function needs to be computed multiple times during the search.  
The evaluation function should be reliable, meaning it should remain consistent throughout the search process, without fluctuating.  
The selected evaluation function is the Euclidean distance, which calculates the straight-line distance between two nodes, as shown in the following formula:  
\[h(n)=\sqrt{\left(x_{n}-x_{goal}\right)^{2}+\left(y_{n}-y_{goal}\right)^{2}} \tag{3}\]  
\[g(n)=\sqrt{\left(x_{n}-x_{start}\right)^{2}+\left(y_{n}-y_{start}\right)^{2}} \tag{4}\]\[f(n)=h(n)+g(n) \tag{5}\]  
where h(n) represents the actual distance from the current node n to the target node; g(n) represents the actual distance from the current node n to the starting node; and f(n) is used to evaluate the total cost. By comparing the costs of each neighboring node, the algorithm selects the node with the smallest f(n), or if multiple nodes have the same f(n), the node with the smaller g(n), as the next node to expand for further search. This process continues until the target node is found, after which the algorithm backtracks through the recorded nodes to identify the optimal path.  
The flow chart of the A-Star algorithm is shown in Figure 3, and includes the following steps:  
1. Build the grid map, input the coordinates of the start and end points, and initialize the open list and the closed list.
2. Expand from the start point and search for neighboring nodes, while updating the open and closed lists.
3. If a neighboring node is an obstacle, remove it; otherwise, calculate the cost of the neighboring node.
4. Select the node with the smallest cost as the next node to expand for further search.
5. If the target node is found, backtrack through the recorded nodes and output the optimal path; otherwise, repeat steps (2)-(4).  
Figure 3: A-Star algorithm flow chart.  
The A-Star algorithm can find the optimal path in most cases, but the traditional A-Star algorithm struggles with handling some complex problems. In such cases, if the implementation of the A-Star algorithm is incorrect, it may lead to failure in finding the optimal path or result in an infinite loop.  
For the large cruise ship cabin transportation path optimization problem, the main difficulty with the traditional A-Star algorithm lies in its inability to accurately identify line obstacles such as bulkheads. As a result, the standard A-Star algorithm is insufficient for this application, necessitating improvements to better account for these types of obstacles.