Task Allocation and Path Planning of Many Robots with Motion Uncertainty in a Warehouse Environment

Currently, robots have been widely used in the warehouse environment to improve the logistics operation efficiency. In general, the more robots are deployed, the higher efficiency logistics operation will be. However, more robots also bring more challenges to their task allocation and path planning. Towards the two problems, this paper presents an efficient task allocation and path planning solution that can scale up the robots greatly in a warehouse environment. In particular, the decentralized auction-bid scheme is used to allocate tasks, i.e., each robot provides its estimated task completion time as a bid, and the task is allocated to the robot with the lowest bid. In order to estimate the bid accurately, we take the robot's motion uncertainty into account and predict the robot density in the map at runtime, and then use the Floyd algorithm to the plan the robot path. We also design an effective scheme to sufficiently avoid the robot collision. The experimental results of a hundred robots demonstrated that our solution can quickly allocate the task and plan the path. The average task completion time is also minimized compared to some other state-of-the-art approaches. The simulation code has been open sourced11https://github.com/nucleusbiao/Robot-simulation-in-a-warehouse-environment.