進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2008202012001400
論文名稱(中文) 在雙向自動化倉庫中基於衝突分類與任務交換機制的多代理人取貨與運輸演算法
論文名稱(英文) A Multi-Agent Pickup and Delivery Algorithm Based on Collision Classification with Task Exchange in Bidirectional Automated Warehouses
校院名稱 成功大學
系所名稱(中) 電腦與通信工程研究所
系所名稱(英) Institute of Computer & Communication
學年度 108
學期 2
出版年 109
研究生(中文) 姜智元
研究生(英文) Zhi-Yuan Jiang
學號 Q36071130
學位類別 碩士
語文別 英文
論文頁數 38頁
口試委員 指導教授-斯國峰
口試委員-焦惠津
口試委員-歐家和
口試委員-高嘉宏
口試委員-王超
中文關鍵字 自動導引車  多代理人路徑尋找  多代理人取貨與運輸問題  碰撞分類 
英文關鍵字 automated guided vehicle  multi-agent path-finding  multi-agent pickup and delivery  collision classification 
學科別分類
中文摘要 由於近年來電子商務的快速發展,使得倉儲管理透過自動化來提高訂單處理效率的議題更加重要。自動導引車輛可以有效地減少所需的人力,然而如何妥善使用自動導引車來增加處理效能是一個亟待解決的問題。此問題會將每輛自動導引車視為尋找各訂單起點和終點之間路線的代理人,再通過多代理人路徑尋找方法(MAPF)來解決。訂單的處理是一個接續一個且不停的執行。因此問題可以轉移到多代理人取貨與運輸問題(MAPD)。MAPD的主要目標為解決車輛間的碰撞以減少訂單的處理時間。當工作車輛數量增加時,碰撞次數隨之增加,若無法有效解決車輛碰撞造成的壅塞,反而會增加訂單處理的時間。本論文提出一種在雙向倉庫下基於碰撞分類結合任務交換機制的MAPD演算法,可以有效處理在雙向布局下造成自動導引車輛間的阻塞問題。在改良的碰撞分類中,可偵測三種碰撞類型以減少由重疊路線所引起的壅塞問題。模擬結果顯示此方法在增加車輛數量的同時,能有效控制訂單等待時間的增加並降低訂單的完成時間。
英文摘要 Due to the rapid development of e-commerce in recent years, the issue of warehouse management for improving the efficiency of order processing through automation is more important.
Automated guided vehicles can effectively reduce the use of labor.
How to properly use AGVs to enhance processing efficiency is an urgent problem to be solved.
This problem typically considers each AGV as an agent to find the path between the start and end point of the order.
It can be solved by using the multi-agent pathfinding (MAPF).
The processing of orders is an one after another and non-stop execution.
Therefore, the problem can be transformed to the multi-agent pickup and delivery problem (MAPD).
The main goal of MAPD is to solve the collision between AGVs to reduce the processing time of orders.
When the number of working AGVs increases, the number of collisions increases accordingly.
If the congestion caused by AGV collisions cannot be effectively solved, it will raise the processing time of orders.
This thesis proposes an MAPD algorithm based on collision classification with task exchange mechanism in a bidirectional warehouse, which can effectively deal with the blocking problem caused by AGVs under the bidirectional layout.
In the improved collision classification, three collision types can be detected to reduce congestion caused by overlapping paths.
The simulation results show that this algorithm can effectively control the growth of average pickup time and reduce the average finish time while raising the number of AGVs.
論文目次 Chapter

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Automated Guided Vehicle Picking System . . . . . . . . . . . . . . . . . 1
1.2 Multi-Agent Pickup and Delivery Problem . . . . . . . . . . . . . . . . . 2
1.3 Collision Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4 Multi-Agent Pickup and Delivery Algorithm . . . . . . . . . . . . . . . 10
4.1 Tasks Assigner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Improved Collision Classification . . . . . . . . . . . . . . . . . . . . . . 12
4.2.1 Collision Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.2 Head-on Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2.3 Cross Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.4 Occupancy Collision . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2.5 Task Exchange Method . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Detection for Idle AGVs . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.4 Update Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2.1 Comparison in Layout 1 . . . . . . . . . . . . . . . . . . . . . . . 25
5.2.2 Comparison in Layout 2 . . . . . . . . . . . . . . . . . . . . . . . 28
5.2.3 Comparison of Different Lifting Time . . . . . . . . . . . . . . . . 32
5.2.4 Comparison of Task Exchange Mechanism . . . . . . . . . . . . . 32

