Enhancing the Hexagon Path Planning Algorithm for Dense Obstacle Environments (Iterative Hexagon Algorithm)

Document Type : Original Article

Authors

1 Roshdy Basha Street, building No.6, Alkhydewia First floor, flat No. 102

2 building no. 6 , Roushdy Basha street , Roushdy

Abstract

This study intends to improve the Hexagon Path Planning algorithm's application in dense obstacle situations by reducing computation time, allowing for real-time path planning with a dynamic search area that starts small and grows until a path is identified (iterative Hexagon visibility Graph). To evaluate the performance of the suggested algorithm, a novel assessment approach is provided that considers a large number of mazes rather than just a few. The key to the proposed algorithm's efficiency comes in the use of an iterative Hexagon visibility Graph, applying rules to identify and hence reject paths likely to be long, thus saving time and compute resources, prioritizing nodes with the likelihood of being part of the solution. This study also introduced the concept of checking Node-to-node visibility as needed, rather than creating a complete visibility map and then solve. This smart search reduces the computational load caused by node-to-node visibility checks complexity which increases by increasing the nodes number greatly. The proposed algorithm can find the shortest path or indicate that there isn't one. It completed mazes with 250 rectangular obstacles (equal to 2000 different nodes). Notably, the proposed methodology saved computing time greatly when compared to the usual method of building a visibility graph and then solving it using the Dijkstra algorithm: by roughly 45.56% without filter application and an astonishing 95.85% when a hexagon filter was used.

Keywords

Files

Share

How to cite

Statistics