Un agente planificador elabora planes para alcanzar sus metas y luego procede a ejecutarlos. Cuando el estado del mundo es accesible, el agente emplea las percepciones que le da el ambiente para construir un modelo completo y correcto del estado del mundo correspondiente a ese momento. Si se plantea una meta, el agente solicita el algoritmo de planificación que corresponda para elaborar un plan de acción. Realizado este, el agente procede a ejecutar los pasos que se indique, uno a la vez.
Planificación y resolución de problemas son cosas distintas:diferente manera de representar metas, estados y acciones y a las diferencias en representación y construcción de secuencias de acciones.
Los elementos básicos de un solucionador de problemas basado en la búsqueda son:
Las claves de la planificación:
La planificación como problema de inferencia lógica se representa con oraciones lógicas que describen tres partes principales de un problema:
El calculo de situaciones se basa en la idea de que las acciones transforman a los estados. Tiene algunas limitaciones en cuanto a expresividad, pero es suficiente para los dominios de planificación.
La planificación mediante inferencia lógica no guiada es ineficiente. El procedimiento de inferencia no garantiza nada sobre el plan resultante, sino sólo que permite alcanzar la meta (con pasos irrelevantes).
En la planificación practica es necesario restringir el lenguaje utilizado para definir los problemas (menos soluciones posibles), y para encontrar la solución hay que emplear un algoritmo de propósito especial (planificador).
El método clásico se caracteriza por describir estados y operadores mediante el lenguaje restringido conocido como lenguaje Strips.
Representación de estados y objetivos: los estados se representan mediante conjunciones literales básicas en las que no hay funciones y no tiene que estar completa la especificación de un estado. Las metas se representan con una conjunción de literales y pueden figurar variables (cuantificadas en cuanto a existencia).
Representación de acciones: los operadores Strips constan de tres elementos =>
El esquema de operador es el operador que tiene variables que corresponden a familia de acciones, solo es posible ejecutar operadores concretizados.Un operador o es aplicable a un estado s si existe una manera de concretizar las variables que tiene o, de manera que las condiciones previas de o sean válidas en s.
Espacio de situaciones y de planes: el plan es la ruta que pasa por el espacio, desde el estado inicial hasta el estado meta.
El planificador de espacio de situaciones busca a través del espacio de las situaciones posibles, la ruta que recorre el árbol de búsqueda es el plan que propondrá el planificador, y cada punto de rama añade otro paso sea al inicio (regresión) o al final (progresión) del plan.
El planificador de progresión busca avanzando de la situación inicial a la situación meta, tiene elevado factor de ramificación y por ende: enorme espacio de búsqueda.
El planificador por regresión trata de reducir el factor de ramificación buscando hacia atrás,desde el estado meta hacia el estado inicial.
Una operación consiste en buscar a través del espacio de planes, se empieza por un plan sencillo, incompleto al que se denomina plan parcial. Luego se evalúa como expandir el plan parcial hasta obtener un plan completo que resuelva el problema. Los operadores de esta búsqueda son operadores sobre planes.
Las operaciones que se llevan a cabo en los planes pueden ser de refinamiento (escogen un plan parcial y le añaden restricciones) o de modificación (algunos planificafores construyen planes incorrectos y los depuran mediante los operadores de modificación).
Representaciones de planes:se establece una buena representación mediante planes parciales. Muchos planificadores aplican el principio de compromiso mínimo donde uno sólo debe preocuparse de tomar decisiones relacionadas a aquello que interese a uno, dejando otras decisiones para después.
Orden parcial es el planificador capaz de representar planes en los que solo algunos pasos se ordenan en relación con otros y otros pasos no están ordenados.
Orden total en el que los planes están formados por una sola lista de pasos. Al plan totalmente ordenado que se obtiene de un plan P añadiendo restricciones de ordenamiento se lo conoce como linealización de P.
Los planes completamente concretizados son aquellos en los que toda variable esta enlazada a una constante.
A un plan se lo define como una estructura de datos constituida por:
Soluciones: una solución es un plan que un agente puede ejecutar y garantizar el logro de la meta. Sólo los planes enteramente concretizados, totalmente ordenados, constituyen soluciones.
Se aceptan planes ordenados parcialmente como soluciones mediante la aplicación de una sencilla definición: una solución es un plan completo (cada condición previa de todos los pasos se logra mediante otro paso), consistente (no hay contradicciones en las restricciones de ordenamiento o enlazamiento).
POP inicia con un plan parcial mínimo. A cada paso, el plan se va ampliando mediante la satisfacción de una condición previa. Pone en un registro el vínculo causal de condición previa recién satisfecha y luego elimina las amenazas a los vínculos causales (el manejo de las condiciones previas es conmutativo).
POP es un planificador por regresión, dado que empieza por metas que hay que satisfacer y va trabajando hacia atrás, en busca de operadores que ofrezcan la solución deseada. Una vez satisfechas las condiciones previas de todos los pasos, ya tiene una solución.
POP es un algoritmo confiable y completo.
POP no se ocupa de las restricciones de enlace variables, hay que llevar un registro de las listas de enlace y unificar las expresiones pertinentes en el momento adecuado. Para manejar posibles amenazas hay tres métodos:
Cuando en los planes hay operadores parcialmente concretizados es necesario asegurar que las concretizaciones permitirán lograr la meta.
Si resulta que en el estado inicial no hay variables y si todos los operadores mencionan a todas sus variables en su condición previa, existe la seguridad de que todo plan generado por POP esté totalmente concretizado.
La metodología para resolver problemas mediante la planificación se asemeja a la de ingeniería del conocimiento:
