Back to search

University of Washington

Bipartite Matching and Routing with Congestion Costs: A convex approach to robot task assignment and the multi-agent pathfinding problem

Abstract

dc:description.abstract

Motivated by the congestion-aware path planning and task assignment problem emerging from traffic assignment, ride-sharing, and multi-robot task assignment problems, this thesis incorporates shortest path and assignment problems with congestion by formulating them as a convex optimization problem to minimize the overall matching and routing cost. Two problem settings considered are the street network of Seattle City and the multi-robot system in a warehouse where the drivers and robots are the agents, and the delivery locations are the tasks. We apply our formulation to the defined problem settings and introduce congestion-based cost functions to help agents avoid congestion and reach Wardrop equilibria. Finally, we present a Frank-Wolfe-based algorithm combined with shortest path algorithms such as Dijkstra's and A* algorithms and matching algorithms such as the Hungarian (Kuhn-Munkres) algorithm to find the optimal solution while considering congestion in the system. Furthermore, we extend balanced assignments to unbalanced assignments in our simulation. The results demonstrate that the proposed optimization problem formulation and algorithm effectively provide optimal matching and routing solutions with congestion avoidance.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ho, Kelly
Advisor dc:contributor.advisor
  • Ratliff, Lillian J.

Subjects

dc:subject × 2

Rights

dc:rights
Statement dc:rights
  • none
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1773/51160

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ho, Kelly. Bipartite Matching and Routing with Congestion Costs: A convex approach to robot task assignment and the multi-agent pathfinding problem. 2024. http://hdl.handle.net/1773/51160