Suboptimal Search with Dynamic Distribution of Suboptimality (Extended Abstract)

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 abstract describes Dynamic Suboptimality Weighted A* (DSWA*), an algorithm introduced at AAAI 2025 that allows suboptimality to be dynamically distributed at runtime based on the properties of the search.