Mathematical modeling of tumor growth: the MCF-7 breast cancer cell line

1.   Introduction

Sensible logistics are essential for advancing the manufacturing industry in the context of intelligent manufacturing. Intelligent logistics achieves process automation and intelligence by fusing cutting-edge technologies like the Internet with intelligent instruments like smart robots, in line with the objectives of intelligent manufacturing. Modern technologies like the Internet of Things, cloud computing, big data, and artificial intelligence are essential to the smart logistics distribution system. In order to ensure seamless job completion and minimize the need for human and material resources, they expedite the design of order tasks, material distribution routes, vehicle scheduling, and load capacity. This all-encompassing strategy significantly improves production and logistical efficiencies ^[1]. Both software and hardware are needed to construct a smart logistics system. Stackers, different conveying equipment, and automated guided vehicles (AGV) are foundational elements. The enhancement of intelligent logistics is ensured by the digital workshop control system, path planning, navigation algorithm, and optimization algorithm.

Studies show that throughout the whole product production process, transportation, loading and unloading, and other links use three quarters of the time, while production and processing take up one quarter. Forklifts and other equipment are used in traditional transportation methods, which are dangerous, labor-intensive, and prone to mistakes. Deploying robots or AGVs as a substitute is beneficial in places with high labor costs, scarce human resources, or hazardous situations. As a component of intelligent logistics, AGV automates and simplifies the logistics transportation process, lowering labor costs in warehouses and enhancing operational effectiveness. This is in accordance with the trend of building intelligent and automated logistic systems in industrial development.

AGVs have taken on a variety of complex responsibilities in recent years. The main goal of material distribution using AGVs is to minimize human interaction by guaranteeing efficient conveyance to the work site. Therefore, solving the AGV path planning problem in the intelligent distribution system is necessary to realize intelligent logistics in the digital workshop ^[2,3].

AGV path planning has drawn a lot of interest due to its widespread applicability. The Dijkstra algorithm, A* algorithm, deep reinforcement learning algorithm, and ant colony algorithm are some of the most widely used path planning techniques. Based on the Dijkstra algorithm, Zhou and Huang ^[4] presented an improved method that uses the ant colony optimization strategy to optimize AGV pathways in airport situations. This model takes obstacle-filled situations into account. Results from simulations demonstrate that the combined algorithm in the airport baggage check-in path planning model performs better than three different methods. It is noteworthy that it reduces path lengths by 2.3, 2.64 and 6.06%. In order to provide collision avoidance when crossing known moving obstacles, He ^[5] and colleagues developed a dynamic search mechanism within the DAA (Dynamic A* Algorithm) that takes temporal considerations into account. The results of the simulations show that the DAA star algorithm performs better than the dynamic A* algorithm and the conventional A* algorithm in complex navigation scenarios. In order to learn the best decisions, Gu ^[6] and his associates used the Munchausen deep Q-learning network (m-DQN) for mobile robot applications. The simulation findings highlight how this approach learns more effectively and converges more quickly than DQN, Dueling DQN, and m-DQN counterparts, especially in static and dynamic situations. The technique is also very good at creating pathways that avoid collisions and go around obstructions. A group of researchers led by Miao ^[7] presented an improved adaptable ant colony algorithm (IaACO). Initially, angle guidance and obstacle removal parameters were integrated into the traditional ant colony algorithm (ACO) to increase the transmission probability. Second, adaptive pheromone volatilization factors and heuristic information adaptive adjustment were included to improve the pheromone update algorithms. The results of the experiment show that IaACO allows the robot to achieve global optimal pathways, exhibiting excellent planning stability and real-time performance.

In digital manufacturing workshops, the higher computer system must quickly determine an appropriate path for the AGV in order to guarantee the effectiveness of AGV logistics. Unfortunately, the training procedure for algorithms like the ant colony algorithm, DQN, and others takes a long time ^{[8,9,10,11,12]}, which makes it difficult to increase the workshop's AGV's logistical efficiency. The Dijkstra algorithm wastes time by having to search through an excessive number of nodes in the search path. As a result, the A* algorithm is selected as the fundamental algorithm in this article.

The frequency of AGV starts and pauses, as well as the amount of time they spend navigating turns on the path, can both be greatly reduced with a streamlined path. This optimization is essential to increasing the overall effectiveness of logistics. Five spiral transition curve templates with monotonic (increasing or decreasing) curvature and cubic Bezier curve configurations were presented by Bibi et al. ^[13]. The benefits of cubic Bezier spiral path smoothing technology were illustrated through experimental validation. To tackle the issue of excessive nodes and spikes during path design, Duraklı ^[14] presented a novel solution based on Bezier curves. The results of the experiments demonstrated the effectiveness of the strategy in determining the best routes between the beginning and target points in well-known areas. Global smooth path planning for mobile robots with motion constraints was examined by Song ^[15]. They developed a method that combines spline curves and an improved particle swarm optimization technique. The efficiency of this strategy was demonstrated decisively by the outcomes of the experiment.

