A route planning for oil sample transportation based on improved A* algorithm Authors: Yingjun Sang, Xianyan Chen, Quanyu Chen, Jinglei Tao, Yuanyuan Fan Published: 2023 ABSTRACT AbstractThe traditional A* algorithm suffers from issues such as sharp turning points in the path, weak directional guidance during the search, and a large number of computed nodes. To address these problems, a modified approach called the Directional Search A* algorithm along with a path smoothing technique has been proposed. Firstly, the Directional Search A* algorithm introduces an angle constraint condition through the evaluation function. By converting sharp turns into obtuse angles, the path turning points become smoother. This approach reduces the occurrence of sharp turns in the path, resulting in improved path smoothness. Secondly, the algorithm enhances the distance function to strengthen the directional guidance during the path search. By optimizing the distance function, the algorithm tends to prefer directions that lead towards the target, which helps reduce the search space and shorten the overall path planning time. Additionally, the algorithm removes redundant nodes along the path, resulting in a more concise path representation. Lastly, the algorithm proposes an improved step size adjustment method to optimize the number of path nodes obtained. By appropriately adjusting the step size, the algorithm further reduces the number of nodes, leading to improved path planning efficiency. By applying these methods together, the Directional Search A* algorithm effectively addresses the limitations of the traditional A* algorithm and produces smoother and more efficient path planning results. Simulation experiments comparing the modified A* algorithm with the traditional A* algorithm were conducted using MATLAB. The experimental results demonstrate that the improved A* algorithm can generate shorter paths, with reduced planning time and smoother trajectories. This indicates that the Directional Search A* algorithm, incorporating the angle constraint condition in the evaluation function and the direction-guided strategy, outperforms the traditional A* algorithm in path planning and provides better solutions to the existing issues.Subject terms: Chemical engineering, Engineering, Mathematics and computing Introduction The optimization of robot path planning algorithms is primarily aimed at improving the performance and efficiency of robots in practical applications. By optimizing the path planning algorithm, robots can reach their target locations faster, thereby enhancing the overall efficiency and accuracy of the motion process1. Additionally, optimizing path planning algorithms can assist robots in selecting the shortest and most economical paths when performing tasks, thus reducing the cost of robot movements. Furthermore, optimizing path planning algorithms can help robots avoid collisions with obstacles and hazardous areas, thereby enhancing robot safety2. By optimizing robot path planning algorithms, we can better meet the requirements of real-world applications and drive the development and application of robot technology. The first-generation industrial robots used a coordinate transformation-based approach to control the execution trajectory3. This method performed well for straightforward tasks but encountered challenges in ensuring precision and stability within intricate environments and tasks. To tackle this predicament, researchers commenced their exploration of robot path planning algorithms. Initially, robot path planning algorithms primarily relied on geometric models to calculate the robotic motion trajectory, such as straight-line and circular arc methods4,5. These algorithms could simply describe the robot’s motion path but proved ineffective in handling complex objects or spatial obstacles. Over the next few decades, an increasing number of researchers delved into advanced algorithms to adapt to the complexity of work environments. Techniques like graph theory, search algorithms, and artificial intelligence were used for path planning. Algorithms such as A*, Dijkstra’s algorithm, Rapidly-exploring Random Trees (RRT), and Probabilistic Roadmaps (PRM) gained widespread application6. In recent years, with the development of deep learning technology, artificial neural networks have been introduced to the field of robot path planning. Training neural networks enables more intelligent and efficient path planning7. These algorithms not only improve the speed and accuracy of robot path planning but also enable adaptive adjustment of path planning strategies within complex environments, allowing robots to better adapt to various working conditions. The traditional A* algorithm commonly uses Manhattan distance and Euclidean distance8. The Manhattan distance is obtained by summing the absolute differences in x and y values between the expanding node and the target node, which can result in an overestimation of h(n). On the other hand, the Euclidean distance is the straight-line distance from the expanding node to the target node, leading to an underestimation of h(n). Li et al.9 adopted the second-order Bessel curve function as the heuristic function to meet the requirements of smooth path planning. Although the resulting path is smoother, it tends to approximate the second-order Bézier curve and may not align well with the actual scene. Therefore, adding corner constraints can not only maintain stable driving in path planning, but also adjust the path reasonably according to the actual environment. This ensures that the planned path is not only smooth but also compatible with the real-world scenario. With the advancement of deep learning technology, an increasing number of researchers are turning to neural networks for robot path planning10. These methods require less manual design and can directly learn appropriate planning strategies based on input data, resulting in higher accuracy and efficiency. Integrated with environment perception, path planning that leverages neural networks involves real-time monitoring and analysis of the surroundings, enabling more intelligent decision-making in path planning11. However, neural networks rely heavily on training data to build models. This data needs to encompass various scenarios and complex traffic situations. If the collected data is insufficient or limited, the predictive capability of the neural network will be greatly affected, leading to unreliable path planning results12. Moreover, the training data for neural networks often comes from a series of classical path planning algorithms. To obtain better paths, improvements must be made to these classical algorithms to generate superior training data. Therefore, it is necessary to enhance the A* algorithm to achieve optimal path planning results. The main research content of this paper can be summarized as follows: Introduction of Angle Constraint in the Heuristic Function: The manuscript posits the integration of an angle constraint into the heuristic function, with the intent of refining the path, diminishing path length, curtailing path search duration, and enhancing obstacle avoidance proficiency. By conscientiously considering the angles between consecutive path segments, the algorithm aspires to engender pathways that are both more efficient and more attainable. Introduction of Angle Constraint in the Heuristic Function: The manuscript posits the integration of an angle constraint into the heuristic function, with the intent of refining the path, diminishing path length, curtailing path search duration, and enhancing obstacle avoidance proficiency. By conscientiously considering the angles between consecutive path segments, the algorithm aspires to engender pathways that are both more efficient and more attainable. Path Search Direction Guidance Strategy: The paper introduces a path search direction guidance strategy to help the algorithm quickly determine the search direction, avoiding repetitive searching of feasible points due to obstacles. This strategy not only amplifies the efficiency of the search but also prevents the algorithm from getting trapped in local optima or deadlock situations, thus ensuring the possibility of obtaining globally optimal solutions. Path Search Direction Guidance Strategy: The paper introduces a path search direction guidance strategy to help the algorithm quickly determine the search direction, avoiding repetitive searching of feasible points due to obstacles. This strategy not only amplifies the efficiency of the search but also prevents the algorithm from getting trapped in local optima or deadlock situations, thus ensuring the possibility of obtaining globally optimal solutions. Improved Path Search Step Size: The paper highlights the importance of adjusting the path search step size to enhance search efficiency, save computational resources, improve search accuracy, and make the algorithm more suitable for complex environments. By dynamically adapting the step size based on the local environment, the algorithm can effectively navigate through obstacles and find optimal paths. Improved Path Search Step Size: The paper highlights the importance of adjusting the path search step size to enhance search efficiency, save computational resources, improve search accuracy, and make the algorithm more suitable for complex environments. By dynamically adapting the step size based on the local environment, the algorithm can effectively navigate through obstacles and find optimal paths. The remaining sections of the paper are structured as follows: Section “Background” provides an overview of the research context and background. Section “Optimize A * algorithm” presents the theoretical foundations and methodologies of the improved A* algorithm. Section “Simulation analysis” describes the simulation experiments conducted to validate the feasibility and effectiveness of the proposed algorithm enhancements. Section “Conclusion” discusses potential future research directions and offers recommendations for further improvements. Background In the petrochemical industry, petroleum testing plays a crucial role in detecting and analyzing the physical and chemical characteristics of petroleum and its derivatives. It helps in formulating production and processing strategies to ensure product quality and safety. Petroleum testing often involves multiple testing parameters, which may have complex interdependence and specific sequential requirements. Additionally, petroleum samples need to be transported to multiple destinations. Therefore, path planning for robots in petroleum testing becomes necessary to determine the optimal transport routes, aiming to enhance the efficiency and accuracy of petroleum testing. With the continuous development of computer technology and artificial intelligence, robot path planning techniques can now be automated and intelligent through the use of models and algorithms13. This brings more convenience and benefits to industrial production. Currently, petroleum samples in chemical plants are still collected manually. However, due to the presence of hazardous areas and hard-to-reach locations in petrochemical plants, manual sampling is difficult, time-consuming, and poses high risk. Therefore, in order to enhance the level of intelligence in the petroleum testing process, reduce labor intensity, and improve efficiency, we propose using robots to replace manual labor in the transportation of petroleum samples14. Additionally, during robot path planning, we will consider the environmental characteristics of the petrochemical plant. This approach allows the transportation robot to play a crucial role in petroleum sampling. Many scholars have conducted research on optimizing robot path planning. Susan Sorensen et al. focused on the multi-track routing and scheduling optimization problem for in-orbit refueling space robots15. The objective of this problem is to enable a group of highly maneuverable and refuelable space robots to complete a set of tasks on space orbits through optimal path planning and task allocation. To address this problem, the researchers adopted a mixed-integer linear programming approach and evaluated the quality of solutions by maximizing the weighted number of completed tasks. Through case studies and the use of data from satellites operating in different Earth orbits, the researchers demonstrated algorithms for constructing networks and models. They also proved that considering strategies involving multiple orbits is beneficial when it comes to robot motion, the number of refueling stations, and task dependencies. Overall, their research provides insights into optimizing path planning and scheduling for space robots performing complex tasks such as in-orbit refueling. Li et al.16 proposed an improved Iterative Greedy (IIG) algorithm for the multi-factory robot scheduling problem. They primarily focused on the distributed flow shop problem with order constraints, where jobs of the same production order need to be assigned to the same factory. The algorithm also takes into account deteriorating time limits to minimize job completion time in the factories. Lu et al. proposed a multi-AGV scheduling method considering allocation rules for automatic guided vehicles (AGVs) due to the increase in workload leading to conflicts and deadlocks, and designed a phase conflict avoidance method to generate conflict-free working routes for AGVs in automated warehouses with multiple workstations17. Nguyen et al. proposed a path optimization method for the lower limit of logistics distribution vehicle capacity in their research, which can help the company achieve a lot of operating cost savings18. By optimizing the route planning of vehicles, this method can ensure that the loading capacity of each vehicle is not lower than the set lower limit, thereby improving transportation efficiency and resource utilization. The application of this method can help logistics companies to arrange delivery vehicles more effectively and reduce operating costs. Path planning constitutes a formidable challenge within the realm of oil sample transportation, owing to its time-intensive and computationally demanding nature in practical implementations. Ensuring efficiency and quality remains a formidable task. Therefore, it is of great significance to realize high-quality path planning technology for oil sample transportation19,20. Although there are a large number of literatures for reference, the current oil sampling is mainly realized manually, and the research on the path planning of the robot in the process of oil sample transportation is still relatively weak. This paper proposes an A* algorithm for oil sample transportation path optimization. The algorithm first introduces the angle constraint condition to make the turning of the path smoother. Secondly, the distance function of A* algorithm is improved to enhance the direction of path search and shorten the path planning time. Finally, the path-finding step size of the algorithm is adjusted to reduce the amount of calculation and improve the efficiency of oil sample transportation. These improvements have raised the application of A* algorithm in oil sample transportation to a new level. The algorithm optimization block diagram proposed in this paper is shown in Fig. 1, which can get a path with short planning time, short path length and high smoothness. These optimization schemes make the A* algorithm more applicable and efficient in the transportation of oil samples. Block diagram of algorithm optimization. Optimize A * algorithm The A* algorithm is a heuristic path-finding algorithm used to compute optimal paths in a static two-dimensional space. It combines the global path-planning algorithm Dijkstra's algorithm with the heuristic best-first search algorithm BFS, using a cost evaluation function as the evaluation metric, where a smaller function value indicates a more optimal path node. The algorithm forms the optimal path by progressively selecting the most optimal nodes. The cost evaluation function is as follows: where F(n) is the cost evaluation function of the current position n, h(n) is the actual cost of the robot from the initial position to the current position n, and g(n) is the estimated cost of the robot from the current position n to the target position. The size of F(n) will directly determine the selection of the optimal path node, thus affecting the path planning effect of A * algorithm. The choice of g(n) will also indirectly affect the path planning efficiency of A * algorithm. The closer the value is to the actual value, the higher the chance of successful path search. In the grid map environment, there are three distance models: Manhattan distance Manhattan distance The distance between two nodes is represented by the sum of the distances in the horizontal and vertical directions. It is calculated as the absolute difference between the x-coordinates plus the absolute difference between the y-coordinates of the two nodes. where “x” represents the horizontal coordinate and “y” represents the vertical coordinate. “1” and “2” represent two different location nodes. When considering only the four directions of movement for the robot (up, down, left, right), the Manhattan distance can be used. (2)Chebyshev Distance: Chebyshev Distance: The distance between two nodes is represented by the maximum of the absolute difference between their x-coordinates and the absolute difference between their y-coordinates. It calculates the maximum vertical or horizontal moves required to reach one node from the other. When considering the robot's movement in all eight directions (diagonal, vertical, and horizontal), the Chebyshev distance can be used. (3)Euclidean Distance: Euclidean Distance: The distance between two nodes is represented by the square root of the sum of the squares of the differences between their x-coordinates and y-coordinates. It calculates the straight-line distance between the two points in a two-dimensional plane. When the robot can move in any direction randomly, the Euclidean distance can be used. A* algorithm is widely used in the field of robot path planning. However, when applying this algorithm to petroleum laboratory scenarios, there may be some issues with the generated paths, such as excessive curvature, long planning time, and weak directionality in path searching. Therefore, it is necessary to optimize this algorithm to meet the specific requirements of petroleum sample transportation. Corner constraint In petroleum sample transportation, the original A* algorithm's heuristic function only considers distance cost constraints without taking into account the turning cost constraints during the path. This can lead to issues where the generated path has excessively sharp turns, which can impact the effectiveness of the vehicle's movement. In segments with right-angle turns, the vehicle needs to decelerate before accelerating to pass through. The sharper the turn, the longer the time required for the vehicle to complete the turn, reducing overall efficiency and safety. Additionally, due to the limitations of the vehicle’s steering mechanism, it cannot perform excessively sharp turns. Therefore, it is necessary to optimize the path planning of the A* algorithm to alleviate this situation. By considering special considerations for right-angle turns in the path, the path can be made smoother, thereby improving efficiency and safety in petroleum sample transportation. where F(n) is the estimated cost of the best path from the initial node to the end point; h(n) is the estimated cost from the initial node to the node n; g(n) is the estimated cost from the node n to the target node; p(θ) is the corner constraint condition function, and θ is the number of internal angles formed by three consecutive nodes. By incorporating angle constraints into the heuristic function of the A* algorithm, we can optimize the path planning to achieve obtuse-angle turns, as shown in Fig. 2. This optimization helps reduce the turning time and cost for the vehicle while ensuring smoother and more efficient paths. With this optimization, the path planning in petroleum sample transportation can better adapt to the vehicle's steering mechanism and driving requirements, thereby improving overall efficiency and safety. Block diagram of evaluation function optimization. At the right-angle turn depicted in Fig. 3, the vehicle needs to undergo uniform deceleration. As it approaches the corner, the vehicle gradually reduces its speed to bring it to a complete stop before initiating the turn, ensuring a smooth and safe passage through that segment. This process of uniform deceleration takes into consideration factors such as the vehicle’s turning radius, velocity, and steering inertia to ensure smooth and safe travel. Let v0 be the initial speed of the trolley, x be the braking distance, and t1 be the braking time. Improved A* algorithm bending calculation chart. The braking time of the car is: When x > 3, Starting from the turning point, the vehicle undergoes uniform acceleration until it reaches its original speed, and then continues to travel at a constant velocity until reaching the intersection point where the improved path intersects with the original path. The time it takes for the vehicle to accelerate from the turning point until it reaches its original speed is denoted as t2. This point where the improved path intersects with the original path is called the intersection point. Let t2 the time to accelerate from the inflection point to v0. . When x = 3, From the turning point, the vehicle undergoes uniform acceleration until it reaches the intersection point, and then continues to travel at a constant velocity. . When x < 3, starting from the inflection point, first accelerate uniformly to a velocity of v0, and then move uniformly to the junction. When 2-1