计算机科学 ›› 2020, Vol. 47 ›› Issue (8): 272-277.doi: 10.11896/jsjkx.190700138
姜辰凯1, 李智1, 2, 盘书宝2, 王勇军2
JIANG Chen-kai1, LI Zhi1, 2, PAN Shu-bao2, WANG Yong-jun2
摘要： 针对多自动导引车(Automatic Guided Vehicle, AGV)在柔性制造系统中出现的路径规划与冲突问题, 提出了一种基于时间窗的改进Dijkstra算法, 实现多AGV的动态路径规划。首先, 利用传统Dijkstra算法为执行调度任务的多AGV规划路径, 并统计被规划路径的使用程度, 计算加权系数, 然后将加权后的路径长度更新到数据库中;其次, 计算AGV通过每个工位节点的时间, 通过时间窗的排布避免碰撞冲突;最后, 当产生冲突时, 通过计算并设置AGV的优先级, 对优先级较低的AGV重新进行路径规划。仿真实验结果表明, 该算法能够在最优路径下有效避免冲突与死锁, 不仅提高了系统效率, 而且使系统具有较好的鲁棒性。
中图分类号:
| [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] | 王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020 |
| [2] | 杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005 |
| [3] | 谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生. 海上风电场通用运维路径规划模型优化及仿真 Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms 计算机科学, 2022, 49(6A): 795-801. https://doi.org/10.11896/jsjkx.210400300 |
| [4] | 沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249 |
| [5] | 陈镜宇, 郭志军, 尹亚昆. 基于混合算法的智能割草机全遍历路径规划及其系统设计 Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm 计算机科学, 2021, 48(6A): 633-637. https://doi.org/10.11896/jsjkx.201100002 |
| [6] | 杜婉茹, 王潇茵, 田涛, 张越. 面向未知环境及动态障碍的人工势场路径规划算法 Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles 计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170 |
| [7] | 龚追飞, 魏传佳. 基于拓扑相似和XGBoost的复杂网络链路预测方法 Complex Network Link Prediction Method Based on Topology Similarity and XGBoost 计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026 |
| [8] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
| [9] | 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform 计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085 |
| [10] | 曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划 Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193 |
| [11] | 陈继清, 谭成志, 莫荣现, 王志奎, 吴家华, 赵超阳. 基于人工势场的A*算法的移动机器人路径规划 Path Planning of Mobile Robot with A* Algorithm Based on Artificial Potential Field 计算机科学, 2021, 48(11): 327-333. https://doi.org/10.11896/jsjkx.200900170 |
| [12] | 赵晓薇, 朱小军, 韩周卿. 面向定位应用的无人机的悬停位置和飞行路径优化 Hover Location Selection and Flight Path Optimization for UAV for Localization Applications 计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105 |
| [13] | 王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述 Overview of Global Path Planning Algorithms for Mobile Robots 计算机科学, 2021, 48(10): 19-29. https://doi.org/10.11896/jsjkx.200700114 |
| [14] | 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184 |
| [15] | 曾伟良, 吴淼森, 孙为军, 谢胜利. 自动驾驶出租车调度系统研究综述 Comprehensive Review of Autonomous Taxi Dispatching Systems 计算机科学, 2020, 47(5): 181-189. https://doi.org/10.11896/jsjkx.190400031 |
|
||
首页