Planificación de orden parcial

La planificación de orden parcial es un método de planificación automatizada que mantiene un orden parcial entre las acciones y solo lo establece cuando es necesario; es decir, el orden de las acciones es parcial. Además, este método no especifica qué acción se ejecutará primero cuando se procesan dos acciones. Por el contrario, la planificación de orden total mantiene un orden total entre todas las acciones en cada etapa de la planificación. Dado un problema en el que se necesita una secuencia de acciones para alcanzar un objetivo, un plan de orden parcial especifica todas las acciones que deben realizarse, pero solo establece un orden entre ellas cuando es necesario.

Consideremos la siguiente situación: una persona debe recorrer un circuito de obstáculos desde el inicio hasta el final. El circuito consta de un puente, un balancín y un columpio. El puente debe cruzarse antes de poder alcanzar el balancín y el columpio. Una vez alcanzados, se puede recorrer el balancín y el columpio en cualquier orden, tras lo cual se puede llegar al final. En un plan de orden parcial, el orden entre estos obstáculos se especifica solo cuando es necesario. Primero se debe cruzar el puente. Segundo, se puede recorrer el balancín o el columpio. Tercero, se puede recorrer el obstáculo restante. Finalmente, se puede llegar al final. La eficiencia de la planificación de orden parcial se basa en el principio de mínimo compromiso .

Plan de pedido parcial

Un plan de orden parcial o plan parcial es un plan que especifica todas las acciones que deben realizarse, pero solo especifica el orden entre las acciones cuando es necesario. Es el resultado de un planificador de orden parcial. Un plan de orden parcial consta de cuatro componentes:

Un conjunto de acciones (también conocidas como operadores ).
Un orden parcial para las acciones. Especifica las condiciones sobre el orden de algunas acciones.
Un conjunto de vínculos causales . Especifica qué acciones cumplen qué precondiciones de otras acciones. Alternativamente, un conjunto de relaciones entre las variables de las acciones.
Un conjunto de precondiciones abiertas . Especifica qué precondiciones no se cumplen con ninguna acción en el plan de orden parcial.

Para mantener lo más abiertas posible las posibles secuencias de acciones, el conjunto de condiciones de orden y vínculos causales debe ser lo más pequeño posible.

Un plan es una solución si el conjunto de precondiciones abiertas está vacío.

La linealización de un plan de órdenes parcial es un plan de órdenes total derivado del plan de órdenes parcial en cuestión; en otras palabras, ambos planes de órdenes constan de las mismas acciones, siendo el orden en la linealización una extensión lineal del orden parcial en el plan de órdenes parcial original.

Ejemplo

Por ejemplo, un plan para hornear un pastel podría comenzar así:

ve a la tienda
conseguir huevos; conseguir harina; conseguir leche
pagar por todos los bienes
ve a la cocina

Este es un plan parcial porque no se especifica el orden en que se deben encontrar los huevos, la harina y la leche; el agente puede recorrer la tienda de forma reactiva acumulando todos los artículos de su lista de compras hasta que la lista esté completa.

Planificador de pedidos parciales

Un planificador de orden parcial es un algoritmo o programa que construye un plan de orden parcial y busca una solución. La entrada es la descripción del problema, que consiste en descripciones del estado inicial , el objetivo y las posibles acciones .

El problema puede interpretarse como un problema de búsqueda donde el conjunto de posibles planes de orden parcial constituye el espacio de búsqueda. El estado inicial sería el plan con precondiciones abiertas iguales a las condiciones objetivo. El estado final sería cualquier plan sin precondiciones abiertas, es decir, una solución.

El estado inicial representa las condiciones de partida y puede considerarse como las precondiciones para la tarea en cuestión. Para la tarea de poner la mesa, el estado inicial podría ser una mesa vacía. El objetivo es simplemente la acción final que debe realizarse, por ejemplo, poner la mesa. Los operadores del algoritmo son las acciones mediante las cuales se realiza la tarea. En este ejemplo, puede haber dos operadores: extender (mantel) y colocar (vasos, platos y cubiertos).

Planificar el espacio

El espacio de planificación del algoritmo está restringido entre su inicio y su finalización. El algoritmo comienza produciendo el estado inicial y finaliza cuando se han alcanzado todas las partes del objetivo. En el ejemplo de la preparación de una mesa, existen dos tipos de acciones que deben considerarse: los operadores de "sacar" y "colocar". También existen cuatro operadores sin resolver: Acción 1, colocar mantel; Acción 2, sacar platos; Acción 3, sacar cubiertos; y Acción 4, sacar vasos. Sin embargo, surge un problema si las Acciones 2, 3 o 4 se ejecutan antes que la Acción 1. Este problema radica en que la condición previa para el inicio del algoritmo no se cumplirá, ya que la mesa ya no estará despejada. Por lo tanto, existen restricciones que deben agregarse al algoritmo para obligar a que las Acciones 2, 3 y 4 se ejecuten después de la Acción 1. Una vez completados estos pasos, el algoritmo finalizará y el objetivo se habrá cumplido.

