Post on 11-Feb-2016
description
Distribución de Antenas de
telefonía móvil como CSP
Leandro Abraham – Pablo OcañaInteligencia Artificial - Trabajo Final
FRM – UTN 2011
Resumen
Implementar los algoritmos de resolución de problemas de satisfacción de restricciones,
aplicados a un problema de distribución de antenas en distintas ubicaciones preestablecidas, y teniendo
en cuenta ciertas restricciones
Presentación del Problema
1 - ANÁLISIS
• Restricciones:o Restricción de potencia:
La suma de potencia entre las antenas ubicadas en dos lugares que son considerados visibles no puede ser mayor a una potencia máxima:
Visible(Xi,Xj)=> P(Antena(Xi))+ P(Antena(Xj)) ≤ Pot. Máxima con i ≠ j
Presentación del Problema
o Restricción de Frecuencia:
Dos antenas consecutivas no pueden emitir en la misma frecuencia.
Consec(Ai,Aj) => F(Antena(Xi)) ≠ F(Antena(Xj)) con i ≠ j
Decisiones de Diseño• Diseño Orientado a Objetos.• Aplicación de Patrones de Diseño:
o Patrón Experto o Patrón Fábrica o Patrón Estrategia o Patrón Singletono Patrón Plantilla
• Se buscó tratar al problema como un CSP general (variables, valores, problema), utilizando interfaces que las clases particulares implementarían. También se siguió este esquema para los algoritmos de resolución y heurísticas.
Decisiones de Diseño
Implementación• Desarrollo en Java utilizando NetBeans 6.9• Para la experimentación se creó una clase
Experimentador que solicitaba problemas a un Generador y volcaba los resultados a una plantilla excel utilizando librería específicas
• El Generador toma como parámetros la cantidad de variables, cantidad de frecuencias distintas para las antenas, potencia y frecuencias máximas y restricción de potencia para crear problemas dentro de estos parámetros.
Implementación• Para la implementación de MVR se estableció el método
public Variable getNextVariable(CSP problema)
• Este último método nos devuelve la próxima variable a asignar y a comprobar
• Para la implementación de VMR, en cambio se decidió que el método nos ordene la lista según restringa a las demás variables
public List<Valor> ordenarValores(List<Valor> ValoresPosibles,Variable varActual, int numDominio)
Estudio experimental• Se decidió ejecutar los algoritmos para una serie de
problemas con cantidad de variables (n), o tamaño creciente.
• Se generaron 50 problemas por cada n que se decidió experimentar, siendo los n utilizados 8, 16, 32, 64, 72 y 96 ubicaciones y antenas posibles.
• Los valores de frecuencia de las antenas del problema se generaron dentro de ciertos rangos correspondientes a las siguientes frecuencias máximas: 800 Mhz, 900Mhz, 1Ghz y 1.8GHz. Además para cada problema las antenas generadas tenían entre 5, 10 y 15 frecuencias distintas posibles.
• Las potencias máximas utilizadas para las restricciones fueron de 20mW, 30mW y 40mW.
Estudio experimental• Algoritmos utilizados:
o Backtrackingo Forward checkingo Arco consistencia
• Combinados con las heurísticas:o Minimos valores restanteso Valor mas restringido
Estudio experimental: Resultados
Comparación del runtime de los algoritmos para problemas de 8, 16, 32, 64, 72 y 96 variables.
Estudio experimental: Resultados
Comparación de la cantidad de recursiones de los algoritmos para problemas de 8, 16, 32, 64 y 72 variables.
Estudio Experimental: Resultados
Comparación de la cantidad de backtracks de los algoritmos para problemas de 8, 16, 32, 64 y 72 variables.
Conclusiones• Arco consistencia y Forward checking arrojan
resultados similares en el rendimiento. Sin embargo backtracking muestra ineficiencias en recursiones y backtracks realizados.
• En tiempo de procesamiento, backtracking muestro resultados aceptables para problemas chicos, pero su rendimiento empeora considerablemente.