Summarization

Agents abandon plans and switch top-level goals for a variety of reasons at run-time such as operator failure, incoming requests for cooperation, resource conflict, and the failure of other agents to abide by previous agreements. This means the execution trace may contain actions that should not be part of learned cooperative procedures. The goal of the summarization process is for agents to remove such actions, while preserving consequential ones.

SUMMARIZE-TRACE, whose pseudo-code is given in Figure 4, removes actions from the execution trace in four passes. The first pass does almost all of the summarization; the underlying justifications for the pruning criteria used during this pass are fairly self-evident. The third pass is really part of the preparation process of updating collective memory. However, removing planner-reconstructible operators at this point during summarization simplifies both the next pass of summarization, which removes communication related to those operators, and the reorganization which precedes preparation.

  

Function SUMMARIZE-TRACE(trace)

  Pass 1: foreach event E with action A in trace
    Remove E from trace if:
      A is a no-op
      A is a failed attempted operator
      A is a refusal or a refused request
      A is an agreement or an agreed-to request,
	 but the request was never accomplished
      A achieved only lowest criticality goals
      A is a WAIT
      A was undone by the subsequent operator
  Pass 2: foreach event E in trace
    Remove E if A was intended to achieve a top-
      level goal which the agent did not achieve
  Pass 3: foreach event E still in trace
    Remove other events still in the trace whose
      actions are planner-reconstructible from A
  Pass 4: foreach event E still in trace
    Remove E if A is an agreement or an agreed-to
      request concerning a removed joint action

Figure 4: Algorithm to summarize traces.

The second summarization pass requires some explanation. This step is designed to weed-out operators that seemed to be useful at the time, but eventually were not. For example, suppose a hand-truck operator (HTO) gets a lifter (L1) to load a box onto a hand-truck, which HTO then pushes to the street and stands up. Suppose further that no lifter agreed to unload the box when it was at the street and HTO eventually pushed the hand-truck containing the box back to the box's original location. At this point, L1 unloads it from the hand-truck, carries it (back) to the street and loads it onto the truck. In this case, HTO's request did not help to achieve the goal and should be removed from the summary.

An example of summarization

The simplest plan that lifters learn that their first-principles planner does not construct is to load a box onto a hand-truck and then later unload it and load it onto a truck at the behest of a hand-truck operator. This chunk can get created from the following snippet of activity involving medium-sized box MBOX3.

First, a high-level description:

1.

Hand-truck operator HTO asks lifter L1 to get MBOX3 onto hand-truck HANDTR2. L1 agrees and does so via lifting and loading the box. L1 next fails in an attempt to lift large box LBOX2 by herself, does nothing for a round since she has no plan, and lifts small box SBOX5 while HTO tilts, pushes to the street, and stands up HANDTR2.

2.

HTO asks L1 to get MBOX3 onto truck TRUCK. L1 agrees, puts SBOX5 back down, moves to the street, unloads the box from the hand-truck and then loads it onto the truck.

L1 records her behavior internally in each round of activity, including information about that round's active goals, cooperation agreements, state of the world, attempted action, reason for attempting the action, and result of the attempt. These internal structures contain too much data to show fully, but the gist of them is clear in the following description of L1's execution trace:

(<agreed to achieve (ON MBOX3 HANDTR2) for HTO>
 <executed (LIFT MBOX3)>
 <executed (LOAD MBOX3 HANDTR2)>
 <failed to (LIFT LBOX2)>
 <no-op>
 <executed (LIFT SBOX5)>
 <agreed to achieve (ON MBOX3 TRUCK1) for HTO>
 <executed (PUT-DOWN SBOX5)>
 <executed (MOVE STREET)>
 <executed (UNLOAD MBOX3 HANDTR2)>
 <executed (LOAD MBOX3 TRUCK1)>)

SUMMARIZE-TRACE reduces L1's activity to:

(<agreed to achieve (ON MBOX3 HANDTR2) for HTO>
 <executed (LOAD MBOX3 HANDTR2)>
 <agreed to achieve (ON MBOX3 TRUCK1) for HTO>
 <executed (LOAD MBOX3 TRUCK1)>)

L1 accomplished both agreements and the corresponding top-level goal (ON MBOX3 TRUCK1), so none of the summarization rules applied to them. Likewise, the two LOADs were left untouched by SUMMARIZE-TRACE.

The other actions in L1's execution trace were removed for varying reasons. The attempted LIFT of the large box was pruned just as any other failed operator would. (LIFT SBOX5) is omitted since it was undone by the subsequent PUT-DOWN operator, which was in turn dropped since it achieved HANDEMPTY, a lowest criticality goal. Lifting, and later unloading, MBOX3 is removed in the third pass of SUMMARIZE-TRACE since they are planner-reconstructible from the precondition (HOLDING MBOX3) of the LOAD operators following them.