Improving Determinization in Hindsight for On-line Probabilistic Planning

Authors

  • Sungwook Yoon Palo Alto Research Center
  • Wheeler Ruml University of New Hampshire
  • J. Benton Arizona State University
  • Minh Do Palo Alto Research Center

DOI:

https://doi.org/10.1609/icaps.v20i1.13413

Keywords:

Deterministic Planning, Probabilistic Planning, Scheduling, Sampling

Abstract

Recently, "determinization in hindsight" has enjoyed surprising success in on-line probabilistic planning. This technique evaluates the actions available in the current state by using non-probabilistic planning in deterministic approximations of the original domain. Although the approach has proven itself effective in many challenging domains, it is computationally very expensive. In this paper, we present three significant improvements to help mitigate this expense. First, we use a method for detecting potentially useful actions, allowing us to avoid estimating the values of unnecessary ones. Second, we exploit determinism in the domain by reusing relevant plans rather than computing new ones. Third, we improve action evaluation by increasing the chance that at least one determin- istic plan reaches a goal. Taken together, these improvements allow determinization in hindsight to scale significantly better on large or mostly-deterministic problems.

Downloads

Published

2021-05-25

How to Cite

Yoon, S., Ruml, W., Benton, J., & Do, M. (2021). Improving Determinization in Hindsight for On-line Probabilistic Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 20(1), 209-216. https://doi.org/10.1609/icaps.v20i1.13413