Associate Professor - Tufts University

First Order Decision Diagrams for Relational Markov Decision Processes

Markov decision processes (MDP) capture sequential decision making under uncertainty, where an agent must choose actions so as to optimize long term reward. Relational MDPs capture problems where world states have an internal relational structure that can be naturally described in terms of objects and relations among them. For example, a system managing shipment of packages using trucks and airplanes must optimize for short delivery time and low costs. Such problems are often huge in size and yet offer potential for efficient algorithmic solutions taking advantage of their structure.

The talk will first introduce First Order Decision Diagrams (FODD), a new compact representation for functions over relational structures, generalizing the well known binary decision diagrams. It will then show how a "calculus of FODDs" can be used to solve relational MDPs at the abstract level using a "lifted" form of the value iteration algorithm. Several extensions of this approach will be briefly discussed handling more expressive representations, lifting other algorithms, and coping with partial observability. Finally results of a prototype implementation will demonstrate the potential of this approach in solving challenging problems.