发帖
雷达卡
摘要翻译：
本文研究了随机最短路径问题(SSP)中的规划问题，这是马尔可夫决策问题(MDP)的一个子类。我们关注的是状态空间可以完全枚举的中等规模问题。该问题有许多重要的应用，如不确定环境下的导航和规划。我们提出了一种新的方法来构造一个多层次的层次结构，该层次结构由原始问题的逐步简单的抽象组成。一旦计算出来，层次结构可以通过首先为最抽象的级别找到策略，然后递归地将其细化为原始问题的解决方案来加快规划。这种方法是完全自动化的，在返回接近最优解的同时，在样本问题上比最先进的MDP求解器加快了两个数量级。我们还证明了由于抽象的使用而导致的解的最优性损失的理论界。
---
英文标题：
《Speeding Up Planning in Markov Decision Processes via Automatically
Constructed Abstractions》
---
作者：
Alejandro Isaza, Csaba Szepesvari, Vadim Bulitko, Russell Greiner
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
In this paper, we consider planning in stochastic shortest path (SSP) problems, a subclass of Markov Decision Problems (MDP). We focus on medium-size problems whose state space can be fully enumerated. This problem has numerous important applications, such as navigation and planning under uncertainty. We propose a new approach for constructing a multi-level hierarchy of progressively simpler abstractions of the original problem. Once computed, the hierarchy can be used to speed up planning by first finding a policy for the most abstract level and then recursively refining it into a solution to the original problem. This approach is fully automated and delivers a speed-up of two orders of magnitude over a state-of-the-art MDP solver on sample problems while returning near-optimal solutions. We also prove theoretical bounds on the loss of solution optimality resulting from the use of abstractions.
---
PDF链接：
https://arxiv.org/pdf/1206.3233
京公网安备 11010802022788号
