ロボット意思決定2025/10/1arXiv:2510.03481

区間MDPに対する最適化ベースのロバスト許容合成

Optimization-Based Robust Permissive Synthesis for Interval MDPs

遷移確率が区間で与えられるロボット意思決定問題に対し、ロバスト性を保ちつつ許容度を最大化する方策を混合整数線形計画で合成する手法を提案した。

詳しい要約

1. どんなもの？

- ロボティクスにおける遷移不確実性下の意思決定を動機とし、Interval Markov Decision Processes (IMDPs) に対する robust permissive synthesis の最適化ベースの枠組みを提示する研究。 - 遷移確率が区間値で与えられる IMDP 上で、準拠するあらゆる戦略が全ての許容遷移実現下で probabilistic reachability や expected reward 仕様を満たすことを保証しつつ、permissiveness 指標を最大化する。 - ロボット意思決定への応用を想定した基盤的手法。

2. 先行研究と比べてどこがすごい？

- 従来の robust IMDP synthesis は単一ポリシーを返し、permissive synthesis は正確なモデルを仮定していた。 - 本研究は区間不確実性下での robust permissive synthesis を扱う点が異なる。 - これを global mixed-integer linear program (MILP) として定式化し、robust Bellman constraints を直接符号化する点が特徴。 - vertex-based な不確実性表現の指数計算量に対し、dualization ベースの符号化で頂点列挙を排除し、後続状態数に対して線形にスケールする。

3. 技術・手法の肝は？

- robust permissive synthesis を global mixed-integer linear program (MILP) として定式化する。 - robust Bellman constraints を直接符号化する。 - 目的関数は定量的 permissiveness 指標（enabled state-action pairs の数）の最大化。 - 全ての compliant strategy が全許容遷移実現下で probabilistic reachability または expected reward 仕様を満たすことを保証する制約を課す。 - vertex-based 不確実性表現の指数計算量に対し、dualization-based encoding を導出し、明示的な頂点列挙を排除して後続状態数に線形なスケーリングを実現する。

4. どうやって有効だと検証した？

- 4つの代表的なロボティクス benchmark domains での実験的評価を実施。 - 数十万状態（hundreds of thousands of states）の IMDPs へのスケーラビリティを示した。 - 具体的なベースライン比較や指標の詳細は要旨からは不明。

5. 議論はある？

- 提案枠組みは不確実性を考慮しつつ柔軟性を保持するコントローラ合成の実用的かつ一般的な基盤を提供すると主張。 - 計算量やスケーラビリティに関する詳細な議論、限界、仮定の妥当性については要旨からは不明。

6. 次に読むべき論文は？

- Interval Markov Decision Processes (IMDPs) における robust synthesis および permissive synthesis の既存研究。 - mixed-integer linear program (MILP) を用いた synthesis 手法。 - robust Bellman constraints や dualization を用いた不確実性下の検証・合成に関する研究。 - 要旨で明示的に参照されている個別論文は不明。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Khang Vo Huynh, David Parker, Lu Feng

分類: cs.RO, cs.SY, eess.SY

原文アブストラクト

We present an optimization-based framework for robust permissive synthesis for Interval Markov Decision Processes (IMDPs), motivated by robotic decision-making under transition uncertainty. In many robotic systems, model inaccuracies and sensing noise lead to interval-valued transition probabilities. While robust IMDP synthesis typically yields a single policy and permissive synthesis assumes exact models, we show that robust permissive synthesis under interval uncertainty can be cast as a global mixed-integer linear program (MILP) that directly encodes robust Bellman constraints. The formulation maximizes a quantitative permissiveness metric (the number of enabled state-action pairs), while guaranteeing that every compliant strategy satisfies probabilistic reachability or expected reward specifications under all admissible transition realizations. To address the exponential complexity of vertex-based uncertainty representations, we derive a dualization-based encoding that eliminates explicit vertex enumeration and scales linearly with the number of successors. Experimental evaluation on four representative robotic benchmark domains demonstrates scalability to IMDPs with hundreds of thousands of states. The proposed framework provides a practical and general foundation for uncertainty-aware, flexibility-preserving controller synthesis in robotic systems.

arXivで原文を読む →arXiv概要ページ

← 論文一覧