The Experts below are selected from a list of 3426 Experts worldwide ranked by ideXlab platform

Ferdinando Fioretto - One of the best experts on this subject based on the ideXlab platform.

  • Exploiting the Structure of Distributed constraint optimization problems (Doctoral Consortium)
    2020
    Co-Authors: Ferdinando Fioretto
    Abstract:

    In the proposed thesis, we study Distributed constraint optimization problems (DCOPs), which are problems where several agents coordinate with each other to optimize a global cost function. The use of DCOPs has gained momentum, due to their capability of addressing complex and naturally distributed problems. However, the adoption of DCOP on large problems faces two main limitations: (1) Modeling limitations, as current resolution methods detach the model from the resolution process, assuming that each agent controls a single variable of the problem; and (2) Solving capabilities, as the inability of current approaches to capitalize on the presence of structural information which may allow incoherent/unnecessary data to reticulate among the agents as well as to exploit structure of the agent’s local problems. The purpose of the proposed dissertation is to address such limitations, studying how to adapt and integrate insights gained from centralized solving techniques in order to enhance DCOP performance and scalability, enabling their use for the resolution of real-world complex problems. To do so, we hypothesize that one can exploit the DCOP structure in both problem modeling and problem resolution phases.

  • solving multiagent constraint optimization problems on the constraint composite graph
    Pacific Rim International Conference on Multi-Agents, 2018
    Co-Authors: Ferdinando Fioretto, Hong Xu, Sven Koenig, T Satish K Kumar
    Abstract:

    We introduce the constraint Composite Graph (CCG) for Distributed constraint optimization problems (DCOPs), a popular paradigm used for the description and resolution of cooperative multi-agent problems. The CCG is a novel graphical representation of DCOPs on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this representation, agents are able to reduce the size of the problem. We propose a novel variant of Max-Sum—a popular DCOP incomplete algorithm—called CCG-Max-Sum, which is applied to CCGs, and demonstrate its efficiency and effectiveness on DCOP benchmarks based on several network topologies.

  • PRIMA - Solving Multiagent constraint optimization problems on the constraint Composite Graph
    Lecture Notes in Computer Science, 2018
    Co-Authors: Ferdinando Fioretto, Hong Xu, Sven Koenig, T. K. Satish Kumar
    Abstract:

    We introduce the constraint Composite Graph (CCG) for Distributed constraint optimization problems (DCOPs), a popular paradigm used for the description and resolution of cooperative multi-agent problems. The CCG is a novel graphical representation of DCOPs on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this representation, agents are able to reduce the size of the problem. We propose a novel variant of Max-Sum—a popular DCOP incomplete algorithm—called CCG-Max-Sum, which is applied to CCGs, and demonstrate its efficiency and effectiveness on DCOP benchmarks based on several network topologies.

  • ai buzzwords explained distributed constraint optimization problems
    AI Matters archive, 2018
    Co-Authors: Ferdinando Fioretto, William Yeoh
    Abstract:

    The power network is the largest operating machine on earth, generating more than US$400bn a year1 keeping the lights on for our homes, offices, and factories. A significant concern in power networks is for the energy providers to be able to generate enough power to supply the demands at any point in time. Short terms demand peaks are however hard to predict and, thus, in the modern smart electricity grid, the energy providers can exploit the demand-side flexibility of the consumers to reduce the peaks in load demand.

  • exploiting gpus in solving distributed constraint optimization problems with dynamic programming
    Principles and Practice of Constraint Programming, 2015
    Co-Authors: Ferdinando Fioretto, Tiep Le, Enrico Pontelli, William Yeoh
    Abstract:

    This paper proposes the design and implementation of a dynamic programming based algorithm for (distributed) constraint optimization, which exploits modern massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs). The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The experimental analysis, performed on unstructured and structured graphs, shows the advantages of employing GPUs, resulting in enhanced performances and scalability. This research is partially supported by the National Science Foundation under grant number HRD-1345232. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, or the U.S. government.

