Redundant Information Gathering

The problem of redundant information gathering is best illustrated by a simple example. Suppose that we ask a UNIX agent to find out whether paper.tex is in the directory /tex, and that when it executes ls -a, the agent discovers that the file is not there. Unless it knew that ls -a has provided exhaustive information about the contents of the directory, the agent would backtrack and consider alternative ways of satisfying the goal, such as executing ls paper.tex or find in the directory, not realizing that these information-gathering actions will never succeed. In general, once any exhaustive information gathering action is successfully executed, additional information gathering actions are redundant.

The magnitude of the redundant sensing problem should not be underestimated (see Section 5 for empirical measurements). Furthermore, the problem of redundant sensing is both domain and planner independent; When trying alternative ways of satisfying a goal, a planner is forced to consider every sensory action at its disposal. Since each action has preconditions, and there are multiple ways of achieving these preconditions, the amount of wasted work can increase exponentially with the length of the information-gathering plan - unless the planner has some criterion for deciding which actions will not yield new information.

Fortunately, LCW is just that: an agent should not execute, or plan to execute, observational actions (or actions in service of observational actions) to support a goal when it has LCW on that goal. In fact, a single LCW sentence can service a wide range of goals. For example, LCW(parent.dir(,/tex)), which results from executing ls in /tex, indicates that XII knows all the files in /tex. Thus, it can satisfy any goal of the form ``Find out whether some file is in /tex'' by examining its world model - no information gathering is necessary. In addition, XII can combine LCW sentences to avoid redundant information gathering on composite goals. For example, if XII knows all the files owned by Smith, and all the files in /tex, then it can satisfy the conjunctive goal ``Give me all the files in /tex that are owned by Smith'' by consulting its model.

XII utilizes LCW in three ways:

• Execution pruning: when XII is about to execute an observational step which only supports links labeled with goals ,..., , XII checks whether holds for all . If so, is redundant and XII does not execute it. Instead, it replaces all links from with links from the model (), since any information that could be obtained by executing is already recorded in . This simple test prevents XII from executing some redundant information gathering steps. However, XII might still do redundant planning (and execution!) to satisfy 's preconditions, and the preconditions' preconditions, etc.

• Option pruning: to address this problem, XII tests for LCW when it computes the set of actions that could potentially support a goal . If LCW() holds, XII can omit observational actions from the set.

• Post hoc pruning: XII may gain LCW() after is computed (so option pruning did not apply) but considerably before any of the steps in are about to be executed (so execution pruning is not yet applicable). This occurs when executing an action yields LCW(), or when a binding constraint is asserted that constrains one or more of the variables in . For instance, XII may not have LCW(parent.dir(,)), but once is instantiated to, say, /tex, LCW(parent.dir(,/tex)) can result in significant pruning.

In concert, these pruning techniques are surprisingly powerful, as demonstrated in the next section.