実行時情報を組み込んだ準最適リアクティブ合成
Near-Optimal Reactive Synthesis Incorporating Runtime Information
実行時にしか得られない情報を活用するため、候補シナリオごとに戦略を事前合成し、安全性と活性を保証しつつ動的に切り替える手法を提案し、性能劣化の上限も示した。
著者: Suda Bharadwaj, Abraham P. Vinod, Rayna Dimitrova, Ufuk Topcu
分類: cs.RO, cs.AI
原文アブストラクト
We consider the problem of optimal reactive synthesis - compute a strategy that satisfies a mission specification in a dynamic environment, and optimizes a performance metric. We incorporate task-critical information, that is only available at runtime, into the strategy synthesis in order to improve performance. Existing approaches to utilising such time-varying information require online re-synthesis, which is not computationally feasible in real-time applications. In this paper, we pre-synthesize a set of strategies corresponding to candidate instantiations (pre-specified representative information scenarios). We then propose a novel switching mechanism to dynamically switch between the strategies at runtime while guaranteeing all safety and liveness goals are met. We also characterize bounds on the performance suboptimality. We demonstrate our approach on two examples - robotic motion planning where the likelihood of the position of the robot's goal is updated in real-time, and an air traffic management problem for urban air mobility.
