Content area
This thesis explores a decentralized multi-robot task scheduling problem in which a heterogeneous group of energy-constrained robots collaborates to complete tasks with varying capability requirements and cross-schedule dependencies. We introduce a framework along with three distributed algorithms, coined Greedy plus Wiggle Scheduling (G+WS), Monte Carlo plus Wiggle Scheduling (MC+WS), and Q-Learning plus Wiggle Scheduling (QL+WS), which utilize a task allocation approach termed wiggle scheduling to allocate tasks to robots. To benchmark performance, the proposed algorithms are compared against a centralized mathematical optimization solution implemented using Gurobi.
Experimental evaluations demonstrate that the MC+WS algorithms consistently produce better solution rewards than the other distributed algorithms and can produce solution rewards at 95% average of optimal solution while having a significantly faster algorithm run time compared to the centralized solutions, but are still slower than the other distributed algorithms and lack scalability. The G+WS algorithm yields the lowest solution rewards, at 86% average of optimal, but consistently achieves the fastest algorithm run time and demonstrates strong scalability as the number of tasks and robots increases. The QL+WS algorithm offers a balanced trade-off, requiring less algorithm run time than MC+WS while producing better solution rewards than G+WS, at 89% of optimal.