用切换策略求解MDP中带安全约束的sc-LTL最优规划
Optimal Constrained sc-LTL Planning in MDPs via Switching Policies
- 将约束sc-LTL规划转化为扩展模型上的可达性问题
- 证明基于静态策略的切换策略足以实现最优解
- 可转化为线性规划，适合实际应用中的复杂任务
我们研究在马尔可夫决策过程（MDP）上，针对同时包含目标与安全约束的共安全线性时序逻辑（sc-LTL）规范，合成最优策略的规划问题。由于sc-LTL规范的复杂性，此类问题本质上是非马尔可夫的，且可能需要策略随机化以平衡目标与约束。本文提出一种新方法，将约束sc-LTL规划问题转化为一个扩展模型上的约束可达性问题。我们进一步证明，一类由各sc-LTL规范对应的静态策略构造出的切换策略，足以在该约束可达性问题中达到最优。这一发现使得最优策略可通过可计算的线性规划求解。网格世界案例研究验证了该方法能实现目标与安全约束间的最优权衡，并证实其最优性与可 tractability。
原文摘要 · Abstract (English)
We study the synthesis of optimal policies for planning problems on Markov decision processes with both objectives and safety constraints specified in co-safe linear temporal logic (sc-LTL). Our problems are inherently non-Markovian due to the complexity of the sc-LTL specification and may require policy randomization to balance the objective and constraint. We propose a novel approach that reduces the constrained sc-LTL planning problem to a constrained reachability problem on an extended model. We then show that a class of switching policies constructed from stationary policies for the individual sc-LTL specifications is sufficient for optimality for the constrained reachability problem. Our finding enables a tractable linear program to compute the optimal policy. A grid world case study demonstrates that our switching policies can achieve the optimal trade-off between the objective and the safety constraint and validates both optimality and tractability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。