On the Benefits of Randomly Adjusting Anytime Weighted A*

Authors

  • Abhinav Bhatia College of Information and Computer Sciences, University of Massachusetts Amherst
  • Justin Svegliato College of Information and Computer Sciences, University of Massachusetts Amherst
  • Shlomo Zilberstein College of Information and Computer Sciences, University of Massachusetts Amherst

Keywords:

Real-time Search, Problem Solving Using Search, Time, Memory, And Solution Quality Trade-offs, Random Vs. Systematic Search Strategy Selection

Abstract

Anytime Weighted A*---an anytime heuristic search algorithm that uses a weight to scale the heuristic value of each node in the open list---has proven to be an effective way to manage the trade-off between solution quality and computation time in heuristic search. Finding the best weight, however, is challenging because it depends on not only the characteristics of the domain and the details of the instance at hand, but also the available computation time. We propose a randomized version of this algorithm, called Randomized Weighted A*, that randomly adjusts its weight at runtime and show a counterintuitive phenomenon: RWA* generally performs as well or better than AWA* with the best static weight on a range of benchmark problems. The result is a simple algorithm that is easy to implement and performs consistently well without any offline experimentation or parameter tuning.

Downloads

Published

2021-07-21