Tide-Inspired Path Planning Algorithm for Autonomous Vehicles
With the extensive developments in autonomous vehicles (AV) and the increase of interest in artificial intelligence (AI), path planning is becoming a focal area of research. However, path planning is an NP-hard problem and its execution time and complexity are major concerns when searching for optim...
Main Authors: | , , , , , , |
---|---|
Other Authors: | |
Format: | Article |
Published: |
Multidisciplinary Digital Publishing Institute
2021
|
Online Access: | https://hdl.handle.net/1721.1/138226.2 |
_version_ | 1811097754403864576 |
---|---|
author | Kurdi, Heba A. Almuhalhel, Shaden ElGibreen, Hebah Qahmash, Hajar Albatati, Bayan Al-Salem, Lubna Almoaiqel, Ghada |
author2 | Massachusetts Institute of Technology. Department of Mechanical Engineering |
author_facet | Massachusetts Institute of Technology. Department of Mechanical Engineering Kurdi, Heba A. Almuhalhel, Shaden ElGibreen, Hebah Qahmash, Hajar Albatati, Bayan Al-Salem, Lubna Almoaiqel, Ghada |
author_sort | Kurdi, Heba A. |
collection | MIT |
description | With the extensive developments in autonomous vehicles (AV) and the increase of interest in artificial intelligence (AI), path planning is becoming a focal area of research. However, path planning is an NP-hard problem and its execution time and complexity are major concerns when searching for optimal solutions. Thus, the optimal trade-off between the shortest path and computing resources must be found. This paper introduces a path planning algorithm, tide path planning (TPP), which is inspired by the natural tide phenomenon. The idea of the gravitational attraction between the Earth and the Moon is adopted to avoid searching blocked routes and to find a shortest path. Benchmarking the performance of the proposed algorithm against rival path planning algorithms, such as A*, breadth-first search (BFS), Dijkstra, and genetic algorithms (GA), revealed that the proposed TPP algorithm succeeded in finding a shortest path while visiting the least number of cells and showed the fastest execution time under different settings of environment size and obstacle ratios. |
first_indexed | 2024-09-23T17:04:04Z |
format | Article |
id | mit-1721.1/138226.2 |
institution | Massachusetts Institute of Technology |
last_indexed | 2024-09-23T17:04:04Z |
publishDate | 2021 |
publisher | Multidisciplinary Digital Publishing Institute |
record_format | dspace |
spelling | mit-1721.1/138226.22022-08-31T20:32:06Z Tide-Inspired Path Planning Algorithm for Autonomous Vehicles Kurdi, Heba A. Almuhalhel, Shaden ElGibreen, Hebah Qahmash, Hajar Albatati, Bayan Al-Salem, Lubna Almoaiqel, Ghada Massachusetts Institute of Technology. Department of Mechanical Engineering With the extensive developments in autonomous vehicles (AV) and the increase of interest in artificial intelligence (AI), path planning is becoming a focal area of research. However, path planning is an NP-hard problem and its execution time and complexity are major concerns when searching for optimal solutions. Thus, the optimal trade-off between the shortest path and computing resources must be found. This paper introduces a path planning algorithm, tide path planning (TPP), which is inspired by the natural tide phenomenon. The idea of the gravitational attraction between the Earth and the Moon is adopted to avoid searching blocked routes and to find a shortest path. Benchmarking the performance of the proposed algorithm against rival path planning algorithms, such as A*, breadth-first search (BFS), Dijkstra, and genetic algorithms (GA), revealed that the proposed TPP algorithm succeeded in finding a shortest path while visiting the least number of cells and showed the fastest execution time under different settings of environment size and obstacle ratios. King Fahd University of Petroleum & Minerals. Researching Supporting Unit (Project number (RSP- 2021/204)) 2021-11-29T18:31:41Z 2021-11-29T15:34:51Z 2021-11-29T18:31:41Z 2021-11-18 2021-11-25T16:00:00Z Article http://purl.org/eprint/type/JournalArticle 2072-4292 https://hdl.handle.net/1721.1/138226.2 Remote Sensing 13 (22): 4644 (2021) PUBLISHER_CC http://dx.doi.org/10.3390/rs13224644 Remote sensing Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ application/octet-stream Multidisciplinary Digital Publishing Institute Multidisciplinary Digital Publishing Institute |
spellingShingle | Kurdi, Heba A. Almuhalhel, Shaden ElGibreen, Hebah Qahmash, Hajar Albatati, Bayan Al-Salem, Lubna Almoaiqel, Ghada Tide-Inspired Path Planning Algorithm for Autonomous Vehicles |
title | Tide-Inspired Path Planning Algorithm for Autonomous Vehicles |
title_full | Tide-Inspired Path Planning Algorithm for Autonomous Vehicles |
title_fullStr | Tide-Inspired Path Planning Algorithm for Autonomous Vehicles |
title_full_unstemmed | Tide-Inspired Path Planning Algorithm for Autonomous Vehicles |
title_short | Tide-Inspired Path Planning Algorithm for Autonomous Vehicles |
title_sort | tide inspired path planning algorithm for autonomous vehicles |
url | https://hdl.handle.net/1721.1/138226.2 |
work_keys_str_mv | AT kurdihebaa tideinspiredpathplanningalgorithmforautonomousvehicles AT almuhalhelshaden tideinspiredpathplanningalgorithmforautonomousvehicles AT elgibreenhebah tideinspiredpathplanningalgorithmforautonomousvehicles AT qahmashhajar tideinspiredpathplanningalgorithmforautonomousvehicles AT albatatibayan tideinspiredpathplanningalgorithmforautonomousvehicles AT alsalemlubna tideinspiredpathplanningalgorithmforautonomousvehicles AT almoaiqelghada tideinspiredpathplanningalgorithmforautonomousvehicles |