There are still a number of issues with path smoothing, despite the large amount of research on the subject. Interestingly, a great deal of current path smoothing research projects unintentionally introduce curvature to the straight regions of the path by applying smoothing algorithms to such segments. Once smoothed, this curvature becomes detrimental to the best possible operating of AGVs. Therefore, there is a strong need to present a novel method of path smoothing that successfully takes care of this issue.

To sum up, this post will enhance the A* algorithm on the inside as well as the outside. In order to increase the efficiency of the A* algorithm, the traditional heuristic function is first replaced with a diagonal heuristic function, and the turning cost is increased. Afterwards, redundant turns and path optimization at corners are reduced by enhancing the forward search algorithm and the Bezier curve method outside of the A* algorithm.

The main contributions of this paper are as follows:

1) Enhance the A* algorithm internally. We improve node traversal logic to stop pathways from intersecting barriers diagonally, which would produce erroneous paths. The search efficiency of the algorithm can be increased by using a diagonal distance heuristic function for 8 neighborhood search directions, which can more precisely estimate the expected cost from the current node to the target node. We reduce the number of nodes traveled during the path search of the A* algorithm and increase search efficiency by adding turning weights to the method's formula.

2) On the output path of the internally improved A* algorithm, we do external optimization. The forward search optimization technique is improved and a new algorithm is suggested in this paper. This technique can identify important turning points in the path and eliminate unnecessary ones. To smooth out important turning points, this article uses an optimization technique based on Bessel curves.

2.   Problem statement and environmental modeling

2.1.   Problem statement

A digital manufacturing workshop serves as the path planning algorithm's application scenario in this article. Inside the manufacturing workshop, there are numerous production scenarios, unlike in ports, airports, and storage facilities. AGVs can go straight from the conclusion of one task to the beginning of the next, eliminating the requirement for them to stop and return to a fixed node while in operation. As a result, the AGVs' starting point and destination in the production workplace are dynamic, and they must be able to swiftly plan their route from one task node to the next.

2.2.   Environment

The manufacturing areas in the workshop have a basic layout, and that is where the impediments are positioned. For map modeling, this tutorial opts to utilize the grid map method. The area where an AGV may walk is shown by the white area in the grid map (Figure 1), while the area with obstacles is represented by the black area. The grid's numbering is represented by the numbers on the grid, which are written as $1, 2, 3, ..., w$ from top to bottom and left to right. Arrows in eight directions grant authorization to search for paths from those eight directions. Specifically, the positive X-axis direction is defined from left to right, and the positive Y-axis direction is specified from bottom to top, starting from the bottom left corner of the grid area. Define the grid length as the unit length to establish a two-dimensional coordinate plane XOY ^[16]. The following is the correspondence between the grid number and coordinates:

Figure 1.  Grid map.

DownLoad: Full-Size Img PowerPoint

In this formula, $x, y$ represents the horizontal and vertical coordinates of the grid map, $\bmod$ is a remainder operation, $W$ is the number of the grid, $N$ is the number of rows and columns in the grid, and $ceil$ is the rounding function.

3.   Introduction of A* algorithm

3.1.   A* algorithm

The A* algorithm ^[19] constitutes a heuristic search-driven routing algorithm, designed for identifying the shortest path between a given starting point and an end point within a graph (or grid) structure. This approach employs an evaluation function to assess potential pathways and subsequently opts for the most promising route based on the outcome of the evaluation. Equation (2) delineates the evaluation function employed by the A* algorithm.

where $f(n)$is the total cost of current node n, $g(n)$ is the actual cost from the starting point to node n, and $h(n)$ is the estimated cost from node n to the end point.

The algorithm maintains an open list that contains the nodes to be evaluated and a closed list that contains the evaluated nodes. The flow chart of the A* algorithm is shown in Figure 2.

Figure 2.  A* algorithm flow chart.

DownLoad: Full-Size Img PowerPoint

At present, the Euclidean distance, Manhattan distance, and Chebyshev distance are commonly used in the A* algorithm. The Euclidean distance is expressed as

The Manhattan distance is expressed as

The Chebyshev distance is expressed as

where $({x_e}, {y_e})$ is the endpoint coordinate, and $({x_n}, {y_n})$ is the current node coordinate.

3.2.   Selection of actual cost function