Enrico Pontelli - One of the best experts on this subject based on the ideXlab platform.

  • ASP-DPOP: Solving Distributed constraint optimization problems with Logic Programming (Extended Abstract)
    2020
    Co-Authors: Tiep Le, Enrico Pontelli, William Yeoh
    Abstract:

    Researchers have used Distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. However, existing DCOP algorithms have focused almost exclusively on imperative programming techniques. This paper explores a new direction, which is to develop algorithms that use declarative programming, specically logic programming, techniques.

  • Solving distributed constraint optimization problems using logic programming
    Theory and Practice of Logic Programming, 2017
    Co-Authors: Tiep Le, Enrico Pontelli, William Yeoh
    Abstract:

    AbstractThis paper explores the use ofAnswer Set Programming (ASP)in solvingDistributed constraint optimization problems (DCOPs). The paper provides the following novel contributions: (1) it shows how one can formulate DCOPs as logic programs; (2) it introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (3) it experimentally shows that ASP-DPOP can be up to two orders of magnitude faster than DPOP (its imperative programming counterpart) as well as solve some problems that DPOP fails to solve, due to memory limitations; and (4) it demonstrates the applicability of ASP in a wide array of multi-agent problems currently modeled as DCOPs.

  • solving distributed constraint optimization problems using logic programming
    arXiv: Multiagent Systems, 2017
    Co-Authors: Tiep Le, Enrico Pontelli, William Yeoh
    Abstract:

    This paper explores the use of Answer Set Programming (ASP) in solving Distributed constraint optimization problems (DCOPs). The paper provides the following novel contributions: (1) It shows how one can formulate DCOPs as logic programs; (2) It introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (3) It experimentally shows that ASP-DPOP can be up to two orders of magnitude faster than DPOP (its imperative programming counterpart) as well as solve some problems that DPOP fails to solve, due to memory limitations; and (4) It demonstrates the applicability of ASP in a wide array of multi-agent problems currently modeled as DCOPs. Under consideration in Theory and Practice of Logic Programming (TPLP).

  • exploiting gpus in solving distributed constraint optimization problems with dynamic programming
    Principles and Practice of Constraint Programming, 2015
    Co-Authors: Ferdinando Fioretto, Tiep Le, Enrico Pontelli, William Yeoh
    Abstract:

    This paper proposes the design and implementation of a dynamic programming based algorithm for (distributed) constraint optimization, which exploits modern massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs). The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The experimental analysis, performed on unstructured and structured graphs, shows the advantages of employing GPUs, resulting in enhanced performances and scalability. This research is partially supported by the National Science Foundation under grant number HRD-1345232. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, or the U.S. government.

  • large neighborhood search with quality guarantees for distributed constraint optimization problems
    Adaptive Agents and Multi-Agents Systems, 2015
    Co-Authors: Ferdinando Fioretto, Agostino Dovier, Florence Campeotto, Enrico Pontelli, William Yeoh
    Abstract:

    This paper proposes Distributed Large Neighborhood Search (D-LNS), an incomplete DCOP algorithm that builds on the strengths of centralized LNS. D-LNS: (i) is anytime; (ii) provides guarantees on solution quality (upper and lower bounds); and (iii) can learn online the best neighborhood to explore. Experimental results show that D-LNS outperforms other incomplete DCOP algorithms in random and scale-free network instances.

