Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-12556
Authors: Kubica, Manuel
Title: Optimized multi-agent resource extraction
Issue Date: 2022
metadata.ubs.publikation.typ: Abschlussarbeit (Bachelor)
metadata.ubs.publikation.seiten: 43
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-125759
http://elib.uni-stuttgart.de/handle/11682/12575
http://dx.doi.org/10.18419/opus-12556
Abstract: Multi-Agent Resource Extraction combines collecting resources with Multi-Agent Pathfinding. For this, multiple agents are coordinated in a graph to remove resources and deposit them into a warehouse. Agents can collide with each other and as long as a resource is not removed, it is an obstacle for the agents. This problem is inspired by real-time strategy computer games, but could also apply to automated warehouses or pickup and delivery problems. In this work, we have studied the complexity of Multi-Agent Resource Extraction for finding a feasible solution as well as finding the fastest possible solution. In this context, we introduced two restrictions to our problem: One where the starting positions are constrained, and another where the capacity of each agent and the size of each resource deposit is limited to one. We showed that finding the fastest possible solution is NP-hard, even if we impose both restrictions. Unlike other related problems, we concluded that deciding if a solution exists is NP-complete. This is still the case when the two restrictions are applied individually. Only by applying both, we were able to find a subset of problems that is not NP-hard. For that subset of problems, we developed an š¯‘‚(š¯‘›5) algorithm that finds a feasible solution. As part of this algorithm, we also developed another algorithm that decides whether an agent can reach a specific vertex.
Appears in Collections:05 FakultƤt Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
BA_kubica.pdf1,16 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.