Integer Programming for Multi-Robot Planning: A Column Generation Approach
This addresses efficient multi-robot planning for warehouse logistics, presenting an incremental improvement through a specific optimization approach.
The paper tackles the problem of coordinating a fleet of robots in a warehouse to maximize reward under time and constraint limits, achieving this by formulating it as a weighted set packing problem and solving it with column generation.
We consider the problem of coordinating a fleet of robots in a warehouse so as to maximize the reward achieved within a time limit while respecting problem and robot specific constraints. We formulate the problem as a weighted set packing problem where elements are defined as being the space-time positions a robot can occupy and the items that can be picked up and delivered. We enforce that robots do not collide, that each item is delivered at most once, and that the number of robots active at any time does not exceed the total number available. Since the set of robot routes is not enumerable, we attack optimization using column generation where pricing is a resource-constrained shortest-path problem.