Multi-Robot Routing with Linear Decreasing Rewards over Time

We study multi-robot routing problems (MR-LDR) where a team of robots has to visit a set of given targets with linear decreasing rewards over time, such as required for the delivery of goods to rescue sites after disasters. The objective of MR-LDR is to find an assignment of targets to robots and a path for each robot that maximizes the surplus, which is defined to be the total reward collected by the team minus its total travel cost. We develop a mixed integer program that solves MR-LDR optimally with a flow-type formulation and can be solved faster than the standard TSP-type formulations but also show that solving MR-LDR optimally is NP-hard. We then develop an auction-based algorithm and demonstrate that it solves MR-LDR in seconds and with a surplus that is comparable to the surplus found by the mixed integer program with a 12 hour time limit.