In recent years, efficient and safe path planning for robots has become a critical research area in robot technology. As robots are increasingly deployed in complex environments such as autonomous driving, smart logistics, and disaster response, the demand for robust path planning algorithms that minimize computational time, ensure smooth trajectories, and enhance safety has grown. Traditional algorithms like A* and its variants have been widely used, but they often suffer from issues like high computational complexity, suboptimal path smoothness, and inefficiency in large-scale maps. To address these challenges, we propose an improved Rectangle Expansion A* (REA*) algorithm that incorporates bidirectional alternating search, an adaptive evaluation function, and a novel path smoothing strategy. Our approach aims to reduce path length, computation time, and turning angles while maintaining safety through obstacle buffering. This paper details the system model, algorithm improvements, and experimental validation, demonstrating the superiority of our method in various simulated environments. The integration of these elements advances robot technology by enabling more adaptive and efficient navigation in dynamic settings.
Path planning is a fundamental component of robot technology, involving the determination of an optimal path from a start to a goal while avoiding obstacles. Global path planning algorithms, such as A* and RRT, rely on complete environmental knowledge, whereas local methods like DWA handle dynamic obstacles. However, these methods often require post-processing for smoothness, increasing computational overhead. Our work builds upon the REA* algorithm, which expands search regions as rectangles to reduce node evaluations. By enhancing REA* with bidirectional search and adaptive evaluation, we achieve faster convergence and smoother paths. This is particularly relevant in robot technology applications where real-time performance and energy efficiency are crucial. For instance, in warehouse automation or search-and-rescue missions, our algorithm can help robots navigate efficiently through cluttered spaces, reducing physical wear and improving task completion rates.
In the following sections, we first review related work on path planning algorithms, highlighting their strengths and limitations. We then present our system model, including the grid-based environment and safety considerations. Next, we describe the improved REA* algorithm with bidirectional expansion, optimized evaluation function, and path smoothing. Experimental results on three map types compare our method with A*, JPS, REA*, and SBREA*, showing reductions in search time, path length, and turning angles. Finally, we conclude with insights and future directions for enhancing robot technology in path planning.
Related Work
Path planning algorithms have evolved from traditional methods to modern bio-inspired approaches, each with unique advantages for robot technology. Classical algorithms like A* use a grid-based search with an evaluation function $$f(n) = g(n) + h(n)$$, where $$g(n)$$ is the cost from the start node, and $$h(n)$$ is a heuristic estimate to the goal. While A* guarantees optimality, it can be inefficient in large maps due to high node expansions. To address this, variants like weighted A* and bidirectional A* have been proposed. For example, bidirectional alternating search (BAS) reduces the search space by exploring from both start and goal simultaneously, improving efficiency in robot navigation systems.
Jump Point Search (JPS) optimizes A* by skipping redundant nodes through “jump points,” but it may produce paths with unnecessary turns. The REA* algorithm, introduced by Zhang et al., expands the search as rectangles, treating passable intervals (PIs) as single units. This reduces the number of evaluated nodes and storage requirements. Further improvements, such as SBREA*, incorporate BAS and smoothing techniques like the slide-rail corner adjustment method. However, SBREA* may not fully optimize path smoothness, as seen in cases where path points remain unchanged within intervals. Other approaches, like RRT and artificial potential fields, offer alternatives but often lack completeness or suffer from local minima. In contrast, our method enhances REA* by integrating adaptive evaluation and smoothing directly into the search process, leveraging vector-based computations to minimize resource usage. This aligns with the growing needs of robot technology for real-time, energy-efficient solutions in unpredictable environments.
Bio-inspired algorithms, such as ant colony optimization and particle swarm optimization, have also been applied to path planning. These methods explore multiple paths in parallel, accelerating convergence. However, they can be computationally intensive and may not guarantee optimality. Our work focuses on refining traditional algorithms like REA* to achieve a balance between efficiency and performance, making it suitable for practical robot technology applications where reliability and speed are paramount.
System Model
We model the robot path planning environment using a grid-based representation, where the map is defined as a matrix $$M_{n \times m}$$. Each element $$M(x, y)$$ corresponds to a grid cell, with values indicating different types of areas: non-obstacle (white), obstacle (blue), safety buffer area (light blue), path nodes (orange), forward passed intervals (yellow), and reverse passed intervals (green). This discretization simplifies algorithm computation but requires assumptions to ensure practicality. First, we assume the map is fully known, and the grid resolution is sufficient for path accuracy. Second, to prevent collisions, we add a safety buffer area (SBA) around obstacles, which is treated as part of the obstacle region. Third, the robot is modeled as a point mass, ignoring specific kinematics, to focus on path planning aspects. The buffer zones enhance safety in robot technology by maintaining a minimum distance from obstacles, reducing the risk in dynamic operations.
The path planning problem is formulated as finding a sequence of path nodes $$P = \{\alpha_1, \alpha_2, \dots, \alpha_n\}$$ from start $$S$$ to goal $$D$$ that minimizes the total path length $$L(P) = \sum_{i=1}^{n-1} d(\alpha_i, \alpha_{i+1})$$, where $$d$$ is the Euclidean distance, subject to constraints: $$\alpha_i \notin O$$ for all $$i$$ (avoiding obstacles), and $$\alpha_i \neq \alpha_j$$ for $$i \neq j$$ (no repeated nodes). The objective also includes minimizing computation time $$t$$, as expressed in the following model:
$$ \begin{aligned}
&\text{Minimize} \quad L(P) = \sum_{i=1}^{n-1} d(\alpha_i, \alpha_{i+1}), \\
&\text{Minimize} \quad t, \\
&\text{subject to} \quad \alpha_1 = S, \quad \alpha_n = D, \\
&\quad \alpha_i \notin O \quad \forall i = 1, 2, \dots, n, \\
&\quad \alpha_i \neq \alpha_j \quad \forall i \neq j.
\end{aligned} $$
To implement this, we first preprocess the map by identifying SBAs around obstacles. Algorithm 1 outlines this safety distance setting: for each non-obstacle cell, if any of its eight neighbors is an obstacle, it is marked as an SBA. This step ensures that the path planning algorithm operates on a modified map where buffers are considered obstacles, simplifying subsequent calculations. In robot technology, such preprocessing is essential for robust navigation in cluttered environments, as it accounts for the physical dimensions of robots and environmental uncertainties.
The original REA* algorithm expands rectangles from nodes, stopping when obstacles are encountered, and identifies passable intervals (PIs) along the rectangle boundaries. A PI is defined as a contiguous set of non-obstacle cells on a rectangle edge. For example, on the north edge, a PI satisfies:
$$ \begin{aligned}
&\text{PI} = \{ (x, y) \mid M(x, y) \notin O, x = ne – 1, y \in [we, ee] \},
\end{aligned} $$
where $$ne$$, $$se$$, $$we$$, and $$ee$$ define the rectangle’s edges. REA* evaluates nodes within PIs using the A* evaluation function, but this can be inefficient. Our improved model incorporates bidirectional search and adaptive evaluation to address these issues, as detailed in the next section. The use of rectangles allows for larger search steps, reducing the number of expansions and accelerating the planning process, which is beneficial in time-sensitive robot technology applications.
| Matrix Value | Color | Meaning |
|---|---|---|
| 1 | White | Non-Obstacle (NO) |
| 2 | Blue | Obstacle (O) |
| 3 | Light Blue | Safety Buffer Area (SBA) |
| 5 | Orange | Path Node (PN) |
| 6 | Yellow | Forward Passed Interval (FPI) |
| 7 | Green | Reverse Passed Interval (RPI) |
Improved REA* Algorithm
Our enhanced REA* algorithm consists of three main components: bidirectional expansion, an optimized evaluation function, and a path smoothing strategy. These improvements collectively reduce computation time, path length, and turning angles, making the algorithm more suitable for real-world robot technology.
Bidirectional Expansion Strategy
We employ a bidirectional alternating search (BAS) where rectangles expand simultaneously from the start $$S$$ and goal $$D$$. This approach reduces the search space and accelerates convergence. Algorithm 2 describes the process: initially, rectangles are expanded from $$S$$ and $$D$$, generating forward passed intervals (FPIs) and reverse passed intervals (RPIs). The PIs are stored as pairs of endpoints with direction information (e.g., north, south, east, west), minimizing storage needs. The search continues by selecting the PI with the smallest evaluation value from open lists for each direction. If new FPIs and RPIs intersect, the search terminates, and the path is reconstructed. This method efficiently prunes unnecessary nodes and leverages the larger step size of rectangle expansion, which is advantageous in robot technology for handling large environments with fewer computations.
Directions are encoded as vectors: north as $$[-1, 0]$$ (value 1), south as $$[1, 0]$$ (value 2), west as $$[0, -1]$$ (value 3), and east as $$[0, 1]$$ (value 4). This representation facilitates vector-based calculations in the evaluation function. For example, when expanding from a PI, the next rectangle is formed using the PI as one edge, and new PIs are generated along the other edges. The bidirectional search ensures that both directions progress toward each other, reducing the likelihood of local minima and improving overall efficiency in robot path planning.
Optimized Evaluation Function
The evaluation function in traditional A* and REA* computes $$f(n)$$ for individual nodes, but we adapt it to evaluate entire PIs. For a current PI $$pi_{cur}$$, represented by its midpoint $$pi_{cur}^{mid}$$, we define the evaluation function as:
$$ f(pi_{cur}) = g(pi_{cur}) + (1 + w) h(pi_{cur}), $$
where $$g(pi_{cur}) = \| pi_{cur}^{mid} – ns^{mid} \|_2$$ is the distance from the new start midpoint, $$h(pi_{cur}) = \| pi_{cur}^{mid} – nd^{mid} \|_2$$ is the heuristic distance to the new goal midpoint, and $$w$$ is an adaptive weight. The weight $$w$$ is computed based on vector directions to prioritize promising paths. Specifically, let $$\mathbf{V} = nd^{mid} – pi_{cur}^{mid}$$ be the vector from the current PI to the goal, and $$\mathbf{VS} = \text{sgn}(\mathbf{V})$$ be its unit vector. The direction of the PI, $$\mathbf{DIR}$$, is compared to $$\mathbf{VS}$$ to compute a difference vector $$\mathbf{D}_{diff} = \mathbf{VS} – \mathbf{DIR}$$. Then, $$\mathbf{VS}^m$$ is obtained by element-wise multiplication of $$\mathbf{VS}$$ and $$\mathbf{D}_{diff}$$, and the weight is:
$$ w = \frac{\mathbf{VS}^m \cdot \mathbf{VS}}{ed}, $$
where $$ed$$ is the effective map dimension in the direction of $$\mathbf{DIR}$$, calculated as $$ed = \mathbf{S} \cdot (1 – \mathbf{DIR})$$ with $$\mathbf{S}$$ being the map size. This formulation adapts the heuristic to the environment layout, reducing unnecessary expansions and guiding the search more effectively. In robot technology, this vector-based approach minimizes computational overhead by leveraging directional information, enhancing path planning in complex terrains.
Algorithm 3 outlines the evaluation function optimization: it computes $$g$$ and $$h$$ as Euclidean distances between midpoints, derives $$\mathbf{V}$$ and $$\mathbf{VS}$$, and calculates $$w$$ to adjust the heuristic. The updated $$f$$ value promotes paths that align with the goal direction while avoiding obstacles, resulting in faster convergence and shorter paths. This adaptive mechanism is particularly useful in dynamic robot technology applications where environmental changes require quick replanning.
Path Smoothing Optimization
To improve path smoothness, we propose a novel method that selects path nodes within PIs based on direction sequences. After obtaining the path as a sequence of PIs, we extract the direction sequence $$D = \{d_1, d_2, \dots, d_n\}$$, where each $$d_i$$ corresponds to the expansion direction (1 for north, 2 for south, etc.). We compute the difference sequence $$\Delta D = \{\Delta d_1, \Delta d_2, \dots, \Delta d_{n-1}\}$$ with $$\Delta d_i = d_{i+1} – d_i$$, which captures turning patterns. Based on $$\Delta D$$, we assign markers to PIs: “1” for direction changes, “2” for U-turns or fixed points, and “0” for straight segments. Algorithm 4 describes how path nodes are selected: for markers “2”, the endpoint closest to the previous path node is chosen; for markers “1”, we check if the line between adjacent path nodes intersects the PI, selecting the intersection point or the nearest endpoint. This ensures that the path minimizes sharp turns and adheres to the natural geometry of rectangles, enhancing smoothness.
For example, if $$\Delta d_i = 0$$, the direction is unchanged, and the path segment is straight. If $$\Delta d_i \neq 0$$ and $$\Delta d_{i+1} = -\Delta d_i$$, it indicates a U-turn, and the path follows the obstacle boundary. This method avoids post-processing steps like Bézier curves, reducing computational load. In robot technology, smooth paths reduce mechanical wear and energy consumption, which is critical for prolonged operations. The overall algorithm complexity is $$O(N)$$ for smoothing, similar to SBREA*, but with better performance due to integrated handling of directions.
Experimental Results and Analysis
We evaluated our improved REA* algorithm on three grid maps (50×50 cells) with different obstacle densities: Map A (35% density) with mixed obstacles, Map B (20% density) mimicking a maze, and Map C (35% density) with irregular obstacles. We compared our method against A*, JPS, REA*, and SBREA* in terms of average search time, path length, number of expansions, sum of turning angles, number of turns, and relative smoothness. The results, averaged over multiple runs, demonstrate the effectiveness of our approach in advancing robot technology.
| Metric | A* | JPS | REA* | SBREA* | Improved REA* |
|---|---|---|---|---|---|
| Map A – Time (s) | 2.74 | 0.14 | 0.06 | 0.27 | 0.11 |
| Map A – Length (m) | 98.63 | 93.11 | 96.29 | 94.48 | 87.84 |
| Map A – Expansions | 559 | 31 | 32 | 25 | 19 |
| Map A – Turning Angle Sum (°) | 900 | 675 | 510.26 | 531.08 | 338.40 |
| Map A – Number of Turns | 19 | 15 | 12 | 12 | 10 |
| Map A – Relative Smoothness | 1 | 1.33 | 1.76 | 1.69 | 2.66 |
| Map B – Time (s) | 5.10 | 0.14 | 0.04 | 0.21 | 0.09 |
| Map B – Length (m) | 168.47 | 146.28 | 150.25 | 166.78 | 148.98 |
| Map B – Expansions | 1075 | 31 | 21 | 18 | 13 |
| Map B – Turning Angle Sum (°) | 2070 | 945 | 852.97 | 908.08 | 858.17 |
| Map B – Number of Turns | 43 | 21 | 11 | 13 | 11 |
| Map B – Relative Smoothness | 1 | 2.19 | 2.43 | 2.28 | 2.41 |
| Map C – Time (s) | 1.19 | 0.19 | 0.08 | 0.27 | 0.12 |
| Map C – Expansions | 236 | 47 | 39 | 23 | 25 |
| Map C – Length (m) | 66.50 | 64.25 | 71.97 | 64.17 | 64.06 |
| Map C – Turning Angle Sum (°) | 1305 | 675 | 1014.60 | 423.11 | 670.19 |
| Map C – Number of Turns | 26 | 15 | 27 | 20 | 23 |
| Map C – Relative Smoothness | 1 | 1.93 | 1.29 | 3.08 | 1.95 |
Our improved REA* algorithm consistently outperforms others in most metrics. For instance, on Map A, it reduces the average search time to 0.11 seconds, compared to 2.74 seconds for A* and 0.27 seconds for SBREA*. The path length is shortened to 87.84 meters, and the sum of turning angles is minimized to 338.40°, indicating smoother trajectories. The number of expansions decreases to 19, highlighting efficiency gains. Similar trends are observed on Maps B and C, where our method achieves lower turning angles and fewer turns, essential for robot technology to reduce mechanical stress and energy use. The relative smoothness, measured against A*, shows improvements up to 3.08 on Map C, demonstrating the effectiveness of our path smoothing strategy.
Visualizations of the paths confirm that our algorithm produces smoother routes with fewer redundant turns, especially in complex environments like Map C. The bidirectional search and adaptive evaluation contribute to faster convergence, while the smoothing method ensures optimal node selection within PIs. These advancements make our approach highly suitable for robot technology applications requiring real-time performance and reliability, such as autonomous vehicles and industrial automation.
Conclusion and Future Work
In this paper, we presented an improved REA* algorithm for robot path planning that integrates bidirectional search, an adaptive evaluation function, and a novel smoothing technique. Our method reduces computation time, path length, and turning angles while ensuring safety through obstacle buffering. Experimental results on diverse maps validate its superiority over existing algorithms, making it a valuable contribution to robot technology. The use of vector-based computations and direction-based smoothing enhances efficiency and path quality, addressing key challenges in autonomous navigation.
For future work, we plan to extend our algorithm to dynamic environments by incorporating local planners like DWA or VFH for real-time obstacle avoidance. This will enable applications in unpredictable settings, such as urban mobility or disaster response. Additionally, we aim to optimize the termination conditions in bidirectional search to further reduce computation time. Exploring the integration of machine learning for adaptive heuristic tuning could also improve performance in complex robot technology scenarios. Overall, our approach lays a foundation for more robust and efficient path planning systems, advancing the capabilities of robots in various domains.