Inteligencia artificial · Planificación automática
Lightsout
Un estudio de planificación automática para resolver Lightsout y comparar cuánto cuesta encontrar soluciones con menos movimientos.
Mi contribución
Mi compañero y yo realizamos juntos el código, los experimentos y la memoria, sin una división fija de tareas.
- Planificación con PDDL
- Comparación de tiempo y movimientos
Modelar el problema
En la variante estudiada partimos de un tablero apagado y buscamos encender todas las casillas. Cada pulsación cambia el estado de una casilla y de sus vecinas ortogonales.
Modelamos estados y acciones con PDDL y Unified Planning para resolver el problema con Fast Downward. Después implementamos una búsqueda en anchura modificada con una heurística que prioriza estados con más luces encendidas.
Menos movimientos, más tiempo de búsqueda
La heurística conserva N sucesores en cada expansión. Aumentar N permite explorar más alternativas, pero incrementa el tiempo de búsqueda. Estos son los resultados documentados para el caso de prueba 5 × 5:
| Método | Movimientos | Tiempo |
|---|---|---|
| Fast Downward | 49 | 0,61 s |
| BFS · N = 2 | 25 | 0,99 s |
| BFS · N = 3 | 17 | 14,20 s |
| BFS · N = 4 | 15 | 58,95 s |
| BFS · N = 5 | 15 | 175,63 s |
La conclusión del experimento
Con N = 2 obtuvimos 25 movimientos en menos de un segundo. Con N = 4 bajamos a 15 movimientos, pero el tiempo aumentó hasta unos 59 segundos. Son dos configuraciones distintas: no se logró la mayor reducción manteniendo el tiempo subsegundo.
La poda de sucesores limita la búsqueda; estos resultados no prueban que el algoritmo encuentre siempre una solución óptima ni que supere a Fast Downward en cualquier problema. El trabajo fue conjunto, tanto en el código como en la memoria.
Caso documentado a partir de la memoria y la presentación académicas. No hay un repositorio público enlazado.