Amenazas

Como se observa en el algoritmo presentado anteriormente, la planificación de orden parcial puede encontrar ciertas amenazas, es decir, ordenaciones que amenazan con romper acciones conectadas, lo que podría destruir todo el plan. Hay dos maneras de resolver las amenazas:

La promoción ordena la posible amenaza después de la conexión que amenaza. La degradación ordena la posible amenaza antes de la conexión que amenaza.

Los algoritmos de planificación de orden parcial son conocidos por ser tanto sólidos como completos, entendiéndose por sólidos el ordenamiento total del algoritmo y por completo la capacidad de encontrar una solución, dado que dicha solución existe.

Planificación de pedidos parciales frente a planificación de pedidos totales

La planificación de orden parcial es lo opuesto a la planificación de orden total , en la que las acciones se secuencian simultáneamente para toda la tarea. Surge la pregunta cuando se tienen dos procesos en competencia: ¿cuál es mejor? Anthony Barret y Daniel Weld argumentaron en su libro de 1993 que la planificación de orden parcial es superior a la de orden total , ya que es más rápida y, por lo tanto, más eficiente. Probaron esta teoría utilizando la taxonomía de Korf de colecciones de subobjetivos , en la que descubrieron que la planificación de orden parcial funciona mejor porque produce una serializabilidad más trivial que la planificación de orden total . La serializabilidad trivial facilita la capacidad del planificador para actuar rápidamente al tratar con objetivos que contienen subobjetivos. Los planificadores actúan más lentamente al tratar con subobjetivos laboriosamente serializables o no serializables . El factor determinante que hace que un subobjetivo sea trivial o laboriosamente serializable es el espacio de búsqueda de los diferentes planes. Descubrieron que la planificación de orden parcial es más eficaz para encontrar la ruta más rápida y, por lo tanto, es el tipo de planificación más eficiente de los dos principales.

La anomalía de Sussman

Se sabe que los planes de orden parcial resuelven de forma sencilla y óptima la anomalía de Sussman . El uso de este tipo de sistema de planificación incremental resuelve este problema de manera rápida y eficiente. Esto fue resultado de la consolidación de la planificación de orden parcial como un sistema de planificación eficiente.

Desventajas de la planificación de pedidos parciales

Una desventaja de este tipo de sistema de planificación es que requiere mucha más potencia computacional por nodo. Este mayor coste por nodo se debe a que el algoritmo de planificación de orden parcial es más complejo que otros. Esto tiene importantes implicaciones para la inteligencia artificial . Al programar un robot para realizar una tarea específica, el creador debe tener en cuenta la energía necesaria. Si bien un plan de orden parcial puede ser más rápido, su coste energético para el robot podría no compensarse. El creador debe considerar y sopesar estas dos opciones para construir un robot eficiente.

Referencias

Inteligencia artificial: un enfoque moderno, por Stuart Russell y Peter Norvig.
Introducción a la planificación de mínimo compromiso por Daniel Weld
Kambhampati, S., Knoblock, CA, Yang, Q. (1994). Planning as Refinement Search: A Unified Framework for Evaluating Design Tradeoffs in Partial-Order Planning. Elsevier Science.
Poole, D., Mackworth, A. (2010). Planificación de orden parcial en inteligencia artificial: Fundamentos de agentes computacionales. Cambridge University Press.
Dyer, CR “Planificación de orden parcial (Capítulo 11).”(2003) CS 540. Universidad de Wisconsin-Madison. Madison, Wisconsin.
Barrett, A., y Weld, D. (1993). Planificación de orden parcial: evaluación de posibles ganancias de eficiencia. Universidad de Washington: Departamento de Ciencias de la Computación e Ingeniería. Notas .
Simmons, Reid. (2001). “Planificación, ejecución y aprendizaje 1. Planificación de orden parcial”. Universidad Carnegie Mellon. Pittsburgh. Notas.
http://pdf.aminer.org/000/744/302/partial_order_planning_evaluating_possible_efficiency_gains.pdf
http://pdf.aminer.org/000/037/660/decomposition_and_causality_in_partial_order_planning.pdf
http://dl.acm.org/citation.cfm?id=1867345
http://arxiv.org/pdf/1106.0249.pdf
http://www.grastien.net/ban/teaching/06-planning4.pdf