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.

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