Planning

Los modelos de planificación de Inteligencia Artificial diseñan planes para alcanzar una meta.

Estos métodos, dado un espacio de estados, intentan encontrar una secuencia de acciones que lleve el problema desde un estado inicial a un estado objetivo.

Estos sistemas no se preocupan por cómo ejecutar esa secuencia. No se los debe confundir con Búsqueda. No existe una relación fija entre el orden de la planificación y el orden de la ejecución.

No siempre es posible encontrar un camino de solución.

Hay 3 conceptos clave para evitar la explosión combinatoria:

1. Apertura en la representación de estados, objetivos y acciones.
2. Libertad para añadir acciones al plan siempre que sea necesario.
3. Divide y vencerás: generar sub-planes más sencillos.

Los objetivos y estados son conjuntos de sentencias, y las acciones son descripciones lógicas de las pre-condiciones y post-condiciones o efectos. Así, las acciones conectan estados.

STRIPS

STanford Research Institute Problem Solver es un lenguaje simple para representar estados y acciones.

Los estados se representan como conjunciones de literales sin funciones, es decir predicados aplicados a símbolos constantes. Por convención se asume que un literal no presente está negado.

Los operadores tienen 3 elementos:

1. Especificación de la acción.
2. Condición previa (pre-condición).
3. Efecto (post-condición).

Un operador $o$ es aplicable a un estado $s$ siempre que en ese estado se puedan concretizar las variables que contiene dicho operador.

Ejemplo de operador:

operador(ACCION: Ir(y)
		 PRECOND: En(x) Y Ruta(x, y)
		 EFECTO: En(y) Y -En(x))

Representación gráfica:

Según la estrategia que usan, se tienen:

• Planificadores de progresión: aplican operadores partiendo del estado inicial. Tienen el problema de la explosión combinatoria.
• Planificadores de regresión: parten del estado objetivo para satisfacer pre-condiciones. Tienen el problema de operadores incompletos.

Una alternativa a buscar a través del espacio de estados es buscar en el espacio de planes. Esto involucra operadores de refinamiento (eliminan planes) y modificación (crean planes potencialmente incorrectos).

Una buena representación de planes asegura una búsqueda eficiente. Los planificadores aplican el principio de compromiso mínimo: resolver lo que actualmente sea de interés (un problema a la vez).

Hay planificadores de:

• Orden parcial: algunos pasos se ordenan en relación a los demás.
• Orden total: incluyen todas las posibilidades.

Formalmente, un plan contiene:

• Un conjunto de pasos del plan.
• Un conjunto de restricciones de ordenamiento de pasos del tipo $S_i\prec S_j$.
• Un conjunto de vínculos causales $S_i{\to }^{(c)}{S}_j$ (se lee $S_i$ logra $c$ de $S_j$).

Una amenaza para un vínculo causal es una acción que destruye el efecto del vínculo y que se puede intercalar entre la acción y su efecto. Las amenazas vuelven incompatibles algunos pasos. Se pueden eliminar modificando el orden de los pasos (introduciendo una restricción de orden).

Un plan completo es aquel en que cada condición previa de todos los pasos se logra con la ejecución de otro paso, es decir que todas las pre-condiciones se cumplen.

Un plan linealizado es aquel con un solo orden posible. Se puede linealizar un plan agregando restricciones de orden.

Una solución es un plan completo y consistente.

Como ejemplo, sea el siguiente plan inicial para el problema de comprar comida en un supermercado y máquinas en una ferretería:

Una solución sería:

Algoritmo POP

El algoritmo POP (Partial Order Planning) es un planificador de orden parcial que comienza desde un plan inicial mínimo y en cada paso lo extiende logrando una pre-condición $c$ de un paso $S_{need}$ (principio de compromiso mínimo).

$$\begin{array}{rl}& \text{function }\text{POP}(initial,goal,operators)\text{returns}plan\\ & plan\leftarrow \text{Make-Minimal-Plan}(initial,goal)\\ & \text{loop do}\\ & \text{if }\text{Solution}?(plan)\text{then return }plan\\ & S_{need},c\leftarrow \text{Select-Subgoal}(plan)\\ & \text{Choose-Operator}(plan,operators,S_{need},c)\\ & \text{Resolve-Threats}(plan)\\ & \text{end}\end{array}$$

En $\text{Select-Subgoal}$ se elige un solo objetivo, respetando el principio de compromiso mínimo.

$$\begin{array}{rl}& \text{function }\text{Select-Subgoal}(plan)\text{returns }{S}_{need},c\\ & \text{pick a plan step }{S}_{need}\in \text{Steps}(plan)\\ & \text{with a precondition }c\text{ that has not been achieved}\\ & \text{return }{S}_{need},c\end{array}$$

En $\text{Choose-Operator}$ se elige un paso existente o un operador y se agrega el vínculo causal y su restricción de orden asociada. Si se eligió un operador, se crea un nuevo paso que lo aplica.

$$\begin{array}{rl}& \text{procedure }\text{Choose-Operator}(plan,operators,S_{need},c)\\ & \text{choose }{S}_{add}\in operators\text{or }\text{Steps}(plan)\text{ that has }c\text{ as an effect}\\ & \text{if }\text{no such step }\text{then fail}\\ & \text{add the causal link }{S}_{add}\stackrel{c}{\to }{S}_{need}\text{ to }\text{Links}(plan)\\ & \text{add the ordering constraint }{S}_{add}\prec S_{need}\text{ to }\text{Orderings}(plan)\\ & \text{if }{S}_{add}\text{ is a newly added step from operators then}\\ & add{S}_{add}\text{to }\text{Steps}(plan)\\ & addStart\prec S_{add}\prec Finish\text{to }\text{Orderings}(plan)\end{array}$$

En $\text{Resolve-Threats}$ se introduce una restricción de orden por cada amenaza. Si el plan no resulta consistente, entonces falla el algoritmo.

$$\begin{array}{rl}& \text{procedure }\text{Resolve-Threats}(plan)\\ & \text{for each }{S}_{threat}\text{ that threatens a link }{S}_i\stackrel{c}{\to }{S}_j\in \text{Links}(plan)\text{do}\\ & \text{choose either:}\\ & \text{Promotion: Add }{S}_{threat}\prec S_i\text{to }\text{Orderings}(plan)\\ & \text{Demotion: Add }{S}_j\prec S_{threat}\text{to }\text{Orderings}(plan)\\ & \text{if not }\text{Consistent}(plan)\text{then fail}\\ & \text{endfor}\\ & \text{end}\end{array}$$