A fast constructive path planning algorithm for mobile robot navigation

Path planning is a vitally important ability for autonomous mobile robots. Because of the high computational complexity, the optimal solution is generally infeasible since the required computation time increases exponentially with the increase in the problem size. Instead, it is common to rely on heuristic and meta-heuristic algorithms to find near-optimal solutions. Although heuristic algorithms have proven effective and computationally inexpensive in small workspaces, they do not always scale to large environments and tend to get trapped in local minima. Also, while meta-heuristic algorithms are attracting considerable attention because of their effectiveness in optimization, they still require significant computational resources and are non-deterministic. In this paper, we introduce a novel Fast Constructive Algorithm (FCA) for deterministic path optimization that requires comparatively few computational resources to generate an optimized path. Our proposed FCA efficiently generates the waypoints for a path based only on the obstacles that intersect with the straight-line segment linking the robot's current position to the target location. The key idea is to construct the path by iteratively calculating the best waypoint to avoid the next obstacle in the robot's path. The effectiveness of the FCA is assessed on several maps with distinct complexities and its performance is compared with different state-of-the-art path planning algorithms. Our results show that the proposed FCA is competitive and can outperform existing algorithms in terms of path length and computation time.