A Logic-based Approach to Dynamic Programming

Contents

We present a first-order value iteration algorithm that addresses the scalability problem of classical dynamic programming techniques by logically partitioning the state space. An MDP is represented in the Probabilistic Fluent Calculus, that is a first-order language for reasoning about actions. Moreover, we develop a normalization algorithm that discovers and prunes redundant states. We have implemented our approach and describe some experimental results.