由於近年來電子商務的快速發展，使得倉儲管理透過自動化來提高訂單處理效率的議題更加重要。自動導引車輛可以有效地減少所需的人力，然而如何妥善使用自動導引車來增加處理效能是一個亟待解決的問題。此問題會將每輛自動導引車視為尋找各訂單起點和終點之間路線的代理人，再通過多代理人路徑尋找方法（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.

[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.