Back to search

Georgia Institute of Technology

Congestion game-based task allocation for multi-robot teams

Abstract

dc:description.abstract

Multi-robot teams can complete complex missions that are not amenable to an individual robot. A team of heterogeneous robots with complementing capabilities is endowed with advantages to allow deep collaboration in dynamic and complicated environments. Multi-robot Task Allocation (MRTA) presents a fundamental for multi-robot system research. Despite the previous research efforts, there remains a knowledge gap in developing decentralized approaches for MRTA by viewing robots as resources and optimizing the distribution of robots to achieve the best overall performance at the system level. To address this knowledge gap, the objective of this research is to develop decentralized resource allocation algorithms to provide approximate solutions for the MRTA problem. Both standard congestion game theory and weighted congestion game theory are exploited as the theoretical framework to formulate and solve the MRTA problems. Two types of resource allocation problems are considered, one has increasing marginal gain with respect to the number of participating robots, the other has decreasing marginal gain with respect to the number of participating robots. For MRTA problems with homogeneous robot teams, the sequential best response dynamics is integrated in the framework of standard congestion game theory. A concurrent version of best response dynamics with convergence guarantees is developed. In addition, a decentralized dual greedy algorithm is proposed and its convergence to a pure Nash equilibrium is proved. For MRTA problems with heterogeneous robot teams, the best sequential dynamics is shown to converge to pure Nash equilibrium in the framework of weighted congestion games. The suboptimality of the approximate solutions is discussed by \lambda-μ smoothness technique. Simulations and experiments using robots in the Robotarium are conducted to validate the effectiveness of the proposed algorithms.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhong, Hai
Advisor dc:contributor.advisor
  • Hutchinson, Seth
Committee members dc:contributor.committeemember
  • Coogan, Samuel
  • Vamvoudakis, Kyriakos

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/62843

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

Zhong, Hai. Congestion game-based task allocation for multi-robot teams. Masters thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/62843