6 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
參考文獻 [1] T. van Gils, K. Ramaekers, A. Caris, and R. B. M. de Koster, “Designing efficient order picking systems by combining planning problem: State-of-the-art classification and review,” European Journal of Operational Research, vol. 267, no. 1, pp. 1 – 15, May 2018.
[2] A. Kelly, B. Nagy, D. Stager, and R. Unnikrishnan, “An infrastructure-free automated guided vehicle based on computer vision - an effort to make an industrial robot vehicle that can operate without supporting infrastructure,” in IEEE Robotics and Automation Magazine, Sept. 2007, pp. 24 – 34.
[3] H. Yoshitake, R. Kamoshida, and Y. Nagashima, “New automated guided vehicle system using real-time holonic scheduling for warehouse picking,” in IEEE Robotics and Automation Letters, Apr. 2019, pp. 1045 – 1052.
[4] Y. Liu, M. Chen, and H. Huang, “Multi-agent pathfinding based on improved cooperative A* in kiva system,” in 2019 5th International Conference on Control, Automation and Robotics (ICCAR), Aug. 2019, pp. 633 – 638.
[5] H. Ma, S. Koenig, N. Ayanian, L. Cohen, W. Honig, T. K. S. Kumar, T. Uras, and H. Xu, “Overview: Generalizations of multi-agent path finding to real-world scenarios,” in IJCAI - 16 Workshop on Multi-Agent Path Finding, July 2016.
[6] M. Liu, H. Ma, J. Li, and S. Koenig, “Task and path planning for multi-agent pickup and delivery,” in International Conference on Autonomous Agents and MultiAgent Systems, May 2019, pp. 1152 – 1160.
[7] J. Li, T. K. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding in large-scale warehouses,” in international Joint Conference on Autonomous Agents and Multiagent Systems, May 2020.
[8] O. Wangapisit, E. Taniguchi, J. S. Teo, and A. G. Qureshi, “Multi-agent systems modelling for evaluating joint delivery systems,” Procedia - Social and Behavioral Sciences, no. 125, pp. 472 – 483, Mar. 2014.
[9] Z. Zhang, Q. Guo, and P. Yuan, “Conflict-free route planning of automated guided vehicles based on conflict classification,” in IEEE International Conference on Systems, Oct. 2017, pp. 1459 – 1464.
[10] P. Udhayakumar and S. Kumanan, “Task scheduling of AGV in FMS using non-traditional optimization techniques,” International Journal of Simulation Modelling, vol. 9, no. 1, pp. 28 – 39, Mar. 2010.
[11] Z. Han, D. Wang, F. Liu, and Z. Zhao, “Multi-AGV path planning with double-path constraints by using an improved genetic algorithm,” PLos ONE, pp. 1 – 16, July 2017.
[12] A. Singha, A. K. Ray, and A. B. Samaddar, “Grid-based UGV navigation in a dynamic environment using neural network,” in International Conference on Inventive Research in Computing Applications, July 2018, pp. 509 – 514.
[13] P. Pourrahimian, “A new memetic algorithm for mitigating tandem automated guided vehicle system partitioning problem,” Journal of Industrial Engineering International, pp. 845 – 855, Nov. 2017.
[14] V. K. Chawla, A. K. Chanda, and S. Angra, “Automatic guided vehicles fleet size optimization for flexible manufacturing system by grey wolf optimization algorithm,”Management Science Letters, pp. 79 – 90, Dec. 2017.
[15] T. Lienert and J. Fottner, “Routing-based sequencing applied to shuttle systems,” in International Conference on Intelligent Transportation Systems, Nov. 2018.
[16] S. Sun, C. Gu, Q. Wan, H. Huang, and X. Jia, “CROTPN based collision-free and deadlock-free path planning of AGVs in logistic center,” in International Conference on Control, Automation, Robotics and Vision, Nov. 2018, pp. 1685 – 1691.
[17] R. Barták, J. vancara, and M. Vlk, “A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs,” in International Conference on Autonomous Agents and MultiAgent Systems, July 2018, pp. 748 – 756.
[18] C. Henkel and M. Toussaint, “Optimized directed roadmap graph for multi-agent path finding using stochastic gradient descent,” in ACM/SIGAPP Symposium on Applied Computing, Mar. 2020, pp. 776 – 783.
[19] W. Honig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian, “Persistent and robust execution of MAPF schedules in warehouses,” IEEE Robotics and Automation Letters, pp. 1125 – 1131, Jan. 2019.
[20] Z. Zhang, Q. Guo, J. Chen, and P. Yuan, “Collision-free route planning for multiple AGVs in an automated warehouse based on collision classification,” IEEE Access,vol. 6, pp. 26 022 – 26 035, Mar. 2018.
[21] P. Long, T. Fan, X. Liao, W. Liu, H. Zhang, and J. Pan, “Towards optimally decentralized multi-robot collision avoidance via deep reinforcement learning,” in IEEE International Conference on Robotics and Automation, May 2018, pp. 6252 – 6259.
[22] F. Grenouilleau, W.-J. van Hoeve, and J. N. Hooker, “A multi-label A* algorithm for multi-agent pathfinding,” in International Conference on Automated Planning and Scheduling, July 2019, pp. 181 – 185.
[23] R. Claes, T. Holvoet, and J. V. Gompel, “Coordination in hierarchical pickup and delivery problems using delegate multi-agent systems,” Jan. 2010.
[24] H. Ma, J. Li, T. K. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding for online pickup and delivery tasks,” in International Conference on Autonomous Agents and MultiAgent Systems, May 2017.
[25] V. Nguyen, P. Obermeier, and T. C. Son, “Generalized target assignment and path finding using answer set programming,” in International Joint Conference on Artificial Intelligence, Aug. 2017, pp. 1216 – 1223.
[26] J. Merlevede, R. R. van Lon, and T. Holvoet, “Neuroevolution of a multi-agent system for the dynamic pickup and delivery problem,” in International Conference on Autonomous Agents and MultiAgent Systems, May 2014.
[27] J. Svancara, M. Vlk, R. Stern, D. Atzmon, and R. Bartak, “Online multi-agent pathfinding,” in AAAI Conference on Articial Intelligence, vol. 33, no. 1, July 2019, pp. 7732 – 7739.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2025-07-06起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2025-07-06起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw