Motion Planning for Mobile Robots Through Iterative Task Allocation

This paper proposes and comparatively analyses different techniques of allocating tasks to mobile robots in a computationally efficient manner, with the purpose that the robotic team should satisfy an imposed Boolean formula over a set of tasks. At the same time, various tweaks in solving the path planning problem are investigated. The development starts from structural properties of the Robot Motion Petri Net model of the team that allows one to solve a sequence of Linear Programming (LP) problems instead of a Mixed Integer Linear Programming (MILP) that may become intractable for a large number of robots. We employ various strategies for iterative roundings of non-integer elements of the LP's solution of the task allocation part of the problem, while also examining a rounding technique directly referring to the path planning step. Although the sequence of LPs returns a sub-optimal solution versus the MILP formulation, it brings a net advantage regarding the reduced runtime. The effectiveness of the approach is supported through extensive numerical simulations that compare the influence of different rounding techniques on both runtime and solution cost. The results indicate that the iterative LP-based methods offer a good trade-off between tractable computation and solution quality, especially for teams composed of a few hundred robots.