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.