Suboptimal Search with Dynamic Distribution of Suboptimality
Mohammadreza Hami, Nathan R. Sturtevant
Abstract
In bounded-suboptimal heuristic search, the aim is to find a solution path within a given bound as quickly as possible, which is crucial when computational resources are limited. Recent research has demonstrated Weighted A* variants such as XDP that find bounded suboptimal solutions without needing to perform state re-expansions; they work by shifting where the suboptimality in the search is allowed. However, the suboptimality distribution is fixed before the search begins. This paper introduces Dynamic Suboptimality Weighted A* (DSWA*), a search framework that allows suboptimality to be dynamically distributed at runtime, based on the properties of the search. Experiments show that dynamic policies can consistently outperform existing algorithms across a diverse set of domains, particularly those with dynamic costs.
BibTeX
@article{Hami_Sturtevant_2025, title={Suboptimal Search with Dynamic Distribution of Suboptimality}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34905}, DOI={10.1609/aaai.v39i25.34905}, abstractNote={In bounded-suboptimal heuristic search, the aim is to find a solution path within a given bound as quickly as possible, which is crucial when computational resources are limited. Recent research has demonstrated Weighted A* variants such as XDP that find bounded suboptimal solutions without needing to perform state re-expansions; they work by shifting where the suboptimality in the search is allowed. However, the suboptimality distribution is fixed before the search begins. This paper introduces Dynamic Suboptimality Weighted A* (DSWA*), a search framework that allows suboptimality to be dynamically distributed at runtime, based on the properties of the search. Experiments show that dynamic policies can consistently outperform existing algorithms across a diverse set of domains, particularly those with dynamic costs.}, number={25}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Hami, Mohammadreza and Sturtevant, Nathan R.}, year={2025}, month={Apr.}, pages={26991-26999} }