Task Allocation for Mobile Robot Fleets with Decentralised Genetic Algorithms
Authors
Thomsen, Rasmus Finderup ; Albertsen, Ditte Damgaard ; Staal, Alexander Schøn
Term
4. semester
Education
Publication year
2021
Submitted on
2021-06-03
Pages
73
Abstract
Denne afhandling undersøger, hvordan opgaver kan fordeles effektivt mellem flere autonome, decentraliserede AGV’er ved at formulere problemet som et multiple travelling salesman problem (mTSP) og løse det med en genetisk algoritme (GA). Arbejdet fokuserer på den overordnede flådelederfunktion, dvs. at tildele opgaver og bestemme rækkefølgen, mens detaljer som tidsplanlægning, routing og sti-planlægning ligger uden for projektets scope. Med udgangspunkt i en virksomhedsrelateret use case for et pick‑and‑place‑miljø udvikles og tilpasses en GA bestående af initial population, fitnessfunktion, selektion, crossover og mutation til løbende at optimere rækkefølger af opgaver for flere robotter. Decentraliseringsstrategier blev undersøgt med henblik på at forbedre robusthed og skalerbarhed; en fuld implementering lykkedes dog ikke på grund af en sen softwarefejl og blev derfor kun afprøvet konceptuelt og via simulering. Resultaterne viser, at den udviklede GA kan fordele opgaver mellem flere AGV’er og typisk finde løsninger inden for 20% af den globale minimumsløsning i 90% af kørslerne i den testede opsætning. Arbejdet peger på GA’ers anvendelighed til opgaveallokering i robotflåder og identificerer behov for yderligere arbejde med en fuldt decentraliseret implementering.
This thesis addresses how to effectively allocate tasks across multiple decentralized AGVs by framing the problem as a multiple travelling salesman problem (mTSP) and solving it with a genetic algorithm (GA). The work targets high‑level fleet management—assigning tasks and deciding their execution order—while scheduling, traffic routing, and path planning are out of scope. Using a company‑inspired pick‑and‑place use case, a GA with initial population, fitness function, selection, crossover, and mutation is designed and tailored to continually optimize task sequences for multiple robots. Decentralization strategies were explored to improve robustness and scalability; however, a full implementation could not be completed due to a late software issue and was therefore only evaluated conceptually and via simulation. Results indicate that the developed GA can allocate tasks among multiple AGVs and typically finds solutions within 20% of the global minimum in 90% of runs under the tested setup. The study demonstrates the promise of GAs for fleet task allocation and highlights the need for further work toward a fully decentralized implementation.
[This summary has been generated with the help of AI directly from the project (PDF)]
Documents