Reverse Iterative Deepening for Finite-Horizon MDPs with Large Branching Factors
Reverse Iterative Deepening for Finite-Horizon MDPs with Large Branching Factors
复制标题
具有大分支因子的有限范围 MDP 的逆向迭代深化
DOI：
10.1609/icaps.v22i1.13523
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Daniel S. Weld
中科院分区：
文献类型：
--
作者：
A. Kolobov;P. Dai;Mausam;Daniel S. Weld
与以往的竞赛不同，2011年国际概率规划竞赛（IPPC-2011）强调了具有大分支因子的有限时域奖励最大化问题。这些MDP模拟了更现实的规划场景，并向以前最先进的规划者提出了挑战（例如，来自IPPC-2008的那些），其主要基于域确定--一种更适合于具有小分支因子的目标导向的MDP的技术。此外，大的分支因子也使得RTDP和LAO风格算法的现有实现效率低下。在本文中，我们介绍了GLUTTON，我们的规划师在IPPC-2011，这些具有挑战性的MDPs表现良好。GLUTTON使用的主要算法是LR 2 TDP，这是一种基于LRTDP的有限时间问题优化算法，围绕着反向迭代深化的新思想。我们详细介绍了LR 2 TDP本身以及GLUTTON中包含的一系列优化，这些优化帮助LR 2 TDP在具有大分支因子的困难问题上实现具有竞争力的性能-对转换函数进行子采样，分离出自然动态，缓存转换函数样本等。实验表明，GLUTTON和PROST，IPPC-2011年的赢家，有互补的优势，与GLUTTON表现出上级性能的问题与几个高回报的终端状态。
In contrast to previous competitions, where the problems were goal-based, the 2011 International Probabilistic Planning Competition (IPPC-2011) emphasized finite-horizon reward maximization problems with large branching factors. These MDPs modeled more realistic planning scenarios and presented challenges to the previous state-of-the-art planners (e.g., those from IPPC-2008), which were primarily based on domain determinization — a technique more suited to goal-oriented MDPs with small branching factors. Moreover, large branching factors render the existing implementations of RTDP- and LAO-style algorithms inefficient as well. In this paper we present GLUTTON, our planner at IPPC-2011 that performed well on these challenging MDPs. The main algorithm used by GLUTTON is LR2TDP, an LRTDP-based optimal algorithm for finite-horizon problems centered around the novel idea of reverse iterative deepening. We detail LR2TDP itself as well as a series of optimizations included in GLUTTON that help LR2TDP achieve competitive performance on difficult problems with large branching factors -- subsampling the transition function, separating out natural dynamics, caching transition function samples, and others. Experiments show that GLUTTON and PROST, the IPPC-2011 winner, have complementary strengths, with GLUTTON demonstrating superior performance on problems with few high-reward terminal states.