Hexagon path planning algorithm.

The paper presents a novel 2D geometrical path plan algorithm that reduces calculation load and time by filtering obstacles before path planning starts by the newly introduced hexagon filter and also while path search is in progress. Unlike other methods that use only obstacle filtering before path planning starts. The suggested algorithm was able to solve a randomly created maze that contains 400 obstacles with 800 nodes, which was considered before, as next to impossible to solve. This is because computational time is proportional to n2log(n) where n is the number of obstacles, node suggested algorithm reduced the computational time to about 1 in 2500 times compared to the best of (ESOVG, DVG or ECoVG). In addition, the suggested algorithm can be used in the case of a fixed start point and different target points (e.g. a swarm of robots leaving from the same start point with different targets). [ABSTRACT FROM AUTHOR]