AIRS: Anytime Iterative Refinement of a Solution

Many exponentially-hard problems can be solved by searching through a space of states to determine a sequence of steps constituting a solution. Algorithms that produce optimal solutions (e.g., shortest path) generally require greater computational resources (e.g., time) than their sub-optimal counterparts. Consequently, many optimal algorithms cannot produce any usable solution when the amount of time available is limited or hard to predict in advance. Anytime algorithms address this problem by initially finding a suboptimal solution very quickly and then generating incrementally better solutions with additional time, effectively providing the best solution generated so far anytime it is required. In this research, we generate initial solutions cheaply using a fast search algorithm. We then improve this low-quality solution by identifying subsequences of steps that appear, based on heuristic estimates, to be considerably longer than necessary. Finally, we perform a more expensive search between the endpoints of each subsequence to find a shorter connecting path. We will show that this improves the overall solution incrementally over time while always having a valid solution to return whenever time runs out. We present results that demonstrate in several problem domains that AIRS (Anytime Iterative Refinement of a Solution) rivals other widely used and recognized anytime algorithms and also produces results comparable to other popular (but not anytime) heuristic algorithms such as Bidirectional A* search.