Given that this paper designates the AGV's movement direction on the map as comprising 8 directions, both straight-line and diagonal motions of the AGV are factored into consideration. Specifically, this study presumes the cost of straight-line motion as 1 and the cost of diagonal motion as 1.4, expressed mathematically as

where $({x_n}, {y_n})$ is the coordinates of the current node and $({x_{n + 1}}, {y_{n + 1}})$ is the coordinates of the child nodes of the current node.

3.3.   Selection of estimated cost function

The estimated cost significantly influences the search direction of the A* algorithm. An accurate estimated cost effectively gauges the expense from the present node to the destination, thereby steering the A* algorithm toward a correct search direction. The trajectories corresponding to three distinct estimated costs are illustrated in Figure 3.

Figure 3.  Comparison of paths under different estimation functions.

DownLoad: Full-Size Img PowerPoint

The evaluation criteria for the estimated cost function encompass the actual path cost, the count of turns, and the number of traversed nodes. As depicted in Figure 1, when employing Euclidean distance as the metric, the path's actual cost totals 30, involving 9 turns and traversing 117 nodes. Utilization of the Manhattan distance results in the algorithm primarily navigating through nodes during its search. Due to the sparse number of traversed nodes, the path derived from this estimation function might not necessarily represent the optimal trajectory. Specifically, the path under Manhattan distance exhibits an actual cost of 31.2, accompanied by 13 turns and 26 traversed nodes. When employing Chebyshev distance, the path incurs the highest tally of turns and traversed nodes, at 14 turns and 172 nodes, with an actual cost of 30. A comprehensive comparison of evaluation metrics under the three distinct estimated cost functions is detailed in Table 1.

Table 1.  Comparison of results.

$h(n)$	Actual cost	Number of turns	traversal nodes
Euclidean distance	30	9	117
Manhattan distance	31.2	13	26
Chebyshev distance	30	14	172

---

 | Show Table

DownLoad: CSV

To sum up, this paper selects Euclidean distance as the estimated cost function when improving the A* algorithm.

4.   Improvement of the A* algorithm

4.1.   Internal improvement of A* algorithm

1) Optimize node traversal logic. In the conventional employment of the A* algorithm for path planning, the algorithm stores the traversed nodes within a closed list. Within this list, any two nodes that share a relationship are regarded as interconnected. However, this approach can lead to an issue wherein the final planned path navigates between the vertices of two obstacles, as visually demonstrated in Figure 4. Consequently, the planned path might prove impractical for real-world applications.

Figure 4.  Schematic diagram of the path passing through the middle of the obstacle.

DownLoad: Full-Size Img PowerPoint

To address the aforementioned issues, this study enhances the node traversal logic within the traditional A* algorithm. The function ${\text{Node_traversal}}()$ is constructed. When the A* algorithm is traversing the nodes, it judges whether the upper, lower, left, and right adjacent nodes of the visited node $(i, j)$ are obstacles. When the upper and right adjacent nodes of the node are obstacles, it skips traversing the adjacent node $(i + 1, j + 1)$ in the upper right direction of the node and does not put it into the close list, so as to avoid the nodes. This adjustment prevents scenarios where paths inadvertently pass through the interstices between two obstacles located at opposing corners, as depicted in Figure 5. Under the refined node traversal logic, as the traversal progresses to node (2.5, 1.5), the presence of obstacles above and to the right of this node prevents the inclusion of point (3.5, 2.5) in the closed list.

Figure 5.  Schematic diagram of improved node traversal logic.

DownLoad: Full-Size Img PowerPoint

The pseudo code of function ${\text{Node_traversal}}()$ is shown in Algorithm 1.

In the pseudo code, the initial line defines the four cardinal directions: up, down, left, and right. The second line designates the presently traversed node, referred to as "current". Subsequently, lines 3 and 4 establish a loop to sequentially access the four adjacent nodes to the current node through the iterative process. Lines 5 and 6 are formulated to avoid traversing the upper-right node if both the upper and right sides of the current node are obstructed. Similarly, lines 7 and 8 are designed to bypass traversal of the upper-left node in scenarios where the upper and left sides of the current node are obstructed. Analogously, lines 9 and 10, as well as lines 11 and 12, serve to prevent traversal of the lower-right and lower-left nodes, respectively, under conditions where the corresponding sides of the current node are occupied by obstacles.

The improved A* algorithm successfully mitigates the challenge of navigating through the vertices within obstacles, thereby enabling the A* algorithm to formulate a more rational path. The operational outcome of the improved A* approach is visually illustrated in Figure 6. Notably, as demonstrated in the figure, when the node's traversal reaches the coordinates (10.5, 11.5), the search does not encompass a node located at (11.5, 12.5).

Figure 6.  Algorithm running results of improved node traversal logic.

