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 / Abril López, M. (2007). Particionamiento y resolución distribuida multivariable de problemas de satisfacción de restricciones [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/1946 / Palancia
Identifer | oai:union.ndltd.org:upv.es/oai:riunet.upv.es:10251/1946 |
Date | 07 May 2008 |
Creators | Abril López, Montserrat |
Contributors | Barber Sanchís, Federico, Salido Gregorio, Miguel Angel, Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació |
Publisher | Universitat Politècnica de València |
Source Sets | Universitat Politècnica de València |
Language | Spanish |
Detected Language | Spanish |
Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/acceptedVersion |
Source | Riunet |
Rights | http://rightsstatements.org/vocab/InC/1.0/, info:eu-repo/semantics/openAccess |
Page generated in 0.0015 seconds