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. 4 Experimental results Grid Size Variation: In the results obtained by varying the grid size (see Figure 1, 3, 2), ARA* displays relatively stable solving time. However, it has some fluctuation in its standard deviation, with a slight increase as the grid size increases. Its maximum value of (76ms) was obtained at size 200. At grid size 50, RTAA* was the fastest algorithm, recording a solving time of (21ms). Subsequently, its solving time and allocated memory increased notably with the grid size. which indicates that the grid size affects the performance of RTAA* as it increases; and the algorithm is forced to do more searches. LRTA* has the highest solving time across all sizes compared to ARA*, RTAA*, D* Lite, LPA*, and even D* at size 50. Its performance greatly varies as indicated by its high standard deviations. Moreover, LRTA* did not show a clear trend in increasing time relative to grid size, indicating that it may be unpredictable and inefficient for this task. Both D* Lite and LPA* exhibited relatively stable performances. D* Lite has a lower solution time across all grid sizes compared to LPA*. However, both algorithm’s standard deviations show some degree of fluctuation. D*, on the other hand, showcased an extreme increase in solution time when transitioning from size 50 to 100, revealing its challenges as the grid size increases. Regarding path cost (see Figure 3), while LPA*, D*, and ARA* lines overlap, suggesting similar path costs across all grid sizes, D* Lite consistently generates the shortest paths across all grid sizes, with a relatively small standard deviation. In terms of memory allocation (see Figure 2), LPA* and D* Lite were consistent across all grid sizes, requiring the least memory among all algorithms. In contrast, RTAA*, LRTA*, and D* demanded more memory as the grid size increased. Start to goal distance variation: The obtained results from running the algorithms on grids with varying start-to-goal distances (see figures 4, 5, 6) revealed that both the mean of the path cost and the mean of solving time for all algorithms escalate as the distance increases (see Figure 4, 6). This outcome was expected, since longer distances naturally demand more computational efforts and more nodes to expand. ARA* seems to have a strong correlation with the distance between the start and goal; its solving time is drastically influenced by this factor. Precisely, ARA* remains the fastest algorithm for distances smaller than approximately 140. Beyond this threshold, however, RTAA* takes the lead in terms of solving time. Observing the path cost (see Figure 6), the lines for D* Lite, LRTA* RTAA* overlap, indicating similar performances. Correspondingly, LPA*, ARA*, and D* also exhibit overlapping lines, where D* Lite being the algorithm with the lowest path cost. In the context of allocated memory (see Figure 5), D* lite allocates the least memory for all distances followed by LPA* and then ARA*. The rest of the algorithms allocate almost a similar amount of memory with D* being the worst. Obstacle density variation: RTAA* constantly excels by producing the shortest solving time among all algorithms and across all obstacle densities as depicted in Figure 7. This superior performance can be explained due to its rapid heuristic values update procedure within its local search space. The rest of the algorithm’s solving time increases as the obstacle density rises, with D* being the one with a higher solving time, except for LPA*, which starts to decrease slightly after a density of 0.20. Figure 9 shows that the path cost of all algorithms tends to increase as the density increases, which can be a predictable outcome since denser environments pose more complex navigation challenges. Amongst all algorithms, D* Lite maintains the lowest path across all densities, marking its efficiency in complex environments. D* Lite’s performance is followed by LRTA* for obstacle densities below 0.25, and RTAA* outperforms the rest for densities higher than 0.25. In addition to maintaining the lowest path cost, D* Lite allocates the least amount of memory at all densities, as depicted in Figure 8, followed by LPA*. In contrast, both RTAA* and LRTA* consume a lot of memory, but not as much as D*, which allocates even more. We hypothesize that changing other parameters that we have fixed while varying other ones could indeed provide us with further insight into how these parameters interact and affect the performance of the search algorithms i.e., using an obstacle density of 0.4 rather than 0.25 while changing the grid size. However, to maintain simplicity and manage the computational resources, we opted to keep a balanced grid size, obstacle density, and distance from the start to the goal that will help us fairly represent an environment for a pathfinding task. Also, the combination of varying one parameter independently from the other ones and then repeating the same experiment, in which we vary the fixed parameter using all other possible values would dramatically increase the number of possible experiments that must be done, in addition to the number of runs that they must be made for each grid, which will amplify the number of experiments that must be performed. Horizontal wall configuration: In the horizontal wall configuration results, as depicted in Figures (10, 11, and 12). We observed that the path cost tends to increase for all algorithms as walls are added (see Figure 12), which is expected. LRTA* exhibited the highest solving time (see Figure 10), followed, in descending order by D* Lite, RTAA*, LPA*, ARA*, and LRTA*. Regarding the obtained results for the path cost, D* Lite produces the most optimal paths followed by ARA*, D*, and LPA*. In terms of memory allocation (see Figure 11), all algorithms tend to allocate the same amount of memory even when new walls are introduced, with only slight increases. Among all algorithms, D* allocates the highest amount of memory, while LPA* allocates the least memory, followed by D* Lite, LRTA*, RTAA*, and ARA*. However, it is worth noting that both ARA* and LPA* had a remarkable increase in memory consumption when adding the last wall. Horizontal wall length configuration: The results obtained from varying the wall sizes are depicted in the figures 13, 14, and 15. The numbers on the axis represent seven different lengths. The initial length corresponds to half the grid width, and with each subsequent step, it increases by two obstacles. All algorithm’s solving times varied across the different wall lengths showing a general trend of increasing as the wall lengths increase as depicted in Figure 13. LRTA* recorded the highest solving times, whereas ARA* recorded the lowest across all wall lengths. For the amount of memory used by the algorithms (see Figure 14), D* was again the one that consumed more memory. In contrast, both D* Lite and LPA* allocated almost similar and the latest amount of memory over all seven wall lengths. Turning to the path cost metrics (see Figure 15), all algorithm’s path costs tend to increase as the wall lengths increase, with D* Lite generating the lowest path costs for all wall lengths. Based on the results obtained in the grid size variation, the performance of most algorithms, particularly RTAA*, was affected by grid size. In the meanwhile, the high level of consistency of ARA* performance in terms of solving time regardless of the grid size indicates its suitability for various grid sizes higher than 100. D* proved to be the one generating the lowest path costs, and also allocating the least memory alongside LPA*. Obstacle density results showed that it is a factor that influences the performance of all algorithms. However, D* Lite kept generating the most efficient paths, which indicates its effectiveness in dense environments. Based on the results obtained by increasing the start-to-goal distance, ARA* appears to be the most affected one since its solving time continuously increases. In addition to allocating the least memory, D* Lite consistently exhibits the optimal paths, which indicates its utility where the shortest path is of importance. Adding horizontal walls each time in the same grid setting has increased the path length and solving time for all algorithms with D* being the worst. D* Lite keeps its optimal performance by generating the most optimal paths, which suggests its suitability in environments with many obstacles. However when increasing the length of the walls, ARA* displayed the lowest solving times, suggesting its efficiency in environments with extensive barriers. Moreover, D* Lite keeps generating the lowest path costs. In summary, while each algorithm has its strengths and weaknesses, D* Lite has continuously shown a good performance across most conditions, particularly in generating the optimal paths. Meanwhile, ARA* has proved its stability in producing the fastest paths regardless of the grid size. Moreover, RTAA* showed its ability to generate faster paths regardless of the obstacle density due to its faster procedure in updating the heuristic values. 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. 4 Experimental results Grid Size Variation: In the results obtained by varying the grid size (see Figure 1, 3, 2), ARA* displays relatively stable solving time. However, it has some fluctuation in its standard deviation, with a slight increase as the grid size increases. Its maximum value of (76ms) was obtained at size 200. At grid size 50, RTAA* was the fastest algorithm, recording a solving time of (21ms). Subsequently, its solving time and allocated memory increased notably with the grid size. which indicates that the grid size affects the performance of RTAA* as it increases; and the algorithm is forced to do more searches. LRTA* has the highest solving time across all sizes compared to ARA*, RTAA*, D* Lite, LPA*, and even D* at size 50. Its performance greatly varies as indicated by its high standard deviations. Moreover, LRTA* did not show a clear trend in increasing time relative to grid size, indicating that it may be unpredictable and inefficient for this task. Both D* Lite and LPA* exhibited relatively stable performances. D* Lite has a lower solution time across all grid sizes compared to LPA*. However, both algorithm’s standard deviations show some degree of fluctuation. D*, on the other hand, showcased an extreme increase in solution time when transitioning from size 50 to 100, revealing its challenges as the grid size increases. Grid Size Variation: Regarding path cost (see Figure 3), while LPA*, D*, and ARA* lines overlap, suggesting similar path costs across all grid sizes, D* Lite consistently generates the shortest paths across all grid sizes, with a relatively small standard deviation. In terms of memory allocation (see Figure 2), LPA* and D* Lite were consistent across all grid sizes, requiring the least memory among all algorithms. In contrast, RTAA*, LRTA*, and D* demanded more memory as the grid size increased. Start to goal distance variation: The obtained results from running the algorithms on grids with Start to goal distance variation: varying start-to-goal distances (see figures 4, 5, 6) revealed that both the mean of the path cost and the mean of solving time for all algorithms escalate as the distance increases (see Figure 4, 6). This outcome was expected, since longer distances naturally demand more computational efforts and more nodes to expand. ARA* seems to have a strong correlation with the distance between the start and goal; its solving time is drastically influenced by this factor. Precisely, ARA* remains the fastest algorithm for distances smaller than approximately 140. Beyond this threshold, however, RTAA* takes the lead in terms of solving time. Observing the path cost (see Figure 6), the lines for D* Lite, LRTA* RTAA* overlap, indicating similar performances. Correspondingly, LPA*, ARA*, and D* also exhibit overlapping lines, where D* Lite being the algorithm with the lowest path cost. In the context of allocated memory (see Figure 5), D* lite allocates the least memory for all distances followed by LPA* and then ARA*. The rest of the algorithms allocate almost a similar amount of memory with D* being the worst. Obstacle density variation: RTAA* constantly excels by producing the shortest solving time among all algorithms and across all obstacle densities as depicted in Figure 7. This superior performance can be explained due to its rapid heuristic values update procedure within its local search space. The rest of the algorithm’s solving time increases as the obstacle density rises, with D* being the one with a higher solving time, except for LPA*, which starts to decrease slightly after a density of 0.20. Obstacle density variation: Figure 9 shows that the path cost of all algorithms tends to increase as the density increases, which can be a predictable outcome since denser environments pose more complex navigation challenges. Amongst all algorithms, D* Lite maintains the lowest path across all densities, marking its efficiency in complex environments. D* Lite’s performance is followed by LRTA* for obstacle densities below 0.25, and RTAA* outperforms the rest for densities higher than 0.25. In addition to maintaining the lowest path cost, D* Lite allocates the least amount of memory at all densities, as depicted in Figure 8, followed by LPA*. In contrast, both RTAA* and LRTA* consume a lot of memory, but not as much as D*, which allocates even more. We hypothesize that changing other parameters that we have fixed while varying other ones could indeed provide us with further insight into how these parameters interact and affect the performance of the search algorithms i.e., using an obstacle density of 0.4 rather than 0.25 while changing the grid size. However, to maintain simplicity and manage the computational resources, we opted to keep a balanced grid size, obstacle density, and distance from the start to the goal that will help us fairly represent an environment for a pathfinding task. Also, the combination of varying one parameter independently from the other ones and then repeating the same experiment, in which we vary the fixed parameter using all other possible values would dramatically increase the number of possible experiments that must be done, in addition to the number of runs that they must be made for each grid, which will amplify the number of experiments that must be performed. Horizontal wall configuration: In the horizontal wall configuration results, as depicted in Figures Horizontal wall configuration: (10, 11, and 12). We observed that the path cost tends to increase for all algorithms as walls are added (see Figure 12), which is expected. LRTA* exhibited the highest solving time (see Figure 10), followed, in descending order by D* Lite, RTAA*, LPA*, ARA*, and LRTA*. Regarding the obtained results for the path cost, D* Lite produces the most optimal paths followed by ARA*, D*, and LPA*. In terms of memory allocation (see Figure 11), all algorithms tend to allocate the same amount of memory even when new walls are introduced, with only slight increases. Among all algorithms, D* allocates the highest amount of memory, while LPA* allocates the least memory, followed by D* Lite, LRTA*, RTAA*, and ARA*. However, it is worth noting that both ARA* and LPA* had a remarkable increase in memory consumption when adding the last wall. Horizontal wall length configuration: The results obtained from varying the wall sizes are depicted in the figures 13, 14, and 15. The numbers on the axis represent seven different lengths. The initial length corresponds to half the grid width, and with each subsequent step, it increases by two obstacles. Horizontal wall length configuration: All algorithm’s solving times varied across the different wall lengths showing a general trend of increasing as the wall lengths increase as depicted in Figure 13. LRTA* recorded the highest solving times, whereas ARA* recorded the lowest across all wall lengths. For the amount of memory used by the algorithms (see Figure 14), D* was again the one that consumed more memory. In contrast, both D* Lite and LPA* allocated almost similar and the latest amount of memory over all seven wall lengths. Turning to the path cost metrics (see Figure 15), all algorithm’s path costs tend to increase as the wall lengths increase, with D* Lite generating the lowest path costs for all wall lengths. Based on the results obtained in the grid size variation, the performance of most algorithms, particularly RTAA*, was affected by grid size. In the meanwhile, the high level of consistency of ARA* performance in terms of solving time regardless of the grid size indicates its suitability for various grid sizes higher than 100. D* proved to be the one generating the lowest path costs, and also allocating the least memory alongside LPA*. Obstacle density results showed that it is a factor that influences the performance of all algorithms. However, D* Lite kept generating the most efficient paths, which indicates its effectiveness in dense environments. Based on the results obtained by increasing the start-to-goal distance, ARA* appears to be the most affected one since its solving time continuously increases. In addition to allocating the least memory, D* Lite consistently exhibits the optimal paths, which indicates its utility where the shortest path is of importance. Adding horizontal walls each time in the same grid setting has increased the path length and solving time for all algorithms with D* being the worst. D* Lite keeps its optimal performance by generating the most optimal paths, which suggests its suitability in environments with many obstacles. However when increasing the length of the walls, ARA* displayed the lowest solving times, suggesting its efficiency in environments with extensive barriers. Moreover, D* Lite keeps generating the lowest path costs. In summary, while each algorithm has its strengths and weaknesses, D* Lite has continuously shown a good performance across most conditions, particularly in generating the optimal paths. Meanwhile, ARA* has proved its stability in producing the fastest paths regardless of the grid size. Moreover, RTAA* showed its ability to generate faster paths regardless of the obstacle density due to its faster procedure in updating the heuristic values. 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.

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

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

Performance Metrics of Heuristic Search Algorithms in Grid Environments