-
摘要:
针对直角坐标机器人在动态分拣过程中顺序规划算法效率低下的问题,提出了一种适用于机器人连续分拣作业的改进贪心策略规划算法。建立直角坐标机器人的运动学模型,确保物体被准确拾取。设计时间窗口,对传送带上的连续运动物体进行区域划分,并应用贪心策略对同一时间窗口内的物体规划分拣顺序。考虑物体存在分拣遗漏的风险,设计评价函数对贪心策略进行改进,增强了所提算法的实用性。设计模拟程序对所提算法进行仿真,并利用搭建的机器人平台开展分拣实验,验证了算法的可行性和有效性。实验表明:所提算法可在机器人实际分拣作业中规划出有效的分拣路径,平均分拣距离和分拣时间均小于顺序规划算法,提高了机器人对平面随机分布的连续运动物体的分拣效率,实时性好,实用性强,对机器人动态分拣场景下的分拣路径优化研究具有一定的指导意义。
Abstract:An improved greedy strategy planning algorithm for continuous robot sorting is proposed for the problem that the efficiency is low when traditional sequential sorting algorithm is applied to sort dynamically materials with Cartesian robot. Kinematic model of the Cartesian robot was established to ensure that materials can be accurately picked up. Time window was designed to divide the continuous flow materials on the conveyor belt into regions one by one, and the greedy strategy was applied to plan the sorting sequence of materials in the same time window. Cost function was designed to improve the greedy strategy considering the risk of missing materials in the sorting, which enhances the practicality of the algorithm. Simulation environment was designed to simulate the algorithm, and the sorting experiment was carried out using the designed robot platform to verify the feasibility and effectiveness of the algorithm. Experiments show that the algorithm can plan an effective sorting path in the actual sorting operation of the robot. The average sorting distance and sorting time are both smaller than the sequence planning algorithm, which improves the efficiency of robot sorting for continuous moving materials in the plane. The algorithm, with good real-time performance and strong practicability, has certain guiding significance for the research on the optimization of the sorting path in the case of dynamic sorting with Cartesian robot.
-
Key words:
- dynamic sorting /
- Cartesian robot /
- sorting planning /
- greedy strategy /
- materials sorting
-
表 1 直角坐标机器人D-H模型参数
Table 1. D-H model parameter of Cartesian robot
关节序号i ai-1/mm αi-1/(°) di/mm θi/(°) 变量 1 0 0 d1 0 d1 2 0 -90 d2 -90 d2 3 0 90 d3 0 d3 4 0 0 0 θ4 θ4 表 2 分拣系统参数
Table 2. Parameters of sorting system
参数 数值 Xmax/mm +1 000 Xmin/mm -1 000 Tmin/ms 1 500 收集箱数量 4 传送带宽度/mm 1 200 机器人工作空间/(mm×mm) 2 000×2 000 机器人X轴运动速度/(mm·s-1) 2 000 机器人Y轴运动速度/(mm·s-1) 2 000 机器人Z轴运动速度/(mm·s-1) 1 800 表 3 物料标准分布分拣模拟结果
Table 3. Simulated sorting results of standard position distribution of materials
传送带速率/ (mm·s-1) 算法 分拣数量 分拣顺序 总分拣时间/ms 总分拣行程/mm 平均分拣时间/ms 平均分拣行程/mm 200 贪心策略 10 2-5-3-8-11-12-9-1-7-10 12 150 15 008 1 215 1 500 顺序规划 9 1-2-3-4-5-6-7-8-9 11 370 18 144 1 263 2 016 250 贪心策略 8 2-5-3-8-11-12-9-10 10 205 11 691 1 276 1 461 顺序规划 8 1-2-3-4-5-6-7-9 11 308 14 826 1 414 1 853 300 贪心策略 7 2-5-8-11-12-9-10 9 150 10 753 1 331 1 536 顺序规划 6 1-2-3-4-5-6 9 315 12 914 1 553 2 152 350 贪心策略 6 2-5-8-11-9-10 8 038 9 618 1 340 1 603 顺序规划 5 1-2-3-4-5 7 875 11 213 1 575 2 243 400 贪心策略 6 2-5-8-11-9-10 7 980 9 678 1 330 1 613 顺序规划 5 1-2-3-4-9 7 550 10 749 1 510 2 150 450 贪心策略 5 2-5-9-1-7 6 658 7 829 1 332 1 566 顺序规划 4 1-2-3-5 6 655 10 443 1 664 2 611 500 贪心策略 4 2-5-9-6 5 140 5 736 1 285 1 434 顺序规划 4 1-2-3-9 6 400 9 893 1 600 2 473 表 4 物料随机分布分拣模拟结果
Table 4. Simulated sorting results of random position distribution of materials
传送带速率/ (mm·s-1) 算法 分拣数量 分拣顺序 总分拣时间/ms 总分拣行程/mm 平均分拣时间/ms 平均分拣行程/mm 200 贪心策略 11 2-4-5-10-8-6-3-1-9-12-11 15 220 18 757 1 384 1 705 顺序规划 10 1-2-3-4-5-6-7-8-9-11 16 420 23 317 1 642 2 332 250 贪心策略 9 2-4-5-10-8-6-3-7-12 12 257 14 798 1 362 1 644 顺序规划 8 1-2-3-4-5-6-7-10 13 090 18 795 1 636 2 349 300 贪心策略 8 2-4-5-10-8-6-11-12 11 015 13 172 1 379 1 647 顺序规划 7 1-2-3-4-5-6-12 11 030 16 141 1 576 2 306 350 贪心策略 7 2-4-5-10-6-9-12 9 745 11 792 1 392 1 684 顺序规划 6 1-2-3-4-5-12 10 085 15 039 1 681 2 507 400 贪心策略 6 2-4-6-3-10-12 8 570 10 728 1 428 1 788 顺序规划 5 1-2-3-4-8 8 510 12 962 1 702 2 592 450 贪心策略 4 1-2-3-4 6 700 10 056 1 675 2 514 顺序规划 4 1-2-3-5 6 803 10 174 1 701 2 544 500 贪心策略 5 2-10-8-6-12 6 825 8 403 1 365 1 681 顺序规划 4 1-2-3-7 6 510 9 431 1 628 2 358 表 5 顺序规划算法与贪心策略规划算法实验结果
Table 5. Experimental results of sequence planning algorithm and greedy strategy planning algorithm
次数 顺序规划算法 贪心策略规划算法 分拣结果 平均分拣时间/ms 分拣结果 平均分拣时间/ms 1 A1-A2-A6 2 195 A2-A4-A6 1 925 2 A1-A2-A5 2 245 A2-A4-A6 1 960 3 A1-A2-A5 2 275 A2-A4-A6 1 945 均值 2 238 1 943 表 6 顺序规划算法与贪心策略规划算法分拣时间
Table 6. Time consumed by sequence planning algorithm and greedy strategy planning algorithm
序号 耗时/ms 贪心策略规划算法 顺序规划算法 1 1 720 1 825 2 1 810 2 150 3 1 680 2 255 4 1 540 2 065 5 1 775 1 910 6 1 620 2 255 7 1 735 1 910 8 1 630 1 785 9 1 715 1 785 10 1 760 1 775 平均 1 698.5 1 971.5 -
[1] 王田苗, 陶永. 我国工业机器人技术现状与产业化发展战略[J]. 机械工程学报, 2014, 50(9): 1-13. https://www.cnki.com.cn/Article/CJFDTOTAL-JXXB201409001.htmWANG T M, TAO Y. Research status and industrialization development strategy of Chinese industrial robot[J]. Journal of Mechanical Engineering, 2014, 50(9): 1-13(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JXXB201409001.htm [2] 赵京, 张自强, 郑强, 等. 机器人安全性研究现状及发展趋势[J]. 北京航空航天大学学报, 2018, 44(7): 1347-1358. doi: 10.13700/j.bh.1001-5965.2017.0568ZHAO J, ZHANG Z Q, ZHENG Q, et al. Research status and development trend of robot safety[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(7): 1347-1358. doi: 10.13700/j.bh.1001-5965.2017.0568 [3] SKINDEROWICZ R. An improved ant colony system for the sequential ordering problem[J]. Computers & Operations Research, 2017, 86: 1-17. [4] DAHAN F, HINDI E, MATHKOUR A, et al. Dynamic flying ant colony optimization (DFACO) for solving the traveling salesman problem[J]. Sensors, 2019, 19(8): 1-28. doi: 10.1109/JSEN.2019.2897393 [5] HUANG R H, YU T H. An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting[J]. Applied Soft Computing, 2017, 57: 642-65. doi: 10.1016/j.asoc.2017.04.062 [6] BAYKASOGLU A, SENOL M E. Weighted superposition attraction algorithm for combinatorial optimization[J]. Expert Systems with Applications, 2019, 138: 1-15. [7] PAUL B, NIELS A, MARIE S. Dynamic programming approaches for the traveling salesman problem with drone[J]. Networks, 2018, 72(4): 528-542. doi: 10.1002/net.21864 [8] WANG L, CAI R, LIN M, et al. Enhanced list-based simulated annealing algorithm for large-scale traveling salesman problem[J]. IEEE Access, 2019, 7: 144366-144380. doi: 10.1109/ACCESS.2019.2945570 [9] QIAO J, HU Z, LI W. Hysteretic noisy frequency conversion sinusoidal chaotic neural network for traveling salesman problem[J]. Neural Computing and Applications, 2019, 31(11): 7055-7069. doi: 10.1007/s00521-018-3535-9 [10] LIU C F, ZHANG Y X. Research on MTSP problem based on simulated annealing[C]//International Conference on Information Science and System. New York: ACM, 2018: 283-285. [11] GAO W. New ant colony optimization algorithm for the traveling salesman problem[J]. International Journal of Computational Intelligence Systems, 2020, 13(1): 44-45. doi: 10.2991/ijcis.d.200117.001 [12] 魏彤, 龙琛. 基于改进遗传算法的移动机器人路径规划[J]. 北京航空航天大学学报, 2020, 46(4): 703-711. doi: 10.13700/j.bh.1001-5965.2019.0298WEI T, LONG C. Path planning for mobile robot based on improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 703-711(in Chinese). doi: 10.13700/j.bh.1001-5965.2019.0298 [13] 贺磊盈, 杨太玮, 武传宇, 等. 基于贪心遗传算法的穴盘苗补栽路径优化[J]. 农业机械学报, 2017, 48(5): 36-43. https://www.cnki.com.cn/Article/CJFDTOTAL-NYJX201705004.htmHE L Y, YANG T W, WU C Y, et al. Optimization of replugging tour planning based on greedy genetic algorithm[J]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(5): 36-43(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NYJX201705004.htm [14] BOUDJEDIR C E, BOURI M, BOUKHETALA D. Iterative learning control for trajectory tracking of a parallel Delta robot[J]. Automatisierungstechnik, 2019, 67(2): 145-156. doi: 10.1515/auto-2018-0086 [15] LIU C, CAO G H, QU Y Y, et al. An improved PSO algorithm for time-optimal trajectory planning of Delta robot in intelligent packaging[J]. International Journal of Advanced Manufacturing Technology, 2020, 107(3-4): 1091-1099. doi: 10.1007/s00170-019-04421-7 [16] LIANG X, SU T. Quintic Pythagorean-Hodograph curves based trajectory planning for Delta robot with a prescribed geometrical constraint[J]. Applied Sciences, 2019, 9(21): 1-14. [17] KANSAL S, MUKHERJEE S. Automatic single-view monocular camera calibration-based object manipulation using novel dexterous multi-fingered Delta robot[J]. Neural Computing and Applications, 2019, 31(7): 2661-2678. doi: 10.1007/s00521-017-3221-3 [18] LIU Y N, HU T L, NI H P, et al. Design of a PC-based open industrial robot control system integrated with real-time machine vision[C]//Symposium on Advanced Robotics and Automation. Piscataway: IEEE Press, 2018: 1-6. [19] CORONADO E, MAYA M, CARDENAS A, et al. Vision-based control of a Delta parallel robot via linear camera-space manipulation[J]. Journal of Intelligent & Robotic System, 2017, 85(1): 93-106. [20] ZHANG H, SU T, WU S, et al. Simultaneous path planning and trajectory optimization for high-speed sorting system[J]. International Journal of Advanced Robotic Systems, 2018, 15(5): 1-13. [21] DENAVIT J, HARTENBERG R S. A kinematic notation for low-pair mechanisms based on matrices[J]. Journal of Applied Mechanics, 1955, 22(2): 215-221. doi: 10.1115/1.4011045