Hexagon path planning algorithm
Abstract 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 bef...
Main Author: | |
---|---|
Format: | Article |
Language: | English |
Published: |
Wiley
2022-12-01
|
Series: | IET Radar, Sonar & Navigation |
Subjects: | |
Online Access: | https://doi.org/10.1049/rsn2.12250 |
_version_ | 1798019324920725504 |
---|---|
author | Hany Mohamed Elsayed Ibrahim Mohamed Arnaoot |
author_facet | Hany Mohamed Elsayed Ibrahim Mohamed Arnaoot |
author_sort | Hany Mohamed Elsayed Ibrahim Mohamed Arnaoot |
collection | DOAJ |
description | Abstract 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). |
first_indexed | 2024-04-11T16:38:54Z |
format | Article |
id | doaj.art-f72edf2f0f8c428ea7291001a98ca338 |
institution | Directory Open Access Journal |
issn | 1751-8784 1751-8792 |
language | English |
last_indexed | 2024-04-11T16:38:54Z |
publishDate | 2022-12-01 |
publisher | Wiley |
record_format | Article |
series | IET Radar, Sonar & Navigation |
spelling | doaj.art-f72edf2f0f8c428ea7291001a98ca3382022-12-22T04:13:45ZengWileyIET Radar, Sonar & Navigation1751-87841751-87922022-12-0116121895191110.1049/rsn2.12250Hexagon path planning algorithmHany Mohamed Elsayed Ibrahim Mohamed Arnaoot0Mechatronics Department Alexandria Higher Institute of Engineering & Technology Alexandria EgyptAbstract 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).https://doi.org/10.1049/rsn2.12250autonomous navigationcomplex environmentDVGECoVGESOVGgeometrical path planning |
spellingShingle | Hany Mohamed Elsayed Ibrahim Mohamed Arnaoot Hexagon path planning algorithm IET Radar, Sonar & Navigation autonomous navigation complex environment DVG ECoVG ESOVG geometrical path planning |
title | Hexagon path planning algorithm |
title_full | Hexagon path planning algorithm |
title_fullStr | Hexagon path planning algorithm |
title_full_unstemmed | Hexagon path planning algorithm |
title_short | Hexagon path planning algorithm |
title_sort | hexagon path planning algorithm |
topic | autonomous navigation complex environment DVG ECoVG ESOVG geometrical path planning |
url | https://doi.org/10.1049/rsn2.12250 |
work_keys_str_mv | AT hanymohamedelsayedibrahimmohamedarnaoot hexagonpathplanningalgorithm |