Thomas Schiex - One of the best experts on this subject based on the ideXlab platform.

  • bounding the optimum of constraint optimization problems
    Principles and Practice of Constraint Programming, 1997
    Co-Authors: Simon De Givry, Gerard Verfaillie, Thomas Schiex
    Abstract:

    Solving constraint optimization problems is computationally so expensive that it is often impossible to provide a guaranteed optimal solution, either when the problem is too large, or when time is bounded. In these cases, local search algorithms usually provide good solutions. However, and even if an optimality proof is unreachable, it is often desirable to have some guarantee on the quality of the solution found, in order to decide if it is worthwile to spend more time on the problem. This paper is dedicated to the production of intervals, that bound as precisely as possible the optimum of Valued constraint Satisfaction problems (VCSP). Such intervals provide an upper bound on the distance of the best available solution to the optimum i.e., on the quality of the optimization performed. Experimental results on random VCSPs and real problems are given.

  • russian doll search for solving constraint optimization problems
    National Conference on Artificial Intelligence, 1996
    Co-Authors: Gerard Verfaillie, Michel Lemaitre, Thomas Schiex
    Abstract:

    If the constraint Satisfaction framework has been extended to deal with constraint optimization problems, it appears that optimization is far more complex than satisfaction. One of the causes of the inefficiency of complete tree search methods, like Depth First Branch and Bound, lies in the poor quality of the lower bound on the global valuation of a partial assignment, even when using Forward Checking techniques. In this paper, we introduce the Russian Doll Search algorithm which replaces one search by n successive searches on nested subproblems (n being the number of problem variables), records the results of each search and uses them later, when solving larger subproblems, in order to improve the lower bound on the global valuation of any partial assignment. On small random problems and on large real scheduling problems, this algorithm yields surprisingly good results, which greatly improve as the problems get more constrained and the bandwidth of the used variable ordering diminishes.

  • AAAI/IAAI, Vol. 1 - Russian doll search for solving constraint optimization problems
    1996
    Co-Authors: Gerard Verfaillie, Michel Lemaitre, Thomas Schiex
    Abstract:

    If the constraint Satisfaction framework has been extended to deal with constraint optimization problems, it appears that optimization is far more complex than satisfaction. One of the causes of the inefficiency of complete tree search methods, like Depth First Branch and Bound, lies in the poor quality of the lower bound on the global valuation of a partial assignment, even when using Forward Checking techniques. In this paper, we introduce the Russian Doll Search algorithm which replaces one search by n successive searches on nested subproblems (n being the number of problem variables), records the results of each search and uses them later, when solving larger subproblems, in order to improve the lower bound on the global valuation of any partial assignment. On small random problems and on large real scheduling problems, this algorithm yields surprisingly good results, which greatly improve as the problems get more constrained and the bandwidth of the used variable ordering diminishes.

William Yeoh - One of the best experts on this subject based on the ideXlab platform.

  • ASP-DPOP: Solving Distributed constraint optimization problems with Logic Programming (Extended Abstract)
    2020
    Co-Authors: Tiep Le, Enrico Pontelli, William Yeoh
    Abstract:

    Researchers have used Distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. However, existing DCOP algorithms have focused almost exclusively on imperative programming techniques. This paper explores a new direction, which is to develop algorithms that use declarative programming, specically logic programming, techniques.

  • new algorithms for functional distributed constraint optimization problems
    arXiv: Multiagent Systems, 2019
    Co-Authors: Khoi D Hoang, William Yeoh, Makoto Yokoo, Zinovi Rabinovich
    Abstract:

    The Distributed constraint optimization Problem (DCOP) formulation is a powerful tool to model multi-agent coordination problems that are distributed by nature. The formulation is suitable for problems where variables are discrete and constraint utilities are represented in tabular form. However, many real-world applications have variables that are continuous and tabular forms thus cannot accurately represent constraint utilities. To overcome this limitation, researchers have proposed the Functional DCOP (F-DCOP) model, which are DCOPs with continuous variables. But existing approaches usually come with some restrictions on the form of constraint utilities and are without quality guarantees. Therefore, in this paper, we (i) propose exact algorithms to solve a specific subclass of F-DCOPs; (ii) propose approximation methods with quality guarantees to solve general F-DCOPs; and (iii) empirically show that our algorithms outperform existing state-of-the-art F-DCOP algorithms on randomly generated instances when given the same communication limitations.

  • IJCAI - Towards Improving the Expressivity and Scalability of Distributed constraint optimization problems.
    Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018
    Co-Authors: William Yeoh
    Abstract:

    constraints have long been studied in centralized systems and have proven to be practical and efficient for modeling and solving resource allocation and scheduling problems. Slightly more than a decade ago, researchers proposed the distributed constraint optimization problem (DCOP) formulation, which is well suited for modeling distributed multi-agent coordination problems. In this paper, we highlight some of our recent contributions that are aiming towards improved expressivity of the DCOP model as well as improved scalability of the accompanying algorithms.

  • ai buzzwords explained distributed constraint optimization problems
    AI Matters archive, 2018
    Co-Authors: Ferdinando Fioretto, William Yeoh
    Abstract:

    The power network is the largest operating machine on earth, generating more than US$400bn a year1 keeping the lights on for our homes, offices, and factories. A significant concern in power networks is for the energy providers to be able to generate enough power to supply the demands at any point in time. Short terms demand peaks are however hard to predict and, thus, in the modern smart electricity grid, the energy providers can exploit the demand-side flexibility of the consumers to reduce the peaks in load demand.

  • Solving distributed constraint optimization problems using logic programming
    Theory and Practice of Logic Programming, 2017
    Co-Authors: Tiep Le, Enrico Pontelli, William Yeoh
    Abstract:

    AbstractThis paper explores the use ofAnswer Set Programming (ASP)in solvingDistributed constraint optimization problems (DCOPs). The paper provides the following novel contributions: (1) it shows how one can formulate DCOPs as logic programs; (2) it introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (3) it experimentally shows that ASP-DPOP can be up to two orders of magnitude faster than DPOP (its imperative programming counterpart) as well as solve some problems that DPOP fails to solve, due to memory limitations; and (4) it demonstrates the applicability of ASP in a wide array of multi-agent problems currently modeled as DCOPs.

