  Markov decision processes capture sequential decision making under
uncertainty, where an agent must choose actions so as to optimize long term
reward. The paper studies efficient reasoning mechanisms for Relational Markov
Decision Processes (RMDP) where world states have an internal relational
structure that can be naturally described in terms of objects and relations
among them. Two contributions are presented. First, the paper develops First
Order Decision Diagrams (FODD), a new compact representation for functions over
relational structures, together with a set of operators to combine FODDs, and
novel reduction techniques to keep the representation small. Second, the paper
shows how FODDs can be used to develop solutions for RMDPs, where reasoning is
performed at the abstract level and the resulting optimal policy is independent
of domain size (number of objects) or instantiation. In particular, a variant
of the value iteration algorithm is developed by using special operations over
FODDs, and the algorithm is shown to converge to the optimal policy.
