La planificación de orden parcial es un enfoque de la planificación automatizada que mantiene un orden parcial entre las acciones y solo compromete el orden entre las acciones cuando es necesario, es decir, el orden de las acciones es parcial. Además, esta planificación no especifica qué acción se realizará 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 lograr un objetivo, un plan de orden parcial especifica todas las acciones que se deben realizar, pero especifica un orden entre las acciones solo cuando es necesario.
Consideremos la siguiente situación: una persona debe viajar desde el inicio hasta el final de una pista de obstáculos. La pista está compuesta por un puente, un balancín y un columpio. El puente debe atravesarse antes de poder alcanzar el balancín y el columpio. Una vez alcanzados, el balancín y el columpio pueden atravesarse en cualquier orden, después de 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. El puente debe atravesarse primero. Segundo, se puede atravesar el balancín o el columpio. Tercero, se puede atravesar el obstáculo restante. Luego se puede atravesar el final. La planificación de orden parcial se basa en el principio del mínimo compromiso para su eficiencia.
Un plan de orden parcial o plan parcial es un plan que especifica todas las acciones que se deben realizar, pero solo especifica el orden entre acciones cuando es necesario. Es el resultado de un planificador de orden parcial. Un plan de orden parcial consta de cuatro componentes:
Para mantener los posibles órdenes de las acciones lo más abiertos posible, 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 condiciones previas abiertas está vacío.
Una linealización de un plan de orden parcial es un plan de orden total derivado del plan de orden parcial particular; en otras palabras, ambos planes de orden constan de las mismas acciones, y la orden en la linealización es una extensión lineal de la orden parcial en el plan de orden parcial original.
Por ejemplo, un plan para hornear un pastel podría comenzar:
Este es un plan parcial porque no se especifica el orden para encontrar huevos, harina y leche, el agente puede deambular por la tienda acumulando reactivamente todos los artículos de su lista de compras hasta completar la lista.
Un planificador de orden parcial es un algoritmo o programa que construirá un plan de orden parcial y buscará una solución. La entrada es la descripción del problema, que consta de 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 es el espacio de búsqueda. El estado inicial sería el plan con las 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 son las condiciones iniciales y se puede considerar como las condiciones previas a la tarea en cuestión. En el caso de una tarea de poner la mesa, el estado inicial podría ser una mesa despejada. El objetivo es simplemente la acción final que se debe realizar, por ejemplo, poner la mesa. Los operadores del algoritmo son las acciones mediante las cuales se realiza la tarea. Para este ejemplo, puede haber dos operadores: poner (mantel) y colocar (vasos, platos y cubiertos).
El espacio de planificación del algoritmo está restringido entre su inicio y su fin. El algoritmo comienza, produciendo el estado inicial y termina cuando se han logrado todas las partes del objetivo. En el ejemplo de la configuración de una mesa, existen dos tipos de acciones que deben abordarse: los operadores poner y colocar. También existen cuatro operadores sin resolver: Acción 1, poner mantel, Acción 2, poner (platos), Acción 3, poner (cubiertos) y Acción 4, poner (vasos). Sin embargo, surge una amenaza si la Acción 2, 3 o 4 viene antes de la Acción 1. Esta amenaza es que la condición previa para el inicio del algoritmo no se satisfaga, ya que la mesa ya no estará vacía. Por lo tanto, existen restricciones que deben agregarse al algoritmo que fuerzan a las Acciones 2, 3 y 4 a venir después de la Acción 1. Una vez que se completen estos pasos, el algoritmo terminará y se habrá completado el objetivo.
Como se ve en el algoritmo presentado anteriormente, la planificación de orden parcial puede encontrarse con ciertas amenazas, es decir, ordenamientos que amenazan con romper acciones conectadas, destruyendo así potencialmente todo el plan. Hay dos formas 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 sólidos y completos; lo sólido se define como el ordenamiento total del algoritmo y lo completo se define como la capacidad de encontrar una solución, dado que de hecho existe una solución.
La planificación de orden parcial es lo opuesto a la planificación de orden total , en la que las acciones se secuencian todas a la vez y para la totalidad de la tarea en cuestión. La pregunta que surge cuando uno tiene dos procesos en competencia, ¿cuál es mejor? Anthony Barret y Daniel Weld han argumentado en su libro de 1993, que la planificación de orden parcial es superior a la planificación 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 encontraron que la planificación de orden parcial funciona mejor porque produce una serialización más trivial que la planificación de orden total . La serialización trivial facilita la capacidad de un planificador para actuar rápidamente cuando se trata de objetivos que contienen subobjetivos. Los planificadores actúan más lentamente cuando tratan 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 diferentes planes. Descubrieron que la planificación de orden parcial es más adecuada para encontrar el camino más rápido y, por lo tanto, es la más eficiente de estos dos tipos principales de planificación.
Se sabe que los planes de orden parcial resuelven de manera fácil 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. Este fue el resultado de la planificación de orden parcial que consolidó su lugar como un sistema de planificación eficiente.
Una desventaja de este tipo de sistema de planificación es que requiere mucha más potencia computacional para cada nodo. Este mayor costo por nodo se debe a que el algoritmo de planificación de orden parcial es más complejo que otros, lo que tiene importantes implicaciones para la inteligencia artificial . Al codificar un robot para que realice una determinada tarea, el creador debe tener en cuenta la cantidad de energía que se necesita. Aunque un plan de orden parcial puede ser más rápido, es posible que no valga la pena el costo energético del robot. El creador debe conocer y sopesar estas dos opciones para construir un robot eficiente.