
PhD Thesis Proposal  ShaoHung Chan
Tue, Mar 05, 2024 @ 02:00 PM  03:00 PM
Thomas Lord Department of Computer Science
University Calendar
PhD Thesis Proposal  ShaoHung Chan
Committee members: Sven Koenig (chair), T.K. Satish Kumar, Lars Lindemann, John Carlsson, and Daniel Harabor
Title: Flex Distribution for BoundedSuboptimal MultiAgent Path Finding
Time: Mar. 5th, 2:00 PM  3:00 PM
Location: EEB 349
Abstract:
MultiAgent Path Finding (MAPF) is the problem of finding collisionfree paths for multiple agents that minimize the sum of path costs. Explicit Estimation ConflictBased Search (EECBS) is a leading twolevel algorithm that solves MAPF boundedsuboptimally, i.e., within some factor w away from the minimum sum of path costs C*. It uses Focal Search to find boundedsuboptimal paths on the low level and Explicit Estimation Search (EES) to resolve collisions on the high level. To solve MAPF boundedsuboptimally, EES keeps track of a lower bound LB on C* to find paths whose sum of path costs is at most w times LB. However, the costs of many paths are often much smaller than w times their minimum path costs, meaning that the sum of path costs is much smaller than w times C*. Thus, in this proposal, we hypothesize that one can improve the efficiency of EECBS via Flex Distribution. That is, one can use the flex of the path costs (that relaxes the requirement to find boundedsuboptimal paths on the low level) to reduce the number of collisions that need to be resolved on the high level while still guaranteeing to solve MAPF bounded suboptimally. We also discuss the limitations of Flex Distribution and propose some techniques to overcome them.
Location: Hughes Aircraft Electrical Engineering Center (EEB)  349
Audiences: Everyone Is Invited
Contact: CS Events