RI: Small: Integrating Paradigms for Approximate Stochastic Planning

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

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.