  We present a heuristic search algorithm for solving first-order Markov
Decision Processes (FOMDPs). Our approach combines first-order state
abstraction that avoids evaluating states individually, and heuristic search
that avoids evaluating all states. Firstly, in contrast to existing systems,
which start with propositionalizing the FOMDP and then perform state
abstraction on its propositionalized version we apply state abstraction
directly on the FOMDP avoiding propositionalization. This kind of abstraction
is referred to as first-order state abstraction. Secondly, guided by an
admissible heuristic, the search is restricted to those states that are
reachable from the initial state. We demonstrate the usefulness of the above
techniques for solving FOMDPs with a system, referred to as FluCaP (formerly,
FCPlanner), that entered the probabilistic track of the 2004 International
Planning Competition (IPC2004) and demonstrated an advantage over other
planners on the problems represented in first-order terms.
