La planificación de orden parcial es un enfoque de la planificación automatizada que mantiene un orden parcial entre acciones y solo confirma el orden entre acciones cuando se ve obligado a ello, es decir, el orden de las acciones es parcial. Además, esta planificación no especifica qué acción saldrá primero cuando se procesan dos acciones. Por el contrario, la planificación de pedidos totales mantiene un orden total entre todas las acciones en cada etapa de la planificación. Dado un problema en el que se requiere alguna secuencia de acciones para lograr una meta, un plan de orden parcial especifica todas las acciones que deben tomarse, pero especifica un orden entre las acciones solo cuando sea necesario.
Considere la siguiente situación: una persona debe viajar desde el principio hasta el final de una carrera de obstáculos. Esta carrera de obstáculos se compone de un puente, un balancín y un columpio. El puente debe ser atravesado antes de que se pueda alcanzar el balancín y el columpio. Una vez que se alcanza, el balancín y el columpio se pueden atravesar 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. Primero se debe atravesar el puente. En segundo lugar, se puede atravesar el balancín o el columpio. En tercer lugar, se puede atravesar el obstáculo restante. Entonces se puede atravesar el final. La planificación de orden parcial se basa en el Principio de Mínimo Compromiso para su eficiencia.
Plan de orden parcial
Un plan de orden parcial o un plan parcial es un plan que especifica todas las acciones que deben tomarse, pero solo especifica el orden entre las acciones cuando es necesario. Es el resultado de un planificador de orden parcial. Un plan de pedido parcial consta de cuatro componentes:
- Un conjunto de acciones (también conocidas como operadores ).
- Un orden parcial de las acciones. Especifica las condiciones sobre el orden de algunas acciones.
- Un conjunto de vínculos causales . Especifica qué acciones cumplen qué condiciones previas de otras acciones. Alternativamente, un conjunto de enlaces entre las variables en acciones.
- Un conjunto de condiciones previas abiertas . Especifica qué condiciones previas no se cumplen con ninguna acción en el plan de pedido parcial.
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 reducido posible.
Un plan es una solución si el conjunto de condiciones previas abiertas está vacío.
Una linealización de un plan de pedido parcial es un plan de pedido total derivado del plan de pedido parcial particular; en otras palabras, ambos planes de orden consisten en las mismas acciones, siendo el orden en la linealización una extensión lineal del orden parcial en el plan de orden parcial original.
Ejemplo
Por ejemplo, un plan para hornear un pastel podría comenzar:
- ve a la tienda
- conseguir huevos; conseguir harina obtener leche
- pagar todos los bienes
- ve a la cocina
Este es un plan parcial porque no se especifica el orden de búsqueda de 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.
Planificador de pedidos parciales
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 se puede interpretar 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 condiciones previas abiertas iguales a las condiciones de la meta. El estado final sería cualquier plan sin condiciones previas abiertas, es decir, una solución.
El estado inicial son las condiciones iniciales y se puede considerar como las condiciones previas para la tarea en cuestión. Para una tarea de poner la mesa, el estado inicial podría ser una mesa clara. 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. Para este ejemplo, puede haber dos operadores: colocar (mantel) y colocar (vasos, platos y cubiertos).
Planificar el espacio
El espacio del plan del algoritmo está restringido entre su inicio y su finalización. El algoritmo comienza, produce el estado inicial y finaliza cuando se han logrado todas las partes del objetivo. En el ejemplo de poner una mesa, hay dos tipos de acciones que deben abordarse: los operadores de salida y los operadores laicos. También hay cuatro operadores sin resolver: Acción 1, mantel, Acción 2, Salida (platos), Acción 3, Salida (cubiertos) y Acción 4, Salida (vasos). Sin embargo, existe una amenaza que surge 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 cumplirá ya que la tabla ya no estará clara. Por lo tanto, hay restricciones que deben agregarse al algoritmo que obligan a las Acciones 2, 3 y 4 a ir después de la Acción 1. Una vez que se completen estos pasos, el algoritmo finalizará y la meta se habrá completado.
Amenazas
Como se ve en el algoritmo presentado anteriormente, la planificación de orden parcial puede encontrar ciertas amenazas, es decir, órdenes 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. Demotion 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, y el sonido se define como el orden total del algoritmo y el completo se define como la capacidad de encontrar una solución, dado que una solución de hecho existe.
Planificación de pedidos parciales frente a 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 todas a la vez y para la totalidad de la tarea en cuestión. La pregunta 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 desempeñarse rápidamente cuando se trata de objetivos que contienen subobjetivos. Los planificadores funcionan más lentamente cuando se trata de subobjetivos laboriosamente serializables o no serializables . El factor determinante que hace trivial o laboriosamente serializable un subobjetivo es el espacio de búsqueda de diferentes planos. Descubrieron que la planificación de orden parcial es más hábil 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.
La anomalía de Sussman
Se sabe que los planes de orden parcial resuelven fácil y óptimamente 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 el resultado de la planificación de pedidos parciales que solidificó su lugar como un sistema de planificación eficiente.
Desventajas de la planificación de pedidos parciales
Un inconveniente 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 para la planificación de pedidos parciales es más complejo que otros. Esto tiene importantes implicaciones en la inteligencia artificial . Al codificar un robot para realizar una determinada tarea, el creador debe tener en cuenta cuánta energía se necesita. Aunque un plan de pedido parcial puede ser más rápido, puede que no valga la pena el costo de energía del robot. El creador debe conocer y sopesar estas dos opciones para construir un robot eficiente.
Referencias
- Inteligencia artificial: un enfoque moderno por Stuart Russell, Peter Norvig
- Una introducción a la planificación de compromiso mínimo por Daniel Weld
- Kambhampati, S., Knoblock, CA, Yang, Q. (1994). Planificación como búsqueda de refinamiento: un marco unificado para evaluar las compensaciones de diseño en la planificación de orden parcial. Ciencia de Elsevier.
- Poole, D., Mackworth, A. (2010). Planificación de orden parcial en la inteligencia artificial Fundamentos de agentes computacionales. Prensa de la Universidad de Cambridge.
- 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 pedidos parciales: evaluación de posibles ganancias de eficiencia. Universidad de Washington: Departamento de Ingeniería y Ciencias de la Computación. Notas .
- Simmons, Reid. (2001). "Planificación, ejecución y aprendizaje 1. Planificación de pedidos parciales". Universidad de 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