Title: Distributed Heterogeneous Multi-robot Task Allocation in Communication-limited Environments

Date: Monday, July 1, 2024

Time: 3:00 PM – 5:00PM EST

Location: Technology Square Research Building (TSRB) 523A

Virtual Link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZDdjMjNjMmEtMTk3Zi00MzQxLWJkYjAtMzg1NTA1OTAyYWQy%40thread.v2/0?context=%7b%22Tid%22%3a%22482198bb-ae7b-4b25-8b7a-6d7f32faa083%22%2c%22Oid%22%3a%22c59d0dbd-0129-4bad-b7a1-d8d78517fe90%22%7d

Shengkang Chen

Robotics PhD Candidate

School of Electrical and Computer Engineering

Georgia Institute of Technology

Committee:

Dr. Fumin Zhang (Co-Advisor) – School of Electrical and Computer Engineering, Georgia Institute of Technology

Dr. Ronald C. Arkin (Co-Advisor) – School of Interactive Computing, Georgia Institute of Technology

Dr. Seth A. Hutchinson – School of Interactive Computing, Georgia Institute of Technology

Dr. Mathew C. Gombolay – School of Interactive Computing, Georgia Institute of Technology

Dr. Jason L. Williams –  Director of Sensor Fusion, Whipbird Signals

Abstract: 

Effective multi-robot coordination for heterogeneous multi-robot systems to complete a wide range of missions. Multi-robot task allocation (MRTA), a key component in multi-robot coordination, aims to find the appropriate assignments between robots and tasks. Considering that communication can be unreliable or limited in real-world settings, it is important to develop robust task allocation strategies that can function under these constraints. 

This dissertation introduces two heterogeneous task allocation approaches for different scenarios leveraging the Speeding-Up and Slowing-Down (SUSD) strategy. The SUSD strategy, a derivative-free optimization technique, achieves convergence in the direction of the gradient through local function evaluations only. Since MRTA can be treated as an integer programming problem with ill-defined gradients, SUSD is a suitable tool to search for solutions since it does not need explicit gradient calculations. 

In the first scenario, each task in the task allocation can be completed by a single robot, with a base station also available. We present a hybrid SUSD-based task allocation algorithm combining a market-based algorithm with the SUSD strategy to improve the results from the market-based algorithm.  In the second scenario, we address a complex task allocation scenario where multiple robots cooperatively complete each task, and each robot can select multiple tasks. To avoid a complex coordination mechanism, we formulate the task allocation problem as a task allocation game. In the task allocation game, robots only share their task selections with others and update their task selection to minimize their individual costs. We have developed a new distributed task selection algorithm based on the SUSD strategy to allow robots to converge toward a Nash equilibrium.