University of Wollongong
Browse

An equitable approach to solving distributed constraint optimization problems

Download (945.82 kB)
thesis
posted on 2024-11-11, 22:31 authored by Graham Billiau
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.

History

Year

2015

Thesis type

  • Doctoral thesis

Faculty/School

School of Computing and Information Technology

Language

English

Disclaimer

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC