Effective Planning Using Compact Problem Representations

[is -9977981] robert L. GivanPurdue大学77,529 - 12美元使用紧凑问题表示的有效规划这是一项为期三年的持续奖励的第一年资助。这个项目研究了解决随机域中非常大的规划问题的新技术。在许多现实领域中，行为的影响不能确定性地给定，马尔可夫决策过程（mdp）是一种自然的形式表示。工业应用程序（例如，联邦快递包裹路由）和认知建模（例如，不确定领域中的问题解决、路由查找、朴素的人类规划）中的许多重要问题都自然地使用MDP形式化表示。运筹学文献已经提供了有效的方法来解决系统可能状态数量相对较少（少于100,000左右）的领域中以mdp表示的问题。然而，大多数工业和人工智能领域不符合这一限制。最近的人工智能研究表明，利用状态空间中的命题结构来紧凑地表示和解决比以前更大的mdp是可能的。传统的人工智能规划研究主要集中在确定性规划领域，并且严重依赖于这些领域的紧凑、逻辑表示。该项目旨在通过为MDP问题设计新的紧凑表示，同时保留传统MDP解决方案技术的有效性，将确定性规划中的许多经验教训应用于随机设置。使用这种表示将允许描述和有效地解决比目前可能的更大的MDP问题，从而导致许多实际规划和优化任务的自动化接近最优解决方案，这些任务目前需要手动启发式解决方案

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