E3S Web of Conferences 391, 01140 (2023)
5 Jun 2023
A performance comparison of A* and Depth-Limited Search (DLS), analyzing efficiency, memory usage, and solution quality across different search problems.
Introduction
Pathfinding and graph traversal are core problems in artificial intelligence, with applications ranging from robotics to game development. Two prominent algorithms for these tasks are A* (A-star) and Depth-Limited Search (DLS). A* is known for its heuristic-driven approach that balances exploration and exploitation, while DLS offers a simplified depth-first strategy with a predefined search depth. This paper aims to compare their performance based on efficiency, optimality, and suitability for various problem domains.
Literature Survey
Extensive research has been conducted on both A* and DLS. A* was introduced by Hart et al. (1968) as an optimal and complete algorithm when coupled with an admissible heuristic, making it a preferred choice in many applications. In contrast, DLS is a modification of depth-first search that limits the maximum depth, making it suitable for situations with memory constraints (Russell & Norvig, 2010). Several comparative studies highlight A*’s superior performance in complex environments, while DLS remains a useful technique in simpler scenarios where quick solutions are sufficient (Nilsson, 1998). The trade-offs between optimality and computational resources have been a focal point in this literature.
Proposed Methods
To effectively compare A* and DLS, this study implements both algorithms in a controlled environment using a set of benchmark problems.
A*:The algorithm is enhanced with various admissible heuristics, such as Manhattan distance and Euclidean distance, to evaluate node costs effectively.
DLS: A series of experiments are conducted with different depth limits to assess how the choice of limit impacts the search efficiency and solution quality. The performance metrics include the number of nodes expanded, search time, and path optimality.
Results and Discussions
The study findings reveal that A* surpasses DLS significantly in terms of nodes expanded and search time, especially evident in larger and more intricate graphs. A*'s utilization of heuristics enables it to prioritize promising paths, leading to quicker convergence towards the optimal solution. On the contrary, DLS encounters challenges in deeper search spaces; inadequate depth limits may result in overlooking viable solutions, whereas excessively high limits can escalate memory usage without substantial performance enhancements. The research also underscores situations where DLS can excel, notably in tightly restricted settings or when optimality is of lesser importance.
Conclusion and Future Enhancements
In conclusion, A* is favored for applications requiring optimal pathfinding and efficient search in complex environments, whereas DLS offers benefits in scenarios where memory is a limiting factor. Future research should explore hybrid algorithms that combine the heuristic strengths of A* with the memory efficiency of DLS. Additionally, investigating adaptive depth limits in DLS could enhance its performance by dynamically adjusting the limit based on the search context. Further studies could also analyze the effects of various heuristic functions on A*'s performance across diverse applications, providing deeper insights into optimizing pathfinding algorithms.
Our Team
Our team collaborated effectively on the A vs. Depth-Limited Search* project, leveraging individual strengths to analyze and compare these search algorithms. Through active discussions, shared responsibilities, and collective problem-solving, we successfully implemented and evaluated both algorithms, demonstrating the power of teamwork in achieving technical excellence.