DownLoad: Full-Size Img PowerPoint

2) Replacing the conventional cost estimation function. While the A* algorithm utilizing Euclidean distance can find the shortest path with fewer traversed nodes, it might result in a higher number of turns within the path, as illustrated in Figure 7.

Figure 7.  Path under euclidean distance.

DownLoad: Full-Size Img PowerPoint

Under such circumstances, the smooth operation of the AGV would be compromised. Therefore, this study replaces the Euclidean distance with diagonal distance in order to achieve a more accurate representation of the cost estimation function from the current point to the destination. This enhancement better guides the A* algorithm in finding the optimal path. The formula for diagonal distance is as follows:

Among these, ${h_d}$ represents the cost in the diagonal direction, ${h_s}$ represents the cost in the straight line direction, $({x_n}, {y_n})$ represents the current node coordinate, $({x_e}, {y_e})$ represents the target node coordinate, ${h_{total}}$ represents the diagonal distance calculation formula, and ${D_1}$, ${D_2}$ represent parameters, where ${D_1}$ is 1 and ${D_2}$ is 1.4.

Upon employing diagonal distance, the planned path effectively reduces the count of redundant turns and the number of traversed nodes, as depicted in Figure 8.

Figure 8.  Paths under diagonal distance.

DownLoad: Full-Size Img PowerPoint

3) Increase the cost of turning. The conventional A* algorithm predominantly employs length as the primary criterion, prioritizing the attainment of the shortest overall distance as the optimal path. However, an exclusive focus on minimizing length may result in frequent turns by the AGV during its movement. In practical scenarios, the act of acceleration and deceleration during turning substantially escalates the time expense, rendering it considerably higher than that incurred during linear motion. This divergence in time costs undermines overall efficiency and hampers the attainment of a smooth path. To address this concern, this paper introduces an enhancement to the calculation formula of the conventional A* algorithm. This enhancement entails the incorporation of a turning cost into the original calculation formula. By introducing this turning cost, the aim is to curtail the frequency of turns within the path, thereby fostering a more streamlined trajectory.

When accounting for the turning cost, it becomes imperative to initially assess the occurrence of a turn. In this investigation, the analysis employs the three-point collinear method for turn detection. This method involves utilizing three nodes and applying Eq (8) to perform the calculation.

where $({x_{n - 1}}, {y_{n - 1}})$ is the parent node of the current node, $({x_n}, {y_n})$ is the current node, and $({x_{n + 1}}, {y_{n + 1}})$ is the current node sub node. The node relationship is shown in Figure 9.

Figure 9.  Node relationship.

DownLoad: Full-Size Img PowerPoint

For a straight-line path, Eq (8) yields a K value of 0. However, during turning maneuvers, distinct K values emerge. Specifically, based on the outcomes of Eq (8), a left turn corresponds to a K value of -1, while a right turn corresponds to a K value of 1. In this study, the costs associated with left and right turns are not individually considered, but rather are collectively regarded as turning costs. Consequently, the expression for the C value is illustrated in Eq (9).

where $C$ is the turning cost.

To sum up, the improved A* formula is:

Under these conditions, the A* algorithm with improved heuristic function will give priority to traversing nodes in the current direction during the node search process, which will minimize the exploration of nodes in other directions. In Figure 10, the concept is displayed. Figure 10(a), (b) depict the search procedure using conventional heuristic functions and weighted heuristic functions, respectively. It is evident that node (2.5, 1.5) determines which child nodes are selected differently between the two. When choosing child nodes, weighted heuristic functions incur a higher cost at point (2.5, 2.5) since (2.5, 1.5) is the turning point, whereas traditional heuristic functions execute a turning point at node (2.5, 1.5). Therefore, the weighted heuristic functions continue to search in the original direction, reducing the number of turning points and traversing nodes in the path.

Figure 10.  Weighted heuristic function search process.

DownLoad: Full-Size Img PowerPoint

4.2.   External improvement of the A* algorithm

The objective of this section is to conduct further path optimization based on the output path generated by the A* algorithm. This process is chiefly divided into two primary steps: Path Optimization: Initially, the path is optimized to eliminate extraneous turning points present within it; Bezier Curve Fitting: Subsequently, the remaining turning points are subjected to a fitting process using Bezier curves.

1) Path optimization

While the internal enhancements applied to the A* algorithm effectively curtail the occurrence of turns within the path, it is important to acknowledge that the path's optimality remains contingent on the constraints of the grid map. Consequently, the resultant path might not always be the absolute optimal solution, and some degree of turns may still persist. As illustrated in Figure 11, an excessive number of turns can extend the logistics duration, thereby substantially diminishing logistics efficiency within the production workshop setting.

