隨著電子商務的發展，倉儲管理紛紛藉著自動化來提升效率。機械化物流系統使用無人搬運車來進行貨架的移動，有效的降低人力的使用。而如何規劃無人搬運車的使用來增加系統吞吐量是一個重要的議題，此類問題常將車輛視為代理人在起終點之間尋找路線，而成為一個多代理人路徑尋找問題。考量到實際運作情形，可以把它歸納成線上多代理人取貨交貨問題，各代理人會不斷地被派發新的運送任務，包含取貨及送貨的路程，並減少碰撞的產生。當車輛數目提升時，車輛間衝突的數量及排解時間也跟著提高。
本篇論文提出一個使用單向道並基於車輛間合作改善的A*演算法，單向道的使用能減少隨著車輛上升急劇提升的碰撞種類及解決時間，並在A*演算法中考慮其他車輛的路線資訊，來降低因路線重疊可能帶來的壅塞問題，最後再加入鄰近任務優先的分派方法。實驗結果顯示改善的演算法在增加車輛數目的同時，能有效的控制因衝突數目提升而產生的等待時間。

With the development of e-commerce, warehouse management has gradually improved efficiency through automation. Robotic mobile fulfillment systems reduce the use of manpower effectively by using automated guided vehicles (AGV). However, how to plan the use of the AGVs to increase system throughput is an important issue. This problem usually treats each vehicle as an agent looking for a route between the start and end points. The problem can be solved by using the multi-agent path-finding problem (MAPF). In the real-world scenario, the tasks will be assigned consistently. The problem can be transferred to the multi-agent pickup and delivery problem (MAPD). When the number of vehicles increases, the number of conflicts and the resolution time will increase. This thesis proposes an improved A* algorithm based on uni-directional layout and cooperation between vehicles. The use of the uni-directional layout can reduce the types of collision and resolution time. In the improved A* algorithm, the route information of other vehicles is examined to reduce the problem of congestion caused by overlapping routes. The simulation results show that the algorithm can control the growth of waiting time while increasing the number of vehicles.

References
[1] N. Boysen, R. de Koster, and F. Weidinger, “Warehousing in the e-commerce era: A survey,” European Journal of Operational Research, vol. 277, no. 2, pp. 396 - 411, Sept. 2019.
[2] R. de Koster, T. Le-Duc, and K. J. Roodbergen, “Design and control of warehouse order picking: A literature review,” European Journal of Operational Research, vol. 182, no. 2, pp. 481 - 501, Oct. 2007.
[3] J. J. Enright and P. R. Wurman, “Optimization and coordinated autonomy in mobile fulfillment systems,” in Proceedings of the 9th AAAI Conference on Automated Action Planning for Autonomous Mobile Robots, Jan. 2011, pp. 33-38.
[4] J. Yu and S. M. LaValle, “Planning optimal paths for multiple robots on graphs,” in 30th IEEE International Conference on Robotics and Automation (ICRA), May 2013, pp. 3612-3617.
[5] B. Zou, Y. Y. Gong, X. Xu, and Z. Yuan, “Assignment rules in robotic mobile fulfillment systems for online retailers,” International Journal of Production Research, vol. 55, no. 20, pp. 6175-6192, May 2017.
[6] N. Boysen, D. Briskorn, and S. Emde, “Parts-to-picker based order processing in a rack-moving mobile robots environment,” European Journal of Operational Research, vol. 262, no. 2, pp. 550 - 562, Oct. 2017.
[7] T. Lamballais, D. Roy, and M. D. Koster, “Estimating performance in a robotic mobile fulfillment system,” European Journal of Operational Research, vol. 256, no. 3, pp. 976 - 990, Feb. 2017.
[8] T. Lienert, T. Staab, C. Ludwig, and J. Fottner, “Simulation-based performance analysis in robotic mobile fulfilment systems,” in 8th International Conference on Simulation and Modeling, Nov. 2018, pp. 2949-2954.
[9] M. Guan and Z. Li, “Pod layout problem in kiva mobile fulfillment system using synchronized zoning,” Journal of Applied Mathematics and Physics, vol. 06, pp. 2553-2562, Jan. 2018.
[10] M. Phillips, B. J. Cohen, S. Chitta, and M. Likhachev, “E-graphs: Bootstrapping planning with experience graphs,” in Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS), July 2012, pp. 188-189.
[11] L. Cohen, T. Uras, T. K. S. Kumar, H. Xu, N. Ayanian, and S. Koenig, “Improved solvers for bounded-suboptimal multi-agent path finding,” in Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), July 2016, pp. 3067-3074.
[12] Y. Liu, M. Chen, and H. Huang, “Multi-agent pathfinding based on improved cooperative a* in kiva system,” in 5th International Conference on Control, Automation and Robotics (ICCAR), Apr. 2019, pp. 633-638.
[13] N. Smolic-Rocak, S. Bogdan, Z. Kovacic, and T. Petrovic, “Time windows based dynamic routing in multi-agv systems,” IEEE Transactions on Automation Science and Engineering, vol. 7, no. 1, pp. 151-155, Jan. 2010.
[14] Z. Fan, C. Gu, X. Yin, C. Liu, and H. Huang, “Time window based path planning of multi-agvs in logistics center,” in 10th International Symposium on Computational Intelligence and Design (ISCID), vol. 2, Dec. 2017, pp. 161-166.
[15] T. Lienert and J. Fottner, “Routing-based sequencing applied to shuttle systems,” in 21st International Conference on Intelligent Transportation Systems (ITSC), Nov. 2018, pp. 2949-2954.
[16] M. Merschformann, L. Xie, and D. Erdmann, “Path planning for robotic mobile fulfillment systems,” arXiv:1706.09347 [cs.AI], June 2017.
[17] F. Jia, C. Ren, Y. Chen, and Z. Xu, “A system control strategy of a conflict-free multi-agv routing based on improved a star algorithm,” in 24th International Conference on Mechatronics and Machine Vision in Practice (M2VIP), Nov. 2017, pp. 1-6.
[18] H. Ma, J. Li, T. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding for online pickup and delivery tasks,” in Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS), May 2017, pp. 837-845.
[19] J. Švancara, M. Vlk, R. Stern, D. Atzmon, and R. Barták, “Online multi-agent pathfinding,” in Proceedings of the 33th AAAI Conference on Artificial Intelligence, July 2019, pp. 7732-7739.
[20] F. Grenouilleau, W.-J. van Hoeve, and J. N. Hooker, “A multi-label a* algorithm for multi-agent pathfinding,” in Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS), July 2019, pp. 181-185.