|
|
仓储作业中多搬运机器人动态路径优化
|
Abstract:
搬运机器人在无人仓的“货到人”拣选系统中得到了广泛应用，然而多个搬运机器人协同作业还存在着路径寻优规划不合理、路径冲突等问题。考虑路径的负载平衡及搬运机器人转弯耗费的时间，建立了带有时间窗的多搬运机器人路径规划模型；结合调整优先级的避障策略，提出了一种改进的“离线–在线”两阶段动态路径规划算法，实现全局离线路径规划和在线冲突规避，提升了无人仓系统的运行效率。最后，设计三组仿真实验，通过对比搬运机器人的总运行时间，验证了改进算法的有效性。
Handling robots have been widely used in the picking system of “part-to-picker” in un-manned warehouse. However, there are still problems such as unreasonable path seeking planning and path conflict in the collaborative operation of multi-handling robot. Considering the load balance of the path and the turning time of the handling robot, the path planning model of the multi-handling robot with time window is established. Combined with the obstacle avoidance strategy of adjusting the priority, an improved “offline-online” two-stage dynamic path planning algorithm was proposed to realize the combination of global off-line path planning and online conflict avoidance, thus improving the operation efficiency of the un-manned warehouse system. Finally, three sets of simulation experiments are designed to verify the effectiveness of the improved algorithm by comparing the total running time of the handling robots.
| [1] | 胡国盛. 我国电商企业物流体系优化分析[J]. 商业经济研究, 2017(19): 106-108. |
| [2] | Hazard, C.J. and Wurman, P.R. (2006) Alphabet Soup: A Testbed for Studying Resource Allocation in Multi-Vehicle Systems. Proceedings of the 2006 AAAI Workshop on Auction Mechanisms for Robot Coordination, Boston, 17 July 2006, 23-30. |
| [3] | Li, W., Jiang, L. and Li, Z. (2016) Research on the Task Assignment Problem of Warehouse Robots in the Smart Warehouse. 12th International Symposium on Operations Research and Its Applications in Engineering, Technology and Management, Luoyang, 21-24 August 2015, 29-33. |
| [4] | Yeung, W.-K., Choi, T.M. and Cheng, T.C.E. (2011) Supply Chain Scheduling and Coordination with Dual Delivery Modes and Inventory Storage Cost. International Journal of Production Economics, 132, 223-229. https://doi.org/10.1016/j.ijpe.2011.04.012 |
| [5] | Khorshid, M.M., Holte, R.C. and Sturtevant, N.R. (2013) A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding. Symposium on Combinatorial Search. Proceedings of the 4th Annual Symposium on Combinatorial Search, Castell de Cardona, Barcelona, 15-16 July 2011, 76-83. |
| [6] | Chang, W.K. and Tanchoco, J.M.A. (1991) Journal of Production Research Conflict-Free Shortest Time Bidirectional AGV Routing. International Journal of Production Research, 29, 2377-2391. https://doi.org/10.1080/00207549108948090 |
| [7] | Ma, Y., Wang, H., Xie, Y. and Guo, M. (2014) Path Planning for Multiple Mobile Robots under Double-Warehouse. Information Sciences, 278, 357-379. https://doi.org/10.1016/j.ins.2014.03.058 |
| [8] | Umar, U.A., Ariffin, M.K.A. and Ismail, N. (2012) Priority-Based Genetic Al-gorithm for Conflict-Free Automated Guided Vehicle Routing. Journal of Engineering Valuation and Cost Analysis, 50, 732-739. |
| [9] | Desrochers, M., Desrosiers, J. and Solomon, M. (1992) A New Optimization Algorithm for the Vehicle Routing Problem with Time windows. Operation Research, 40, 199-415. https://doi.org/10.1287/opre.40.2.342 |
| [10] | Wang, W. and Goh, W.B. (2015) A Stochastic Algorithm for Makespan Minimized Multi-Agent Path Planning in Discrete Space. Applied Soft Computing, 30, 287-304. https://doi.org/10.1016/j.asoc.2015.01.046 |
| [11] | Hidalgo-Paniagua, A., Miguel Vega-Rodríguez, A., Ferruz, J. and Pavón, N. (2015) MOSFLA-MRPP: Multi-Objective Shuffled Frog-Leaping Algorithm Applied to Mobile Robot Path Planning. Engineering Applications of Artificial Intelligence, 44, 123-136. https://doi.org/10.1016/j.engappai.2015.05.011 |
| [12] | Ma, H., Koenig, S., Ayanian, N., et al. (2017) Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios. Computer Science, arXiv: 1702.05515. |
| [13] | Miao, H. and Tian, Y.C. (2013) Dynamic Robot Path Planning Using an Enhanced Simulated Annealing Approach. Applied Mathematics and Computation, 222, 420-437. https://doi.org/10.1016/j.amc.2013.07.022 |
| [14] | Standley, T.S. and Korf, R.E. (2011) Complete Algorithms for Cooperative Pathfinding Problems. International Joint Conference on Artificial Intelligence. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, 16-22 July 2011, 223-229. |
| [15] | Sharon, G., Stern, R., Felner, A. and Sturtevant, N.R. (2015) Conflict-Based Search for Optimal Multi-Agent Pathfinding. Artificial Intelligence, 219, 40-66. https://doi.org/10.1016/j.artint.2014.11.006 |
| [16] | 何小锋, 马良. 带时间窗车辆路径问题的量子蚁群算法[J]. 系统工程理论与实践, 2013, 33(5): 1255-1261. |
| [17] | 张立峰, 易万里, 刘晓兰. 基于两阶段算法的大规模成品油二次配送优化[J]. 系统工程理论与实践, 2016, 36(11): 2951-2963. |
| [18] | Maza, S. and Castagna, P. (2005) A Performance-Based Structural Policy for Con-flict-Free Routing of Bidirectional Automated Guided Vehicles. Computers in Industry, 56, 719-733. https://doi.org/10.1016/j.compind.2005.03.003 |
| [19] | Lee, J.H., Lee, B.H. and Choi, M.H. (1998) A Real-Time Traffic Control Scheme of Multiple AGV Systems for Free Minimum Time Motion: A Routing Table Approach. IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, 28, 347-358. https://doi.org/10.1109/3468.668966 |
| [20] | 孟祥虎, 胡蓉, 钱斌. 求解带时间窗车辆路径问题的有效混合PBIL算法[J]. 系统工程理论与实践, 2014, 34(10): 2701-2709. |