Figure 11.  Grid map restrictions.

DownLoad: Full-Size Img PowerPoint

To solve this problem, this paper adopts a path optimization method based on forward search optimization ^[25]. The optimization process of this method is shown in Figure 12: First, define the set of input path nodes. Then, take the starting node of the path as the current vertex, search the subsequent path nodes, find the last key node ${k_1}$ connected with the starting point (connectivity means that the connection between the starting point and ${k_1}$ point does not pass through obstacles), connect the starting point with ${k_1}$, then take ${k_1}$ as the starting point, search the points after ${k_1}$ with the same logic, and set these key points to ${k_2}$, ${k_3}$ in turn. Then, insert the sampling point ${s_i}$ on the path, take ${s_{10}}$ (the ${k_2}$ point in the previous step) as the current key point, and check whether the connection between ${s_1} - {s_5}$ and ${s_{10}}$ will pass through obstacles. If there are none, take ${s_{13}}$ (the ${k_3}$ point in the previous step) as the current key point, and check whether the connection between ${s_1} - {s_9}$ and ${s_{10}}$ will pass through obstacles. Since point ${s_7}$ is the first point that can be connected with ${s_{13}}$, ${s_7}$ is taken as the new key point ${k_2}$. Then, connect ${s_7}$ and ${s_{13}}$ to form the second optimization path, and ${s_1} - {s_7}$ is optimized by using similar methods. Finally, the final optimization path is obtained.

Figure 12.  Process diagram of forward search optimization method.

DownLoad: Full-Size Img PowerPoint

While the concept behind the path optimization method is viable, the execution process proves excessively intricate. Consequently, this paper introduces an improved forward search optimization approach. This improved method is primarily segmented into the subsequent steps:

Step 1. The output path set $P = ([{x_1}, {y_1}], [x{}_2, {y_2}], \cdots, [{x_i}, {y_i}])$ of the A* algorithm is interpolated. The interpolation method employed here is uniform interpolation, wherein a new node is inserted between two given points. This process can be mathematically represented as

where $({x_{new}}, {y_{new}})$ are the coordinates of the inserted new node, $({x_n}, {y_n})$ are the coordinates of the current node, and $({x_{n + 1}}, {y_{n + 1}})$ are the coordinates of the child nodes of the current node.

Take the interpolated path set ${P_{new}} = ([{x_1}, {y_1}], [x{}_{new}, {y_{new}}], [x{}_2, {y_2}], \cdots, [{x_i}, {y_i}])$ as a new path set.

Step 2. Construct a key point set $K$ and an obstacle vertex set $Ovc$. Starting from the initial point, perform a forward search to identify the first point connected to the initial point and also present in the set $Ovc$. Label this point as ${k_1}$ and add it to $K$.

Step 3. Set ${k_1}$ as the new starting point, repeat Step 2, and designate the subsequent points as ${k_2}, {k_3}, \cdots, {k_i}$, with $i$ representing the number of key points.

Step 4. Repeat Step 3 to obtain the final set of key points, denoted as $K$.

Step 5. Connect all key points in $K$ to achieve path optimization.

The process diagram of the improved forward search optimization method proposed in this paper is shown in Figure 13.

Figure 13.  Process diagram of the improved forward search optimization method in this paper.

DownLoad: Full-Size Img PowerPoint

The pseudo code is shown in Algorithm 2

In the pseudo code of Algorithm 2, lines 1 to 12 correspond to the process in Step 1. Lines 13 to 26 correspond to the process in Steps 2–4. The $line(start, p\_new[j])$ function is used to determine whether $start$ points are connected with $p\_new[j]$ points.

2) Path smoothing

The smoothing of the path refers to the use of Bezier curves, spline interpolation curves, and other methods to fit the path by using the curve to improve the smoothness of the path.

Although the optimized path greatly reduces turning, the turning point intersects with the vertex of the obstacle, and the AGV may collide with the obstacle when passing by. Therefore, the path must be adjusted for obstacle avoidance before curve fitting.

First, the relationship between the optimized path and the nearby obstacles is analyzed, as shown in Figure 14, where the gray grid indicates the location of the possible obstacles.

Figure 14.  Schematic diagram of grid with possible obstacles around.

DownLoad: Full-Size Img PowerPoint

Based on this, to ensure a certain safe distance between the path and the obstacle, the obstacle avoidance adjustment process proposed in this paper is presented as follows:

Step 1. Calculate the direction vector of ${k_1}$ and obstacle coordinates according to Eq (12).

where $\vec a$ is the direction vector, $({x_{{\text{obstacle}}}}, {y_{{\text{obstacle}}}})$ is the obstacle coordinate, and $({x_{{k_1}}}, {y_{{k_1}}})$ is the ${k_1}$ coordinate.

