Solving Concurrent Markov Decision Processes
Solving Concurrent Markov Decision Processes
复制标题
解决并发马尔可夫决策过程
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Daniel S. Weld
中科院分区：
文献类型：
--
作者：
Mausam;Daniel S. Weld
通常，马尔可夫决策问题 (MDP) 假设每个决策时期执行一个操作，但在现实世界中，人们可能经常并行执行某些操作。本文探讨了并发 MDP，即允许同时执行多个非冲突操作的 MDP，并提出了两种新算法。我们的第一种方法利用了两个可证明合理的修剪规则，从而保证了解决方案的最优性。我们的第二种技术是一种快速的、基于采样的算法，它可以极快地产生接近最优的解决方案。实验表明，我们的方法优于现有算法，可实现两个数量级的加速。
Typically, Markov decision problems (MDPs) assume a single action is executed per decision epoch, but in the real world one may frequently execute certain actions in parallel. This paper explores concurrent MDPs, MDPs which allow multiple non-conflicting actions to be executed simultaneously, and presents two new algorithms. Our first approach exploits two provably sound pruning rules, and thus guarantees solution optimality. Our second technique is a fast, sampling-based algorithm, which produces c1ose-to-optimal solutions extremely quickly. Experiments show that our approaches outperform the existing algorithms producing up to two orders of magnitude speedup.