Min-Max Tours and Paths for Task Allocation to Heterogeneous Agents

Abstract

We consider a scenario consisting of a set of heterogeneous mobile agents and a set of tasks dispersed over a geographic area. The agents are partitioned into different types. The tasks are partitioned into specialized tasks that can only be done by agents of a certain type, and generic tasks that can be done by any agent. Given this scenario, we address the problem of allocating these tasks among the available agents (subject to type compatibility constraints) while minimizing the maximum travel cost for any agent. We first look at the heterogeneous agent cycle problem where agents start at a common depot and need to tour the set of tasks allocated to them before returning to the depot. We provide a 5-approximation algorithm to solve this problem, regardless of the total number of agents and the number of agents of each type. We then consider the heterogeneous agent path problem (HAPP) where agents can start from arbitrary locations and are not constrained to return to their start location. We consider two approaches to solve HAPP. The first approach yields a 15-approximation factor, while the second yields a factor of 16.