[1]吕太之,赵春霞,夏平平.基于同步可视图构造和A*算法的全局路径规划[J].南京理工大学学报(自然科学版),2017,41(03):313.[doi:10.14177/j.cnki.32-1397n.2017.41.03.007]
 Lv Taizhi,Zhao Chunxia,Xia Pingping.Global path planning based on simultaneous visibility graphconstruction and A* algorithm[J].Journal of Nanjing University of Science and Technology,2017,41(03):313.[doi:10.14177/j.cnki.32-1397n.2017.41.03.007]
点击复制

基于同步可视图构造和A*算法的全局路径规划()
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
41卷
期数:
2017年03期
页码:
313
栏目:
出版日期:
2017-06-30

文章信息/Info

Title:
Global path planning based on simultaneous visibility graphconstruction and A* algorithm
文章编号:
1005-9830(2017)03-0313-09
作者:
吕太之12赵春霞1夏平平2
1.南京理工大学 计算机科学与工程学院,江苏 南京 210094; 2.江苏海事职业技术学院 信息工程学院,江苏 南京 211170
Author(s):
Lv Taizhi12Zhao Chunxia1Xia Pingping2
1.School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China; 2.School of Information Engineering,Jiangsu Maritime Institute,Nanjing 211170,China
关键词:
全局路径规划 可视图 A*算法 路径搜索
Keywords:
global path planning visibility graph A* algorithm path search
分类号:
TP301.6
DOI:
10.14177/j.cnki.32-1397n.2017.41.03.007
摘要:
为提高全局路径规划的效率,在路径搜索的过程中同步构造可视图,提出了1种新的算法。在搜索过程中,使用A*算法确定待扩展的节点。根据节点状态,构造上一节点到当前节点或者当前节点到目标点的连线。如果该连线没有穿越障碍物,则将其添加到可视图中,否则将被穿越障碍物远离连线的2个顶点添加到待扩展列表中。仿真结果表明,与完整可视图+A*算法、导向可视图(OVG)+A*算法、简化可视图+A*算法比较,该文算法在能够搜索到最优路径的前提下,降低了路径规划的耗时。
Abstract:
A novel algorithm is proposed by constructing a visibility graph(VG)in the process of path search to improve the efficiency of global path planning.In the search process,a node is selected by A* algorithm for expansion.According to the status of the node,a through line from the preview node to the node or from the node to the destination is drawn.If the line is collision-free,it is added to the VG as a visible edge,or the 2 vertices of obstacles are added to the list for expansion.Simulation results show that compared with complete visibility graph+A*,oriented visibility graph(OVG)+A* and simplified visibility graph+A*,the proposed algorithm can search the optimal path and decrease the time for path planning.

参考文献/References:

[1] 谭民,王硕.机器人技术研究进展[J].自动化学报,2013,39(7):963-972.
Tan Min,Wang Shuo.Research progress on robotics[J].Acta Automatica Sinica,2013,39(7):963-972.
[2]刘传领.基于势场法和遗传算法的机器人路径规划技术研究[D].南京:南京理工大学计算机科学与工程学院,2012.
[3]秦利超.基于扇形栅格地图的移动机器人地图创建[D].天津:天津工业大学电气工程与自动化学院,2012.
[4]郭利进,师五喜,李颖,等.基于四叉树的自适应栅格地图创建算法[J].控制与决策,2011,26(11):1690-1694.
Guo Lijin,Shi Wuxi,Li Ying,et al.Mapping algorithm using adaptive size of occupancy grids based on quadtree[J].Control and Decision,2011,26(11):1690-1694.
[5]张琦,马家辰,马立勇.基于简化可视图的环境建模方法[J].东北大学学报(自然科学版),2013,34(10):1383-1386.
Zhang Qi,Ma Jiachen,Ma Liyong.Environment modeling approach based on simplified visibility graph[J].Journal of Northeastern University(Natural Science),2013,34(10):1383-1386.
[6]Tran N,Nguyen D T,Vu D L,et al.Global path planning for autonomous robots using modified visibility-graph[C]//Proceedings of IEEE Interna-tional Conference on Control,Automation and Information Sciences.Nha Trang,Vietnam:IEEE,2013:317-321.
[7]Nguyet T T N,Hoai T V,Thi N A.Some advanced techniques in reducing time for path planning based on visibility graph[C]//Proceedings of International Conference on Knowledge & Systems Engineering.Hanoi,Vietnam:IEEE,2011:190-194.
[8]Wooden D,Egerstedt M.Oriented visibility graphs:Low-complexity planning in real-time environments[C]//Proceeding of the 2006 IEEE International Conference on Robotics and Automation.Orlando,USA:IEEE,2006:2354-2359.
[9]刘罡,刘玉斌,赵杰.基于可视切线图的未知环境建模新方法研究[J].高技术通讯,2010,20(5):505-510.
Liu Gang,Liu Yubin,Zhao Jie.Research on a new method for unknown environment modeling based on visual tangent graphs[J].High Technology Letters,2010,20(5):505-510.
[10]Xie Yang,Cheng Wushan.AGV path planning based on smoothing A* algorithm[J].International Journal of Software Engineering & Applications,2015,6(5):1-8.
[11]Nash A,Daniel K,Koenig S,et al.Theta*:Any-angle path planning on grids[J].Journal of Artificial Intelligence Research,2014,39(1):533-579.
[12]蔡炯,汪小志.基于粗糙集与遗传算法的采摘机器人路径规划[J].农机化研究,2016,38(8):189-193.
Cai Jiong,Wang Xiaozhi.Path planning of picking robot based on rough set and genetic algorithm[J].Journal of Agricultural Mechanization Research,2016,38(8):189-193.
[13]刘杰,闫清东,马越,等.基于蚁群几何优化算法的全局路径规划[J].东北大学学报(自然科学版),2015,36(7):923-928.
Liu Jie,Yan Qingdong,Ma Yue,et al.Global path planning based on improved ant colony optimization algorithm for geometry[J].Journal of Northeastern University(Natural Science),2015,36(7):923-928.
[14]赵娟平,高宪文,符秀辉.改进蚁群优化算法求解移动机器人路径规划问题[J].南京理工大学学报,2011,35(5):637-641.
Zhao Juanping,Gao Xianwen,Fu Xiuhui.Improved ant colony optimization algorithm for solving path planning problem of mobile robot[J].Journal of Nanjing University of Science and Technology,2011,35(5):637-641.
[15]Russell S,Norvig P.Artificial intelligence:A modern approach[M].3th ed.Upper Saddle River,NJ,USA:Pearson,2010:93-99.

备注/Memo

备注/Memo:
收稿日期:2016-05-22 修回日期:2016-10-09
基金项目:国家自然科学基金(61101197); 江苏省高校优秀中青年教师和校长赴境外研修项目(201121)
作者简介:吕太之(1979-),男,博士生,高级工程师,主要研究方向:全局路径规划、同时定位与地图创建、机器人自主导航,E-mail:lvtaizhi@163.com。
引文格式:吕太之,赵春霞,夏平平.基于同步可视图构造和A*算法的全局路径规划[J].南京理工大学学报,2017,41(3):313-321.
投稿网址:http://zrxuebao.njust.edu.cn
更新日期/Last Update: 2017-06-30