Authors:
(1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento;
(2) Marco Robol, Department of Information Engineering and Computer Science University of Trento;
(3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento;
(4) Paolo Giorgini,  Department of Information Engineering and Computer Science University of Trento. 2 State of the art and related work Path planning is a relevant problem in autonomous agents, such as, self-driving cars, robots, unmanned aerial vehicles (UAVs), and unmanned ground vehicles (UGVs), in which the host agent deliberates its path by moving from one position to another while avoiding obstacles and respecting some constraints [19]. One of the path planning approaches that have been proposed to control the movement of these agent-based systems is search-based algorithms, with Dijkstra and its extension A* [5, 21], being the most popular and effective ones. Besides these, other search algorithms have been proposed in the literature, specifically to reduce reaction time, broadly classified as real-time or incremental search algorithms. Real-time search algorithms must find a solution in a limited time, while incremental search instead uses the previously obtained searches to speed up the search. Amongst the first class, Real-time A* (RTA*) and Learning real-time A* (LRTA*) [14] were some of the first algorithms to apply real-time heuristic search in path planning problems for moving agents. Both algorithms use heuristics to guide the search toward the goal, with RTA* storing the second-best f-values of the previous state as the best alternative to choose when backtracking from the current state. However, this may mislead the agent. Thereby, LRTA* overcomes this by storing the first best value rather than the second and learning from comparing the heuristic values of the adjacent states, thus preventing the algorithm from misleading the agent. Another optimized version of LRTA* is real-time adaptive A* (RTAA*) [12]. It first determines its local search space and then speeds up the search by updating the heuristics values of states. It was developed for stationary target search problems and it follows trajectories of smaller costs. Anytime repairing A* (ARA*) [15] is a variation of A* that has been designed to find suboptimal solutions fast and then improve them over time, which makes it a good algorithm for problems where finding an optimal solution is not mandatory or too expensive [15]. However, finding suboptimal solutions does not make it find the optimal solution [15]. Moving to incremental search algorithms, D* (Dynamic A*) is an incremental search algorithm used in real-time planning in robotics [20]. It is designed to react quickly to changes in the environment, by updating the nodes affected in the search tree rather than recomputing a new plan from scratch. D* has a main drawback that it requires a lot of memory to perform the search. LPA* (Lifelong Planning A*), an incremental version of A*. This algorithm is used in path planning or robot navigation in unknown terrain. It behaves just like A* in the first run, and then for the rest of subsequent searches it reuses the previous search thus reducing the number of examined nodes, which makes it fast. LPA* differs from D* in its search direction where it finds a path from the initial state to the initial goal state, therefore it does not fit in applications where the starting point may change over time. Another variant of D*, D* Lite, was developed based on LPA*, and is used for goal-directed path planning in unknown environments using the same idea as D*, however, it is a simple version of D* and produces effective results as the one delivered by D* as proven in [11]. While these heuristic search algorithms are numerous and diverse, it is important to emphasize that there are even more algorithms in the literature with new ones being developed, or existing ones being improved such as [2, 13, 7]. This variety of algorithms in the field emphasizes the complexity of the problem. Consequently, this variety of proposed algorithms presents a challenge; the wide number of these algorithms results in disparate performances in tasks such as path planning, making it difficult to select the optimal algorithms for a given task. Given the multitude of algorithms, studies have been done to compare the performance of RTS algorithms in path planning tasks such as [1] where authors have compared the performances of path planning algorithms using agents equipped with a sensor in both stationary and moving target settings to select the most appropriate algorithm. The obtained results were compared using various sensor ranges and angles, and the authors concluded that sensor range is an important parameter in selecting the algorithm, unlike the sensor angle. Therefore the most appropriate algorithm can be selected based on the sensor range and its priorities. However, the authors did not consider varying the environmental characteristics, which may influence the performance of the algorithms. Another study has been presented in [13], in which the authors also compared real-time and incremental heuristic search algorithms using an autonomous agent in a navigation task to know which class of heuristic search approach is better to be used depending on how informed the h-values are, and the search objective such as minimizing the sum of the search and action execution. The comparative analysis done in [1] considers only a static environment, neglecting the possible variations in the algorithm performance under different environmental characteristics. This limitation hampers us from creating a clear understanding of different search algorithms that could perform under different environmental characteristics, precisely in the context of path planning. Similarly, the study conducted in [13] restricts its investigation to only two algorithms each one from a different class i.e., real-time and incremental heuristic search. Even though it provides an insightful comparison, the study does not fully capture the breadth of available algorithms in these classes. Moreover, the study aimed to provide a recommendation on when to use each of the algorithm classes, but also does not investigate algorithm performances in diverse environmental characteristics. Consequently, considering the challenge posed by the presence of a wide range of search algorithms and the lack of a comprehensive comparative analysis under different environment settings, we propose to evaluate and analyze the performance of some search algorithms under different environment characteristics in the context of path planning, But first, we define the characteristics of the environment used, and through our experiments, we aim to provide a comprehensive evaluation of these algorithms followed by proposing our selection algorithm. This paper is available on arxiv under CC 4.0 license. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini,  Department of Information Engineering and Computer Science University of Trento. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini,  Department of Information Engineering and Computer Science University of Trento. 2 State of the art and related work Path planning is a relevant problem in autonomous agents, such as, self-driving cars, robots, unmanned aerial vehicles (UAVs), and unmanned ground vehicles (UGVs), in which the host agent deliberates its path by moving from one position to another while avoiding obstacles and respecting some constraints [19]. One of the path planning approaches that have been proposed to control the movement of these agent-based systems is search-based algorithms, with Dijkstra and its extension A* [5, 21], being the most popular and effective ones. Besides these, other search algorithms have been proposed in the literature, specifically to reduce reaction time, broadly classified as real-time or incremental search algorithms. Real-time search algorithms must find a solution in a limited time, while incremental search instead uses the previously obtained searches to speed up the search. Amongst the first class, Real-time A* (RTA*) and Learning real-time A* (LRTA*) [14] were some of the first algorithms to apply real-time heuristic search in path planning problems for moving agents. Both algorithms use heuristics to guide the search toward the goal, with RTA* storing the second-best f-values of the previous state as the best alternative to choose when backtracking from the current state. However, this may mislead the agent. Thereby, LRTA* overcomes this by storing the first best value rather than the second and learning from comparing the heuristic values of the adjacent states, thus preventing the algorithm from misleading the agent. Another optimized version of LRTA* is real-time adaptive A* (RTAA*) [12]. It first determines its local search space and then speeds up the search by updating the heuristics values of states. It was developed for stationary target search problems and it follows trajectories of smaller costs. Anytime repairing A* (ARA*) [15] is a variation of A* that has been designed to find suboptimal solutions fast and then improve them over time, which makes it a good algorithm for problems where finding an optimal solution is not mandatory or too expensive [15]. However, finding suboptimal solutions does not make it find the optimal solution [15]. Moving to incremental search algorithms, D* (Dynamic A*) is an incremental search algorithm used in real-time planning in robotics [20]. It is designed to react quickly to changes in the environment, by updating the nodes affected in the search tree rather than recomputing a new plan from scratch. D* has a main drawback that it requires a lot of memory to perform the search. LPA* (Lifelong Planning A*), an incremental version of A*. This algorithm is used in path planning or robot navigation in unknown terrain. It behaves just like A* in the first run, and then for the rest of subsequent searches it reuses the previous search thus reducing the number of examined nodes, which makes it fast. LPA* differs from D* in its search direction where it finds a path from the initial state to the initial goal state, therefore it does not fit in applications where the starting point may change over time. Another variant of D*, D* Lite, was developed based on LPA*, and is used for goal-directed path planning in unknown environments using the same idea as D*, however, it is a simple version of D* and produces effective results as the one delivered by D* as proven in [11]. While these heuristic search algorithms are numerous and diverse, it is important to emphasize that there are even more algorithms in the literature with new ones being developed, or existing ones being improved such as [2, 13, 7]. This variety of algorithms in the field emphasizes the complexity of the problem. Consequently, this variety of proposed algorithms presents a challenge; the wide number of these algorithms results in disparate performances in tasks such as path planning, making it difficult to select the optimal algorithms for a given task. Given the multitude of algorithms, studies have been done to compare the performance of RTS algorithms in path planning tasks such as [1] where authors have compared the performances of path planning algorithms using agents equipped with a sensor in both stationary and moving target settings to select the most appropriate algorithm. The obtained results were compared using various sensor ranges and angles, and the authors concluded that sensor range is an important parameter in selecting the algorithm, unlike the sensor angle. Therefore the most appropriate algorithm can be selected based on the sensor range and its priorities. However, the authors did not consider varying the environmental characteristics, which may influence the performance of the algorithms. Another study has been presented in [13], in which the authors also compared real-time and incremental heuristic search algorithms using an autonomous agent in a navigation task to know which class of heuristic search approach is better to be used depending on how informed the h-values are, and the search objective such as minimizing the sum of the search and action execution. The comparative analysis done in [1] considers only a static environment, neglecting the possible variations in the algorithm performance under different environmental characteristics. This limitation hampers us from creating a clear understanding of different search algorithms that could perform under different environmental characteristics, precisely in the context of path planning. Similarly, the study conducted in [13] restricts its investigation to only two algorithms each one from a different class i.e., real-time and incremental heuristic search. Even though it provides an insightful comparison, the study does not fully capture the breadth of available algorithms in these classes. Moreover, the study aimed to provide a recommendation on when to use each of the algorithm classes, but also does not investigate algorithm performances in diverse environmental characteristics. Consequently, considering the challenge posed by the presence of a wide range of search algorithms and the lack of a comprehensive comparative analysis under different environment settings, we propose to evaluate and analyze the performance of some search algorithms under different environment characteristics in the context of path planning, But first, we define the characteristics of the environment used, and through our experiments, we aim to provide a comprehensive evaluation of these algorithms followed by proposing our selection algorithm. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Performance Metrics of Heuristic Search Algorithms in Grid Environments

Evaluating Heuristic Search Algorithms in Pathfinding: A Comprehensive Study on Performance Metrics 

HeuristicSearch.TECH

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

Evaluating Path Planning Algorithms: Real-Time vs. Incremental Search

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Smart Heuristic Methods for Solving Bin Packing Problems

Evaluating Heuristic Search Algorithms in Pathfinding: A Comprehensive Study on Performance Metrics

Performance Metrics of Heuristic Search Algorithms in Grid Environments

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

5 Smart Heuristic Methods for Solving Bin Packing Problems

Evaluating Heuristic Search Algorithms in Pathfinding: A Comprehensive Study on Performance Metrics

Performance Metrics of Heuristic Search Algorithms in Grid Environments

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps