La planificación y programación automatizadas , a veces denominada simplemente planificación de IA , [1] es una rama de la inteligencia artificial que se ocupa de la realización de estrategias o secuencias de acciones, típicamente para su ejecución por agentes inteligentes , robots autónomos y vehículos no tripulados . A diferencia de los problemas clásicos de control y clasificación , las soluciones son complejas y deben descubrirse y optimizarse en un espacio multidimensional. La planificación también está relacionada con la teoría de la decisión .
En entornos conocidos con modelos disponibles, la planificación se puede realizar sin conexión. Se pueden encontrar soluciones y evaluarlas antes de la ejecución. En entornos dinámicos desconocidos, a menudo es necesario revisar la estrategia en línea. Los modelos y las políticas deben adaptarse. Las soluciones suelen recurrir a procesos iterativos de prueba y error que se ven comúnmente en la inteligencia artificial . Estos incluyen la programación dinámica , el aprendizaje por refuerzo y la optimización combinatoria . Los lenguajes que se utilizan para describir la planificación y la programación a menudo se denominan lenguajes de acción .
Dada una descripción de los posibles estados iniciales del mundo, una descripción de los objetivos deseados y una descripción de un conjunto de acciones posibles, el problema de planificación es sintetizar un plan que garantice (cuando se aplica a cualquiera de los estados iniciales) la generación de un estado que contenga los objetivos deseados (dicho estado se denomina estado objetivo).
La dificultad de la planificación depende de los supuestos simplificadores que se empleen. Se pueden identificar varias clases de problemas de planificación en función de las propiedades que tengan los problemas en varias dimensiones.
El problema de planificación más simple posible, conocido como el problema de planificación clásico, está determinado por:
Dado que el estado inicial se conoce de forma inequívoca y todas las acciones son deterministas, el estado del mundo después de cualquier secuencia de acciones se puede predecir con precisión y la cuestión de la observabilidad es irrelevante para la planificación clásica.
Además, los planes pueden definirse como secuencias de acciones, porque siempre se sabe de antemano qué acciones serán necesarias.
Con acciones no deterministas u otros eventos fuera del control del agente, las posibles ejecuciones forman un árbol y los planes deben determinar las acciones apropiadas para cada nodo del árbol.
Los procesos de decisión de Markov en tiempo discreto (MDP) son problemas de planificación con:
Cuando la observabilidad total se reemplaza por una observabilidad parcial, la planificación corresponde a un proceso de decisión de Markov parcialmente observable (POMDP).
Si hay más de un agente, tenemos planificación multiagente , que está estrechamente relacionada con la teoría de juegos .
En la planificación de IA, los planificadores suelen introducir un modelo de dominio (una descripción de un conjunto de posibles acciones que modelan el dominio) así como el problema específico que se debe resolver especificado por el estado inicial y el objetivo, a diferencia de aquellos en los que no hay un dominio de entrada especificado. Dichos planificadores se denominan "independientes del dominio" para enfatizar el hecho de que pueden resolver problemas de planificación de una amplia gama de dominios. Ejemplos típicos de dominios son el apilamiento de bloques, la logística, la gestión del flujo de trabajo y la planificación de tareas de robots. Por lo tanto, se puede utilizar un único planificador independiente del dominio para resolver problemas de planificación en todos estos diversos dominios. Por otro lado, un planificador de rutas es típico de un planificador específico del dominio.
Los lenguajes más utilizados para representar dominios de planificación y problemas de planificación específicos, como STRIPS y PDDL para la planificación clásica, se basan en variables de estado. Cada estado posible del mundo es una asignación de valores a las variables de estado, y las acciones determinan cómo cambian los valores de las variables de estado cuando se realiza esa acción. Dado que un conjunto de variables de estado induce un espacio de estado que tiene un tamaño exponencial en el conjunto, la planificación, de manera similar a muchos otros problemas computacionales, sufre la maldición de la dimensionalidad y la explosión combinatoria .
Un lenguaje alternativo para describir los problemas de planificación es el de las redes de tareas jerárquicas , en las que se proporciona un conjunto de tareas y cada una de ellas puede realizarse mediante una acción primitiva o descomponerse en un conjunto de otras tareas. Esto no implica necesariamente variables de estado, aunque en aplicaciones más realistas las variables de estado simplifican la descripción de las redes de tareas.
La planificación temporal se puede resolver con métodos similares a la planificación clásica. La principal diferencia es que, debido a la posibilidad de que se realicen simultáneamente varias acciones superpuestas temporalmente con una duración determinada, la definición de un estado debe incluir información sobre el tiempo absoluto actual y hasta dónde ha llegado la ejecución de cada acción activa. Además, en la planificación con tiempo racional o real, el espacio de estados puede ser infinito, a diferencia de la planificación clásica o la planificación con tiempo entero. La planificación temporal está estrechamente relacionada con los problemas de programación cuando hay incertidumbre involucrada y también se puede entender en términos de autómatas temporizados . La red temporal simple con incertidumbre (STNU) es un problema de programación que involucra acciones controlables, eventos inciertos y restricciones temporales. La controlabilidad dinámica para tales problemas es un tipo de programación que requiere una estrategia de planificación temporal para activar acciones controlables de manera reactiva a medida que se observan eventos inciertos, de modo que se garantice que se satisfagan todas las restricciones. [2]
La planificación probabilística se puede resolver con métodos iterativos como la iteración de valores y la iteración de políticas , cuando el espacio de estados es suficientemente pequeño. Con observabilidad parcial, la planificación probabilística se resuelve de manera similar con métodos iterativos, pero utilizando una representación de las funciones de valores definidas para el espacio de creencias en lugar de estados.
En la planificación basada en preferencias, el objetivo no es solo elaborar un plan, sino también satisfacer las preferencias especificadas por el usuario . A diferencia de la planificación basada en recompensas más común, por ejemplo, la correspondiente a los MDP, las preferencias no tienen necesariamente un valor numérico preciso.
La planificación determinista se introdujo con el sistema de planificación STRIPS , que es un planificador jerárquico. Los nombres de las acciones se ordenan en una secuencia y este es un plan para el robot. La planificación jerárquica se puede comparar con un árbol de comportamiento generado automáticamente . [3] La desventaja es que un árbol de comportamiento normal no es tan expresivo como un programa de computadora. Esto significa que la notación de un gráfico de comportamiento contiene comandos de acción, pero no bucles ni declaraciones if-then. La planificación condicional supera el cuello de botella e introduce una notación elaborada que es similar a un flujo de control , conocido de otros lenguajes de programación como Pascal . Es muy similar a la síntesis de programas , lo que significa que un planificador genera un código fuente que puede ser ejecutado por un intérprete. [4]
Un ejemplo temprano de un planificador condicional es “Warplan-C”, que se introdujo a mediados de la década de 1970. [5] ¿Cuál es la diferencia entre una secuencia normal y un plan complicado, que contiene declaraciones if-then? Tiene que ver con la incertidumbre en el tiempo de ejecución de un plan. La idea es que un plan puede reaccionar a señales de sensores que son desconocidas para el planificador. El planificador genera dos opciones de antemano. Por ejemplo, si se detecta un objeto, se ejecuta la acción A, si falta un objeto, se ejecuta la acción B. [6] Una ventaja importante de la planificación condicional es la capacidad de manejar planes parciales . [7] Un agente no está obligado a planificar todo de principio a fin, sino que puede dividir el problema en fragmentos . Esto ayuda a reducir el espacio de estados y resuelve problemas mucho más complejos.
Hablamos de "planificación contingente" cuando el entorno es observable a través de sensores, que pueden ser defectuosos. Se trata, por tanto, de una situación en la que el agente planificador actúa con información incompleta. En un problema de planificación contingente, un plan ya no es una secuencia de acciones sino un árbol de decisiones , porque cada paso del plan está representado por un conjunto de estados en lugar de un único estado perfectamente observable, como en el caso de la planificación clásica. [8] Las acciones seleccionadas dependen del estado del sistema. Por ejemplo, si llueve, el agente elige coger el paraguas, y si no llueve, puede optar por no cogerlo.
Michael L. Littman demostró en 1998 que con acciones ramificadas, el problema de planificación se vuelve EXPTIME -completo. [9] [10] Un caso particular de planificación contigua está representado por los problemas FOND -para "completamente observables y no deterministas". Si el objetivo se especifica en LTLf (lógica de tiempo lineal en traza finita), entonces el problema siempre es EXPTIME-completo [11] y 2EXPTIME-completo si el objetivo se especifica con LDLf.
La planificación conforme se produce cuando el agente no está seguro del estado del sistema y no puede realizar ninguna observación. El agente tiene creencias sobre el mundo real, pero no puede verificarlas con acciones de detección, por ejemplo. Estos problemas se resuelven mediante técnicas similares a las de la planificación clásica, [12] [13] pero donde el espacio de estados es exponencial en el tamaño del problema, debido a la incertidumbre sobre el estado actual. Una solución para un problema de planificación conforme es una secuencia de acciones. Haslum y Jonsson han demostrado que el problema de la planificación conforme es EXPSPACE -completo, [14] y 2EXPTIME-completo cuando la situación inicial es incierta y no hay determinismo en los resultados de las acciones. [10]
{{cite journal}}: CS1 maint: multiple names: authors list (link){{cite conference}}: CS1 maint: multiple names: authors list (link){{cite conference}}: CS1 maint: multiple names: authors list (link): Avances recientes en la planificación de la IA