Leighton Collins, IV | Robotics and Software Engineering

Fall 2019

Multi-agent task allocation is an important research area as a wide range of real-world problems can be modelled as a multi-agent task allocation problem. This project aimed to solve the multi-agent task allocation problem in which the system is comprised of multiple agents with differing capabilities that solve different parts of the problem, working collaboratively to achieve goals that are broken down into several tasks.

​

The project resulted in the construction of a valid heterogeneous multi-task-robot allocation (HMRTA) algorithm, with task prioritization rules which can be optimized to yield faster task completion times. The HMRTA algorithm is composed of three phases:

1. First, a bipartite graph is constructed which creates edges between robots which are feasible pairs to a corresponding task, taking into account the physical constraints specified for the intended environment.

2. The second phase prioritizes all incomplete tasks to determine which task to allocate robots to first, based on a set of predefined rules that directly affect the performance of the algorithm. These rules can be tuned through the incorporation of hyper-parameters that scale the importance of each rule relative to the others.

3. The final phase uses the graph and priority rankings from phases one and two, and allocates robots to tasks using a greedy algorithm which aims to always complete the highest priority task with the highest corresponding robot-task edge. The states of all robots and tasks are then updated, and the algorithm begins another iteration.
    

This algorithm was optimized using genetic algorithm and particle swarm optimization methods, using the hyper-parameters of phase two as design variables to optimize an objective function which maximizes the number of tasks completed in a given time frame of 150 seconds. The final report is given below.