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. 3 Experimental environment and performance metrices Heuristic search algorithms play an important role in fields such as robotic pathfinding, as they determine the optimal path given a starting position and a goal position. Grid-based environments are commonly used for representing real-world environment scenarios, where these algorithms can be implemented, such as in autonomous navigation and robotics [6]. In this study, we comprehensively analyze well known heuristic search algorithms, namely D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in different grid environments. We use the Euclidean distance heuristic to guide the search of the algorithms and assess the impact of a few grid characteristics, such as the obstacle density and the grid size, on the performance of the algorithms. In our study, we use grid-based environments due to their simplicity, and control ease, in addition to being commonly used in path-planning tasks in the research community. The grids are composed of white cells, representing traversable states, whereas the black ones represent non-traversable obstacles. The agent in our simulation can move in eight directions, with a cost equal to 1 for horizontal and vertical moves, and √ 2 for diagonal movements. We used two types of grid environments: randomly generated grid environments and personalized grid environments. Randomly generated grid-based environments: The grids are characterized by three parameters: grid size (NxN), obstacle density, and the distance between the start and the goal states. To investigate the impact of each parameter on the performance of the search algorithms, we varied each parameter independently while keeping the other parameters constant. The variations included varying the grid size, varying start to goal distance, and varying the obstacle densities. For each grid in a variation, we generated ten random instances of the same grid parameters (e.g., a grid with 0.25 of obstacle density, size 300x300, and 140 of start to goal distance, have ten instances, which were generated randomly). Personalised grid environment: Designed for simulating more specific scenarios. These grids have fixed size (71x31 units) and a fixed position for both the start and goal states, and they were divided into two parts based on their obstacle configuration: • Horizontal wall configuration: For these experiments, we add horizontal walls of half grid width every 10 units of grid length. We added the walls in two orientations: once from left to right, and once from right to left in the newly generated grid. • Horizontal wall length configuration: Here, we add all possible walls that can be placed within the grid length, and each time we generate a new grid we increase all wall lengths by 2 units. We adopted these two distinct environments to provide a thorough analysis, seeking to reveal nuanced insights into the performance of the search algorithm in the presence of two different hindering scenarios. In the first one, obstacles are scattered randomly within the grid, whereas in the second one, the wall-like structures, appear as a mass of connected obstacles. To evaluate the performance of the different search algorithms used in the experiments, we have selected the following metrics: • Path cost: The metric measures the path length or the number of executed actions from the start to the goal state. It indicates the quality of the solution. • Memory consumption: It measures the required amount of memory for the algorithm to find a solution. It is relevant to check the scalability of the algorithm, and it is measured in (KB). • Solving Time: Represent the total time an algorithm takes to find a solution in (ms), measured in milliseconds (ms). We carried out our experiments on 3.30GHz 27 Intel i9 cores, equipped with 250Gb of RAM and running Ubuntu Linux 22.04. Using the following settings: All algorithms were using the Euclidean distance as the heuristic function. For LRTA* and RTAA*, we set the number of expended nodes to 250 for each iteration. The ARA* algorithm was run with a weight of 2.5 for the heuristic. We ran each algorithm 100 times on each grid to account for randomness and to ensure the reliability of the results. 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. 3 Experimental environment and performance metrices Heuristic search algorithms play an important role in fields such as robotic pathfinding, as they determine the optimal path given a starting position and a goal position. Grid-based environments are commonly used for representing real-world environment scenarios, where these algorithms can be implemented, such as in autonomous navigation and robotics [6]. In this study, we comprehensively analyze well known heuristic search algorithms, namely D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in different grid environments. We use the Euclidean distance heuristic to guide the search of the algorithms and assess the impact of a few grid characteristics, such as the obstacle density and the grid size, on the performance of the algorithms. In our study, we use grid-based environments due to their simplicity, and control ease, in addition to being commonly used in path-planning tasks in the research community. The grids are composed of white cells, representing traversable states, whereas the black ones represent non-traversable obstacles. The agent in our simulation can move in eight directions, with a cost equal to 1 for horizontal and vertical moves, and √ 2 for diagonal movements. We used two types of grid environments: randomly generated grid environments and personalized grid environments. Randomly generated grid-based environments: The grids are characterized by three parameters: Randomly generated grid-based environments: grid size (NxN), obstacle density, and the distance between the start and the goal states. To investigate the impact of each parameter on the performance of the search algorithms, we varied each parameter independently while keeping the other parameters constant. The variations included varying the grid size, varying start to goal distance, and varying the obstacle densities. For each grid in a variation, we generated ten random instances of the same grid parameters (e.g., a grid with 0.25 of obstacle density, size 300x300, and 140 of start to goal distance, have ten instances, which were generated randomly). Personalised grid environment: Designed for simulating more specific scenarios. These grids have fixed size (71x31 units) and a fixed position for both the start and goal states, and they were divided into two parts based on their obstacle configuration: Personalised grid environment: • Horizontal wall configuration: For these experiments, we add horizontal walls of half grid width every 10 units of grid length. We added the walls in two orientations: once from left to right, and once from right to left in the newly generated grid. Horizontal wall configuration: • Horizontal wall length configuration: Here, we add all possible walls that can be placed within Horizontal wall length configuration: the grid length, and each time we generate a new grid we increase all wall lengths by 2 units. We adopted these two distinct environments to provide a thorough analysis, seeking to reveal nuanced insights into the performance of the search algorithm in the presence of two different hindering scenarios. In the first one, obstacles are scattered randomly within the grid, whereas in the second one, the wall-like structures, appear as a mass of connected obstacles. To evaluate the performance of the different search algorithms used in the experiments, we have selected the following metrics: • Path cost: The metric measures the path length or the number of executed actions from the start to the goal state. It indicates the quality of the solution. Path cost: • Memory consumption: It measures the required amount of memory for the algorithm to find a solution. It is relevant to check the scalability of the algorithm, and it is measured in (KB). Memory consumption: • Solving Time: Represent the total time an algorithm takes to find a solution in (ms), measured in milliseconds (ms). Solving Time: We carried out our experiments on 3.30GHz 27 Intel i9 cores, equipped with 250Gb of RAM and running Ubuntu Linux 22.04. Using the following settings: All algorithms were using the Euclidean distance as the heuristic function. For LRTA* and RTAA*, we set the number of expended nodes to 250 for each iteration. The ARA* algorithm was run with a weight of 2.5 for the heuristic. We ran each algorithm 100 times on each grid to account for randomness and to ensure the reliability of the results. 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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

5 Smart Heuristic Methods for Solving Bin Packing Problems

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

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

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

Future Directions in Heuristic Search

5 Smart Heuristic Methods for Solving Bin Packing Problems

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

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

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

Future Directions in Heuristic Search

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps