Performance Metrics of Heuristic Search Algorithms in Grid Environments

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.