A Heuristic Search Algorithm for Solving First-Order MDPs
This work addresses the challenge of efficiently solving FOMDPs for planning systems, but it appears incremental as it builds on existing techniques like state abstraction and heuristic search.
The paper tackles the problem of solving first-order Markov Decision Processes (FOMDPs) by introducing a heuristic search algorithm that combines first-order state abstraction and heuristic search, resulting in a system called FCPlanner that competed in the International Planning Competition in 2004.
We present a heuristic search algorithm for solving first-order MDPs (FOMDPs). Our approach combines first-order state abstraction that avoids evaluating states individually, and heuristic search that avoids evaluating all states. Firstly, we apply state abstraction directly on the FOMDP avoiding propositionalization. Such kind of abstraction is referred to as firstorder state abstraction. Secondly, guided by an admissible heuristic, the search is restricted only to those states that are reachable from the initial state. We demonstrate the usefullness of the above techniques for solving FOMDPs on a system, referred to as FCPlanner, that entered the probabilistic track of the International Planning Competition (IPC'2004).