טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentVornovitsky Kolman
SubjectAbstractions for Devising Compact Controllers for MDPs
DepartmentDepartment of Computer Science
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

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.