Using a knowledge base to solve the Multi-Agent Pathfinding problem in a warehouse environment

Sammanfattning: E-commerce services is becoming more and more popular, and thus more pressure is being put on the warehouses which handles the orders. One prominent way to increase said warehouses efficiencies is to apply the Amazon Robotics approach of having hundreds of Automated Guided Vehicles (AGVs) deliver the storage shelfs to the workers, instead of having the workers walk around. Controlling such a system is a challenge containing multiple problems; one is the MultiAgent Pathfinding problem (MAPF) which includes the path planning and the collision avoidance of the AGVs. This report studies a new approach to solve the MAPF problem: the Dynamic Knowledge Based Routing algorithm (DKBR), a local repair algorithm that chooses a collision solving rule using machine learning. The DKBR algorithm is compared to a baseline algorithm called Windowed Hierarchical Cooperative A' (WHCA') in terms of the collective number of steps each AGV takes. The result showed that the DKBR algorithm is a valid algorithms for the MAPF problem. However, its performance is essentially identical to an algorithm that choses a random rule instead of utilizing machine learning. This could be explained by the poor accuracy of the decision tree due to the curse of dimensionality or the lack of data. Further research is recommended to investigate if the accuracy of the decision tree can be improved and if that leads to better performance for the DKBR algorithm.