Step 2. Move one half of the grid distance in the opposite direction of ${k_1}$ along the direction vector as follows:

where $({x_{{k_1}\_n}}, {y_{_{{k_1}\_n}}})$ represents the new coordinates of ${k_1}$, and $L$ represents the width of the grid.

Step 3. Update ${k_1}$ coordinates, build the linear equation from the starting point to ${k_1}$, and assess the distance between the obstacle coordinates and the straight line. When the distance is less than $L$, set the nearest vertex from the obstacle to the straight line to ${k_{insert}}$ and repeat Steps 1 and 2. At this time, ${k_1}$ in Steps 1 and 2 is ${k_{insert}}$, and the obstacle avoidance of the path is completed. ${k_{insert}}$ is located between the starting point and ${k_1}$.

Step 4. After completing the obstacle avoidance operation from the starting point to ${k_1}$, make ${k_1}$ a new starting point and repeat Steps 1 to 3 to complete the obstacle avoidance of the entire road.

The process is shown in Figure 15.

Figure 15.  Path after obstacle avoidance.

DownLoad: Full-Size Img PowerPoint

Then, the second-order Bezier curve is used to fit the rotation angle. The second-order Bezier curve is mathematically expressed as

where ${P_0}$, ${P_1}$, and ${P_2}$ are the three control points, and $t$ is a parameter.

In this paper, the selection method of control points ${P_0}$ and ${P_2}$ is explained as follows. First, calculate the direction vectors of ${k_{insert}}$ and ${k_1}$ coordinates and the starting line and the next node line. Second, use a similar method in obstacle avoidance adjustment to select ${P_0}$ and ${P_2}$ control points on the two paths with length $L$ as the distance. Finally, ${k_{insert}}$ and ${k_1}$ are used as ${P_1}$ control points to achieve curve fitting at turns, as shown in Figure 16.

Figure 16.  Path after curve fitting.

DownLoad: Full-Size Img PowerPoint

4.3.   Path planning method based on the improved A* algorithm

After improving the traditional A* algorithm in Sections 4.1 and 4.2, the AGV path planning method based on the improved A* algorithm can be illustrated by the flow chart in Figure 17.

Figure 17.  Flow chart of the AGV path planning method based on the improved A* algorithm.

DownLoad: Full-Size Img PowerPoint

5.   Simulation experiments and analyses

Comprehensive experiments were conducted on the Pycharm 2022.3 platform. The programming language is Python 3.10. The performance of the proposed improved A* algorithm was tested, and the framework used by the DQN network was TensorFlow. The performance parameters of the execution host are Windows 10, and the hardware parameters are Intel(R) core(TM) i5-8250U CPU, 1.6 GHz, x64, 8 GB (RAM).

5.1.   Experimental map and evaluation index

The obstacles in the production workshop are each production area. These production areas are usually large in area and simple in shape. Therefore, this article simulates and constructs maps with sizes of 20 × 20, 30 × 30, and 40 × 40 based on the characteristics of obstacles in the production workshop, as shown in Figure 18.

Figure 18.  Grid map used in the experiment.

DownLoad: Full-Size Img PowerPoint

This study uses path length, turning angle, number of traversal nodes, and algorithm running time as evaluation indices. The length of the path indicates the true cost of the path. The turning angle is the total of the degrees the AGV must turn in order to travel down the course. The number of nodes that the algorithm traverses in order to locate the path is represented by the number of traversal nodes. The algorithm's running time shows how long the path is searched throughout that period.

This paper uses both theoretical and simulated experiments for its experimental section. In the theoretical experimental part, the internal improved A* algorithm is first compared with other algorithms, and then the improved forward search optimization algorithm is verified. A custom path planner in the ROS system is used in the simulation experiment section of this article to use the traditional A* algorithm, internally improved A* algorithm, and improved A* algorithm as plugins. Simulation verification is carried out by calling algorithm plugins.

5.2.   Theoretical experiments

5.2.1.   Performance verification of internal improved A* algorithm

The algorithms involved in the comparison include the traditional A* algorithm, Dijkstra algorithm, bidirectional A* algorithm, ant colony algorithm, DQN algorithm, and the internal improved A* algorithm in this paper. The starting point is the (0.5, 0.5) point, and the ending point is the point in the upper right corner. The cyan and red grids in the grid graph represent the traversed nodes. The parameters of the ant colony algorithm are shown in Table 2, and the parameters of the DQN algorithm are shown in Table 3.

Table 2.  Ant colony algorithm parameters.

parameter	value
Number of ants	20
Number of iterations	150
Pheromone evaporation rate	0.5
pheromone factor	1.1
heuristic function factor	4

