TASK ASSIGNMENT IN VARIABLE CAPACITY DRONE SWARMS USING DYNAMICALLY STABLE MATCHING

Abstract

Autonomous multivehicle systems and swarming systems are seen as increasingly applicable to military operations. Successful deployment, however, hinges on the ability to efficiently allocate system resources through task decomposition and subtask assignment. As the general task assignment problem is nondeterministic polynomial-time hard, approximation techniques must be employed to derive near-optimal solutions in a timely manner. Currently, auction and forest-based algorithms are popular choices for this purpose. This thesis proposes the Dynamic Stable Matching (DSM) algorithm as an alternative approach to deriving task allocation solutions. The algorithm's performance is demonstrated and compared to its alternatives through the implementation of DSM-based area search behaviors for an unmanned air vehicle swarm. Our findings establish the DSM algorithm as a viable alternative to existing approaches in terms of computation speed and solution quality. Further research is needed to characterize the algorithm's scalability to larger swarm and area sizes.