Iterative-Refinement for Action Timing Discretization

Abstract

Artificial Intelligence search algorithms search discrete systems. To apply such algorithms to continuous systems, such systems must first be discretized, i.e. approximated as discrete systems. Action-based discretization requires that both action parameters and action timing be discretized. We focus on the problem of action timing discretization. After describing an e-admissible variant of Korf's recursive best-first search (e-RBFS), we introduce iterative-refinement e-admissible recursive best-first search (IR e-RBFS) which offers significantly better performance for initial time delays between search states over several orders of magnitude. Lack of knowledge of a good time discretization is compensated for by knowledge of a suitable solution cost upper bound.