Markov Decision Processes are a powerful framework for planning under uncertainty, but current algorithms have difficulties scaling to large problems. We present a novel probabilistic planner based on the notion of hybridizing two algorithms. In particular, we hybridize GPT, an exact MDP solver, with MBP, a planner that plans using a qualitative (non-deterministic) model of uncertainty. Whereas exact MDP solvers produce optimal solutions, qualitative planners sacrifice optimality to achieve speed and high scalability. Our hybridized planner, Hyb-PLAN, is able to obtain the best of both techniques - speed, quality and scalability. Moreover, Hyb-Plan has excellent anytime properties and makes effective use of available time and memory.
展开▼