Multi-Robot Path-Planning algorithm for automated parcel sorting centre with ring road layout

• Main Author: Jong, Qian Biao
• Format: Final Year Project / Dissertation / Thesis
• Published: 2023
• Subjects: Q Science (General); T Technology (General)
• Online Access: http://eprints.utar.edu.my/5782/1/fyp_CS_2023_JQB.pdf; http://eprints.utar.edu.my/5782/

Due to the rapid growth of e-commerce, warehouses and sorting centres need to handle a huge number of parcels every day. Some companies are automating their warehouses and sorting centres to cope with the increasing number of parcels. Automated warehouses use automated guided vehicles (AGV) or autonomous mobile robots (AMR) to help sort parcels. These robots work in a highly dynamic environment and are usually implemented in huge numbers. Therefore, it is important to ensure that the robots do not collide with each other and that tasks are distributed fairly and efficiently. Most recent approaches to the navigation of robots assume that the road system for robots to travel in the indoor environment exhibits a simple grid layout. As a result, although the proposed algorithms by recent papers could solve the collisions among the robots, they have less effect in resolving the traffic jam issue caused by the robots passing through the core part of the road system. Such a traffic congestion phenomenon greatly limits the throughput when the number of robots increases. Since the automated warehouses and sorting centres are usually large and contain hundreds of robots, the recent algorithms with the simple grid layout assumption are doubted to be efficient in the real world. Therefore, this project proposes a map layout that implements the outer ring road concept in addition to the inner grid layout. The outer ring road allows robots that wish to travel a longer distance from one end to another without the need to pass through the core road system, thus reducing the amount of traffic in high-traffic areas. This layout works because it provides traffic that travels a longer distance and an alternative path towards their destinations, minimising congestion with other robots. Besides, this project also evaluates and implements the approaches of recent studies and discovers new approaches that could handle the movements of hundreds of robots in real-time while maximising the throughput.