Boi Faltings - One of the best experts on this subject based on the ideXlab platform.

  • duct an upper confidence bound approach to distributed constraint optimization problems
    ACM Transactions on Intelligent Systems and Technology, 2017
    Co-Authors: Brammert Ottens, Christos Dimitrakakis, Boi Faltings
    Abstract:

    We propose a distributed upper confidence bound approach, DUCT, for solving distributed constraint optimization problems. We compare four variants of this approach with a baseline random sampling algorithm, as well as other complete and incomplete algorithms for DCOPs. Under general assumptions, we theoretically show that the solution found by DUCT after T steps is approximately T−1-close to the optimal. Experimentally, we show that DUCT matches the optimal solution found by the well-known DPOP and O-DPOP algorithms on moderate-size problems, while always requiring less agent communication. For larger problems, where DPOP fails, we show that DUCT produces significantly better solutions than local, incomplete algorithms. Overall, we believe that DUCT is a practical, scalable algorithm for complex DCOPs.

  • duct an upper confidence bound approach to distributed constraint optimization problems
    National Conference on Artificial Intelligence, 2012
    Co-Authors: Brammert Ottens, Christos Dimitrakakis, Boi Faltings
    Abstract:

    The Upper Confidence Bounds (UCB) algorithm is a well-known near-optimal strategy for the stochastic multiarmed bandit problem. Its extensions to trees, such as the Upper Confidence Tree (UCT) algorithm, have resulted in good solutions to the problem of Go. This paper introduces DUCT, a distributed algorithm inspired by UCT, for solving Distributed constraint optimization problems (DCOP). Bounds on the solution quality are provided, and experiments show that, compared to existing DCOP approaches, DUCT is able to solve very large problems much more efficiently, or to find significantly higher quality solutions.

  • AAAI - DUCT: an upper confidence bound approach to distributed constraint optimization problems
    2012
    Co-Authors: Brammert Ottens, Christos Dimitrakakis, Boi Faltings
    Abstract:

    The Upper Confidence Bounds (UCB) algorithm is a well-known near-optimal strategy for the stochastic multiarmed bandit problem. Its extensions to trees, such as the Upper Confidence Tree (UCT) algorithm, have resulted in good solutions to the problem of Go. This paper introduces DUCT, a distributed algorithm inspired by UCT, for solving Distributed constraint optimization problems (DCOP). Bounds on the solution quality are provided, and experiments show that, compared to existing DCOP approaches, DUCT is able to solve very large problems much more efficiently, or to find significantly higher quality solutions.

  • DUCT: An Upper Confidence Bound Approach to Distributed constraint optimization problems.
    Aaai, 2012
    Co-Authors: Brammert Ottens, Christos Dimitrakakis, Boi Faltings
    Abstract:

    The Upper Confidence Bounds (UCB) algorithm is a well-known near-optimal strategy for the stochastic multi-armed bandit problem. Its extensions to trees, such as the Upper Confidence Tree (UCT) algorithm, have resulted in good solutions to the problem of Go. This paper introduces DUCT, a distributed algorithm inspired by UCT, for solving Distributed constraint optimization problems (DCOP). Bounds on the solution quality are provided, and experiments show that, compared to existing DCOP approaches, DUCT is able to solve very large problems much more efficiently, or to find significantly higher quality solutions. Copyright © 2012, Association for the Advancement of Artificial Intelligence. All rights reserved.

  • H-DPOP : Using Hard constraints for Search Space Pruning in DCOP
    Journal of the ACM, 2008
    Co-Authors: Akshat Kumar, Adrian Petcu, Boi Faltings
    Abstract:

    In distributed constraint optimization problems, dynamic programming methods have been recently proposed (eg DPOP). In dynamic programming many valuations are grouped together in fewer messages, which produce much less networking