Page 248 - 2024-Vol20-Issue2
P. 248
244 | Sabeeh & Al-Furati
optimize path planning and outperforms conventional methods searchers and engineers have developed numerous path-planning
in extensive simulations. Overall, this work contributes to the algorithms, each with its strengths and suitability for differ-
advancement of autonomous robotics in various applications, ent scenarios. This overview discusses the top 10 algorithms
from exploration to surveillance and transportation tasks. The known for their efficiency and effectiveness in real-world
key contributions of this paper can be briefly summarized in applications, highlighting their ability to handle complex path-
three primary aspects: planning tasks accurately.
1. Novel path-planning algorithm. The paper introduces • Probabilistic Roadmaps (PRM): Probabilistic Roadmaps
a new path-planning algorithm that combines genetic (PRM) is a popular sampling-based path-planning al-
algorithms (GA) and probabilistic roadmaps (PRM) gorithm used in robotics and motion planning [3]. It
to enhance autonomous robot navigation. This novel constructs a graph by randomly sampling points in
approach improves path-planning efficiency and quality the configuration space and connecting them through
compared to traditional algorithms. collision-free paths. PRM offers advantages in complex
and high-dimensional spaces and is widely applied in
2. Real-time performance and robustness. The focus is real-world robot motion planning tasks.
on real-time performance and adaptability in dynamic
environments. The algorithm operates in real-time and • Rapidly Exploring Random Trees (RRT): Rapidly
includes dynamic obstacle avoidance, allowing robots Exploring Random Trees (RRT) is a rapidly growing
to respond quickly to environmental changes and navi- tree-based path-planning algorithm [4]. It starts with
gate safely around moving obstacles. This robustness a single vertex representing the initial state and incre-
makes it suitable for real-world applications. mentally explores the search space by adding new ver-
tices connected to the existing tree. RRT is particularly
3. Comparative analysis and scalability. The paper also effective in exploring large spaces efficiently and is
conducts a comprehensive comparison with existing well suited for applications involving real-time obstacle
path-planning methods like A*, RRT, genetic algo- avoidance and dynamic environments.
rithms, and PRM. The main objective of this compari-
son is to gain insights into the advantages and shortcom- • A* (A-star): A* (pronounced as ”A-star”), a widely
ings of these methods about three essential performance recognized graph search algorithm, is employed to lo-
measures: average path length, average computational cate the shortest path connecting two nodes within a
time, and average smoothness. weighted graph [5].It employs a heuristic function to
guide the search towards the goal, making it both com-
The paper reviews existing algorithms, details the new algo- plete and optimal. A* is widely used in various do-
rithm’s components, and explains the system model in sec- mains, including robotics, computer games, and route
tions II. , III. , and IV. , respectively. Section V. explains planning applications.
the experimental setup, while Section VI. presents results
with clear evaluation and analysis. The conclusion empha- • D* (D-star): D* (D-star) is an incremental heuristic
sizes the algorithm’s significance and suggests future research search algorithm designed for dynamic environments
directions. where both the cost of the path and the terrain change
over time [6]. It efficiently updates the path based
II. LITERATURE REVIEW on new information and avoids recomputing the entire
path, making it suitable for scenarios with uncertain
In this part, we perform an extensive examination of existing and changing conditions.
research on the development of path-planning algorithms for
robotics and autonomous systems. We will examine multiple • Dijkstra’s Algorithm: Dijkstra’s algorithm is a classi-
recent research papers to gain a deep understanding of the cal shortest-path algorithm used to find the minimum-
current methods and innovations in this area. Through ana- cost path in a weighted graph [7]. It iteratively explores
lyzing and synthesizing these discoveries, we aim to pinpoint neighboring nodes from the start node, keeping track
areas where improvements can be made, identify challenges, of the minimum distance to each node. Dijkstra’s al-
and uncover opportunities for enhancing path-planning algo- gorithm guarantees the shortest path but may become
rithms. computationally expensive in large graphs.
A. Existing Path-Planning Algorithms • Wavefront Propagation: Wavefront Propagation is a
Path-planning is a vital challenge in robotics, involving find- simple and widely used algorithm for grid-based path-
ing the best path while avoiding obstacles. Over time, re- planning [8]. It operates on a grid map where each
