Study of Path Planning Algorithm Based on Fuzzy Logic

Dianhua Zhang, Yimin Chen, Chen Huang, Mingke GaoAdvances 2015 · DOI

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$).

Fuzzy logic system architecture for calculating trafficability.

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.

Comparison of standard grid search (top) versus the pruned search space of the Jump Point Search algorithm (bottom).

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

Abstract

The path planning problem is an important problem in the research area of robot, games and group animation. However, the current path planning algorithms don't consider practical problems such as roughness, gradient, and barrier height etc. This paper shows a 2.5dimensional terrain grid which can reduce the amount of computation. By applying the fuzzy logic theory, the terrain trafficability of the rugged road can be evaluated based on different gradient, roughness, elevation difference; the trafficability factor can be achieved and applied to the heuristic function. The improved algorithm can solve the symmetry problem of path planning on uneven surfaces, reduce the search space, and improve the search speed.
BibTeX
@inproceedings{zhang2015study,
  author = {Dianhua Zhang and Yimin Chen and Chen Huang and Mingke Gao},
  title = {{Study of Path Planning Algorithm Based on Fuzzy Logic}},
  booktitle = {Advances},
  year = {2015},
  doi = {10.2991/lemcs-15.2015.24},
}
Figure