First Order Decision Diagrams for Relational MDPs

Chenggang Wang, Saket Joshi, Roni Khardon

Dynamic programming algorithms provide a basic tool identifying optimal solutions in Markov Decision Processes (MDP). The paper develops a representation for decision diagrams suitable for describing value functions, transition probabilities, and domain dynamics of First Order or Relational MDPs (FOMDP). By developing appropriate operations for such diagrams the paper shows how value iteration can be performed compactly for such problems. This improves on previous approaches since the representation combines compact form with efficient operations. The work also raises interesting issues on suitability of different representations to different FOMDPs tasks.