Heuristic reoptimization of time‐extended multi‐robot task allocation problems
Networks · 2024-07 · 84 (1) · 64-83
DOI: 10.1002/net.22217 ↗Kurz gefasst
Fachartikel in der Zeitschrift Networks, online erschienen am 12.03.2024. Verfasst von Esther Bischoff und 5 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
Providing high quality solutions is crucial when solving NP‐hard time‐extended multi‐robot task allocation (MRTA) problems. Reoptimization, that is, the concept of making use of a known solution to an optimization problem instance when the solution to a similar problem instance is sought, is a promising and rather new research field in this application domain. However, so far no approximative time‐extended MRTA solution approaches exist for which guarantees on the resulting solution's quality can be given. We investigate the reoptimization problems of inserting as well as deleting a task to/from a time‐extended MRTA problem instance. For both problems, we can give performance guarantees in the form of an upper bound of 2 on the resulting approximation ratio for all heuristics fulfilling a mild assumption. We furthermore introduce specific solution heuristics and prove that smaller and tight upper bounds on the approximation ratio can be given for these heuristics if only temporal unconstrained tasks and homogeneous groups of robots are considered. A conclusory evaluation of the reoptimization heuristic demonstrates a near‐to‐optimal performance in application.
Zitieren
APA
Bischoff, E., Kohn, S., Hahn, D., Braun, C., Rothfuß, S., & Hohmann, S. (2024). Heuristic reoptimization of time‐extended multi‐robot task allocation problems. Networks, 84(1), 64-83. https://doi.org/10.1002/net.22217
Vancouver
Bischoff E, Kohn S, Hahn D, Braun C, Rothfuß S, Hohmann S. Heuristic reoptimization of time‐extended multi‐robot task allocation problems. Networks. 2024;84(1):64-83. doi:10.1002/net.22217
BibTeX
@article{Bischoff2024,
author = {Bischoff, Esther and Kohn, Saskia and Hahn, Daniela and Braun, Christian and Rothfuß, Simon and Hohmann, Sören},
title = {Heuristic reoptimization of time‐extended multi‐robot task allocation problems},
journal = {Networks},
year = {2024},
volume = {84},
number = {1},
pages = {64--83},
doi = {10.1002/net.22217}
}
EUVIMED