基于线性时序逻辑的最优巡回路径规划

摘要

基于线性时序逻辑(Linear temporal logic, LTL)的路径规划方法中,多点巡回路径规划问题尚无有效解决方案。为了在道路网络中实现最优巡回监测,提出了基于LTL 的最优巡回路径规划方法。首先,将环境建模成一个切换系统,用LTL语言描述包含多个巡回点和障碍物的任务需求；接着,利用循环移位法构建能够融合任务需求和环境模型的扩展乘机自动机,以建立路径信息完整的网络拓扑；最后,采用基于迪科斯彻法的最优综合算法搜索扩展乘机自动机网络上的最优路径,从而获得能够满足复杂任务需求的最优巡回路径。仿真结果表明,该方法能够有效实现最优巡回路径规划。%For a complex road network environment, the problem of patrolling path planning with multiple nodes has not be effectively solved. In order to accomplish high-level patrolling task in road network, an optimal patrolling path planning method is proposed on the basis of the theory of linear temporal logic (LTL). Firstly, the environment is modeled as a transition system and the patrolling task is described with linear temporal logic formula. Then, an extended product automaton combining the transition system and the linear temporal logic formula is constructed by implementing a circular shift algorithm such that the network topology with complete path information could be established. Finally, the Dijkstra algorithm is utilized to search the optimal path in the network of the extended product automaton, and thus, the optimal path satisfying the task requirement is correspondingly obtained. The results of the simulation experiment show the validity of the algorithm.