Curso de Doctorado 2003-2004 - DCCIA
Atrás
Modelos y Técnicas para Problemas de Satisfacción
de Restricciones.
Programa de Doctorado:
INGENIERÍA INFORMÁTICA Y COMPUTACIÓN
Profesores:
Isabel Alfonso Galipienso, Miguel Ángel Salido Gregorio
Número créditos: 4
Prerrequisitos: No son
necesarios prerrequisitos especiales para cursar esta asignatura.
Presentación: Tranparencias presentación
El objetivo de este curso se centra en conocer y aplicar los distintos
modelos y técnicas existentes en la literatura sobre Problemas de Satisfacción de Restricciones (CSP).
Esta tipología de problemas se encuentra presente en numerosas áreas tales como
planificación, scheduling, diagnosis, configuración, diseño, logística, etc.
Brevemente un problema de satisfacción de restricciones consiste en un conjunto
de variables acotadas en un dominio discreto o continuo y una serie de
restricciones que acotan los valores que las variables pueden simultáneamente
tomar. El objetivo de este tipo de problemas es encontrar una asignación de
valores a las variables de manera que se satisfagan todas las restricciones. La
complejidad de este problema es NP-completo, por lo que es necesario el uso de
técnicas eficientes que resuelvan estos problemas en un tiempo razonable. Por
ello, se considera esta línea de investigación de gran interés y aplicabilidad.
En este curso se pretende que el alumno conozca a fondo
algunas de las técnicas más importantes e incluso que investigue algunas de las
técnicas que se están desarrollando en la actualidad.
Los tópicos fundamentales que se tratan en el curso son:
- Problemas de Satisfacción de Restricciones (CSP).
Definición, tipos de CSPs y áreas de aplicación.
- Algoritmos de búsqueda y de consistencia. Los principales
algoritmos los podemos clasificar como algoritmos de búsqueda y los algoritmos
de consistencia. Los primeros como su nombre indica se basan en buscar una
solución que satisfaga todas las restricciones del problema. Los segundos no
tienen este objetivo sino filtrar y eliminar de los dominios de las variables
aquellos valores que no van a formar parte de ninguna solución.
- Técnicas Híbridas y de Preproceso. Existen en
la literatura diferentes técnicas hibridas que combinan la búsqueda y
consistencia así como otros que mediante un preproceso previo se basan en la ordenación de los
valores, variables y restricciones para llevar a cabo la búsqueda. Estas
últimas heurísticas de ordenación mejoran sustancialmente la eficiencia de los
algoritmos de búsqueda y consistencia.
- CSPs Distribuidos. La introducción
de los agentes y los sistemas multiagentes en el campo de la Inteligencia
Artificial han generado una nueva manera de resolver los CSPs de forma
distribuida. Veremos los distintos algoritmos que llevan a cabo la búsqueda de
forma distribuida.
- CSPs No Binarios.
Una gran cantidad de problemas reales se pueden modelar de forma
natural como un CSP no binario. Sin embargo existen técnicas de transformación
de CSPs no binarios a binarios. Veremos dichas técnicas así como las ventajas
e inconvenientes. Alternativamente estudiaremos algunas técnicas que manejar
los CSPs no binarios en su formulación original.
- Aplicaciones.
Las aplicaciones de los CSPs son muchas y muy variadas. Nos centraremos en
algunas consideradas como fundamentales tales como la diagnosis de
enfermedades, y la planificación de rutas en el transporte ferroviario.
- Problemas sobre-restringidos.
Muchos problemas reales se llaman sobrerestringidos debido a que no existe una
solución que satisfaga todas las restricciones del problema. Para poder
resolver este tipo de problemas, es necesario relajar el mismo eliminando
algunas de las restricciones del problema.
- Algoritmos heurísticos y estocásticos.
Debido a la complejidad exponencial que presentan los algoritmos completos que
resuelven los CSPs, es necesario es uso de algoritmos y técnicas heurísticas
para resolver los problemas en tiempo polinómico. Estas heurísticas nos sirven
tanto para encontrar la solución como para reducir la talla del problema o
guiarnos hacia la solución. Los algoritmos estocásticos son una
alternativa a los algoritmos de búsqueda de manera que exploran el árbol de
búsqueda de una manera diferente
-
Aplicaciones: scheduling. El problema de scheduling constituye
un campo activo de investigación en el que se aplican con éxito las técnicas
CSP. En este punto definiremos el problema de scheduling y los principales
tipos, así como la manera de modelarlos como un CSP.
- Trabajos prácticos. En esta
sesión presentaremos los trabajos prácticos que se pueden realizar en esta
asignatura. El alumno tiene la libertad de elegir entre la implementación y la
investigación. En cuanto a implementación, utilizaremos la herramienta LEKIN
que se utiliza para resolver problemas de scheduling. En cuanto a
investigación, tanto el profesor como el alumno investigarán sobre técnicas
heurísticas para mejorar el comportamiento de algoritmos existentes en la
literatura
Objetivos:
El
objetivo fundamental es introducir los conceptos, técnicas y aplicaciones de los
Problemas de Satisfacción de Restricciones (CSP). Para ello, se tratarán
aspectos básicos (Modelización de problemas CSP, Técnicas de Resolución y
Búsqueda), así como aplicados específicamente a los problemas de scheduling.
Temario:
PARTE I
1. Problemas de Satisfacción de Restricciones (CSP).
- Definición de problema de satisfacción de restricciones
(CSP). Áreas de aplicación.
- Especificación de un problema CSP: variables, dominios y
restricciones.
- Tipología de restricciones (discretas y continuas, aridad de
las restricciones, fuertes y débiles, restricciones lineales, disyuntivas,
etc.).
2. Algoritmos de búsqueda y
consistencia.
- Algoritmos de búsqueda: Generar y testear, backtracking y
backjumping.
- Algoritmos de consistencia. Niveles de
consistencia.
3. Técnicas híbridas y de preproceso
- Algoritmos híbridos:
- forward checking
- Look ahead
- maintaining arc consistency.
- Técnicas heurísticas de preproceso:
- Ordenación de valores
- Ordenación de variables
- Ordenación de restricciones
4. CSPs Distribuidos
- Definición de agente y sistema multiagente.
- Algoritmos distribuidos.
5. CSPs No Binarios
- Definición.
- Técnicas de transformación:
- Codificación dual
- Codificación de variables ocultas
- Codificación mixta
- Técnicas de manejo de CSPs no binarios.
6.
Aplicaciones
- Aplicación de CSPs no binarios a la diagnosis.
- Aplicación a la planificación de rutas en el transporte
ferroviario.
PARTE II
7. Problemas
sobre-restringidos
- Extensión de los CSP
- Problemas PCSP
- Jerarquías de restricciones y algoritmos
- Aproximaciones alternativas
8. Algoritmos
heurísticos y estocásticos
- Terminologia
- Algoritmos heurísticos más utilizados
9. Aplicaciones:
scheduling
- El problema de scheduling
- Principales aproximaciones de scheduling como CSP
10. Trabajos prácticos
- Herramienta Lekin
- Propuesta de trabajos
Bibliografía:
Se facilitarán diversas referencias bibliográficas
actualizadas al principio del curso, así como diversa documentación asociada.
Particularmente, merecen destacarse:
Evaluación:
La evaluación del curso se
llevará a cabo mediante la presentación de los trabajos prácticos realizados en
esta asignatura.
Para más información:
Miguel A. Salido
Mª Isabel Alfonso