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. I 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. The advantage of this approach is that the resulting policy is given at the abstract level and it can be used to solve any instance of any size in the domain. Results of a prototype implementation on simulated challenge problems, and when deployed to control a physical robot, illustrate the potential of this approach. |

Back to School Seminar Webpage |