Planificación automática

Fuente: Dana S. Nau - University of Maryland (CC-BY-NC-SA)

La planificación automática es una disciplina de la Inteligencia Artificial que nos permite resolver problemas complejos mediante ordenador, sin el cual se tardaría una cantidad ingente de tiempo en obtener una solución. 

Los planificadores actuales permiten diseñar estrategias para un conjunto extenso de dominios como son:

• Diseño de planes de negocio en empresas.
• Diseño de estrategias de defensa del cliente en despachos de abogados.
• Organización de espacios habitables y seguros en arquitectura.
• Mejora de la conectividad en redes de comunicaciones.
• Planes estratégicos militares.
• Logística de transportes en el comercio.
• Inteligencia artificial en robots.
• etc.

Los planificadores clásicos están basados en algoritmos de búsqueda heurística (A*, Alfa-beta o Greedy) como por ejemplo STRIPS (STanford Research Institute Problem Solver [Fikes y Nilsson 1971]) en el que se aplica un algoritmo de búsqueda lineal, mientras que los planificadores neoclásicos como graphplan aplican restricciones y optimizaciones en cada estado antes de avanzar al siguiente. Esto hace que su estructura tenga forma de grafo de planes en vez de árbol o grafo acíclico.

Imagen de Graphplan

Otros tipos de planificadores están basados en técnicas más avanzadas como los probabilísticos, los de redes de tareas jerárquicas, los de planificación heurística (HSP y FF)  o los temporales (scheduling).

En general, un problema de planificación dado en lenguajes como STRIPS o PDDL debe contener la siguiente información:

• Un estado inicial.
• Un estado final o estados meta.
• Un conjunto de acciones: precondiciones y postcondiciones.

Así, por ejemplo, para resolver el problema del granjero que debe cruzar un río llevando únicamente en la barca una cabra, una col o un lobo sin que se coman entre ellos al quedarse en la orilla, se formularía de la siguiente manera en formalismo STRIPS:

Estado inicial:  barcaen(a)
                 colocado(lobo,a)
                 colocado(cabra,a)
                 colocado(col,a)
                 vacío

Estado final:

                 colocado(col,b)
                 colocado(lobo,b)
                 colocado(cabra,b)

Acciones:        

mover(inicio,fin):
            pre: embarcado(cabra) ∨
            (colocado(col,inicio) ∧ colocado (cabra,fin)) 
            ∨
            (colocado(cabra,inicio) ∧ colocado(lobo,fin))
                                 
            post:  barcaen(fin) ∧
                  ¬barcaen(inicio)
                                       

embarcar(posicion,animal):
           pre: barcaen(posicion) ∧ 
           colocado(animal, posicion) ∧ (vacio)
           post:   embarcado(animal) ∧
                   ¬colocado(animal,posicion) ∧
                   ¬(vacío)                        
                          
desembarcar(posicion,animal):
            pre: barcaen(posicion) ∧ embarcado(animal)      
            post: colocado(animal,posicion) ∧
                  vacío ∧  ¬embarcado(animal) 

Si ejecutamos el programa en un planificador como SGP, obtendremos el siguiente resultado:

Levels 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
(((EMBARCAR A CABRA)) ((MOVER A B)) ((DESEMBARCAR B CABRA)) ((MOVER B A))((EMBARCAR A LOBO)) ((MOVER A B)) ((DESEMBARCAR B LOBO)) ((EMBARCAR B CABRA))((MOVER B A)) ((DESEMBARCAR A CABRA)) ((EMBARCAR A COL)) ((MOVER A B)) ((DESEMBARCAR B COL)) ((MOVER B A)) ((EMBARCAR A CABRA)) ((MOVER A B))((DESEMBARCAR B CABRA)))

Problema del cruce del río. Videojuego. (http://layton.wikia.com/wiki/Puzzle:Over_the_River)