PhD Thesis Proposal - Shao-Hung Chan

PhD Thesis Proposal - Shao-Hung Chan
 
Committee members: Sven Koenig (chair), T.K. Satish Kumar, Lars Lindemann, John Carlsson, and Daniel Harabor
 
Title: Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding
 
Time: Mar. 5th, 2:00 PM - 3:00 PM 
Location: EEB 349
 
 
Abstract:
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.
 

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 349

Audiences: Everyone Is Invited

Contact: CS Events