|Table of Contents|

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


Research Field:
Publishing date:


Global path planning based on simultaneous visibility graphconstruction and A* algorithm
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
global path planning visibility graph A* algorithm path search
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.


[1] 谭民,王硕.机器人技术研究进展[J].自动化学报,2013,39(7):963-972.
Tan Min,Wang Shuo.Research progress on robotics[J].Acta Automatica Sinica,2013,39(7):963-972.
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.
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.
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.
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.
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.
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.


Last Update: 2017-06-30