Logo: University of Southern California

Events Calendar

  • PhD Thesis Proposal - Shao-Hung Chan

    Tue, Mar 05, 2024 @ 02:00 PM - 03:00 PM

    Thomas Lord Department of Computer Science

    University Calendar

    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
    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

    Add to Google CalendarDownload ICS File for OutlookDownload iCal File

Return to Calendar