Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (8): 272-277.doi: 10.11896/jsjkx.190700138

Previous Articles     Next Articles

Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm

JIANG Chen-kai1, LI Zhi1, 2, PAN Shu-bao2, WANG Yong-jun2   

  1. 1 School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
    2 School of Electronics and Automation, Guilin University of Aerospace Technology, Guilin, Guangxi 541004, China
  • Online:2020-08-15 Published:2020-08-10
  • About author:JIANG Chen-kai, born in 1993, graduate student.His main research interests include AGV dispatching system and path planning research.
    PAN Shu-bao, born in 1985, B.Eng, M.Eng, lecturer.His main research inte-rests include precision measurement and intelligent control.

PDF (PC)

1386

Abstract: Aiming at the path planning and conflict problems of automatic guided vehicle (AGV) in flexible manufacturing systems, an improved Dijkstra algorithm based on time window is proposed to realize dynamic path planning of multiple AGVs.Firstly, the traditional Dijkstra algorithm is used to calculate the path of the multi-AGV for the scheduled task, and the degree of use of the planned path is calculated and the weighting coefficient is calculated, and then the weighted path length is updated to the database.Secondly, calculate the time for the AGV to pass through each station node, and avoid collision conflicts through the arrangement of time windows.In the end, when the conflict occurs, the path of the lower priority AGV is re-planned by calcula-ting and setting the priority of the AGV.The simulation results show that the proposed algorithm can effectively avoid conflicts and deadlocks under the optimal path, which not only improves the system efficiency, but also makes the system more robust.

Key words: Automatic guided vehicle, Collision-free conflict, Improved dijkstra algorithm, Path planning, Time window

CLC Number: 

  • TP242
[1]QIU L, HSU W J, HUANG S Y, et al.Scheduling and routing algorithms for AGVs:a survey[J].International Journal of Production Research, 2002, 40(3):745-760.
[2]GAO X, SU Q.Multi-robot path planning and collision avoi-dance based on double fuzzy logic[J].Computer Technology and Development, 2014, 24(11):79-82.
[3]HE L N, LOU P H, QIAN X M, et al.Conflict-free automatedguided vehicles routing based on time window[J].Computer Integrated Manufacturing Systems, 2010, 16(12):2630-2634.
[4]ZHANG S Y, YANG Y S, LIANG C J, et al.Optimal control of multiple AGV path conflict in automated terminals[J].Journal
of Transportation System Engineering and Information Techno-logy, 2017, 17(2):83-89.
[5]YUAN R, DONG T, LI J.Research on the collision-free pathplanning of multi-AGVs system based on improved A*, algorithm[J].American Journal of Operations Research, 2016, 6(6):442-449.
[6]ZHU L B, WANG H, WANG J L, et al.Research on path planning of parking system based on dynamic time window[J].Chinese Journal of Engineering Design, 2017, 24(4):440-448.
[7]JEON S M, KIM K H, KOPFER H.Routing automated guided vehicles in container terminals through the Q-learning technique[J].Logistics Research, 2011, 3(1):19-27.
[8]SMOLIC R N, BOGDAN S, KOVACIC Z, et al.Time windows based dynamic routing in multi-AGV systems[J].IEEE Tran-sactions on Automation Science and Engineering, 2010, 7(1):151-155.
[9]WEI S, WANG L, WANG B R, et al.Improvement of A*, algorithm and its application in AGV path planning[J].Process automation instrumentation, 2017, 38(11):51-54.
[10]ZHONG M S, YANG Y S, ZHUO Y M.Free conflict AGV path planning in automated terminals based on speed control[J].Computer Science, 2019, 46(7):308-314.
[11]TAI Y P, XING K X, LIN Y G, et al.Research of path planning in multi-AGV system[J].Computer Science, 2017, 44(S2):84-87.
[12]XU F.Research on robot obstacle avoidance and path planning based on improved artificial potential field method[J].Computer Science, 2016, 43(12):293-296.
[13]GHASEMZADEH H, BEHRANGI E, ABDOLLAHI A M.Conflict-free scheduling and routing of automated guided vehicles in mesh topologies[J].Robotics and Autonomous Systems, 2009, 57(6):738-748.
[14]WANG H, ZHU L B, WANG J L, et al.Research on path planning of parking system based on Dijstra-ant colony hybrid algorithm[J].Chinese Journal of Engineering Design, 2016, 23(5):489-496.
[1] WANG Bing, WU Hong-liang, NIU Xin-zheng. Robot Path Planning Based on Improved Potential Field Method [J]. Computer Science, 2022, 49(7): 196-203.
[2] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[3] TAN Ren-shen, XU Long-bo, ZHOU Bing, JING Zhao-xia, HUANG Xiang-sheng. Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms [J]. Computer Science, 2022, 49(6A): 795-801.
[4] CHEN Jing-yu, GUO Zhi-jun, YIN Ya-kun. Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm [J]. Computer Science, 2021, 48(6A): 633-637.
[5] DU Wan-ru, WANG Xiao-yin, TIAN Tao, ZHANG Yue. Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles [J]. Computer Science, 2021, 48(2): 250-256.
[6] GONG Zhui-fei, WEI Chuan-jia. Complex Network Link Prediction Method Based on Topology Similarity and XGBoost [J]. Computer Science, 2021, 48(12): 226-230.
[7] GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm [J]. Computer Science, 2021, 48(12): 304-311.
[8] ZHAO Yang, NI Zhi-wei, ZHU Xu-hui, LIU Hao, RAN Jia-min. Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform [J]. Computer Science, 2021, 48(11A): 30-38.
[9] CHEN Ji-qing, TAN Cheng-zhi, MO Rong-xian, WANG Zhi-kui, WU Jia-hua, ZHAO Chao-yang. Path Planning of Mobile Robot with A* Algorithm Based on Artificial Potential Field [J]. Computer Science, 2021, 48(11): 327-333.
[10] ZHAO Xiao-wei, ZHU Xiao-jun, HAN Zhou-qing. Hover Location Selection and Flight Path Optimization for UAV for Localization Applications [J]. Computer Science, 2021, 48(11): 345-355.
[11] WANG Zi-qiang, HU Xiao-guang, LI Xiao-xiao, DU Zhuo-qun. Overview of Global Path Planning Algorithms for Mobile Robots [J]. Computer Science, 2021, 48(10): 19-29.
[12] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[13] ZHOU Jun and WANG Tian-qi. Single Departure and Arrival Procedure Optimization in Airport Terminal Area Based on Branch and Bound Method [J]. Computer Science, 2020, 47(6A): 552-555.
[14] ZENG Wei-liang, WU Miao-sen, SUN Wei-jun, XIE Sheng-li. Comprehensive Review of Autonomous Taxi Dispatching Systems [J]. Computer Science, 2020, 47(5): 181-189.
[15] WANG Wei-guang, YIN Jian, QIAN Xiang-li, ZHOU Zi-hang. Realtime Multi-obstacle Avoidance Algorithm Based on Dynamic System [J]. Computer Science, 2020, 47(11A): 111-115.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.