M.Sc Student | Vornovitsky Kolman |
---|---|

Subject | Abstractions for Devising Compact Controllers for MDPs |

Department | Department of Computer Science |

Supervisor | Professor Carmel Domshlak |

Full Thesis text |

The ability to plan a course of
action is crucial for intelligent systems. Planning under uncertainty is
captured by *decision-theoretic planning* (DTP), where the goal is to
devise a policy of acting with a high expected utility. This is in contrast to *deterministic
planning*, where a sequence of actions that translates an agent from an
initial state to a goal state is sought. The classic mathematical framework for
decision-theoretic planning is that of the *Markov decision process*
(MDP).

One of the most popular structures of AI planning is variable-based representations to describe problems, which is common practice in planning. Such variable based representations allow for compact description of the huge state space, but cast doubt upon the viability of most standard solutions for MDPs, i.e., algorithms which compute the optimal policy assuming an explicit state space.

Some works have presented solutions
for MDPs with variable based representation. *Factored MDPs* (Boutilier et
al.) use implicit variable based state space and a *dynamic Bayesian network*
(DBN) for transition model. Most works have approximated the solution using an
approximate value function with compact representation given by a linear
combination of possibly non-linear, basis functions (Bellman et al. 1963;
Sutton, 1988; Tsitsiklis et al. 1997). Guestrin et al. 2003 proposed a similar
solution, built on the idea of Koller & Parr (1999, 2000) and using
factored (linear) functions, where each basis function is restricted to some
small subset of the state variables.

While previous works on factored MDPs approximate the value function of the original MDP, in this work we explore a different approach of calculating the exact value function of an approximated MDP. We exploit and extend a technique known as over-approximating abstractions to approximately solve the exponential state space MDP problem.

An abstraction can, in general, be seen as a mapping that reduces the size of the state space by compacting several states into one. If the abstract state space is made small enough, the standard solutions for explicit state space become feasible for it as well. Over-approximating abstractions, adapted to the context of deterministic planning by Helmert, Haslum & Hoffmann. We depart from these methodologies, adapting the merge-and-shrink abstraction technique to devise compact controllers for MDPs. We introduce the notion of action abstractions to extend the merge-and-shrink abstraction technique for MDPs and for deterministic planning. Finally, we provide a clear testbed evaluation for our methods and compare them to other state-of-the-art approaches.