Hispanopedia WikiLa planificación y programación automatizada , 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, generalmente 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 puede realizarse sin conexión. Se pueden encontrar y evaluar soluciones antes de la ejecución. En entornos dinámicamente desconocidos, la estrategia a menudo necesita revisarse en línea. Los modelos y las políticas deben adaptarse. Las soluciones suelen recurrir a procesos iterativos de ensayo y error, comunes en la inteligencia artificial . Estos incluyen la programación dinámica , el aprendizaje por refuerzo y la optimización combinatoria . Los lenguajes utilizados para describir la planificación y la programación se denominan a menudo lenguajes de acción .
Descripción general
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 consiste en 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 las suposiciones simplificadoras empleadas. Se pueden identificar varias clases de problemas de planificación según las propiedades que presenten en diversas dimensiones.
- ¿Las acciones son deterministas o no deterministas? En el caso de las acciones no deterministas, ¿se dispone de las probabilidades asociadas?
- ¿Las variables de estado son discretas o continuas? Si son discretas, ¿tienen solo un número finito de valores posibles?
- ¿Se puede observar el estado actual de forma inequívoca? Puede haber observabilidad total y observabilidad parcial.
- ¿Cuántos estados iniciales existen, un número finito o un número arbitrario?
- ¿Las acciones tienen una duración?
- ¿Se pueden realizar varias acciones simultáneamente o solo es posible una a la vez?
- ¿El objetivo de un plan es alcanzar un estado final determinado o maximizar una función de recompensa ?
- ¿Hay un solo agente o varios? ¿Los agentes son cooperativos o egoístas? ¿Cada agente elabora sus propios planes por separado o los planes se elaboran de forma centralizada para todos?
El problema de planificación más simple posible, conocido como el Problema de Planificación Clásico, se determina mediante:
- un estado inicial conocido único,
- acciones sin duración,
- acciones deterministas,
- que solo se puede tomar de uno en uno,
- y un solo agente.
Dado que el estado inicial se conoce sin ambigüedad 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.
Ante acciones no deterministas u otros eventos que escapan al 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) de tiempo discreto son problemas de planificación que incluyen:
- acciones sin duración,
- acciones no deterministas con probabilidades,
- observabilidad completa,
- maximización de una función de recompensa,
- y un solo agente.
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 planificación multiagente , que está estrechamente relacionada con la teoría de juegos .
Planificación independiente del dominio
En la planificación de IA, los planificadores suelen recibir como entrada 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, definido por el estado inicial y el objetivo. Esto contrasta con aquellos planificadores que no especifican un dominio de entrada. Estos planificadores se denominan "independientes del dominio" para enfatizar su capacidad de resolver problemas de planificación en una amplia gama de dominios. Ejemplos típicos de dominios son el apilamiento de bloques, la logística, la gestión de flujos de trabajo y la planificación de tareas robóticas. Por lo tanto, un único planificador independiente del dominio puede utilizarse para resolver problemas de planificación en todos estos dominios. Por otro lado, un planificador de rutas es un ejemplo típico de planificador específico de dominio.
Lenguajes de modelado de dominios de planificación
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 dicha acción. Dado que un conjunto de variables de estado induce un espacio de estados cuyo tamaño es 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 redes jerárquicas de tareas , en el que se proporciona 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.
Algoritmos para la planificación
Planificación clásica
- Búsqueda en el espacio de estados mediante encadenamiento hacia adelante , posiblemente mejorada con heurísticas.
- búsqueda de encadenamiento hacia atrás , posiblemente mejorada mediante el uso de restricciones de estado (ver STRIPS , graphplan ).
- planificación de pedidos parciales
Aprendizaje mediante modelos de acción
El aprendizaje de modelos de acción (a veces abreviado como aprendizaje de acciones) es un área del aprendizaje automático que se ocupa de la creación y modificación del conocimiento de un agente de software sobre los efectos y las precondiciones de las acciones que se pueden ejecutar dentro de su entorno . Este conocimiento se suele representar en un lenguaje de descripción de acciones basado en lógica y se utiliza como entrada para planificadores automatizados .
El aprendizaje de modelos de acción es importante cuando cambian los objetivos. Cuando un agente ha actuado durante un tiempo, puede utilizar su conocimiento acumulado sobre las acciones en el dominio para tomar mejores decisiones. Por lo tanto, el aprendizaje de modelos de acción difiere del aprendizaje por refuerzo . Permite razonar sobre las acciones en lugar de realizar costosos ensayos en el mundo. [ 2 ] El aprendizaje de modelos de acción es una forma de razonamiento inductivo , donde se genera nuevo conocimiento basado en las observaciones del agente .
La motivación habitual para el aprendizaje de modelos de acción radica en que la especificación manual de modelos de acción para planificadores suele ser una tarea difícil, laboriosa y propensa a errores (especialmente en entornos complejos). [ 3 ] [ 4 ] [ 5 ]
Reducción a otros problemas
- reducción al problema de satisfacibilidad proposicional ( satplan ).
- reducción a verificación de modelos : ambos son esencialmente problemas de recorrido de espacios de estados, y el problema de planificación clásico corresponde a una subclase de problemas de verificación de modelos.
Planificación temporal
La planificación temporal puede resolverse con métodos similares a la planificación clásica. La principal diferencia radica en 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 el grado de avance de 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 interviene la incertidumbre y también puede entenderse 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 este tipo de problemas es un tipo de programación que requiere una estrategia de planificación temporal para activar acciones controlables de forma reactiva a medida que se observan eventos inciertos, de modo que se garantice el cumplimiento de todas las restricciones. [ 6 ]
Planificación probabilística
La planificación probabilística puede resolverse con métodos iterativos como la iteración de valor 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 valor definidas para el espacio de creencias en lugar de los estados.
Planificación basada en preferencias
En inteligencia artificial , la planificación basada en preferencias es una forma de planificación y programación automatizada que se centra en generar planes que satisfagan la mayor cantidad posible de preferencias especificadas por el usuario . En muchos ámbitos, una tarea puede realizarse mediante diversas secuencias de acciones (también conocidas como planes). Estos planes pueden variar en calidad: existen muchas maneras de resolver un problema, pero generalmente se prefieren aquellas que son más rentables, rápidas y seguras.
Los planificadores basados en preferencias tienen en cuenta estas preferencias al elaborar un plan para un problema determinado. Algunos ejemplos de software de planificación basado en preferencias son PPLAN [ 7 ] y HTNPlan-P [ 8 ] ( planificación de redes de tareas jerárquicas (HTN) basada en preferencias).
Planificación condicional
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, lo que constituye un plan para el robot. La planificación jerárquica puede compararse con un árbol de comportamiento generado automáticamente . [ 9 ] La desventaja es que un árbol de comportamiento normal no es tan expresivo como un programa informático. Es decir, la notación de un grafo de comportamiento contiene comandos de acción, pero no bucles ni sentencias condicionales (if-then). La planificación condicional supera este obstáculo e introduce una notación elaborada similar a un diagrama de flujo de control , conocido en otros lenguajes de programación como Pascal . Es muy similar a la síntesis de programas , lo que significa que un planificador genera código fuente que puede ser ejecutado por un intérprete. [ 10 ]
Un ejemplo temprano de planificador condicional es “Warplan-C”, que se introdujo a mediados de la década de 1970. [ 11 ] ¿Cuál es la diferencia entre una secuencia normal y un plan complicado, que contiene sentencias if-then? Tiene que ver con la incertidumbre en 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 por adelantado. Por ejemplo, si se detectó un objeto, entonces se ejecuta la acción A; si falta un objeto, entonces se ejecuta la acción B. [ 12 ] Una ventaja importante de la planificación condicional es la capacidad de manejar planes parciales . [ 13 ] Un agente no está obligado a planificar todo de principio a fin, sino que puede dividir el problema en partes . Esto ayuda a reducir el espacio de estados y resuelve problemas mucho más complejos.
Planificación de contingencias
Hablamos de "planificación contingente" cuando el entorno es observable mediante sensores, que pueden ser defectuosos. Se trata, por lo 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, puesto que 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. [ 14 ] 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. [ 15 ] [ 16 ] Un caso particular de planificación contigua está representado por los problemas FOND, por "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 [ 17 ] y 2EXPTIME-completo si el objetivo se especifica con LDLf.
Planificación conforme
La planificación conforme se da cuando el agente desconoce el estado del sistema y no puede realizar observaciones. El agente tiene entonces creencias sobre el mundo real, pero no puede verificarlas mediante acciones de detección, por ejemplo. Estos problemas se resuelven con técnicas similares a las de la planificación clásica, [ 18 ] [ 19 ] 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 planificación conforme es EXPSPACE -completo, [ 20 ] y 2EXPTIME-completo cuando la situación inicial es incierta y existe no determinismo en los resultados de las acciones. [ 16 ]
Despliegue de sistemas de planificación
- El telescopio espacial Hubble utiliza un sistema a corto plazo llamado SPSS y un sistema de planificación a largo plazo llamado Spike .
Véase también
- Lenguaje de descripción de acciones – Lenguaje de programación de robots
- Modelo de actores – Modelo de computación concurrente
- Aplicaciones de la inteligencia artificial
- Problema de satisfacción de restricciones : conjunto de objetos cuyo estado debe satisfacer límites.
- Conferencia Internacional sobre Planificación y Programación Automatizadas – Conferencia sobre Inteligencia Artificial
- Planificación reactiva
- Planificación (informática) – Método mediante el cual se asigna el trabajo.
- Estrategia (teoría de juegos) : Plan completo sobre cómo se comportará un jugador en cada posible situación de juego.
- Liza
Referencias
- ↑ Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Planificación automatizada: teoría y práctica , Morgan Kaufmann , ISBN 1-55860-856-7Archivado del original el 24/08/2009 , consultado el 20/08/2008.
- ↑Error de cita: La referencia con nombre
Action model learning amir2008fue invocada pero nunca definida (consulte la página de ayuda ). - ↑ Callanan, Ethan y De Venezia, Rebecca y Armstrong, Victoria y Paredes, Alison y Chakraborti, Tathagata y Muise, Christian (2022). MACQ: Una visión holística de las técnicas de adquisición de modelos (PDF) . Taller ICAPS sobre ingeniería del conocimiento para la planificación y la programación (KEPS).
{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace ) - ↑ Aineto, Diego y Jiménez Celorrio, Sergio y Onaindia, Eva (2019). "Modelos de acción de aprendizaje con mínima observabilidad" . Inteligencia artificial . 275 : 104– 137. doi : 10.1016/j.artint.2019.05.003 . hdl : 10251/144560 .
{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ) - ↑ Jiménez, Sergio y de la Rosa, Tomás y Fernández, Susana y Fernández, Fernando y Borrajo, Daniel (2012). "Una revisión del aprendizaje automático para la planificación automatizada" . La revisión de la ingeniería del conocimiento . 27 (4): 433– 467. doi : 10.1017/S026988891200001X .
{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ) - ↑ Vidal, Thierry (enero de 1999). "Manejo de contingencias en redes con restricciones temporales: de la consistencia a las controlabilidades". Journal of Experimental & Theoretical Artificial Intelligence . 11 (1): 23--45. Bibcode : 1999JETAI..11...23V . CiteSeerX 10.1.1.107.1065 . doi : 10.1080/095281399146607 .
- ↑ PPLAN , Bienvenu et al.
- ↑ Planificación de HTN con preferencias , Sohrabi et al.
- ↑ Neufeld, Xenija y Mostaghim, Sanaz y Sancho-Pradel, Dario y Brand, Sandy (2017). "Construyendo un planificador: un estudio de los sistemas de planificación utilizados en videojuegos comerciales". IEEE Transactions on Games . IEEE.
{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ) - ↑ Sanelli, Valerio y Cashmore, Michael y Magazzeni, Daniele y Iocchi, Luca (2017). Interacción humano-robot a corto plazo mediante planificación y ejecución condicional . Actas de la Conferencia Internacional sobre Planificación y Programación Automatizadas (ICAPS). Archivado del original el 16 de agosto de 2019. Recuperado el 16 de agosto de 2019 .
{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace ) - ↑ Peot, Mark A y Smith, David E (1992). Planificación no lineal condicional (PDF) . Sistemas de planificación de inteligencia artificial. Elsevier. págs. 189–197 .
{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace ) - ↑ Karlsson, Lars (2001). Planificación progresiva condicional bajo incertidumbre . IJCAI. pp. 431– 438.
- ↑ Liu, Daphne Hao (2008). Un estudio sobre la planificación en agentes inteligentes: de sistemas motivados externamente a sistemas motivados internamente (Informe técnico). Informe técnico TR-2008-936, Departamento de Ciencias de la Computación, Universidad de Rochester. Archivado del original el 15 de marzo de 2023. Recuperado el 16 de agosto de 2019 .
- ↑ Alexandre Albore; Hector Palacios; Hector Geffner (2009). Un enfoque basado en la traducción para la planificación contingente . Conferencia Internacional Conjunta de Inteligencia Artificial (IJCAI). Pasadena, CA: AAAI. Archivado del original el 3 de julio de 2019. Recuperado el 3 de julio de 2019 .
- ↑ Littman, Michael L. (1997). Probabilistic Propositional Planning: Representations and Complexity . Decimocuarta Conferencia Nacional sobre Inteligencia Artificial. MIT Press. págs. 748–754 . Archivado del original el 12 de febrero de 2019. Recuperado el 10 de febrero de 2019 .
- 1 2 Jussi Rintanen (2004). Complejidad de la planificación con observabilidad parcial (PDF) . Conf. Int. Planificación y programación automatizadas. AAAI. Archivado (PDF) del original el 31-10-2020 . Recuperado el 03-07-2019 .
- ↑ De Giacomo, Giuseppe; Rubin, Sasha (2018). Fundamentos teóricos de autómatas de la planificación FOND para objetivos LTLf y LDLf . IJCAI. Archivado del original el 17 de julio de 2018. Recuperado el 17 de julio de 2018 .
- ↑ Palacios, Hector; Geffner, Hector (2009). "Compiling uncertainty away in conformant planning problems with bounded width" . Journal of Artificial Intelligence Research . 35 : 623–675 . arXiv : 1401.3468 . doi : 10.1613/jair.2708 . Archivado del original el 27 de abril de 2020. Consultado el 16 de agosto de 2019 .
- ↑ Albore, Alexandre; Ramírez, Miquel; Geffner, Hector (2011). Heurísticas efectivas y seguimiento de creencias para la planificación con información incompleta . Vigésimo primera Conferencia Internacional sobre Planificación y Programación Automatizadas (ICAPS). Archivado del original el 6 de julio de 2017. Consultado el 16 de agosto de 2019 .
- ↑ Haslum, Patrik; Jonsson, Peter (2000). Algunos resultados sobre la complejidad de la planificación con información incompleta . Lecture Notes in Computer Science. Vol. 1809. Springer Berlin Heidelberg. pp. 308–318 . doi : 10.1007/10720246_24 . ISBN 9783540446576Conferencia
: Avances recientes en la planificación de IA
Lecturas adicionales
- Vlahavas, I. "Planificación y programación" . EETN . Archivado del original el 22 de diciembre de 2013.
Enlaces externos
- Conferencia Internacional sobre Planificación y Programación Automatizadas
- Planificación y programación automatizadas
