Back to search

Georgia Institute of Technology

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

Abstract

dc:description.abstract

Effective coordination enables heterogeneous multi-robot systems to complete a wide range of missions effectively. Multi-robot task allocation (MRTA), a key component of this coordination, aims to assign tasks to robots appropriately. Given that communication can be unreliable or limited in real-world settings, it is crucial to develop task allocation strategies for these situations. This dissertation introduces two heterogeneous task allocation approaches for different scenarios using the Speeding-Up and Slowing-Down (SUSD) strategy [1], a derivative-free optimization technique that achieves convergence toward the gradient direction through local function evaluations. SUSD is suitable for MRTA problems, which can be treated as integer programming issues with ill-defined gradients, as it does not require explicit gradient calculations. In the first scenario, each task is completed by a single robot, with a base station available. We present a hybrid SUSD-based task allocation algorithm. Initially, robots use a market-based task allocation algorithm, well-suited for environments with limited communication, to generate initial allocation results. The base station then employs the SUSD strategy to improve these results. Testing in simulated underwater sensing missions demonstrated significant improvement in total makespan (mission completion time) for medium-scale problems (fewer than 20 robots and 50 tasks) compared to existing market-based approaches. In the second scenario, multiple robots cooperatively complete tasks, with each robot able to select multiple tasks. To avoid complex coordination mechanisms, we formulate the task allocation as a game where robots share their task selections and update them to minimize individual costs. We developed a distributed task selection algorithm using the SUSD strategy, enabling convergence toward a Nash equilibrium. Aligning robots' cost functions with collective goals ensures effective coordination. Validation through simulated underwater cooperative missions showed significant energy consumption reduction for medium-scale problems compared to existing methods. [1] Al-Abri, S., Lin, T. X., Tao, M., & Zhang, F. (2021). A Derivative-Free Optimization Method with Application to Functions with Exploding and Vanishing Gradients. IEEE Control Systems Letters, 5(2), 587–592.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Shengkang
Advisors dc:contributor.advisor
  • Zhang, Fumin
  • Arkin, Ronald C.
Committee members dc:contributor.committeemember
  • Hutchinson, Seth A.
  • Gombolay, Matthew
  • Williams, Jason L.

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75666

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chen, Shengkang. Distributed Heterogeneous Multi-robot Task Allocation in Communication-limited Environments. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75666