The Experts below are selected from a list of 83244 Experts worldwide ranked by ideXlab platform
Makoto Yokoo - One of the best experts on this subject based on the ideXlab platform.
-
new algorithms for functional distributed Constraint Optimization problems
arXiv: Multiagent Systems, 2019Co-Authors: Khoi D Hoang, William Yeoh, Makoto Yokoo, Zinovi RabinovichAbstract: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.
-
leximin asymmetric multiple objective distributed Constraint Optimization problem
Computational Intelligence, 2018Co-Authors: Toshihiro Matsui, Marius Călin Silaghi, Katsutoshi Hirayama, Hiroshi Matsuo, Makoto YokooAbstract:The Distributed Constraint Optimization Problem (DCOP) lies at the foundations of multiagent cooperation. With DCOPs, the Optimization in distributed resource allocation problems is formalized using Constraint Optimization problems. The solvers for the problem are designed based on decentralized cooperative algorithms that are performed by multiple agents. In a conventional DCOP, a single objective is considered. The Multiple Objective Distributed Constraint Optimization Problem (MODCOP) is an extension of the DCOP framework, where agents cooperatively have to optimize simultaneously multiple objective functions. In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. However, such models do not capture the interests of each agent. On the other hand, in several practical problems, the share of each agent is important. Such shares are modeled as preference values of agents. This class of problems can be defined using the MODCOP on the preferences of agents. In particular, we define Optimization problems based on leximin ordering and Asymmetric DCOPs (Leximin AMODCOPs). The leximin defines an ordering among vectors of objective values. In addition, Asymmetric DCOPs capture the preferences of agents. Because the Optimization based on the leximin ordering improves the equality among the satisfied preferences of the agents, this class of problems is important. We propose several solution methods for Leximin AMODCOPs generalizing traditional operators into the operators on sorted objective vectors and leximin. The solution methods applied to the Leximin AMODCOPs are based on pseudo trees. Also, the investigated search methods employ the concept of boundaries of the sorted vectors.
-
CP - Interactive algorithm for multi-objective Constraint Optimization
Lecture Notes in Computer Science, 2012Co-Authors: Tenda Okimoto, Toshihiro Matsui, Katsutoshi Hirayama, Yongjoon Joe, Atsushi Iwasaki, Makoto YokooAbstract:Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Constraint Optimization Problem (MO-COP) is the extension of a mono-objective Constraint Optimization Problem (COP). In a MO-COP, it is required to provide the most preferred solution for a user among many optimal solutions. In this paper, we develop a novel Interactive Algorithm for MO-COP (MO-IA). The characteristics of this algorithm are as follows: (i) it can guarantee to find a Pareto solution, (ii) it narrows a region, in which Pareto front may exist, gradually, (iii) it is based on a pseudo-tree, which is a widely used graph structure in COP algorithms, and (iv) the complexity of this algorithm is determined by the induced width of problem instances. In the evaluations, we use an existing model for representing a utility function, and show empirically the effectiveness of our algorithm. Furthermore, we propose an extension of MO-IA, which can provide the more detailed information for Pareto front.
-
AAMAS - A quantified distributed Constraint Optimization problem
2010Co-Authors: Toshihiro Matsui, Makoto Yokoo, Hirohsi Matsuo, Marius Călin Silaghi, Katsutoshi Hirayama, Satomi BabaAbstract:In this paper, we propose a Quantifie Distributed Constraint Optimization problem (QDCOP) that extends the framework of Distributed Constraint Optimization problems (DCOPs). DCOPs have been studied as a fundamental model of multi-agent cooperation. In traditional DCOPs, all agents cooperate to optimize the sum of their cost functions. However, in practical systems some agents may desire to select the value of their variables without cooperation. In special cases, such agents may take the values with the worst impact on the quality of the result reachable by the Optimization process. We apply existential/universal quantifier to distinct uncooperative variables. A universally quantifie variable is left unassigned by the Optimization as the result has to hold when it takes any value from its domain, while an existentially quantifie variable takes exactly one of its values for each context. Similar classes of problems have recently been studied as (Distributed) Quantifie Constraint Problems, where the variables of the CSP have quantifiers All Constraints should be satisfie independently of the value taken by universal variables. We propose a QDCOP that applies the concept of game tree search to DCOP. If the original problem is a minimization problem, agents that own universally quantifie variables may intend to maximize the cost value in the worst case. Other agents normally intend to optimize the minimizing problems. Therefore, only the bounds, especially the upper bounds, of the optimal value are guaranteed. The purpose of the new class of problems is to compute such bounds, as well as to compute sub-optimal solutions. For the QDCOP, we also propose several methods that are based on min-max/alpha-beta and ADOPT algorithms.
-
A Resource Constrained Distributed Constraint Optimization Method using Resource Constraint Free Pseudo-tree
Transactions of the Japanese Society for Artificial Intelligence, 2009Co-Authors: Toshihiro Matsui, Makoto Yokoo, Marius Călin Silaghi, Katsutoshi Hirayama, Hiroshi MatsuoAbstract:Cooperative problem solving with shared resources is important in practical multi-agent systems. Resource Constraints are necessary to handle practical problems such as distributed task scheduling with limited resource availability. As a fundamental formalism for multi-agent cooperation, the Distributed Constraint Optimization Problem (DCOP) has been investigated. With DCOPs, the agent states and the relationships between agents are formalized into a Constraint Optimization problem. However, in the original DCOP framework, Constraints for resources that are consumed by teams of agents are not well supported. A framework called Resource Constrained Distributed Constraint Optimization Problem (RCDCOP) has recently been proposed. In RCDCOPs, a limit on resource usage is represented as an n-ary Constraint. Previous research addressing RCDCOPs employ a pseudo-tree based solver. The pseudo-tree is an important graph structure for Constraint networks. A pseudo-tree implies a partial ordering of variables. However, n-ary constrained variables, which are placed on a single path of the pseudo-tree, decrease efficiency of the solver. We propose another method using (i) a pseudo-tree that is generated ignoring resource Constraints and (ii) virtual variables representing the usage of resources. However the virtual variables increase search space. To improve pruning efficiency of search, (iii) we apply a set of upper/lower bounds that are inferred from resource Constraints. The efficiency of the proposed method is evaluated by experiment.
William Yeoh - One of the best experts on this subject based on the ideXlab platform.
-
new algorithms for functional distributed Constraint Optimization problems
arXiv: Multiagent Systems, 2019Co-Authors: Khoi D Hoang, William Yeoh, Makoto Yokoo, Zinovi RabinovichAbstract: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, 2018Co-Authors: William YeohAbstract: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.
-
Solving distributed Constraint Optimization problems using logic programming
Theory and Practice of Logic Programming, 2017Co-Authors: Tiep Le, Enrico Pontelli, William YeohAbstract: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, 2017Co-Authors: Tiep Le, Enrico Pontelli, William YeohAbstract: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).
-
distributed Constraint Optimization problems and applications a survey
arXiv: Artificial Intelligence, 2016Co-Authors: Ferdinando Fioretto, Enrico Pontelli, William YeohAbstract:The field of Multi-Agent System (MAS) is an active area of research within Artificial Intelligence, with an increasingly important impact in industrial and other real-world applications. Within a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent agent architectures to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have enabled them to support MAS in complex, real-time, and uncertain environments. This survey aims at providing an overview of the DCOP model, giving a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions, and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.
Toshihiro Matsui - One of the best experts on this subject based on the ideXlab platform.
-
PAAMS - Decentralized Constraint Optimization in Composite Observation Task Allocation to Mobile Sensor Agents
Advances in Practical Applications of Agents Multi-Agent Systems and Trustworthiness. The PAAMS Collection, 2020Co-Authors: Toshihiro MatsuiAbstract:Cooperative severance and observation by autonomous multiple mobile sensors have been studied for wide area monitoring, disaster response, and exploration in unsafe zones. In practical situations, sensor agents might be required to perform various composite tasks. To integrate them, the general representation of problems and decentralized solution methods for different requirements are necessary. The distributed Constraint Optimization problem has been studied as a general and fundamental combinational Optimization problem in multiagent systems. Although several studies have applied this approach to sensor networks and teams of mobile sensors, opportunities also exit to apply it to manage composite tasks and utilize decentralized protocols in the subtasks in several layers of observation systems. As a case study, we address a cooperative observation system consisting of mobile sensor agents that temporally observe unsafe zones on a floor or a field with obstacles, where the basis of the tasks is the division of observation areas for the agents. We also allocate several tasks with high priority to several agents. We applied a decentralized Constraint Optimization method to the cooperation for both task allocation and the division of an observation area and experimentally verified our proposed approach in a simulated environment.
-
leximin asymmetric multiple objective distributed Constraint Optimization problem
Computational Intelligence, 2018Co-Authors: Toshihiro Matsui, Marius Călin Silaghi, Katsutoshi Hirayama, Hiroshi Matsuo, Makoto YokooAbstract:The Distributed Constraint Optimization Problem (DCOP) lies at the foundations of multiagent cooperation. With DCOPs, the Optimization in distributed resource allocation problems is formalized using Constraint Optimization problems. The solvers for the problem are designed based on decentralized cooperative algorithms that are performed by multiple agents. In a conventional DCOP, a single objective is considered. The Multiple Objective Distributed Constraint Optimization Problem (MODCOP) is an extension of the DCOP framework, where agents cooperatively have to optimize simultaneously multiple objective functions. In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. However, such models do not capture the interests of each agent. On the other hand, in several practical problems, the share of each agent is important. Such shares are modeled as preference values of agents. This class of problems can be defined using the MODCOP on the preferences of agents. In particular, we define Optimization problems based on leximin ordering and Asymmetric DCOPs (Leximin AMODCOPs). The leximin defines an ordering among vectors of objective values. In addition, Asymmetric DCOPs capture the preferences of agents. Because the Optimization based on the leximin ordering improves the equality among the satisfied preferences of the agents, this class of problems is important. We propose several solution methods for Leximin AMODCOPs generalizing traditional operators into the operators on sorted objective vectors and leximin. The solution methods applied to the Leximin AMODCOPs are based on pseudo trees. Also, the investigated search methods employ the concept of boundaries of the sorted vectors.
-
CP - Interactive algorithm for multi-objective Constraint Optimization
Lecture Notes in Computer Science, 2012Co-Authors: Tenda Okimoto, Toshihiro Matsui, Katsutoshi Hirayama, Yongjoon Joe, Atsushi Iwasaki, Makoto YokooAbstract:Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Constraint Optimization Problem (MO-COP) is the extension of a mono-objective Constraint Optimization Problem (COP). In a MO-COP, it is required to provide the most preferred solution for a user among many optimal solutions. In this paper, we develop a novel Interactive Algorithm for MO-COP (MO-IA). The characteristics of this algorithm are as follows: (i) it can guarantee to find a Pareto solution, (ii) it narrows a region, in which Pareto front may exist, gradually, (iii) it is based on a pseudo-tree, which is a widely used graph structure in COP algorithms, and (iv) the complexity of this algorithm is determined by the induced width of problem instances. In the evaluations, we use an existing model for representing a utility function, and show empirically the effectiveness of our algorithm. Furthermore, we propose an extension of MO-IA, which can provide the more detailed information for Pareto front.
-
AAMAS - A quantified distributed Constraint Optimization problem
2010Co-Authors: Toshihiro Matsui, Makoto Yokoo, Hirohsi Matsuo, Marius Călin Silaghi, Katsutoshi Hirayama, Satomi BabaAbstract:In this paper, we propose a Quantifie Distributed Constraint Optimization problem (QDCOP) that extends the framework of Distributed Constraint Optimization problems (DCOPs). DCOPs have been studied as a fundamental model of multi-agent cooperation. In traditional DCOPs, all agents cooperate to optimize the sum of their cost functions. However, in practical systems some agents may desire to select the value of their variables without cooperation. In special cases, such agents may take the values with the worst impact on the quality of the result reachable by the Optimization process. We apply existential/universal quantifier to distinct uncooperative variables. A universally quantifie variable is left unassigned by the Optimization as the result has to hold when it takes any value from its domain, while an existentially quantifie variable takes exactly one of its values for each context. Similar classes of problems have recently been studied as (Distributed) Quantifie Constraint Problems, where the variables of the CSP have quantifiers All Constraints should be satisfie independently of the value taken by universal variables. We propose a QDCOP that applies the concept of game tree search to DCOP. If the original problem is a minimization problem, agents that own universally quantifie variables may intend to maximize the cost value in the worst case. Other agents normally intend to optimize the minimizing problems. Therefore, only the bounds, especially the upper bounds, of the optimal value are guaranteed. The purpose of the new class of problems is to compute such bounds, as well as to compute sub-optimal solutions. For the QDCOP, we also propose several methods that are based on min-max/alpha-beta and ADOPT algorithms.
-
A Resource Constrained Distributed Constraint Optimization Method using Resource Constraint Free Pseudo-tree
Transactions of the Japanese Society for Artificial Intelligence, 2009Co-Authors: Toshihiro Matsui, Makoto Yokoo, Marius Călin Silaghi, Katsutoshi Hirayama, Hiroshi MatsuoAbstract:Cooperative problem solving with shared resources is important in practical multi-agent systems. Resource Constraints are necessary to handle practical problems such as distributed task scheduling with limited resource availability. As a fundamental formalism for multi-agent cooperation, the Distributed Constraint Optimization Problem (DCOP) has been investigated. With DCOPs, the agent states and the relationships between agents are formalized into a Constraint Optimization problem. However, in the original DCOP framework, Constraints for resources that are consumed by teams of agents are not well supported. A framework called Resource Constrained Distributed Constraint Optimization Problem (RCDCOP) has recently been proposed. In RCDCOPs, a limit on resource usage is represented as an n-ary Constraint. Previous research addressing RCDCOPs employ a pseudo-tree based solver. The pseudo-tree is an important graph structure for Constraint networks. A pseudo-tree implies a partial ordering of variables. However, n-ary constrained variables, which are placed on a single path of the pseudo-tree, decrease efficiency of the solver. We propose another method using (i) a pseudo-tree that is generated ignoring resource Constraints and (ii) virtual variables representing the usage of resources. However the virtual variables increase search space. To improve pruning efficiency of search, (iii) we apply a set of upper/lower bounds that are inferred from resource Constraints. The efficiency of the proposed method is evaluated by experiment.
Enrico Pontelli - One of the best experts on this subject based on the ideXlab platform.
-
Solving distributed Constraint Optimization problems using logic programming
Theory and Practice of Logic Programming, 2017Co-Authors: Tiep Le, Enrico Pontelli, William YeohAbstract: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, 2017Co-Authors: Tiep Le, Enrico Pontelli, William YeohAbstract: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).
-
distributed Constraint Optimization problems and applications a survey
arXiv: Artificial Intelligence, 2016Co-Authors: Ferdinando Fioretto, Enrico Pontelli, William YeohAbstract:The field of Multi-Agent System (MAS) is an active area of research within Artificial Intelligence, with an increasingly important impact in industrial and other real-world applications. Within a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent agent architectures to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have enabled them to support MAS in complex, real-time, and uncertain environments. This survey aims at providing an overview of the DCOP model, giving a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions, and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.
-
AAAI - Solving distributed Constraint Optimization problems using logic programming
2015Co-Authors: Tiep Le, Enrico Pontelli, William YeohAbstract:This paper explores the use of answer set programming (ASP) in solving distributed Constraint Optimization problems (DCOPs). It makes the following contributions: (i) It shows how one can formulate DCOPs as logic programs; (ii) It introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (iii) 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 (iv) It demonstrates the applicability of ASP in the wide array of multi-agent problems currently modeled as DCOPs.
-
Logic and Constraint Logic Programming for Distributed Constraint Optimization.
arXiv: Multiagent Systems, 2014Co-Authors: Enrico Pontelli, Tran Cao Son, William YeohAbstract:The field of Distributed Constraint Optimization Problems (DCOPs) has gained momentum, thanks to its suitability in capturing complex problems (e.g., multi-agent coordination and resource allocation problems) that are naturally distributed and cannot be realistically addressed in a centralized manner. The state of the art in solving DCOPs relies on the use of ad-hoc infrastructures and ad-hoc Constraint solving procedures. This paper investigates an infrastructure for solving DCOPs that is completely built on logic programming technologies. In particular, the paper explores the use of a general Constraint solver (a Constraint logic programming system in this context) to handle the agent-level Constraint solving. The preliminary experiments show that logic programming provides benefits over a state-of-the-art DCOP system, in terms of performance and scalability, opening the doors to the use of more advanced technology (e.g., search strategies and complex Constraints) for solving DCOPs.
Boi Faltings - One of the best experts on this subject based on the ideXlab platform.
-
distributed Constraint Optimization with structured resource Constraints
Adaptive Agents and Multi-Agents Systems, 2009Co-Authors: Akshat Kumar, Boi Faltings, Adrian PetcuAbstract:Distributed Constraint Optimization (DCOP) provides a framework for coordinated decision making by a team of agents. Often, during the decision making, capacity Constraints on agents' resource consumption must be taken into account. To address such scenarios, an extension of DCOP- Resource Constrained DCOP- has been proposed. However, certain type of resources have an additional structure associated with them and exploiting it can result in more efficient algorithms than possible with a general framework. An example of these are distribution networks, where the flow of a commodity from sources to sinks is limited by the flow capacity of edges. We present a new model of structured resource Constraints that exploits the acyclicity and the flow conservation property of distribution networks. We show how this model can be used in efficient algorithms for finding the optimal flow configuration in distribution networks, an essential problem in managing power distribution networks. Experiments demonstrate the efficiency and scalability of our approach on publicly available benchmarks and compare favorably against a specialized solver for this task. Our results extend significantly the effectiveness of distributed Constraint Optimization for practical multi-agent settings.
-
AAMAS (2) - Distributed Constraint Optimization with structured resource Constraints
2009Co-Authors: Akshat Kumar, Boi Faltings, Adrian PetcuAbstract:Distributed Constraint Optimization (DCOP) provides a framework for coordinated decision making by a team of agents. Often, during the decision making, capacity Constraints on agents' resource consumption must be taken into account. To address such scenarios, an extension of DCOP- Resource Constrained DCOP- has been proposed. However, certain type of resources have an additional structure associated with them and exploiting it can result in more efficient algorithms than possible with a general framework. An example of these are distribution networks, where the flow of a commodity from sources to sinks is limited by the flow capacity of edges. We present a new model of structured resource Constraints that exploits the acyclicity and the flow conservation property of distribution networks. We show how this model can be used in efficient algorithms for finding the optimal flow configuration in distribution networks, an essential problem in managing power distribution networks. Experiments demonstrate the efficiency and scalability of our approach on publicly available benchmarks and compare favorably against a specialized solver for this task. Our results extend significantly the effectiveness of distributed Constraint Optimization for practical multi-agent settings.
-
Distributed Constraint Optimization Applications in Power Networks
2008Co-Authors: Adrian Petcu, Boi FaltingsAbstract:In recent years the electricity sector has undergone a number of changes that all point in the direction of liberalization and decentralization of control. However, a number of technological challenges have to be addressed before the desired degree of de- centralization is obtained. Currently, most of the decisions about the operation of a power system are still made in control centers in a centralized fashion. We present in this paper two applications in this context, and show how they benefit from the Distributed Artificial Intelligence techniques we have developed. The first application is a distributed scheduling application, where several power plant operators schedule preventive maintenance on their generation units in a distributed fashion. This method does not require the centralization of private data of the power plant operators (like available capacities, internal maintenance schedules, maintenance and operation costs, etc). Fur- thermore, the method guarantees globally optimal schedules while observing the power generation demand at all times. The second application is the distributed (re)configuration of power networks, where one seeks to optimally configure the network to e.g. minimize line losses, or restore power to a maximal number of customers after a line failure. The problems are modeled as distributed Constraint Optimization problems (DCOP). DCOP is a powerful paradigm for solving nu- merous tasks in distributed AI, like planning, scheduling, resource allocation. The algorithm that we use is a complete method for distributed Constraint Optimization, based on dynamic programming. It requires a linear number of messages , whose maximal size depends on a parameter of the Constraint graph, called induced width. This makes our algorithm well suited for large but loose problems. We present a number of interesting extensions of the basic method that show promise for applications in power systems well beyond the two examples we present here.
-
a scalable method for multiagent Constraint Optimization
International Joint Conference on Artificial Intelligence, 2005Co-Authors: Adrian Petcu, Boi FaltingsAbstract:We present in this paper a new, complete method for distributed Constraint Optimization, based on dynamic programming. It is a utility propagation method, inspired by the sum-product algorithm, which is correct only for tree-shaped Constraint networks. In this paper, we show how to extend that algorithm to arbitrary topologies using a pseudotree arrangement of the problem graph. Our algorithm requires a linear number of messages, whose maximal size depends on the induced width along the particular pseudotree chosen. We compare our algorithm with backtracking algorithms, and present experimental results. For some problem types we report orders of magnitude fewer messages, and the ability to deal with arbitrarily large problems. Our algorithm is formulated for Optimization problems, but can be easily applied to satisfaction problems as well.
-
A Distributed, Complete Method for Multi-Agent Constraint Optimization
2004Co-Authors: Adrian Petcu, Boi FaltingsAbstract:We present in this paper a new complete method for distributed Constraint Optimization. This is a utility-propagation method, inspired by the sum-product algorithm. The original algorithm requires fixed message sizes, linear memory, and is time-linear in the size of the problem. However, it is correct only for tree-shaped Constraint networks. In this paper, we show how to extend the algorithm to arbitrary topologies using cycle cutsets, while preserving the linear message size and memory requirements. We present some preliminary experimental results on randomly generated problems. The algorithm is formulated for Optimization problems, but can be easily applied to satisfaction problems as well.