Simultaneous dynamic scheduling and collision-free path planning for multiple autonomous vehicles

When autonomous vehicles are deployed to perform transportation tasks within a confined space and strict time constraint, the problem of optimizing the assignment of tasks to vehicles is complicated by the need to ensure safety (they do not collide with or impede each other) and maximize the efficiency and productivity. With the increasing number of autonomous vehicles in practical settings, the ability to schedule tasks in a manner that inherently considers the effects of task allocations on space contention (which in turn compromises efficiency) is important to performance improvement. The main contribution of this paper is an approach to simultaneously conduct dynamic task allocation and collision-free path planning in an environment where multiple autonomous vehicles operate on a network of paths and where each path segment can only be occupied by one vehicle at a given instant. In particular, a generic algorithm for effective task allocation is investigated and applied in conjunction with an application-specific objective function. The proposed approach is able to solve the dynamic scheduling, planning and collision avoidance problem in an integrated way such that the overall productivity of the transportation system is improved. Simulation results based on a real-world industrial material handling environment demonstrate the feasibility and effectiveness of the proposed method.