3.9 Descripción formal de operadores mezclables

Dado un conjunto de metas a alcanzar, un plan  es un conjunto de operadores (acciones) parcialmente ordenado, donde cada operador  es representado por precondiciones P y efectos E, los cuales por simplicidad se asume que son conjuntos de literales (sentencias atómicas positivas o negativas). Ninguna de las precondiciones del operador o su efecto pueden contener al mismo tiempo una literal o su negación. Un plan  puede ser representado como una gráfica  = (O, B) donde los vértices O son el conjunto de operadores en  y las aristas B son el conjunto de relaciones de precedencia en . También se asume que dos operadores especiales existen en cada plan  que representan los estados iniciales y estados de meta en . El operador de estado inicial I precede a los otros operadores en  y el operador de estado meta G es precedido por todos los otros operadores. El operador de estado inicial I tiene un conjunto vacío de precondiciones y tiene como efectos el conjunto de condiciones iniciales. De manera similar el operador de estado meta G tiene un conjunto vacío de poscondiciones y tiene como sus precondiciones las condiciones de meta a ser alcanzadas.

Se asume que cada operador  tiene un costo asociado costo(), y que el costo para un plan , denotado como costo(), es la suma de los costos de los operadores en .

En un plan de orden parcial, el operador  necesariamente precede a , si  precede a  bajo cada orden total consistente del plan. Se usa el símbolo ≺ para denotar precedencia necesaria en el orden parcial de .

Se asume que el plan  se justifica debido a que cada operador en  es útil en establecer algunas precondiciones de otros operadores o los estados de meta deseados. El operador  necesariamente establece una precondición p para un operador , denotado por Establece(, , p) si, y sólo si, p es una precondición de  y un efecto de  y no necesariamente un operador entre  y  tienen p o ¬p como efecto (Yang 97a).

Debido a que los operadores en la integración de una meta de la solución bajo el modelo MeCePCA necesitan mezclarse o eliminarse, se describen las condiciones para realizar estas operaciones.

3.9.1 Concepto de operadores mezclables

Para un plan dado o propuesto, existen algunos operadores en el plan que se pueden agrupar y remplazar o complementar por un operador menos costoso o bien por un conjunto de operadores más descriptivo que alcance los mismos efectos útiles de los operadores agrupados. En tal caso se dice que los operadores son mezclables. En seguida se formaliza este concepto.

Empezaremos por definir que los operadores en un plan pueden agruparse. Un conjunto de operadores  en un plan  = (O, B) induce un subplan (, B) dentro del plan , donde B es un subconjunto máximo de B que son relaciones en . Los operadores en  pueden ser agrupados si, y sólo si, ningún otro operador fuera de  está necesariamente entre cualquier par en . Más precisamente

,  ,    – , tal que ≺ ≺. (4.3)

Sea  un subplan de  = (O, B) inducido por , donde  es un conjunto de operadores que pueden ser agrupados. Considere el comportamiento colectivo de  en . Algunos efectos de los operadores en  son útiles en , debido a que ellos establecen las precondiciones de algunos otros operadores en  que están fuera de  o de las metas directamente. Otros efectos son: efectos laterales de los operadores o son usados para alcanzar las precondiciones de los operadores en . Nótese que  también puede tener un sólo operador. Usamos la función Efectos-Útiles (,) para denotar el conjunto de todos los efectos útiles de los operadores en . Asimismo, usamos la función Red-de-Precondiciones (,) para denotar el conjunto de todas las precondiciones de los operadores en  no alcanzadas por cualquiera de los operadores en . Más formalmente,

Efectos-Útiles(,) = U {e | e  E and   (O - ) tal que Establece(, , e) } (4.4)

Red-de-Precondiciones (,) = U {p  P |   (O - ) tal que Establece(, , p) }

(4.5)

Para dar una definición precisa para la mezcla de planes, un conjunto  de operadores es mezclable en un plan  = (O, B) si, y sólo si, B', , donde B´ es un conjunto de relaciones de precedencia en , y  es un operador, tal que

( es un plan tentativo, analizable a partir de que existe una primera aportación u operador por parte de un agente).

1. puede ser agrupado dentro del plan  o puede ser parte de un sub-plan tomado de cualquier meta de las experiencias de agentes.

2.BUB' es consistente y en un plan ' = (O, B U B')

P  Red Precondiciones(,'), y

Efectos Útiles (,')  E

Esto es los operadores  pueden ser usados para alcanzar todos los efectos

útiles de los operadores en  mientras requiere solamente un subconjunto de

sus precondiciones, después las restricciones de precedencia B' son

impuestas en el plan .

Además  { Acciones (Metas Iguales (Experiencias (Agentes))}

3. {costo() < costo()}   es consensuado (es decir   (O-) )

4 Si no existen acciones anteriores a  se toma como:

 = min ID  Acciones   (Experiencias (Agentes))}

5.-.  {SE}   {IG}    ES. Donde SE = Sesgos, IG = Acciones iguales. y ES = conjunto de estados de la meta

6. El conjunto  es tomado de las experiencias de cada agente, lo cual implica, analizar los pasos 1 a 5 por cada conjunto  mezclable.

Figura 19. Modelo de composición de operadores mezclables.

El operador  es llamado un operador mezclable de  en el plan  y denotado por

 = merge ()

(o simplemente merge() si es claro que se trata del plan ).

Ahora se explica por qué el conjunto de relaciones de precedencias B' es necesario en la definición de arriba.

Recordar que el conjunto de operadores en  puede ser agrupado. Dependiendo de diferentes relaciones de precedencia (es decir B') impuestas sobre, el conjunto  de operadores requerirá diferentes conjuntos de precondiciones globales para ser alcanzadas por los operadores fuera de . Por tanto una opción diferente de B' puede dar surgimiento a un operador mezclable diferente  . Seleccionamos el operador mínimo en costo o el más descriptivo para ser nuestro operador mezclable. Las precondiciones y efectos de los dos operadores están dados en la tabla 1. Las opciones en  se mencionan en seguida:

Opción 1: B' = {1 ≺ 2}. Entonces 1 alcanza la precondición q1 de 2. Por lo tanto la Red-de-Precondiciones de  debe ser {q1}.

Opción 2: B' = {2 ≺ 1}. Entonces 2 alcanza la precondición q2 de 1. Por lo tanto la Red-de-Precondiciones de  debe ser {q2}.

En cada opción de arriba el conjunto de precondiciones es diferente a partir de la otra opción. Así que cada opción de B' puede resultar en un operador  mezclable diferente.

En este caso, el del costo más bajo es un operador mezclable.

Operador Precondición Efectos

1 q1 p1, q2

2 q2 p2, q1

Tabla 2. Definición de operador

La definición para mezclar un operador claramente cubre los ejemplos dados

En seguida se describen un ejemplo en el que se utiliza la descripción de acciones mediante el lenguaje de acciones diseñado por Pednault (Pednault 88), en el cual se describe mediante fórmulas de primer orden, las acciones. El predicado corresponde a la acción y los términos a los argumentos.

Para describir los planes se usará el formato:

Plan (fórmula de primer orden)1 ≺ (fórmula de primer orden)2 ≺ (fórmula de primer orden)3

Meta: condiciones del modelo del mundo

Lista de condiciones

Operadores: Precondiciones

lista de condiciones del modelo del mundo

Efectos

lista de condiciones del modelo del mundo