---

 | Show Table

DownLoad: CSV

Table 3.  DQN algorithm parameters.

parameter	value
Learning rate	0.001
Discount factor	0.995
Exploration rate	0.4
Batch size	64

---

 | Show Table

DownLoad: CSV

As shown in Figure 19, when comparing the ant colony method to other algorithms at a 20 × 20 grid map, it yielded the longest path length, with the other algorithms obtaining the same path length. The turning angle of the traditional A*, bidirectional A*, ant colony algorithm, DQN algorithm, and Dijkstra method has grown by 135,135,315,135, and 90°, respectively. The ant colony algorithm and DQN algorithm have distinct search algorithms from the others, therefore, the indicator of the number of traversal nodes is not considered, however, the traditional A* algorithm, bidirectional A* algorithm, and Dijkstra algorithm have increased by 43, 35, and 285, respectively. Algorithm running times rose by 0.51 s for the traditional A* algorithm, 0.24 s for the bidirectional A* method, 4.59 s for the ant colony algorithm, 4.33 s for the DQN algorithm, and 1.59 s for the Dijkstra algorithm.

Figure 19.  20 × 20 comparison of results in the map.

DownLoad: Full-Size Img PowerPoint

As shown in Figure 20, the conventional A* algorithm outperforms the internal improved A* algorithm on a 30 × 30 grid map in terms of path length, number of traversed nodes, and algorithm running time. The bidirectional A* algorithm outperforms the internal improved A* algorithm in terms of both these metrics. The ant colony and DQN algorithms outperform the internal improved A* algorithm in terms of path length. Although in some indicators the comparison algorithm outperforms the internal improved A* algorithm, the comparison algorithm's planned path, which goes from nodes (20.5, 19.5) to (21.5, 20.5), diagonally passes through two obstacle nodes (20.5, 20.5) and (19.5, 21.5), making the expected path AGV invalid. This illustration confirms that the A* algorithm's internal improvement can prevent the creation of erroneous pathways.

Figure 20.  30 × 30 comparison of results in the map.

DownLoad: Full-Size Img PowerPoint

As shown in Figure 21, the ant colony algorithm produced the longest path length on a 40 × 40 grid map when compared to other algorithms, and the other algorithms produced the same path length. The turning angle of the traditional A*, bidirectional A*, ant colony algorithm, DQN algorithm, and the Dijkstra algorithm has risen by 135,315,360,225, and 45°, respectively. Regarding traversing the number of nodes, the traditional A* algorithm, bidirectional A* algorithm, and Dijkstra algorithm have increased by 12, 87, and 863 respectively; however, there is no need to traverse the number of nodes because the ant colony algorithm and DQN algorithm have different search mechanisms than the others. Algorithm running times rose by 0.76 s for the traditional A* algorithm, 0.47 s for the bidirectional A* method, 10.47 s for the ant colony algorithm, 9.54 s for the DQN algorithm, and 2.05 s for the Dijkstra algorithm.

Figure 21.  40 × 40 comparison of results in the map.

DownLoad: Full-Size Img PowerPoint

The specific experimental results of each algorithm are shown in Table 4.

Table 4.  Comparison of results in different environments.

Map	Algorithm	Length	Turning angle	Number of traversal nodes	Algorithm run time
20 × 20	Traditional A*	30.2	270°	104	1.29 s
	Bidirectional A*	30.2	270°	96	1.02 s
	Ant Colony	31.6	450°	\	5.37 s
	DQN	30.2	270°	\	5.11 s
	Dijk stra	30.2	225°	346	2.37 s
	Internally improved A*	30.2	135°	61	0.78 s
30 × 30	Traditional A*	43.6	360°	151	1.35 s
	Bidirectional A*	45.4	315°	162	1.24 s
	Ant Colony	43.6	540°	\	8.32 s
	DQN	43.6	225°	\	9.43 s
	Dijk stra	43.6	405°	764	2.43 s
	Internally improved A*	45.4	225°	206	1.34 s
40 × 40	Traditional A*	60.6	270°	362	2.32 s
	Bidirectional A*	65.2	450°	437	2.03 s
	Ant Colony	68.6	495°	\	12.03 s
	DQN	65.4	360°	\	11.10 s
	Dijk stra	62.2	180°	1213	3.61 s
	Internally improved A*	60.6	135°	350	1.56 s

---

 | Show Table

DownLoad: CSV

In summary, this comparison demonstrates the usefulness of the internal modification of the A* algorithm in this work by demonstrating the modified algorithm's good performance in terms of path length, turning angle, number of traversal nodes, and algorithm running time.

5.2.2.   Path optimization and smoothness verification

