信号时序逻辑约束下基于终点回溯的高效规划  

Efficient Planning based on Destination Backtracking under Signal Temporal Logic Constraints

作　　者：田戴荧 方浩[1] 杨庆凯 TIAN Daiying;FANG Hao;YANG Qingkai(School of Automation,Beijing Institute of Technology,Beijing 100081,China)

机构地区：[1]北京理工大学自动化学院,北京100081

出　　处：《无人系统技术》2021年第1期44-50,共7页Unmanned Systems Technology

基　　金：国家自然科学基金(U1913602,61873033,61903035);国家自然科学基金重大国际(地区)联合研究项目(61720106011);中国工程院咨询研究项目(2019-XZ-7)。

摘　　要：在信号时序逻辑约束下规划路径是一项具有挑战性的任务,其计算量非常高。提出了一种终点回溯的规划方法,它是一种适用于连续时间系统的抽象化方法。该规划方法分为离线构建阶段和在线规划阶段。离线构建阶段在Transducer理论的指导下,从能够完成任务的合理的终点构造一棵快速随机搜索树,向初始状态空间进行回溯。当采样点足够多时,在线规划阶段使用模型预测控制将机器人驱动到快速随机搜索树的叶子节点。通过所提出的规划方法,避免了环境的有限转移系统与信号时序逻辑对应的自动机乘积引起的状态空间爆炸问题。所提出的方法将在线路径规划所需时间降低到1s以下,充分说明了本方法的有效性。与混合整数线性规划以及贝叶斯优化方法相比较,所提出的终点回溯规划方法在线求解效率更优,且更加易于扩展至多机器人协同工作场景。Synthesizing the continuous path under signal temporal logic specifications is a challenging task resulting in computationally demanding methods.A destination backtracking planning method is presented which is an abstract-based method for continuous-time systems.The planning method consists of an offline construction phase and an online planning phase.The offline phase constructs a rapidly-exploring randomized tree backtracking from rational destinations under the guidance of timed signal transducer.When there are enough sample points,the online planning phase uses Model Predictive Control to drive agents to leaf nodes.Through the proposed planning method,the state space explosion induced by the product of the finite transition system and the automata of STL is avoided.The proposed method reduces the online planning time to less than 1s.Compared with the Mixed-Integer Linear Programming and the Bayesian Optimization,the proposed method is more effective and can be easily extended to multi-agent collaboration.

关 键 词：信号时序逻辑 终点反溯 非一致性采样 抽象化 人工智能 机器人学 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]