Doctor of Philosophy
School of Computing and Information Technology
Billiau, Graham, An equitable approach to solving distributed constraint optimization problems, Doctor of Philosophy thesis, School of Computing and Information Technology, University of Wollongong, 2015. https://ro.uow.edu.au/theses/4566
We propose a new algorithm, Support Based Distributed Optimization (SBDO). SBDO is designed specifically to address the challenges unique to distributed problems. These challenges are autonomy, equality and fault tolerance. SBDO uses an argumentation based approach to solve DCOP problems. Each agent constructs a partial solution to the problem, and attempts to convince the other agents to either extend this partial solution or modify their own partial solution so that it is consistent with this one. The resulting algorithm has the following properties: Anytime, Asynchronous, Dynamic, Fault tolerant and Sound. It can solve DCOP problems which meet the following conditions:
• The domain of each variable must be finite.
• There must be a total order over solutions.
• The quality of a solution must be monotonically non-decreasing as the solution is extended.
Next we present a general model for DCOPs, called Semiring DCOP (SDCOP). SDCOP utilizes semirings to represent utility values and read/write permissions on variables to represent the distributed nature of the problem. The resulting model is capable of representing all of the accepted problems in the constraint programming domain and several problems which have not been explored by the community.
Finally we begin extending SBDO to solve problems represented using SDCOP. We start by removing the restriction that there must be a total order over the solutions. This is achieved by allowing each agent to maintain many different partial solutions simultaneously. Future work includes extending SBDO to support problems where variables may have bounded infinite domains and problems where several agents have write access to the same variable.