RI: Small: Integrating Paradigms for Approximate Stochastic Planning

RI：小型：集成近似随机规划的范式

• 批准号: 1016465
• 负责人: Daniel Weld
• 金额: $ 45.05万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-15 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016465&HistoricalAwards=false
• 关键词: RI; Small; Integrating; Paradigms; Approximate

A fundamental challenge for Artificial Intelligence is sequential decision making under uncertainty, a task where automated algorithms lag far behind human-level intelligence. The primary reason for the disparity is curse of dimensionality - the number of states is exponential in the problem features. Recent advances that restrict decision-theoretic computation to a reachable subset of state space have scaled to moderately-sized problems, but proven ineffective in scaling to real problems. On the other hand, probabilistic planners based on deterministic planning might scale up, but with a massive loss in solution quality.This project is investigating several methods to scale probabilistic planning to real-sized problems. We combine decision-theoretic analysis, basis function approximation and the classical AI planning techniques, to develop a series of highly scalable planners. A common theme in our techniques is the use of deterministic plans to automatically obtain domain abstractions in the form of 'good' or 'bad' properties, or intermediate subgoals. The project introduces and exploits a principled collaboration between decision theory and classical planning techniques, thus retaining the benefits of both - high quality as well as high performance. Experiments show that our new planner solves difficult planning competition problems using orders of magnitude less memory outputting high quality policies.Our research also proposes effective solutions to long-standing problems of generating a set of basis functions and computing a hierarchical problem decomposition. Both basis function approximation and hierarchical decomposition are popular in existing literature for speeding up planning, but they are not fully automated - a human is required to specify the basis functions and the hierarchy. We provide novel, domain-independent solutions that remove this additional human effort. Our research addresses several long standing challenges in AI, like scaling stochastic planning, and automatically generating basis functions and subgoal hierarchies. We expect to produce state-of-the-art planners that will be effective in large and complex real world scenarios, e.g., planetary exploration, military operations planning, and robotic decision making.

人工智能面临的一个根本挑战是在不确定性下进行顺序决策，这是一项自动算法远远落后于人类智能的任务。差异的主要原因是维数灾难-状态的数量在问题特征中是指数级的。将决策理论计算限制在状态空间的可达子集的最新进展已经扩展到中等大小的问题，但在扩展到真实的问题时被证明是无效的。另一方面，基于确定性规划的概率规划器可能会扩大规模，但在解决方案的质量有很大的损失。本项目正在研究几种方法来扩大概率规划到实际规模的问题。我们结合联合收割机决策理论分析，基函数逼近和经典的人工智能规划技术，开发了一系列高度可扩展的规划器。我们的技术中的一个共同主题是使用确定性计划来自动获得“好”或“坏”属性或中间子目标形式的域抽象。该项目引入并利用了决策理论和经典规划技术之间的原则性合作，从而保留了两者的优势-高质量和高性能。实验结果表明，该规划器能够利用数量级更少的内存输出高质量的规划策略，解决了规划竞争问题，并有效地解决了长期存在的基函数集生成和问题分层分解的问题。基函数近似和分层分解在现有文献中都很流行，用于加速规划，但它们不是完全自动化的-需要人来指定基函数和分层结构。我们提供新颖的，独立于领域的解决方案，消除了这种额外的人力投入。 我们的研究解决了人工智能中的几个长期存在的挑战，例如扩展随机规划，自动生成基函数和子目标层次结构。我们希望培养出最先进的规划师，他们将在大型复杂的真实的世界场景中发挥作用，例如，行星探索、军事行动规划和机器人决策。