SixthSense: Fast and Reliable Recognition of Dead Ends in MDPs
SixthSense: Fast and Reliable Recognition of Dead Ends in MDPs
复制标题
SixthSense：快速可靠地识别 MDP 中的死角
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Daniel S. Weld
中科院分区：
文献类型：
--
作者：
A. Kolobov;Mausam;Daniel S. Weld
最新的国际概率规划竞赛（IPPC-2008）的结果表明，死胡同的存在，即没有目标轨迹的状态，使得现代概率规划者很难进行MDP。隐式的死胡同，状态与可执行的行动，但没有路径的目标，是特别具有挑战性的;现有的MDP求解器花费大量的时间和内存来识别这些状态。作为解决这个问题的第一次尝试，我们提出了一种名为SIXTHSENSE的机器学习算法。SIXTHSENSE通过查找无用信息（nogoods）来帮助现有的MDP求解器，这些无用信息是一个状态中的真值意味着该状态是一个死胡同的文字的合取。重要的是，我们习得的无用之物是可靠的，因此它们识别的状态是真正的死胡同。SIXTHSENSE非常快，只需要很少的训练数据，并且只需要总规划时间的一小部分。虽然IPPC问题可能有数百万个死胡同，但它们通常可能只代表十几个或两个无商品。因此，nogood学习有效地产生了一种快速可靠的方法来识别死胡同。我们的实验表明，由SIXTHSENSE发现的nogoods通常会减少IPPC域上的规划空间和时间，使一些规划者能够解决他们以前无法处理的问题。
The results of the latest International Probabilistic Planning Competition (IPPC-2008) indicate that the presence of dead ends, states with no trajectory to the goal, makes MDPs hard for modern probabilistic planners. Implicit dead ends, states with executable actions but no path to the goal, are particularly challenging; existing MDP solvers spend much time and memory identifying these states. As a first attempt to address this issue, we propose a machine learning algorithm called SIXTHSENSE. SIXTHSENSE helps existing MDP solvers by finding nogoods, conjunctions of literals whose truth in a state implies that the state is a dead end. Importantly, our learned nogoods are sound, and hence the states they identify are true dead ends. SIXTHSENSE is very fast, needs little training data, and takes only a small fraction of total planning time. While IPPC problems may have millions of dead ends, they may typically be represented with only a dozen or two no-goods. Thus, nogood learning efficiently produces a quick and reliable means for dead-end recognition. Our experiments show that the nogoods found by SIXTHSENSE routinely reduce planning space and time on IPPC domains, enabling some planners to solve problems they could not previously handle.