UC San Diego

In this paper, we address the problem of assigning tasks and generating trajectories in a collision-free manner for multi-robot systems moving along a predefined roadmap. First, we propose centralized algorithms, which assign tasks to minimize the total travel distance or the collisions and then resolve the collisions with replanning the trajectory by local graph modification. Especially, to minimize the collisions in the initial task assignment, we formulate an optimization problem whose objective function includes the number of collisions based on a conflict graph that encodes all possible collisions among the system. We also develop a method to resolve remaining collisions in the initial task assignment. In this method, each robot has a graph representing the roadmap, which is used to generate its trajectory. When a collision occurs on the trajectory, the robot modifies the graph to regenerate the trajectory that resolves the collision.

We then propose several decentralized algorithms, extending the centralized methods, which assign tasks initially before robots start moving in such a way to minimize the total travel distance, minimize collisions, or deploy randomly, and then avoid collisions with local graph modification. In the initial task assignment minimizing collisions, each robot calculates the expected value of collisions based on the local conflict graph, which encodes possible collisions among the neighborhood and choose a task to minimize the expectation while coordinating to resolve a conflict of the assignment with the neighborhood.

The paper finally reports on simulations for systems of several tens of robots to evaluate the performance of the proposed centralized and decentralized algorithms.