解决多对象并发动作下的高效规划难题
Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions
- 用一阶逻辑表示法避免状态与动作空间爆炸
- 在对象数上实现多项式时间与空间的精确规划
- 提供误差可控的近似版本，速度提升多个数量级
在允许并发动作的马尔可夫决策过程（MDP）中，状态和动作空间随对象数量呈指数增长，导致策略计算极低效，需枚举联合空间。针对不可区分对象的情况，本文提出一种一阶表示法，缓解状态与动作空间的指数膨胀问题。我们设计了Foreplan——一种高效的关联前向规划器，利用该一阶表示，在对象数量上实现多项式时空复杂度的策略计算，显著提升可精确求解的规划问题规模，理论分析验证了其优势。为进一步加速计算，还引入近似版本的Foreplan，附带误差保证。实验表明，两种版本均实现数个数量级的速度提升；近似版本的误差在多数情况下可忽略不计。
原文摘要 · Abstract (English)
When allowing concurrent actions in Markov Decision Processes, whose state and action spaces grow exponentially in the number of objects, computing a policy becomes highly inefficient, as it requires enumerating the joint of the two spaces. For the case of indistinguishable objects, we present a first-order representation to tackle the exponential blow-up in the action and state spaces. We propose Foreplan, an efficient relational forward planner, which uses the first-order representation allowing to compute policies in space and time polynomially in the number of objects. Thus, Foreplan significantly increases the number of planning problems solvable in an exact manner in reasonable time, which we underscore with a theoretical analysis. To speed up computations even further, we also introduce an approximate version of Foreplan, including guarantees on the error. Further, we provide an empirical evaluation of both Foreplan versions, demonstrating a speedup of several orders of magnitude. For the approximate version of Foreplan, we also empirically show that the induced error is often negligible.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。