应用OBDD和PSL的航迹规划方法研究  

ON APPLYING OBDD AND PSL TO AIR ROUTE PLANNING

作　　者：虞蕾[1,2] 赵宗涛[2] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073 [2]第二炮兵工程学院计算机系,陕西西安710025

出　　处：《计算机应用与软件》2011年第2期47-51,105,共6页Computer Applications and Software

基　　金：国家高技术研究发展计划项目(2007AA010301);中国博士后基金(20080431401)

摘　　要：航迹规划是决定无人飞行器飞行航迹优劣的关键环节。由于无人飞行器飞行空域广,态势也较复杂,实际规划中常常面临搜索的状态多、收敛时间慢等问题,这成为无人飞行器执行飞行任务的瓶颈,解决的优化策略包括:缩小问题的状态空间以及根据问题的约束条件,在搜索中剪枝。模型检验的经典OBDD(有序二叉决策图)方法是表示状态和状态迁移的高效率的数据结构方法,可以简化状态系统的表示空间;而PSL是一种重要时序逻辑,利用PSL和一阶逻辑描述无人飞行器航迹规划的领域约束,以期在规划中剪枝搜索状态。在使用上述两种优化策略基础上设计了航迹规划搜索算法,并实现了该算法的规划仿真,仿真结果表明该方法是一种有效可行的航迹规划方法。Air route planning is a crucial step for deciding the quality of flight tracks of UAV.Extensive flight space and complicated environment situation result in a large number of states of search and low efficient convergence speed the UAV often encountered in practical planning,and these have been the bottleneck of UAV in flight mission execution.There are two optimisation methods to overcome these,including decreasing the state expression structure and pruning states during the search according to domain constraints.The classical OBDD for model examination is an efficient data structure method to represent the set of compact states and the state transitions,it can simplify the representation space of state system;while PSL is an important temporal logic.In the paper we use PSL and first-order logic to express the domain constraints of UAV air route planning in order to prune search states during planning.A search algorithm for air route planning is designed with both two optimised strategies described above,and the simulation of the planning of the algorithm is realised,the simulation results show that it is a feasible and efficient method.

关 键 词：航迹规划 OBDD PSL 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]