|Table of Contents|

Global path planning based on simultaneous visibility graphconstruction and A* algorithm(PDF)

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

Issue:
2017年03期
Page:
313-
Research Field:
Publishing date:

Info

Title:
Global path planning based on simultaneous visibility graphconstruction and A* algorithm
Author(s):
Lv Taizhi1; 2; Zhao Chunxia1; Xia 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
Keywords:
global path planning;  visibility graph;  A* algorithm;  path search
PACS:
TP301.6
DOI:
10.14177/j.cnki.32-1397n.2017.41.03.007
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:
-
Last Update: 2017-06-30