Particionamiento y resolución distribuida multivariable de problemas de satisfacción de restricciones

Abstract

Hoy en día, muchos problemas reales pueden modelarse como problemas de satisfacción de restricciones (CSPs) y se resuelven usando técnicas específicas de satisfacción de restricciones. Estos problemas pertenecen a áreas tales como Inteligencia Artificial, investigación operativa, sistemas de información, bases de datos, etc. La mayoría de estos problemas pueden modelarse de forma natural mediante CSPs. Sin embargo, algunos de estos problemas son de naturaleza distribuida, bien por motivos de seguridad, por requerimientos de privacidad, o por restricciones espaciales. Ello requiere que este tipo de problemas sean modelados como problemas de satisfacción de restricciones distribuidos (DCSPs), donde el conjunto de variables y restricciones del problema está distribuido entre un conjunto de agentes que se encargan de resolver su propio sub-problema y deben coordinarse con el resto de agentes para alcanzar una solución al problema global.

En la literatura de satisfacción de restricciones, la necesidad de manejar DCSP comenzó a tratarse a principios de los 90. No obstante, la mayoría de los investigadores que trabajan en este campo centran su atención en algoritmos en los que cada agente maneja una única variable. Estos algoritmos pueden ser transformados para que cada agente maneje múltiples variables. Sin embargo, los algoritmos resultantes no son escalables para manejar grandes sub-problemas locales debido tanto a requerimientos espaciales como a su coste computacional. Por lo tanto, la resolución de problemas reales mediante este tipo de algoritmos resulta prácticamente inviable.

En esta tesis presentamos nuevos algoritmos para la resolución de problemas de satisfacción de restricciones distribuidos capaces de manejar multiples variables por agente. Estos algoritmos realizan un manejo eficiente de la información obtenida mediante la comunicación entre los agentes, consiguiendo con ello una mayor eficiencia durante el proceso de resolución. Además, sus requerimientos