Constrained Intelligent Action: Planning Under the Influence of a Master Agent

Eithan Ephrati, Jeffrey S. RosenscheinAAAI 1992

Abstract

This paper investigates the challenge of "non-absolute control" in hierarchical multi-agent systems. It addresses how a subordinate agent, possessing superior local information, should execute a supervisor's goals while minimizing deviation from the supervisor's original intent. By introducing formal metrics—such as the Hausdorff and Shifting distances—to measure plan deviation, the authors provide a framework for agents to exercise intelligent judgment rather than blind obedience.

Introduction: The Problem of Non-Absolute Hierarchy

In traditional AI planning, agents are typically categorized as either "slaves" that follow rigid instructions or "peers" that negotiate as equals. This research identifies a critical middle ground: non-absolute hierarchy. In such systems, a supervisor provides a goal or plan based on a potentially incomplete or outdated world model. The subordinate agent, operating in the field, may discover new information that makes the original plan inefficient or impossible.

Consider a Mars rover receiving a command to collect a sample from a specific region. If the rover encounters an unmapped obstacle, a "slave" agent might fail or waste resources trying to adhere strictly to the path. An intelligent agent must decide how much to deviate from the supervisor's plan to account for its superior local information while still respecting the supervisor's likely intent.

Measuring Plan Deviation

The authors propose that an agent should maintain a model of the supervisor’s Knowledge Base (KB) to predict what plan the supervisor would have desired given the actual state of the world. To select the optimal alternative, the paper introduces several metrics to quantify the "distance" between the agent's proposed plan ($P^a$) and the supervisor's assumed plan ($P^s$).

Outcome and Cost Metrics

  • Cost Difference: A simple comparison of the total resource expenditure between plans.
  • KB Deviation: A measure of how much the final world state resulting from the agent's plan differs from the state expected by the supervisor.
  • Irreversibility: A constraint designed to prevent the agent from consuming or destroying resources that the supervisor is unaware of, thereby protecting "exclusive knowledge" assets.

Geometric Distance Metrics

Since a plan consists of a sequence of states, the authors apply geometric concepts to measure structural deviation:

  • Hausdorff Metric: This measures the maximum distance from any state in the agent's plan to the nearest state in the supervisor's plan. It is particularly effective at preventing "radical exceptions" or bizarre departures from the expected path.
  • Shifting Distance: This metric sums the distances between all corresponding states, measuring the "total effort" required to align the two plans.
  • Dynamic Deviation: This tracks whether the plans diverge or converge as they progress over time.

Experimental Setup: The Slotted Blocks World

To evaluate these metrics, the authors utilize a Slotted Blocks World simulation. This environment consists of numbered slots and blocks of different colors (e.g., Black 'B' and White 'W'). Operations such as moving, painting, or destroying blocks have associated costs, allowing for concrete numerical analysis of plan selection.

Configurations in the Slotted Blocks World simulation used to test plan deviation metrics.

This toy domain demonstrates how different distance metrics result in different plan selections. For instance, a plan that minimizes cost might involve destroying a block that the supervisor intended to use later, whereas a plan minimizing Hausdorff distance would stay closer to the supervisor's envisioned sequence of moves.

Key Insights and Results

The research highlights that there is no "one size fits all" metric for plan deviation. The choice of metric depends on the supervisor's priorities:

  • The Hausdorff metric is ideal for agents that must avoid "weird" or unexpected departures from the path.
  • The Shifting metric is superior when the overall "drift" of the plan is the primary concern.
  • The Cost metric, while straightforward, often overlooks dangerous side effects or violations of the supervisor's implicit intent.

A central "aha" moment in the paper concerns irreversibility. The authors argue that simply minimizing KB deviation can be counterproductive; if an agent knows about a resource the supervisor doesn't, "bringing the KBs closer" might lead the agent to destroy that resource. Protecting exclusive knowledge is therefore a vital constraint.

Limitations and Conclusion

While providing a robust formal framework, the system has limitations. It relies heavily on the agent having an accurate model of the supervisor's knowledge. Furthermore, calculating distances between sets of states in high-dimensional environments is computationally expensive. The authors suggest using "cheap" approximate metrics to prune the search space before applying more rigorous calculations.

Ultimately, by quantifying "deviation," this work provides a formal path for agents to exercise judgment, ensuring that subordinate intelligence enhances rather than undermines hierarchical coordination.

Summary updated

BibTeX
@inproceedings{ephrati1992constrained,
  author = {Eithan Ephrati and Jeffrey S. Rosenschein},
  title = {{Constrained Intelligent Action: Planning Under the Influence of a Master Agent}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure