BEGIN:VCALENDAR
BEGIN:VEVENT
SUMMARY:PhD Thesis Proposal - Shao-Hung Chan
DESCRIPTION:PhD Thesis Proposal - Shao-Hung Chan\n
\n
Committee members: Sven Koenig (chair), T.K. Satish Kumar, Lars Lindemann, John Carlsson, and Daniel Harabor\n
\n
Title: Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding\n
\n
Time: Mar. 5th, 2:00 PM - 3:00 PM \n
Location: EEB 349\n
\n
\n
Abstract:\n
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents that minimize the sum of path costs. Explicit Estimation Conflict-Based Search (EECBS) is a leading two-level algorithm that solves MAPF bounded-suboptimally, i.e., within some factor w away from the minimum sum of path costs C*. It uses Focal Search to find bounded-suboptimal paths on the low level and Explicit Estimation Search (EES) to resolve collisions on the high level. To solve MAPF bounded-suboptimally, 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 bounded-suboptimal 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.\n
DTSTART:20240305T140000
LOCATION:EEB 349
URL;VALUE=URI:
DTEND:20240305T150000
END:VEVENT
END:VCALENDAR