CSE Doctoral Student Seminar: Khoi Hoang and Christabel Wayllace

Feb 16, 2018
12:30 p.m.
2 p.m.
Lopata Hall, Room 101

"Infinite-Horizon Proactive Dynamic DCOPs"

Khoi Hoang
Adviser: William Yeoh

The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs) to capture the inherent dynamism present in many coordination problems. The PD-DCOP formulation is a finite-horizon model that assumes a finite horizon is known a priori. It ignores changes to the problem after the horizon and is thus not guaranteed to find optimal solutions for infinite-horizon problems, which often occur in the real world.

In this talk, I’ll present the Infinite-Horizon PD-DCOP (IPD-DCOP) model, which extends PD-DCOPs to handle infinite horizons. IPD-DCOP exploits the convergence properties of Markov chains to determine the optimal solution to the problem after it has converged. I’ll also present three distributed greedy algorithms to solve IPD-DCOPs and evaluate both proactive and reactive algorithms to determine the tradeoffs between the two classes. Our evaluation is the first in this important direction.

"Stochastic Goal Recognition Design (S-GRD)"

Christabel Wayllace
Adviser: William Yeoh

Goal recognition is the problem of identifying the goal of an agent through the observation of its actions. In 2014 researchers introduced an formulated a new related problem called Goal Recognition Design (GRD) which involves identifying the best ways to design or re-design the environment that agents operate in with the objective to facilitate goal recognition.

In this talk I will present the GRD model and its relevance, and will introduce the Stochastic GRD (S-GRD) problem, which is an extension that assumes stochasticity in the outcome of agent actions. One common metric used to asses GRD problems and its solution is the worst-case distinctiveness (wcd), which represents the maximum number of actions that need to be observed before the agent reveals its goal; in the case of S-GRD problems, we extended the definition of the wcd to take stochasticity into account and proposed a new metric called expected-case distinctiveness (ecd), that weighs the possible goals based on their likelihood of being the true goal. The ecd can help to improve the model in cases where wcd cannot and can also be used to trade off different solutions provided by the wcd metric.