This part is dedicated to path optimization and smoothing verification. The path generated by the internally enhanced A* algorithm serves as the initial path input and is subsequently smoothed and optimized. The comparative algorithms are the internally enhanced A* algorithm and the improved A* algorithm (with both external and internal enhancements). The turning angle and length of the path act as assessment marks. In Figure 22, the blue dotted line represents the initial path, the green dotted line represents the optimized path, and the red solid line represents the final smoothed path.

Figure 22.  Path optimization and smoothing verification.

DownLoad: Full-Size Img PowerPoint

As can be seen from Table 5, based on the internal improved A* algorithm, after optimizing and smoothing the path, the path length and turning angle obtained are both shorter than the path obtained by the internal improved A* algorithm. In the 20 × 20 map, compared with the internal improved A* algorithm results, the final improved A* algorithm path length is reduced by 4.4, and the turning angle is reduced by 88.49°. In the 30 × 30 map, compared with the internal improved A* algorithm results, the final improved A* algorithm path length is reduced by 4.7, and the turning angle is reduced by 176.79°. In the 40 × 40 map, compared with the internal improved A* algorithm results, the final improved A* algorithm path length is reduced by 5.2, and the turning angle is reduced by 85.69°. It shows that the improved A* algorithm proposed in this article can effectively reduce the length of the path and the turning angle in the path, and can effectively reduce the distance and steering angle of the AGV, ensuring the smoothness of AGV driving.

Table 5.  Comparison of path optimization and smoothing results.

Map	Algorithm	Length	Turning angle
20 × 20	Internally improved A*	30.2	135°
	Improved A*	25.8	46.51°
30 × 30	Internally improved A*	45.4	225°
	Improved A*	40.7	48.21°
40 × 40	Internally improved A*	60.6	135°
	Improved A*	55.4	49.31°

---

 | Show Table

DownLoad: CSV

5.3.   Simulated experiments

This article's suggested algorithm has been verified in ROS. Using the 20 × 20 map as an example, just the essential components of the map were built during the modeling of the map SLAM technique in order to conserve computing power. Figure 23 displays the simulation results. The path is represented by the green line, open space is represented by the gray section, and obstacle boundaries are displayed by the black part.

Figure 23.  Simulation results.

DownLoad: Full-Size Img PowerPoint

The paths designed by the conventional A* algorithm are depicted in Figure 23(a), the internally improved A* method in Figure 23(b), and the improved A* algorithm in Figure 23(c). The three paths take the AGV 21, 15, and 9 seconds to complete, respectively. This demonstrates that the path quality predicted by the revised A* method put forth in this research is high, which can shorten the AGV's running time and increase its effectiveness.

6.   Conclusions

Although the A* algorithm has the advantages of being a simple algorithm and having a fast search speed, the planned path may involve more turns and the path may not be smooth enough. In order to solve this problem, this paper improves the internal and external properties of the traditional A* algorithm. The node traversal logic of the A* algorithm is internally optimized to avoid the path passing between two obstacle vertices. Subsequently, the cost estimation function was modified to replace the traditional Euclidean distance with the diagonal distance, thereby improving the accuracy of cost prediction. This adjustment effectively reduces the number of redundant turns within the path. Then, the weight of the cost estimation function of the A* algorithm is added to give priority to the current search direction when finding a path, thereby reducing the number of nodes traversed and the number of turns compared to the traditional A* algorithm. Finally, a path optimization smoothing method based on the improved forward search optimization method and Bezier curve method is proposed. This method is used in addition to the A* algorithm to eliminate redundant turning points in the path and perform curve fitting at turns to improve the smoothness of the path.

Finally, the experimental results show that the internal modification of the A* algorithm avoids planning invalid paths, reduces the number of turns, reduces the number of traversed nodes, and shortens the search time. After external modifications to the A* algorithm, the number of turns in the path is further reduced and the length of the path is shortened.

Although the path planning method based on the improved A* algorithm proposed in this article can effectively make up for the shortcomings of the traditional A* algorithm, it still encounters some shortcomings and defects:

1) In the actual workshop environment, the location of obstacles cannot be accurately located, but dynamic obstacles may appear, and the method proposed in this article is based on the path planning method in a static obstacle environment.

2) The improved A* algorithm proposed in this article is suitable for environments with concentrated obstacles such as workshops, but is not suitable for areas with many and scattered obstacles, such as in warehousing environments.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors thank the anonymous reviewers for their valuable comments. This work was supported by high level Project of Shihezi University (No. RCZK2021B16); The high-level project led by Professor Baoqin Wen at Shihezi University (No. RCZK202310).

Conflict of interest

The authors declare there is no conflict of interest