What is Task Allocation
In a given setting, a dynamic interplay emerges between agents and tasks. Agents, comprising individual autonomous entities such as drones, cars, and robots, interact with tasks that encompass a wide array of objectives they need to achieve. These objectives range from navigating to specific locations, and traversing designated paths, to tracking various objects.
Amidst the backdrop of recent strides in autonomous systems, with a particular focus on Unmanned Aerial Systems (UAS), the prospect of extensive deployment within urban landscapes becomes tangible. Nonetheless, the current landscape lacks the requisite infrastructure to effectively manage the deployment of large fleets in such complex scenarios. The integration of autonomy emerges as the pivotal solution to forge a secure operational environment for these large UAS fleets.
The paradigm of task allocation optimization surfaces as an instrumental approach to surmount this challenge. By employing this method, a collective of agents—namely, UAS—can collaboratively reach a consensus on the most suitable and cost-efficient courses of action.
Task-Oriented Distributed Assignment Algorithm
In this paper, we propose a new distributed algorithm for task assignment problems for unmanned aerial systems (UAS). Inspired by the Hungarian method, the proposed algorithm, namely, the task-oriented distributed assignment algorithm (TODAA), uses a mechanism that updates the label and the slack variables in a heuristic manner throughout the assignment process for each individual UAS. We compare the proposed TODAA with the Concensus-Based Auction Algorithm (CBAA) in terms of computational time and cost optimality errors. The results show that the TODAA outperforms the CBAA in assignment cost whereas is outperformed in computational time.
Sequential Task Addition Distributed Assignment Algorithm
In this paper, we present a novel distributed task-allocation algorithm, namely the Sequential Task Addition Distributed Assignment Algorithm (STADAA), for autonomous multi-robot systems. The proposed STADAA can implemented in applications such as search and rescue, mobile-target tracking, and Intelligence, Surveillance, and Reconnaissance (ISR) missions. The proposed STADAA is developed by modifying an algorithm (i.e., the Task Oriented Distributed Assignment Algorithm (TODAA)) we previously developed based on the Hungarian algorithm. The STADAA employs a conflict-resolution mechanism that utilizes a slack variable, sequentially adding new admissible tasks to an admissible task list when there exists conflict in an assignment. The STADAA aims to minimize the resulting cost of the task assignments. We compare the STADAA with the Consensus-Based Auction Algorithm (CBAA), the Distributed Hungarian Based Algorithm (DHBA), and the TODAA in terms of the computational time, optimality, the number of steps to converge, and algorithmic complexity. The results show that the STADAA outperforms the CBAA and the TODAA in optimality and outperforms the DHBA in computational time.
More to come
Add dissertation
Add third paper
