ベイズ最適化による多項式時間で確率的完全なSTL軌道合成
Bayesian Optimization for Polynomial Time Probabilistically Complete STL Trajectory Synthesis
STL仕様の軌道合成をMILPではなくベイズ最適化で行い、確率的完全性を保ちつつ計算量を仕様の時間幅に対して多項式、述語数に対して線形に抑えた手法を提案。
著者: Vince Kurtz, Hai Lin
分類: cs.RO, cs.SY, eess.SY
原文アブストラクト
In recent years, Signal Temporal Logic (STL) has gained traction as a practical and expressive means of encoding control objectives for robotic and cyber-physical systems. The state-of-the-art in STL trajectory synthesis is to formulate the problem as a Mixed Integer Linear Program (MILP). The MILP approach is sound and complete for bounded specifications, but such strong correctness guarantees come at the price of exponential complexity in the number of predicates and the time bound of the specification. In this work, we propose an alternative synthesis paradigm that relies on Bayesian optimization rather than mixed integer programming. This relaxes the completeness guarantee to probabilistic completeness, but is significantly more efficient: our approach scales polynomially in the STL time-bound and linearly in the number of predicates. We prove that our approach is sound and probabilistically complete, and demonstrate its scalability with a nontrivial example.
