Events Calendar

PhD Dissertation Defense - Han Zhang

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