First Order Decision Diagrams for Relational MDPs

Abstract

In recent years there has been a growing interest in first order representation of data in the Machine Learning community. In the "Learning to Plan" domain, the states and actions of an automated planning agent are represented as relations among objects in the agent's world. The agent then has to learn a map from states to actions (called a policy), that optimizes some objective function defined over these states and actions. Unfortunately, first order representations bring in expressive power and complexity in a package deal, and efficient algorithms are needed to deal with them. Our work introduces new data structures in the form of "first oder binary decision diagrams" and "first order trees with logical leaves" and efficient algorithms for them in different settings. We are developing learning algorithms and other operations for these data structures that will enable solutions of large first-order planning problems. The talk will give an overview of this area of research and then describe the data structures and algorithms being developed along with some preliminary experimental results.