A fast constructive path planning algorithm for mobile robot navigation

Abderraouf Maoudj, Abdelfetah Hentout, Anders Christensen, Ahmed Kouider

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publication2021 26th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA )
PublisherIEEE
Publication date30. Nov 2021
Pages1-8
ISBN (Electronic)9781728129891
DOIs
Publication statusPublished - 30. Nov 2021
Event26th IEEE International Conference on Emerging Technologies and Factory Automation - Vasteras, Sweden
Duration: 7. Sep 202110. Sep 2021

Conference

Conference26th IEEE International Conference on Emerging Technologies and Factory Automation
Country/TerritorySweden
CityVasteras
Period07/09/202110/09/2021

Fingerprint

Dive into the research topics of 'A fast constructive path planning algorithm for mobile robot navigation'. Together they form a unique fingerprint.

Cite this