Effective Planning Using Compact Problem Representations

IIS-9977981Robert L.吉万普渡大学$77,529 - 12 mosEffective Planning Using Compact Problem Representations这是一个为期三年的连续奖项的第一年资助。这个项目研究解决随机域中非常大的规划问题的新技术。 在许多现实领域中，行动的效果不能确定性地给出，马尔可夫决策过程（MDP）是一种自然的形式化表示。 工业应用中的许多重要问题（例如，联邦快递包裹路由）和认知建模（例如，不确定域中的问题解决、路线寻找、朴素的人类规划）自然地使用MDP形式体系来表示。 运筹学文献提供了有效的方法来解决问题，表示为MDPs的域中，系统的可能状态的数量相对较小（小于100，000左右）。 然而，大多数工业和人工智能领域并不符合这一限制。 最近的人工智能研究表明，有可能利用状态空间中的命题结构来复杂地表示和解决比以前可能的更大的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