La planificación y programación automatizadas , a veces denominada simplemente planificación por IA , [1] es una rama de la inteligencia artificial que se ocupa de la realización de estrategias o secuencias de acciones, normalmente 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. Las soluciones se pueden encontrar y evaluar antes de la ejecución. En entornos dinámicamente desconocidos, a menudo es necesario revisar la estrategia en línea. Es necesario adaptar modelos y políticas. Las soluciones suelen recurrir a procesos iterativos de prueba y error que se ven comúnmente en la inteligencia artificial . Estos incluyen programación dinámica , aprendizaje por refuerzo y optimización combinatoria . Los lenguajes utilizados para describir la planificación y la programación suelen denominarse lenguajes de acción .
Dada una descripción de los posibles estados iniciales del mundo, una descripción de las metas deseadas y una descripción de un conjunto de acciones posibles, el problema de planificación es sintetizar un plan que esté garantizado (cuando se aplica a cualquiera de los estados iniciales) para generar un estado que contenga los objetivos deseados (dicho estado se llama estado objetivo).
La dificultad de la planificación depende de los supuestos simplificadores empleados. Se pueden identificar varias clases de problemas de planificación dependiendo de las propiedades que tienen los problemas en varias dimensiones.
El problema de planificación más simple posible, conocido como problema de planificación clásico, está determinado por:
Dado que el estado inicial se conoce sin ambigüedades 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 (MDP) en tiempo discreto son problemas de planificación con:
Cuando la observabilidad total se reemplaza por la 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 la planificación multiagente , que está muy relacionada con la teoría de juegos .
En la planificación de la IA, los planificadores normalmente ingresan un modelo de dominio (una descripción de un conjunto de acciones posibles que modelan el dominio), así como el problema específico a resolver especificado por el estado inicial y el objetivo, en contraste con aquellos en los que no hay dominio de entrada especificado. Estos planificadores se denominan "independientes de 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 de dominio específico.
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 estados que tiene un tamaño exponencial en el conjunto, la planificación, al igual que muchos otros problemas computacionales, sufre la maldición de la dimensionalidad y la explosión combinatoria .
Un lenguaje alternativo para describir problemas de planificación es el de las redes jerárquicas de tareas , en las que se da un conjunto de tareas y cada tarea 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 que se superpongan temporalmente y con una duración determinada, la definición de un estado debe incluir información sobre el tiempo absoluto actual y hasta qué punto ha avanzado 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 y también puede entenderse en términos de autómatas cronometrados . 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 el cumplimiento de 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 lo 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 valor definidas para el espacio de creencias en lugar de estados.
En la planificación basada en preferencias, el objetivo no es sólo producir un plan sino también satisfacer las preferencias especificadas por el usuario . A diferencia de la planificación más común basada en recompensas, por ejemplo la correspondiente a los MDP, las preferencias no necesariamente tienen 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 están ordenados 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 ordenador. Eso significa que la notación de un gráfico de comportamiento contiene comandos de acción, pero no bucles ni declaraciones si-entonces. La planificación condicional supera el cuello de botella e introduce una notación elaborada similar a un flujo de control , conocida en 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 el "Warplan-C", que se introdujo a mediados de los años 1970. [5] ¿Cuál es la diferencia entre una secuencia normal y un plan complicado, que contiene declaraciones si-entonces? Tiene que ver con la incertidumbre en el momento de la ejecución de un plan. La idea es que un plan pueda reaccionar a señales de sensores 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, pero puede dividir el problema en partes . Esto ayuda a reducir el espacio de estados y resuelve problemas mucho más complejos.
Hablamos de "planificación de contingencia" cuando el entorno es observable a través de sensores, que pueden resultar defectuosos. Se trata, pues, de una situación en la que el agente de planificación actúa con información incompleta. Para 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 estado único 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 opta por coger el paraguas, y si no, 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, es decir, "totalmente 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 entonces tiene creencias sobre el mundo real, pero no puede verificarlas mediante acciones sensoriales, por ejemplo. Estos problemas se resuelven mediante técnicas similares a las de 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)conferencia: Avances recientes en la planificación de la IA