Multi-robot routing with linear decreasing rewards over time

Ali Ekici, Pinar Keskinocak, Sven KoenigICRA 2009 · OpenReview

Abstract

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.
BibTeX
@inproceedings{ekici2009multi,
  author = {Ali Ekici and Pinar Keskinocak and Sven Koenig},
  title = {{Multi-robot routing with linear decreasing rewards over time}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2009},
  url = {https://openreview.net/forum?id=QxdjRyzybvj},
}

Loading related content...

Figure