El planeo automatizado es el proceso computacional de generar un curso de acción para que un agente lo ejecute. Como entrada, un planeador toma una descripción del mundo (en algunos una representación formal de conocimiento), una descripción de las acciones disponibles, y una descripción de la función objetiva del agente (por ejemplo, una función de logro y/o costos de acción). La salida del planeador puede ser una secuencia de acciones (un “plan”), una rama de acciones (un “plan contingente”) o una función del estado mundial de acciones (una “política”).
La complejidad computacional de planeamiento depende en la expresividad de los lenguajes utilizados para representar acciones y metas, pero hasta formulaciones simples son en el disco P-SPACE, y representaciones probabilísticas hacen que el problema sea más difícil.
La dificultad de planeamiento depende de la simplificación de los supuestos empleados. Varias clases de problemas de planeamiento pueden ser identificados dependiendo de las propiedades que los problemas tienen en varias dimensiones.
· ¿Son las acciones deterministas o no deterministas? ¿Para las acciones no deterministas, están disponibles las probabilidades asociadas?
· ¿Son las variables de estado discreta o continuas? ¿Si son discretas, tienen ellas solo un numero finito de valores posibles?
· ¿Puede el estado actual ser observado sin ambigüedades? Puede existir observabilidad completa y observabilidad parcial.
· ¿Cuantos estados iniciales existen, finitos o muchos arbitrarios?
· ¿Las acciones tienen una duración?
· ¿Pueden las acciones ser tomadas concurrentemente, o solo es posible una acción a la vez?
· ¿El objetivo del plan es llegar a un estado meta designado, o maximizar una función de logro?
· ¿Solo hay un agente, o existen varios agentes? ¿Los agentes son cooperativos o egoístas? ¿Todos los agentes construyen sus planes separadamente, o los planes son construidos centralmente para todos los agentes?
Classical Planning Problem
El problema de planeamiento más simple posible, conocido como el Problema de Planeamiento Clásico, es determinado por:
· Un estado inicial conocido.
· Acciones sin duración.
· Acciones deterministas, que solo pueden tomarse una a la vez.
· Un agente único.
Ya que el estado inicial es único y todas las acciones son deterministas, el estado del mundo después de cualquier secuencia de acciones puede ser predicho precisamente, y la cuestión de observabilidad es irrelevante para el planeamiento clásico.
Además, planes pueden ser definidos como secuencia de acciones, porque siempre es mejor conocer de antemano cuales acciones serán necesarias.
Mediante acciones no deterministas u otros eventos fuera del control del agente, las posibles ejecuciones forman un árbol, y los planes tienen que determinar las acciones apropiadas para cada nodo el árbol.
Markov Decision Processes (MDP)
Los procesos de decisión Markov en tiempo discreto son problemas de planeamiento con:
· Acciones sin duración.
· Acciones no deterministas con probabilidades.
· Observabilidad completa.
· Maximización de la función de logro.
· Un agente único.
Cuanto la observabilidad completa es reemplazada por observabilidad parcial, el planeamiento corresponde al partially observable Markov decisión process (POMDP).
0 Komentar