Events Calendar

Thesis Proposal (Han Zhang)

Thesis Proposal Committee Members:
Sven Koenig (Chair)
Satish Kumar Thittamaranahalli
Lars Lindemann
Satyandra Kumar Gupta
Ariel Felner
 
Title: Speeding-up Multi-Objective Search Algorithms
 
Abstract: In the Multi-Objective Search problem, given a graph in which each edge is annotated with a cost vector, a start state, and a goal state, a typical task is to compute a Pareto frontier. State-of-the-art multi-objective search algorithms conform to the same best-first algorithmic framework. These algorithms are similar to best-first search algorithms, such as A*, but, most differently, they need to consider multiple nodes (with costs that do not dominate each other) for the same state. Due to the similarity between multi-objective and single-objective search algorithms, I hypothesize that one can speed up multi-objective search algorithms by applying insights gained from single-objective search. More specifically, I propose to speed up multi-objective search algorithms by (1) sacrificing solution optimality, (2) using preprocessing techniques, and (3) using efficient data structures for dominance checks.

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

Audiences: Everyone Is Invited

Contact: CS Events