Logo: University of Southern California

Events Calendar


  • PhD Dissertation Defense - Han Zhang

    Mon, Oct 21, 2024 @ 09:30 AM - 11:30 AM

    Thomas Lord Department of Computer Science

    University Calendar


    Title: Speeding up Multi-Objective Search Algorithms
     
    Date: Oct 21, 2024 
     
    Location: SAL- Henry Salvatori Computer Science Center 213
     
    Time: 9:30 AM - 11:30 PM
     
    Committee members: Satish Kumar, Sven Koenig, Bistra Dilkina, Satyandra Kumar Gupta, Ariel Felner
     
    Abstract: The multi-objective search problem is the problem of finding paths from a start state to a goal state in a graph where each edge is annotated with multiple costs. A typical task of multi-objective search is to find the Pareto frontier, that is, the set of all undominated paths from the start state to the goal state. This problem is important for many applications, such as transporting hazardous materials, where travel distance and risk are two costs that need to be considered. While researchers have developed various techniques over the past years for speeding up single-objective searches on large graphs, many of them have not been investigated in the context of multi-objective search. In this thesis, I hypothesize that one can speed up multi-objective search algorithms by applying insights gained from single-objective search algorithms after proper generalization. Specifically, I consider the following four classes of techniques that have been used to speed up single-objective search algorithms, namely, (1) by trading off solution quality with efficiency, (2) by anytime search, (3) by preprocessing techniques, and (4) by efficient data structures for time-consuming operations. We validate this hypothesis by introducing various new multi-objective search algorithms and speed-up techniques.

    Location: Henry Salvatori Computer Science Center (SAL) - 213

    Audiences: Everyone Is Invited

    Contact: Ellecia Williams

    Add to Google CalendarDownload ICS File for OutlookDownload iCal File

Return to Calendar