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

肖云涛; 欧林林; 俞立

doi:10.3724/SP.J.1004.2014.02126

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

doi: 10.3724/SP.J.1004.2014.02126

1.
浙江工业大学信息工程学院杭州 310023

基金项目:

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

详细信息

作者简介:
肖云涛浙江工业大学信息工程学院硕士研究生. 主要研究方向为机器人路径规划, 嵌入式系统.E-mail: ctcexiaoyt@foxmail.com

计量
- 文章访问数: 1755
- HTML全文浏览量: 76
- PDF下载量: 1587
- 被引次数: 0
出版历程
- 收稿日期: 2013-08-07
- 修回日期: 2014-02-17
- 刊出日期: 2014-10-20

Optimal Patrolling Path Planning via Linear Temporal Logic

1.
College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023

Funds:

Supported by National Natural Science Foundation of China (61273117,61273116), and Natural Science Foundation of Zhejiang Province (Y1111012)

摘要

摘要: 基于线性时序逻辑(Linear temporal logic, LTL)的路径规划方法中, 多点巡回路径规划问题尚无有效解决方案. 为了在道路网络中实现最优巡回监测, 提出了基于LTL的最优巡回路径规划方法. 首先, 将环境建模成一个切换系统, 用LTL语言描述包含多个巡回点和障碍物的任务需求; 接着, 利用循环移位法构建能够融合任务需求和环境模型的扩展乘机自动机, 以建立路径信息完整的网络拓扑; 最后, 采用基于迪科斯彻法的最优综合算法搜索扩展乘机自动机网络上的最优路径, 从而获得能够满足复杂任务需求的最优巡回路径. 仿真结果表明, 该方法能够有效实现最优巡回路径规划.
- 线性时序逻辑 /
- 任务需求 /
- 切换系统 /
- 巡回路径规划
Abstract: 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.
- Linear temporal logic (LTL) /
- task requirement /
- transition system /
- patrolling path planning

HTML全文

参考文献(17)

[1]	Zhu Yi, Zhang-Tao, Song Jing-Yan. Study on the local minima problem of path planning using potential field method in unknown environments. Acta Automatica Sinica, 2010, 36(8): 1122-1130(朱毅, 张涛, 宋靖雁. 未知环境下势场法路径规划的局部极小问题研究. 自动化学报, 2010, 36(8): 1122-1130)
[2]	Zhu Qing-Bao. Ant algorithm for path planning of mobile robot in a complex environment. Acta Automatica Sinica, 2006, 32(4): 586-593(朱庆保. 复杂环境下的机器人路径规划蚂蚁算法. 自动化学报, 2006, 32(4): 586-593)
[3]	Fan Chang-Hong, Chen Wei-Dong, Xi Yu-Geng. A neural networks-based approach to safe path planning of mobile robot in unknown environment. Acta Automatica Sinica, 2004, 30(6): 816-823(樊长虹, 陈卫东, 席裕庚. 未知环境下移动机器人安全路径规划的一种神经网络方法. 自动化学报, 2004, 30(6): 816-823)
[4]	[4] Khatib O. Real-time obstacle avoidance for manipulator and mobile robots. The International Journal of Robotics Research, 1986, 5(1): 90-98
[5]	Yuan Kui, Li Yuan, Fang Li-Xin. Multiple mobile robot systems: a survey of recent work. Acta Automatica Sinica, 2007, 33(8): 785-794 (原魁, 李园, 房立新. 多移动机器人系统研究发展近况. 自动化学报, 2007, 33(8): 785-794)
[6]	[6] Kloetzer M, Belta C. Automatic deployment of distributed teams of robots from temporal logic motion specifications. IEEE Transactions on Robotics, 2010, 26(1): 48-61
[7]	[7] Smith S, Tumova J, Belta C, Rus D. Optimal path planning for surveillance with temporal logic constraints. The International Journal of Robotics Research, 2011, 30(14): 1695-1708
[8]	[8] Smith S, Tumova J, Belta C, Rus D. Optimal path planning under temporal logic constraints. In: Proceedings of International Conference on Intelligent Robots and Systems. Taipei, China: IEEE, 2010. 3288-3293
[9]	[9] Ulusoy A, Smith S, Xu Chu-Ding, Belta C, Rus D. Optimality and robustness in multi-Robot path planning with temporal logic constraints. The International Journal of Robotics Research, 2013, 32(8): 889-911
[10]	Xu C D, Lazar M, Belta C. Receding horizon temporal logic control for finite deterministic systems. In: Proceedings of American Control Conference. Montreal, Canada: IEEE, 2012. 715-720
[11]	Wongpiromsarn T, Ufuk T, Murray R. Receding horizon temporal logic planning for dynamical systems. In: Proceedings of 48th IEEE Conference on Decision and Control. Shanghai, China: IEEE, 2009. 5997-6004
[12]	Wongpiromsarn T, Ufuk T, Murray R. Receding horizon temporal logic planning. IEEE Transactions on Automatic Control, 2012, 57(11): 2817-2830
[13]	Belta C, Isler V, Pappas G. Discrete abstractions for robot motion planning and control in polygonal environments. IEEE Transactions on Robotics, 2005, 21(5): 864-874
[14]	Clarke E, Grumberg O, Peled D. Model Checking. Massachusetts: MIT Press, 1999. 27-46
[15]	Dijkstra E. A note on two problems in connexion with graphs. Numerical Mathematic, 1959, 1(1): 269-271
[16]	Gastin P, Oddoux D. Fast LTL to Bchi automata translation. In: Proceedings of the 13th International Conference on Computer Aided Verification. Paris, France: IEEE, 2001. 53-65
[17]	Kloetzer M, Belta C. A fully automated framework for control of linear systems from temporal logic specifications. IEEE Transactions on Automatic Control, 2008, 53(1): 287-297