Fast Value Iteration for Goal-Directed Markov Decision Processes
This work addresses planning problems with non-deterministic actions for researchers and practitioners in AI planning, but it is incremental as it builds on standard value iteration methods.
The paper tackled the problem of accelerating value iteration for goal-directed Markov decision processes by proposing techniques that exploit goal-directedness, resulting in significant speedups as shown in empirical studies.
Planning problems where effects of actions are non-deterministic can be modeled as Markov decision processes. Planning problems are usually goal-directed. This paper proposes several techniques for exploiting the goal-directedness to accelerate value iteration, a standard algorithm for solving Markov decision processes. Empirical studies have shown that the techniques can bring about significant speedups.