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. The paper presents a comprehensive performance evaluation of some heuristic search algorithms in the context of autonomous systems and robotics. The objective of the study is to evaluate and compare the performance of different search algorithms in different problem settings on the pathfinding domain. Experiments give us insight into the behavior of the evaluated heuristic search algorithms, over the variation of different parameters: domain size, obstacle density, and distance between the start and the goal states. Results are then used to design a selection algorithm that, on the basis of problem characteristics, suggests the best search algorithm to use. 1 Introduction Autonomous agents and robotics have increasingly been used in various domains, such as, industrial applications [16, 18, 8], surveillance [17], and exploration [4]. These systems are designed to autonomously make decisions and execute actions based on their dynamic and unpredictable environments. Under such conditions, systems are required to be as reactive as possible to changes in the environment. Therefore, ensuring good performance is a significant challenge. In the case of planning, selecting the most effective search algorithm becomes crucial to enhance the overall performance of the system. Real-time heuristic search (RTS) (e.g.,[14, 9]) is a state-of-the-art approach for planning while executing, that helps minimize agent reaction time. These algorithms enable agents to make decisions by interleaving planning with execution while considering the evolving environment, which is an essential property in applications such as robotics, and video game agents. Despite the numerous methods proposed in this field [14, 13, 12, 3, 2], a comprehensive understanding of these algorithms remains elusive. Existing studies [1, 13, 10] have primarily focused on testing the performance of the algorithm based on a single parameter (e.g., look-ahead, sensor range). However, the influence of the problem domain characteristics on algorithm performance remains an understudied aspect. Our objective is to investigate the characteristics of the problem that may impact algorithm performances. To achieve this, we first review existing state of art of search algorithms and their applications. Then we design our experiments to evaluate some of the algorithm performances, also defining relevant metrics to use in the evaluation. Later on, experiment results are analyzed to provide a comprehensive understanding of how problem characteristics influence the performance of the different search algorithms. Finally, from the insight gained from our study, we introduce a selection algorithm that helps us to select the appropriate search algorithm. This paper is structured as follows. We begin by reviewing state-of-the-art search algorithms and previous performance evaluation studies. Next, we describe the approach we adopted to evaluate the search algorithms that are subject to our study, define the problem domain and its characteristics, and the performance metrics. In section four, we present our experimental results. Section five introduces our proposed selection algorithm with an execution example. Finally, we derive our conclusion, the limitations of our study, and possible directions for future work. 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. The paper presents a comprehensive performance evaluation of some heuristic search algorithms in the context of autonomous systems and robotics. The objective of the study is to evaluate and compare the performance of different search algorithms in different problem settings on the pathfinding domain. Experiments give us insight into the behavior of the evaluated heuristic search algorithms, over the variation of different parameters: domain size, obstacle density, and distance between the start and the goal states. Results are then used to design a selection algorithm that, on the basis of problem characteristics, suggests the best search algorithm to use. 1 Introduction Autonomous agents and robotics have increasingly been used in various domains, such as, industrial applications [16, 18, 8], surveillance [17], and exploration [4]. These systems are designed to autonomously make decisions and execute actions based on their dynamic and unpredictable environments. Under such conditions, systems are required to be as reactive as possible to changes in the environment. Therefore, ensuring good performance is a significant challenge. In the case of planning, selecting the most effective search algorithm becomes crucial to enhance the overall performance of the system. Real-time heuristic search (RTS) (e.g.,[14, 9]) is a state-of-the-art approach for planning while executing, that helps minimize agent reaction time. These algorithms enable agents to make decisions by interleaving planning with execution while considering the evolving environment, which is an essential property in applications such as robotics, and video game agents. Despite the numerous methods proposed in this field [14, 13, 12, 3, 2], a comprehensive understanding of these algorithms remains elusive. Existing studies [1, 13, 10] have primarily focused on testing the performance of the algorithm based on a single parameter (e.g., look-ahead, sensor range). However, the influence of the problem domain characteristics on algorithm performance remains an understudied aspect. Our objective is to investigate the characteristics of the problem that may impact algorithm performances. To achieve this, we first review existing state of art of search algorithms and their applications. Then we design our experiments to evaluate some of the algorithm performances, also defining relevant metrics to use in the evaluation. Later on, experiment results are analyzed to provide a comprehensive understanding of how problem characteristics influence the performance of the different search algorithms. Finally, from the insight gained from our study, we introduce a selection algorithm that helps us to select the appropriate search algorithm. This paper is structured as follows. We begin by reviewing state-of-the-art search algorithms and previous performance evaluation studies. Next, we describe the approach we adopted to evaluate the search algorithms that are subject to our study, define the problem domain and its characteristics, and the performance metrics. In section four, we present our experimental results. Section five introduces our proposed selection algorithm with an execution example. Finally, we derive our conclusion, the limitations of our study, and possible directions for future work. 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.

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

Navigation with Large Language Models: Implementation Details

HeuristicSearch.TECH

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Smart Heuristic Methods for Solving Bin Packing Problems

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

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 Path Planning Algorithms: Real-Time vs. Incremental Search

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