Capacitated Multi-Robot Task Allocation with Time Windows Using Location-Routing Task-Motion Planning

摘要

This work presents a four-stage framework that solves a capacitated multi-robot task-motion planning problem with time windows using a location-routing task motion planning (LRTMP) approach that respects the vehicles' maximum item load. We begin by first generating collision-free regions of interest using a probabilistic roadmap. Secondly, we use capacitated clustering algorithms to determine how many facilities to open based on the vehicle's maximum item load and proximity of the goal regions. For each cluster, we also determine the location of the facility. In the third stage, we deploy our task allocation algorithm to determine which vehicle should visit which cluster. Finally, we use an off-the-shelf domain-independent planner and a second-order vehicle model in an obstacle-rich environment for our simulated experiments. We compare the performance of our LRTMP solution with the related work. Results measure the runtime, the number of goods collected, and the average travel distance.