Distributed Constraint Optimization Related with Soft Arc Consistency

Abstract

Los Problemas de Optimización con Restricciones Distribuidos (DCOP) son utilizados para modelar problemas de coordinación multi-agente. Los DCOPs se definen con un número finito de agentes, variables y funciones de coste. El objetivo es encontrar una asignación de todas las variables cuyo coste global sea mínimo. Para lograrlo, los agentes que manejan las variables han de intercambiar información sobre el coste de sus asignaciones hasta encontrar la solución óptima. Varios algoritmos distribuidos se han propuesto para encontrar soluciones óptimas en DCOPs. En el caso centralizado, se han desarrollado técnicas para acelerar la resolución de problemas de optimización con restricciones. En particular, técnicas de arco consistencia blanda, como AC, FDAC y EDAC, las cuales identifican valores inconsistentes que pueden ser eliminados. El objetivo de esta tesis es incluir técnicas de arco consistencia blanda en la resolución de DCOPs. Esta combinación obtiene mejoras sustanciales en el rendimiento. Las arco consistencias blandas son conceptualmente iguales en el caso centralizado y distribuido. Sin embargo, mantenerlas en el caso distribuido requiere un enfoque diferente. En centralizado, todos los elementos del problema están disponibles para el único agente que realiza la búsqueda, mientras que en el caso distribuido los agentes solo conocen algunas partes del problema y deben intercambiar información para lograr el nivel de consistencia deseado. En este proceso, las estructuras del problema se deben modificar de tal manera que la información parcial del problema global permanezca coherente en cada agente. En esta tesis presentamos tres contribuciones para la resolución de DCOPs. En primer lugar, hemos estudiado el algoritmo de búsqueda BnB-ADOPT y hemos podido mejorarlo de manera significativa. Probamos que algunos de los mensajes enviados por BnB-ADOPT son redundantes y pueden ser eliminados sin afectar la optimalidad y completitud del algoritmo. Además, cuando se trabaja con restricciones de aridad mayor que dos, algunos problemas aparecen en este algoritmo. Proponemos una forma simple de solucionarlos obteniendo una nueva versión para el caso n-ario. También, presentamos el nuevo algoritmo ADOPT(k), el cual generaliza los algoritmos ADOPT y BnB-ADOPT. ADOPT(k) realiza una estrategia de búsqueda similar a ADOPT, a BnB-ADOPT, o a un híbrido de ambos dependiendo del parámetro k. En segundo lugar, introducimos técnicas de arco consistencia blanda en DCOPs, utilizando BnB-ADOPT+ como algoritmo de resolución. Durante la búsqueda mantenemos los niveles de consistencia AC y FDAC, con la limitación que solo se propagan borrados incondicionales, logrando importantes beneficios en la comunicación y en esfuerzo de cómputo. Mantenemos FDAC en varios órdenes de las variables obteniendo reducciones en la comunicación. Además, proponemos DAC por propagación de token, una nueva forma de propagar borrados durante la búsqueda distribuida. Experimentalmente, esta estrategia ha demostrado ser competitiva comparada con FDAC. En tercer lugar, exploramos la inclusión de restricciones globales blandas en DCOPs. Pensamos que las restricciones globales mejoran la expresividad de DCOP. Proponemos tres formas de incluir restricciones globales blandas en DCOP y extendemos el algoritmo BnB-ADOPT+ para incorporarlas. Además, exploramos el impacto de mantener arco consistencia en problemas con restricciones globales blandas. Experimentalmente, medimos la eficiencia de los algoritmos propuestos en varios conjuntos de datos comúnmente usados en la comunidad de DCOP.

Distributed Constraint Optimization Problems (DCOPs) can be used for modeling many multi-agent coordination problems. DCOPs involve a finite number of agents, variables and cost functions. The goal is to find a complete variable assignment with minimum global cost. This is achieved among several agents handling the variables and exchanging information about their cost evaluation until an optimal solution is found. Recently, researchers have proposed several distributed algorithms to optimally solve DCOPs. In the centralized case, techniques have been developed to speed up constraint optimization solving. In particular, search can be improved by enforcing soft arc consistency, which identifies inconsistent values that can be removed from the problem. Some soft consistency levels proposed are AC, FDAC and EDAC. The goal of this thesis is to include soft arc consistency techniques in DCOP resolution. We show that this combination causes substantial improvements in performance. Soft arc consistencies are conceptually equal in the centralized and distributed cases. However, maintaining soft arc consistencies in the distributed case requires a different approach. While in the centralize case all problem elements are available in the single agent performing the search, in the distributed case agents only knows some part of the problem and they must exchange information to achieve the desired consistency level. In this process, the operations that modify the problem structures should be done in such a way that partial information of the global problem remains coherent on every agent. In this thesis we present three main contributions to optimal DCOP solving. First, we have studied and experimented with the complete solving algorithm BnB-ADOPT. As result of this work, we have improved it to a large extent. We show that some of BnB-ADOPT messages are redundant and can be removed without compromising optimality and termination. Also, when dealing with cost functions of arity higher than two, some issues appear in this algorithm. We propose a simple way to overcome them obtaining a new version for the n-ary case. In addition, we present the new algorithm ADOPT($k$), which generalizes the algoritms ADOPT and BnB-ADOPT. ADOPT ($k$) can perform a search strategy either like ADOPT, like BnB-ADOPT or like a hybrid of both depending on the $k$ parameter. Second, we have introduced soft arc consistency techniques in DCOPs, taking BnB-ADOPT$^+$ as our base solving algorithm. During the search process, we enforce the soft arc consistency levels AC and FDAC, under the limitation that only unconditional deletions are propagated, obtaining important benefits in communication and computation. We enforce FDAC considering multiple orderings of the variables obtaining savings in communication. Also, we propose DAC by token passing, a new way to propagate deletions during distributed search. Experimentally, this strategy turned out to be competitive when compared to FDAC. Third, we explore the inclusion of soft global constraints in DCOPs. We believe that soft global constraints enhance DCOP expressivity. We propose three different ways to include soft global constraints in DCOPs and extend the solving algorithm BnB-ADOPT$^+$ to support them. In addition, we explore the impact of soft arc consistency maintenance in problems with soft global constrains. Experimentally, we measure the efficiency of the proposed algorithms in several benchmarks commonly used in the DCOP community.