Effective Planning Using Compact Problem Representations

点击翻译按钮获取中文摘要

IIS-9977981Robert L. GivanPurdue University$77,529 - 12 mosEffective Planning Using Compact Problem RepresentationsThis is the first year funding of a three year continuing award. This project examines new techniques for solving very large planning problems in stochastic domains. In many realistic domains, where the effects of actions cannot be deterministically given, Markov Decision Processes (MDPs) are a natural formal representation. Many important problems in both industrial applications (e.g., Federal Express package routing) and cognitive modeling (e.g., problem-solving in uncertain domains, route finding, naive human planning) are naturally represented using the MDP formalism. The operations research literature has provided effective methods for solving problems represented as MDPs for domains in which the number of possible states of the system is relatively small (less than 100,000 or so). However, most industrial and artificial intelligence domains do not meet this restriction. Recent AI research has shown that it is possible to exploit propositional structure in the state space in order to compactly represent and solve larger MDPs than was previously possible. Traditional AI planning research has concentrated on deterministic planning domains, and has relied heavily on compact, logical representations for such domains. This project aims to apply many of the lessons learned in deterministic planning to the stochastic setting by designing new compact representations for MDP problems while retaining the effectiveness of traditional MDP solution techniques. Use of such representations would allow the description and effective solution of much larger MDP problems than is currently possible, resulting in the automated near-optimal solution of many practical planning and optimization tasks that currently require heuristic solution by hand