  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).
