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

Optimal Patrolling Path Planning via Linear Temporal Logic

作　　者：肖云涛[1] 欧林林[1] 俞立[1] 

机构地区：[1]浙江工业大学信息工程学院,杭州310023

出　　处：《自动化学报》2014年第10期2126-2133,共8页Acta Automatica Sinica

基　　金：国家自然科学基金(61273117;61273116);浙江省自然科学基金(Y1111012)资助~~

摘　　要：基于线性时序逻辑(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.

关 键 词：线性时序逻辑 任务需求 切换系统 巡回路径规划 

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