GRUPO-UPV

   GRUPO-UniOvi

   Beca FPI

   Publicaciones

TECNICAS PARA LA EVALUACION Y OBTENCION DE SOLUCIONES ESTABLES Y ROBUSTAS EN PROBLEMAS DE OPTIMIZACION Y SATISFACCION DE RESTRICCIONES.
(TIN2010-20976-C02-01 Spain)
Coordinator/I.P.: Miguel A. Salido. (2011-2013)

RESUMEN

Durante las últimas décadas, el esfuerzo investigador en las técnicas de optimización y satisfacción de restricciones, ampliamente aplicadas en áreas de Inteligencia Artificial (planificación y asignación de recursos (scheduling)), se ha centrado en la obtención eficiente de soluciones optimizadas, asumiendo entornos deterministas e información completa. Sin embargo, muchos de los problemas reales en esas áreas se desarrollan en entornos dinámicos, parcialmente deterministas o con información incompleta, donde se producen incidencias y/o variaciones del problema que hacen que la solución inicialmente obtenida no sea ya válida o tan optimizada como se preveía. Por ello, surge la necesidad de obtener soluciones que sean también robustas y estables.

 Esta es una línea novedosa en la resolución de Problemas de Optimización y Satisfacción de Restricciones (CSOP), que añade aún más complejidad a la NP-hard inherente a estos problemas. Sin embargo, a pesar de su interés, sobre todo si se requiere tratar con escenarios reales, los conceptos asociados a la robustez y estabilidad de soluciones en CSOP no están plenamente formalizados, ni caracterizada su relación con otros parámetros de la propia solución (optimalidad) ni con parámetros significativos de los problemas. Por todo ello, es necesario desarrollar nuevas técnicas y métodos que permitan obtener soluciones más estables y robustas, teniendo en cuenta la información parcial disponible y que, por tanto, puedan asumir incidencias o efectos inesperados en su ejecución. Ello supone un importante reto científico-técnico y de incuestionable aplicabilidad.

 En este proyecto se pretende:

·        Contextualizar los conceptos de robustez, estabilidad, fiabilidad y recuperabilidad para problemas CSP, para problemas CSOP y en particular para problemas de scheduling complejos. Diseñar medidas analíticas de robustez y estabilidad así como medidas de equilibrio entre robustez-optimalidad, estabilidad-optimalidad, etc.

·         Desarrollar técnicas para la evaluación y obtención de soluciones robustas y estables en CSPs, CSOPs y en particular problemas de scheduling dinámicos y con incertidumbre en los datos.

·         Aplicar y evaluar los sistemas desarrollados a problemas reales, así como, cuando sea posible, sobre bancos de ejemplos de uso común por la comunidad científica

 Con estos objetivos, se plantea un proyecto integrador en el que confluyen dos líneas complementarias de investigación: (i) técnicas basadas en Problemas de Satisfacción de Restricciones (CSPs) dinámicos para la obtención de soluciones robustas y (ii) técnicas metaheurísticas para resolver problemas de optimización combinatoria, como es el caso de los problemas de planificación y scheduling en presencia de incertidumbre e imprecisión y en entornos dinámicos. 

 Las actividades a realizar en el Proyecto de Investigación permiten la formación investigadora en las líneas propuestas. Se espera que el becario FPI que se incorpore participe activamente en las diversas actividades dentro del grupo, curse el “Máster en Inteligencia Artificial, Reconocimiento de Formas e Imagen Digital” en el cual el grupo de investigación participa, obtengan resultados propios (publicaciones), participen en la asistencia a Congresos y Workshops, estancias en Centros extranjeros, etc, con el objetivo de completar su formación y finalizar con la lectura de su tesis doctoral.

 La función del becario FPI a nivel investigador se centrará en el diseño en implementación de nuevas técnicas de satisfacción de restricciones capaces de encontrar soluciones con las características anteriormente expuestas. Para ello se requiere de un candidato con altos conocimientos en lenguajes de programación (principalmente en C++), y con capacidad investigadora para trabajar en áreas de Inteligencia Artificial.

Convocatoria de beca FPI