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 espaciales son mínimos, por lo que son capaces de
manejar grandes sub-problemas locales. También se presentan en
esta tesis varios algoritmos y técnicas heurísticas para que cada
agente realice eficazmente la búsqueda de soluciones parciales de
su sub-problema.

Por otra parte, los problemas de satisfacción de restricciones
suelen ser aplicados sobre grandes problemas reales, que
generalmente implican modelos con un gran número de variables y
restricciones y en los cuales, a menudo, se suelen identificar
sub-problemas más reducidos. Esta clase de problemas puede ser
manejada de manera global sólo a costa de un exagerado coste
computacional. Esto motiva una contribución adicional de esta
tesis que se basa en proporcionar unas metodologías para
particionar problemas de gran volumen o con entidades
diferenciales, para posteriormente poder ser resueltos más
eficazmente mediante los algoritmos propuestos para resolver
DCSPs. En esta tesis planteamos tres modos para particionar un
problema: el primero se basa en técnicas de particionamiento de
grafos, el segundo en la identificación de estructuras de árbol y
el tercero en la identificación de entidades propias de cada
problema. Tanto las propuestas de particionamiento de CSPs, como
los nuevos algoritmos de resolución de DCSPs, constituyen el
núcleo de las aportaciones de esta tesis. Finalmente se evalúan
los métodos propuestos sobre escenarios de prueba, se efectúa una
revisión crítica y se plantean líneas de futuro.