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

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 20
  • Download : 0
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.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2020-09
Language
English
Article Type
Article
Citation

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, v.7, no.3, pp.1511 - 1522

ISSN
2325-5870
DOI
10.1109/TCNS.2020.2983791
URI
http://hdl.handle.net/10203/276526
Appears in Collection
AE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0