Abstract
The path planning problem is a critical challenge in robotics, gaming, and group animation. Traditional algorithms often overlook practical terrain constraints such as roughness, gradient, and obstacle height. This paper proposes a 2.5D terrain grid representation that significantly reduces computational overhead compared to full 3D models. By integrating fuzzy logic theory, the system evaluates terrain trafficability based on physical characteristics. This trafficability factor is then incorporated into a modified heuristic for the Jump Point Search (JPS) algorithm. The resulting method effectively addresses the symmetry problem on uneven surfaces, reduces the search space, and improves overall search speed.
Introduction
Most classic pathfinding algorithms, such as A, operate on flat 2D grids. While efficient, they struggle with two main issues in realistic environments: terrain blindness and the symmetry problem*. Terrain blindness occurs when algorithms treat all traversable space as uniform, ignoring physical factors like steepness or rocky surfaces. The symmetry problem leads to computational waste as the algorithm evaluates numerous redundant paths of equal cost in open spaces. While 3D grids can model terrain more accurately, they are memory-intensive and computationally expensive. This paper introduces a 2.5D approach that captures terrain complexity through fuzzy logic while maintaining a lightweight data structure.
Methodology
The proposed system utilizes a multi-stage approach to optimize pathfinding in rugged environments.
2.5D Terrain Representation and Fuzzy Logic
Instead of a full 3D voxel map, the researchers employ a 2D grid where each cell stores an elevation value. This 2.5D representation captures the necessary "ruggedness" while requiring significantly less memory. The core of the system is a Fuzzy Logic Controller used to calculate a Trafficability Factor ($u$).
The controller takes three inputs—gradient (slope), surface roughness, and obstacle height—and processes them through a knowledge base of "if-then" rules. For example, if the slope is steep and the roughness is high, the trafficability is determined to be low. This allows the system to handle "vague" human-like concepts and convert them into precise mathematical factors.
Improved Jump Point Search (JPS)
JPS is an optimization of A* that "jumps" over empty nodes to solve the symmetry problem. The authors extended JPS to work in 2.5D and modified its heuristic function to incorporate the trafficability factor: $$h(n) = D(n)^{w_d} \cdot \frac{1}{u^{w_u}}$$ This ensures the algorithm prioritizes paths that are not only short but also physically easier to traverse.
Key Insights and Results
The "Improved JPS" algorithm was tested against industry standards like A* and Dijkstra’s algorithm in a virtual rugged environment.
Search Space Efficiency
By using JPS instead of standard A*, the algorithm avoids checking every single neighbor node, focusing only on "forced neighbors" (such as the corners of obstacles). This drastically reduces the number of iterations required to find a path.
Performance Benchmarks
The experimental results highlight the efficiency of the proposed method:
| Algorithm | Path Length | Time | Iterations |
|---|---|---|---|
| A* | 16.9 | 8ms | 245 |
| Dijkstra | 16.9 | 29ms | 1047 |
| Improved JPS | 16.9 | 3ms | 24 |
The results demonstrate that the Improved JPS was over 2.6x faster than A and nearly 10x faster than Dijkstra, reaching the goal in only 24 iterations compared to 245 for A. Additionally, the 2.5D approach achieved a 99% reduction in memory footprint compared to a traditional 3D grid.
Conclusion
This research demonstrates that combining fuzzy logic with optimized search algorithms like JPS provides a robust solution for path planning on uneven surfaces. The resulting paths are more realistic, avoiding steep slopes and rough areas that standard algorithms would ignore. Future work will focus on adapting the algorithm for dynamic environments and automating the tuning of heuristic weights for various vehicle types.
Summary updated