Optimal Metric Planning with State Sets in Automata Representation

Abstract

This paper proposes an optimal approach to infinite-state ac-tion planning exploiting automata theory. State sets and ac-tions are characterized by Presburger formulas and repre-sented using minimized finite state machines. The explo-ration that contributes to the planning via model checking paradigm applies symbolic images in order to compute the deterministic finite automaton for the sets of successors. A large fraction of metric planning problems can be translated into Presburger arithmetic, while derived predicates are sim-ply compiled away. We further propose three algorithms for computing optimal plans; one for uniform action costs, one for the additive cost model, and one for linear plan metrics. Furthermore, an extension for infinite state sets is discussed.