Improving the Scalability of Stochastic Planning Algorithms

这是一个研究项目，旨在克服限制部分可观察马尔可夫决策过程算法有用性的障碍。在不确定规划领域，马尔可夫决策过程（MDP）作为一个强大而优雅的框架，在移动机器人控制、机器维护、手势识别、医疗诊断和治疗以及政策制定等广泛的应用领域中解决问题。对于决策者可以完全观察到领域中间状态的情况，有许多有效的算法可以解决大问题。然而，在许多应用程序中，假设可以获得完美的状态信息是不现实的。更通用的、部分可观察的MDP （POMDP）解决了这个困难，但是在这种情况下，计划的计算复杂性使得很难将现有的解决方案技术应用于实际应用程序。该项目将研究解决POMDP算法中关键计算瓶颈的新方法。为此，它将(a)确定和审查可用于大大加速POMDP解决技术的每个关键组成部分的新型信念空间结构；(b)评价这些改进对广泛的精确和近似算法的影响，目的是证明指数加速；(c)将新办法与以前确定的利用搜索、符号表示和并行化加速MDP和POMDP算法的方法结合起来；(d)制订一套新的具有挑战性的测试问题和基准，比现有的简单问题难得多，并对已开发的技术进行严格的评价和比较；(e)增加人工智能社区与采用POMDP解决方案技术（如运筹学和管理科学）的其他社区之间的互动，并利用来自这些社区的最佳解决方案技术汇集在一起时产生的协同效应。该方法基于对信念空间中新型结构的探索，这使得将主要计算组件分解为更快的、基于区域的操作成为可能。理论分析和初步实现表明，该方法可以显著提高精确算法和近似算法的效率，从而提高POMDP算法的可扩展性和适用性。新设计的技术特别适合在网格计算机上并行实现，为性能提升提供了重要的额外机会。该项目的技术影响包括对随机域规划复杂性的理解以及高效规划算法的开发的基本贡献，这些算法可以在计算时间上提供指数级的节省。新方法改进了一些计算操作，这些操作通常被用作现有算法的组成部分-包括精确和近似。因此，该方法的优点很容易转移到许多现有的解决方案技术中。该项目的更广泛的影响来自于所产生的技术在几个科学和工程学科中的广泛适用性，马萨诸塞大学阿姆赫斯特分校的直接教育影响，非传统传播工作的广泛计划，使实验测试平台可供研究界使用，并加强了主要研究者与法国INRIA国际研究团队之间的现有联盟。

This is a research project intended to overcome barriers that have limited the usefulness of partially-observable Markov decision process algorithms. In the area of planning under uncertainty, the Markov decision process (MDP) has emerged as a powerful and elegant framework for solving problems in a wide range of application domains such as mobile robot control, machine maintenance, gesture recognition, medical diagnosis and treatment, and policy making. For situations in which the decision maker can fully observe the intermediate state of the domain, there are many effective algorithms that can solve large problems. However, in many applications, it is unrealistic to assume that perfect state information is available. The more general, partially-observable MDP (POMDP) addresses this difficulty, but in this case the computational complexity of planning makes it hard to apply existing solution techniques to practical applications. This project will study new ways to address the key computational bottlenecks in POMDP algorithms. To achieve this, it will (a) Identify and examine new types of belief-space structures that can be used to accelerate significantly each of the key components of POMDP solution techniques; (b) Evaluate the impact of these improvements on a wide range of exact and approximate algorithms with the goal of demonstrating exponential acceleration; (c) Integrate the new approach with previously identified methods for accelerating MDP and POMDP algorithms using search, symbolic representations, and parallelization; (d) Develop a new set of challenging test problems and benchmarks that are significantly harder than the existing toy problems and perform a rigorous evaluation and comparison of the developed techniques; and (e) Increase the interaction between the artificial intelligence community and other communities that employ POMDP solution techniques such as operations research and management sciences, and exploit the synergy that arises when the best solution techniques from these communities are brought together. The approach is based on exploring new types of structures in the belief space that make it possible to decompose the main computational components into faster, region-based operations. A theoretical analysis of the new approach and a preliminary implementation show that it can significantly increase the efficiency of both exact and approximate algorithms and thus it can improve the scalability of POMDP algorithms and increase their applicability. The newly designed technique is particularly suitable for parallel implementation on grid computers, offering significant additional opportunities for performance gains. The technical impact of this project involves fundamental contributions to the understanding of the complexity of planning in stochastic domains as well as the development of efficient planning algorithms that provide exponential savings in computing time. The new approach improves several computational operations that are often used as components of existing algorithms - both exact and approximate. Therefore, the benefits of the approach transfer easily to many existing solution techniques. The broader impact of the project stems from the broad applicability of the resulting technology in several scientific and engineering disciplines, the immediate educational impact at the University of Massachusetts Amherst, an extensive plan for non-traditional dissemination efforts, making the experimental testbed available to the research community, and enhancing an existing alliance between the principal investigator and an international research team at INRIA, France.