Graph-based robot optimal path planning with bio-inspired algorithms

Abstract

Recently, bio-inspired algorithms have been increasingly explored for autonomous robot path planning on grid-based maps. However, these approaches endure performance degradation as problem complexity increases, often resulting in lengthy search times to find an optimal solution. This limitation is particularly critical for real-world applications like autonomous off-road vehicles, where high-quality path computation is essential for energy efficiency. To address these challenges, this paper proposes a new graph-based optimal path planning approach that leverages a sort of bio-inspired algorithm, improved seagull optimization algorithm (iSOA) for rapid path planning of autonomous robots. A modified Douglas–Peucker (mDP) algorithm is developed to approximate irregular obstacles as polygonal obstacles based on the environment image in rough terrains. The resulting mDP-derived graph is then modeled using a Maklink graph theory. By applying the iSOA approach, the trajectory of an autonomous robot in the workspace is optimized. Additionally, a Bezier-curve-based smoothing approach is developed to generate safer and smoother trajectories while adhering to curvature constraints. The proposed model is validated through simulated experiments undertaken in various real-world settings, and its performance is compared with state-of-the-art algorithms. The experimental results demonstrate that the proposed model outperforms existing approaches in terms of time cost and path length.

Keywords

• Autonomous robot
• Path planning
• Bio-inspired algorithm
• Graph-based model
• Improved seagull optimization algorithm (iSOA)