Planning And Execution in Incompletely Specified Environments

Robert T. Chien, Steven J. Weissman

Introduction

In the early 1970s, Artificial Intelligence research was largely confined to "toy worlds"—static, predictable environments where every variable was known and nothing changed unless the agent acted. This paper by Chien and Weissman represents a pivotal shift in the field, moving toward the messy, unpredictable reality of flight operations. The authors propose a framework for AI agents capable of planning and acting even when environmental data is incomplete or dynamic.

The Problem of the Closed World

Early planning systems, such as STRIPS and PLANNER, operated under the "Closed World Assumption." These systems assumed a complete model of the environment: the computer knew every relevant fact, and the world remained frozen during the planning process.

Chien and Weissman argue that this assumption is untenable for real-world applications like flight operations. In such domains, data may be missing due to sensor limitations, and external factors—such as weather patterns or the movement of other aircraft—change the state of the world independently of the agent. Under traditional frameworks, a missing piece of data would cause a planner to fail immediately. The authors sought to develop a system that could acknowledge ignorance and proceed by making intelligent assumptions.

Methodology

To address the challenges of incomplete specification, the authors introduced several novel extensions to 1970s-era deduction mechanisms:

1. Criticality Ranking

Building upon the concepts introduced in ABSTRIPS, the system assigns a "criticality rank" to preconditions. This allows the planner to prioritize high-level goals (the "big rocks") while deferring low-level details (the "sand") until later in the process. By focusing on the most vital constraints first, the system avoids the combinatorial explosion that occurs when trying to solve every minor detail simultaneously.

2. Assumption-Based Planning

To prevent the planner from stalling when faced with missing information, the system utilizes four distinct types of assumptions:

  • Low-criticality Assumptions: Assuming a minor detail can be resolved easily at a later stage.
  • Logical Assumptions: Assuming a fact is true if it is shown to be logically consistent across all potential future scenarios.
  • Dominance Assumptions: Assuming a goal is satisfiable if a more complex or constrained version of that goal has already been successfully solved.
  • Linkage Assumptions: Assuming that if a value is subject to change during the planning phase, it will be stabilized or known by the time that specific sub-plan is executed.

3. Interleaved Execution and Monitoring

Rather than generating a rigid, end-to-end plan before taking action, the system generates a "plan outline." It begins execution immediately and employs "demons"—background processes that monitor the environment. These demons watch for new information that might provide shortcuts or necessitate plan revisions, allowing the agent to remain opportunistic.

Key Insights

  • The "Unknown" as a Valid State: Instead of treating missing data as a terminal error, the system treats it as a prompt for information gathering, whether through sensors or human interaction.
  • The Planning-Execution Blur: The authors argue that in dynamic environments, there is no meaningful distinction between planning and execution. Planning is a continuous, adaptive process that occurs in parallel with action.
  • Hierarchical Refinement: By planning across different levels of criticality, the system maintains a manageable computational load, focusing resources on the most impactful decisions.

Results and Impact

The paper describes a functional, architectural integration of planning and execution tailored for computer-aided flight operations. Qualitatively, the system proved more robust than its predecessors because it did not collapse when faced with incomplete models. It produced "general nature" plans—flexible outlines that were filled in with specific details as the situation evolved.

Limitations and Future Work

Despite its advancements, the system had notable limitations. The handling of "unknown" information was initially restricted to a limited set of predicates. Furthermore, the system remained "computer-aided," relying heavily on the pilot's expertise and the system's internal model of human capability. The authors noted that planning for all possible alternatives in a truly dynamic world remained computationally unfeasible, suggesting that future research should incorporate probabilities and cost-benefit analysis directly into the deductive process to better manage uncertainty.

Summary updated

BibTeX
@inproceedings{chien1975planning,
  author = {Robert T. Chien and Steven J. Weissman},
  title = {{Planning And Execution in Incompletely Specified Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1975},
}
Figure