Mixed-Integer Programming for Signal Temporal Logic With Fewer Binary Variables
Mixed-Integer Programming for Signal Temporal Logic With Fewer Binary Variables
复制标题
具有较少二进制变量的信号时态逻辑的混合整数规划
作者：
Vince Kurtz;Hai Lin
信号时序逻辑（STL）为机器人和信息物理系统的复杂控制目标提供了一种方便的编码方式。STL轨迹综合的最新技术是基于混合凸规划（MICP）。MICP方法是合理和完整的，但由于二进制变量数量的指数复杂性，可扩展性有限。在这封信中，我们提出了一个更有效的MICP编码STL。我们的新编码是基于这样的见解，即析取可以使用对数的二进制变量进行编码，而合取可以不使用二进制变量进行编码。我们在仿真例子中证明，我们提出的方法显着优于国家的最先进的长期和复杂的规格。开放源码软件可在https://stlpy.readthedocs.io上获得。
Signal Temporal Logic (STL) provides a convenient way of encoding complex control objectives for robotic and cyber-physical systems. The state-of-the-art in trajectory synthesis for STL is based on Mixed-Integer Convex Programming (MICP). The MICP approach is sound and complete, but has limited scalability due to exponential complexity in the number of binary variables. In this letter, we propose a more efficient MICP encoding for STL. Our new encoding is based on the insight that disjunction can be encoded using a logarithmic number of binary variables and conjunction can be encoded without binary variables. We demonstrate in simulation examples that our proposed approach significantly outperforms the state-of-the-art for long and complex specifications. Open-source software is available: https://stlpy.readthedocs.io.
凸集图中的最短路径
DOI：
--
发表时间：
2021
期刊：
ArXivorg
影响因子：
--
作者：
Tobia Marcucci, Jack Umenberger
通讯作者：
Tobia Marcucci, Jack Umenberger