In recent years, the application of mobile robots has expanded across various industries, including industrial manufacturing, emergency rescue, service delivery, and healthcare. A critical aspect of autonomous navigation in robot technology is path planning, which involves finding an optimal, collision-free path from a start point to a goal point in an environment with obstacles. This ensures that robots can reach their destinations safely and efficiently. Path planning can be categorized into global and local methods. Global path planning operates in static environments with known information, while local path planning handles dynamic environments using real-time sensor data. Among the numerous algorithms available, the A* algorithm is widely used in static scenarios due to its efficiency in avoiding unnecessary state searches. However, traditional A* algorithms often produce paths with poor smoothness, excessive length, and numerous redundant nodes, which reduce motion efficiency in robot technology. To address these limitations, we propose a hybrid path planning method, termed SA-A*, which integrates the A* algorithm with the Simulated Annealing (SA) algorithm. This approach leverages the strengths of both algorithms to generate shorter, smoother paths by iteratively removing redundant nodes and optimizing path cost, thereby enhancing the overall performance in robot technology applications.
The traditional A* algorithm is a heuristic search method that guides its exploration using an evaluation function. It starts from the initial node and expands to neighboring nodes in eight directions, selecting the node with the minimum cost estimate as the next parent node. This process continues iteratively until the goal node is reached. The evaluation function $f(n)$ is defined as the sum of the actual cost from the start node to the current node $g(n)$ and the heuristic cost from the current node to the goal node $h(n)$:
$$f(n) = g(n) + h(n)$$
Common heuristic functions include the Manhattan distance, Euclidean distance, and Chebyshev distance. For two points $S(x_s, y_s)$ and $T(x_t, y_t)$ on a 2D plane, these distances are expressed as:
Manhattan distance: $$d(S,T) = |x_t – x_s| + |y_t – y_s|$$
Euclidean distance: $$d(S,T) = \sqrt{(x_t – x_s)^2 + (y_t – y_s)^2}$$
Chebyshev distance: $$d(S,T) = \max(|x_t – x_s|, |y_t – y_s|)$$
Despite its effectiveness, the A* algorithm often results in paths with unnecessary turns and nodes, which are suboptimal for real-world robot technology applications. To overcome this, we incorporate the Simulated Annealing algorithm, a probabilistic optimization technique inspired by the physical process of annealing. SA starts from a high initial temperature $T_0$ and gradually cools down. At each temperature step, it randomly selects a neighbor solution. If the new solution has a lower energy (cost), it is accepted unconditionally; otherwise, it is accepted with a probability $p$ based on the Metropolis criterion:
$$p = \exp\left(-\frac{E_j – E_i}{K T}\right)$$
where $K$ is the Boltzmann constant, $T$ is the current temperature, and $E_i$ and $E_j$ are the energies of the current and new solutions, respectively. This allows SA to explore the solution space broadly initially and focus on refinement as the temperature decreases, making it robust against local optima in complex robot technology environments.
Our SA-A* algorithm combines these two methods to optimize path planning. The process begins by importing a 2D grid occupancy map, which is then processed to account for the robot’s width and irregular obstacle edges by inflating obstacles to ensure a safe distance during navigation. The traditional A* algorithm is applied to generate an initial path. Subsequently, the SA optimization algorithm is used to refine this path by removing redundant nodes, reducing turns, and shortening the path length. The SA optimization involves three key components: randomly removing path nodes to generate new paths, evaluating paths using a cost function, and iteratively seeking the optimal solution through simulated annealing.
The path cost function in SA-A* is designed to balance length and smoothness. The length cost $L_{\text{cost}}$ is calculated as the sum of Euclidean distances between consecutive nodes, weighted by $W_L$:
$$L_{\text{cost}} = W_L \times \sum_{i=1}^{n-1} L(i)$$
where $L(i)$ is the Euclidean distance between node $i$ and $i+1$, and $n$ is the total number of nodes. The smoothness cost $A_{\text{cost}}$ accounts for the cumulative angle changes at each node, weighted by $W_A$:
$$A_{\text{cost}} = W_A \times \sum_{i=2}^{n-1} A(i)$$
Here, $A(i)$ is the angle between the vectors formed by nodes $i-1$, $i$, and $i+1$. The total cost is then:
$$\text{cost} = L_{\text{cost}} + A_{\text{cost}}$$
To generate new paths, nodes (excluding start and end points) are randomly removed, and the validity of the resulting path is checked by ensuring that the straight line between the preceding and succeeding nodes does not intersect any obstacles. This is done using linear interpolation to test points along the line for collisions. The SA algorithm iterates through this process, accepting new paths based on the Metropolis criterion, which helps escape local optima and converge towards a globally optimal path in robot technology systems.
We conducted simulations to evaluate the performance of SA-A* compared to the traditional A* algorithm. The experiments were performed on randomly generated 2D grid maps of sizes 30×30, 40×40, and 50×50, with an obstacle occupancy of 10%. The simulations were run on a Windows 10 system with an AMD R5-4600 processor using MATLAB 2022a. The results demonstrated that SA-A* consistently produced shorter and smoother paths. For instance, in the 30×30 map, SA-A* reduced the number of nodes from 380 to 2, the path length from 516.6 to 503.9 pixels, and the total turn angle from 1485.0° to 0°. Similar improvements were observed in larger maps, as summarized in the table below.
| Map Size | Algorithm | Number of Nodes | Total Length (pixels) | Total Turn Angle (°) |
|---|---|---|---|---|
| 30×30 | A* | 380 | 516.6 | 1485.0 |
| 30×30 | SA-A* | 2 | 503.9 | 0.0 |
| 40×40 | A* | 431 | 545.6 | 4231.0 |
| 40×40 | SA-A* | 5 | 516.5 | 29.0 |
| 50×50 | A* | 436 | 509.6 | 5445.0 |
| 50×50 | SA-A* | 7 | 480.5 | 72.6 |
Overall, SA-A* achieved an average reduction of 98.5% in the number of nodes, 4.5% in path length, and 98.7% in turn angle, significantly enhancing path smoothness and efficiency for robot technology.
To validate the practical feasibility of SA-A*, we implemented the algorithm on a mobile robot platform using the Robot Operating System (ROS). ROS is an open-source middleware that facilitates the integration of various robot technology components, providing communication and tools for development. Our experimental setup involved an exploration robot running Ubuntu 18.04 LTS and ROS Melodic. The robot utilized the Gmapping algorithm for simultaneous localization and mapping (SLAM) to construct a 2D grid map of the laboratory environment with a resolution of 0.01 m per unit. This map was imported into MATLAB for path planning comparisons between A* and SA-A*.
In the experiments, we defined start and end points on the map and executed both algorithms. The results showed that SA-A* generated paths with fewer nodes, shorter lengths, and reduced turns. For example, in one test with start point (1100, 1205) and end point (1593, 480), A* produced a path with 733 nodes, a length of 939.5 cm, and a total turn angle of 1710°, while SA-A* reduced these to 10 nodes, 894.3 cm, and 76.7°, respectively. Another test from (1358, 1291) to (1430, 357) yielded similar improvements, as detailed in the following table.
| Start Point | End Point | Algorithm | Number of Nodes | Total Length (cm) | Total Turn Angle (°) |
|---|---|---|---|---|---|
| (1100, 1205) | (1593, 480) | A* | 733 | 939.5 | 1710 |
| (1100, 1205) | (1593, 480) | SA-A* | 10 | 894.3 | 76.7 |
| (1358, 1291) | (1430, 357) | A* | 943 | 1010.6 | 2870 |
| (1358, 1291) | (1430, 357) | SA-A* | 6 | 957.4 | 36.4 |
The SA-A* algorithm parameters were set as follows: initial temperature of 1200°, cooling rate of 0.99, minimum temperature of 0.01°, maximum iterations of 1000, turn angle weight $W_A = 7.0$, and length weight $W_L = 3.0$. During real-world testing, the robot successfully navigated along the SA-A* path, which was visualized using RViz. The path generated by SA-A* (shown in green) was notably smoother and shorter than the A* path (blue), confirming the algorithm’s practicality and safety in robot technology applications.
In conclusion, the SA-A* algorithm effectively addresses the limitations of traditional A* path planning by integrating simulated annealing to remove redundant nodes, reduce path length, and improve smoothness. This hybrid approach not only enhances performance in simulations but also proves feasible in real-world robot technology scenarios. The random node removal strategy in SA-A* introduces diversity, helping to avoid local optima, though it may yield near-optimal solutions in large, complex maps. Future work will focus on refining the node removal strategy to achieve true global optimality and extending the method to other path planning algorithms like Dijkstra or RRT, further advancing robot technology in diverse environments.