Heuristics for Distributed Pseudo-tree Regeneration

The goal of this project is to develop a new heuristic for pseudo-tree regeneration in S-DPOP. S-DPOP is a version of DPOP which should show performance improvements when resolving problems after small changes. Examples of such problems are: tracking moving targets in sensor networks, truck-task scheduling and also matching patients and donors in kidney exchanges - a new problem for DCOP, which we investigate in this project . In this project, the DCOP-platform FRODO, developed by the artificial intelligence lab (LIA) at EPFL, will be used. Because there is no existing im- plementation of S-DPOP on FRODO, a significant part of the project consists in implementing S-DPOP on FRODO for the first time. The most important part of the project is the development and validation of a new DFS heuristic, which should maximize the amount of reuse when a problem is resolved after a minor change. Furthermore, we want to evaluate the performance of S-DPOP and the new heuristic on a real-life problem. For this, we use the kidney exchange problem, which is a problem class that has been studied in the centralized setting, but which is new to the DCOP community.