EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Heuristic reoptimization of time‐extended multi‐robot task allocation problems

Esther Bischoff, Saskia Kohn, Daniela Hahn, Christian Braun, Simon Rothfuß, Sören Hohmann

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →