Abstract
A. Ekici, P. Keskinocak and S. Koenig. Multi-Robot Routing with Linear Decreasing Rewards over Time. In IEEE International Conference on Robotics and Automation (ICRA), pages 958-963, 2009.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.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.