A Unified Framework for Multi-Robot Task Allocation

PhD Defense Talk
A Unified Framework for Multi-Robot Task Allocation
by Muhammad Usman Arif

Date: Tuesday, June 14, 2022
Time: 10:00am
Venue: Conference Room, Tabba Academic Block, IBA Main Campus, Karachi, Pakistan.
Advisor: Dr. Sajjad Haider
External Examiners: Dr. Ali Raza Jafri (NED University of Engineering & Technology), and Dr. Yasar Ayaz (National Centre of Artificial Intelligence, NUST)

Abstract:

Multi-Robot Task Allocation (MRTA) is concerned with allocating tasks to multi-robot teams for the efficient completion of the mission at hand. With the majority of the MRTA problems classified as NP-hard, problem-specific task allocation solutions are preferred for these scenarios. With the dynamic nature of multi-robot operations such as search and rescue and firefighting, a static scenario cannot be guaranteed throughout the operation. This makes the implementation of customized solutions difficult in dynamic situations. Generic task allocation mechanisms are required for such situations to quickly adapt to the variety of problems possibly faced during operation.

This thesis presents RoSTAM (Robust and Self-adaptive Task Allocation for Multi-robot Teams) for quality task allocations across a range of MRTA problem types. RoSTAM has the flexibility to adapt to a wide variety of scenarios and can adjust to a range of environmental changes during task allocation or execution. RoSTAM utilizes an Evolutionary Algorithm as an underlying solution space exploration mechanism to provide quality task allocations.

The challenges addressed in this research are (a) designing of an Evolutionary Algorithm as a generic solution to a range of computationally complex problems, (b) the modeling of scenario-specific solution evaluation functions which help RoSTAM evaluate feasible and infeasible plans, (c) designing an online implementation to adjust to any environmental changes happening during task allocation or execution, and (d) embedding of all these into a single framework for seamless operation across all the targeted problem types. The novelty of this work lies in its capability to adjust to a variety of MRTA problem types seamlessly. Each of these problems is computationally complex and a majority of them are classified as NP-hard. Designing a single framework to provide quality allocations against multiple problem types is a unique contribution to the field.

In this work, RoSTAM is evaluated against a range of MRTA problem configurations, including scenarios providing scheduling of tasks demanding single robot or multiple robots for completion with tightly coupled and loosely coupled multi robot operations. The allocations are made to single task and multi-tasking capable multi-robot teams both in static and dynamic configurations. RoSTAM’s performance is compared against popular schemes from the literature within each of the tested scenarios. RoSTAM demonstrates that a single framework with a well-designed solution space exploration mechanism and problem specific supporting modules can provide high-quality allocations to a range of MRTA problem types. Although RoSTAM is evaluated against robot task allocation, its applicability can be expanded to other similar fields such as Vehicle Routing Problem, Multiple Traveling Salesman Problem, and Factory Flood Scheduling to name a few.