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

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.