A Planner for Reasoning about Knowledge and Action

Douglas E. AppeltAAAI 1980

Introduction

In the early 1980s, the field of automated planning was dominated by systems like STRIPS and NOAH. While these systems were highly effective at manipulating physical environments—such as moving blocks or navigating hallways—they were fundamentally "mind-blind." They operated under the assumption that all relevant facts were physical and universally accessible to the agent. However, real-world collaboration, particularly when involving natural language communication, requires a robot to reason about propositional attitudes: the internal mental states, beliefs, and knowledge of other agents.

Douglas Appelt’s Knowledge And Modalities Planner (KAMP) was developed to bridge this gap. KAMP represents a pioneering effort to integrate formal modal logic with practical procedural planning, allowing a robot to create multi-agent plans where information is treated as a critical resource and a prerequisite for action.

The Problem of Mental State Reasoning

Standard planners of the era functioned on a world of physical facts, such as At(Robot, Hallway). They lacked the machinery to represent that a human agent might not know a specific fact, or that a robot’s action could be intended solely to change another agent's knowledge rather than the physical state of the world.

For example, if a robot (Rob) needs to assist a human (John) in finding the time, a traditional planner might simply locate a clock and record the time for itself. A knowledge-aware planner, however, must recognize that John lacks the information required to achieve his goal. To help John, Rob must understand "nested" beliefs—knowing what John knows—and realize that providing John with the location of a clock is a valid step that enables John to form and execute his own sub-plan.

Methodology

KAMP utilizes a hybrid architecture that balances the expressive power of formal logic with the computational efficiency required for planning.

1. Possible Worlds Semantics

Drawing on the work of Robert Moore, KAMP employs "possible worlds" semantics to represent knowledge. In this framework, saying "John knows P" implies that in every world John considers possible, P is true. This allows KAMP to distinguish between knowing that an object exists and knowing what or where that object is—a distinction vital for planning information-seeking actions.

2. Meta-Language Translation

Because reasoning directly in modal logic is computationally taxing, KAMP translates complex modal statements into first-order logic. This meta-language approach allows the system to use standard deduction techniques to reason about an agent's knowledge as a property within the world state.

3. Procedural Networks and World States

KAMP adapts the procedural network approach from the NOAH planner. In KAMP, however, each node in the plan network is associated with a specific "world" state. This allows the planner to track the evolution of multiple agents' knowledge bases as actions are performed, ensuring that the preconditions for future actions (both physical and informational) are met.

4. The Efficiency-Logic Tradeoff

To prevent the search space from exploding, KAMP uses a "Plausible Move Generator." This component uses simplified, STRIPS-like action summaries (e.g., an INFORM act results in the hearer knowing a proposition) to quickly suggest potential plan steps. The system then employs its rigorous logical component to verify if these suggested moves are formally sound and actually achieve the desired goal state.

Key Insights: Knowledge as a Precondition

One of Appelt’s central contributions is the formalization of universal knowledge preconditions. KAMP posits that for any action to be executable, an agent must possess a "description" of that action. To "tell John the time," Rob must not only know the time but also know who John is and how to communicate with him. KAMP treats these informational requirements as automatic subgoals for every planned action.

Furthermore, KAMP can plan for others' deductions. It can execute an action whose primary purpose is to trigger a change in another agent's internal logic. By providing a piece of information, the robot can intentionally lead another agent to deduce a new plan, effectively coordinating multi-agent behavior through information sharing.

Evaluation: The Clock Problem

KAMP was evaluated using logical scenarios designed to test multi-agent reasoning, most notably the "Clock Problem." In this scenario, a robot (Rob) and a human (John) are in a room; a clock is located in an adjacent hallway. John wants to know the time but does not know where the clock is. KAMP successfully generated two distinct strategies based on the initial conditions:

  1. Information Sharing: Rob informs John of the clock's location. This changes John’s knowledge state, allowing John to then plan and execute the physical movement to the hallway to read the clock himself.
  2. Direct Assistance: Rob plans to move to the hallway, read the clock, return to the room, and inform John of the specific time.

These results demonstrated KAMP's ability to handle nested knowledge (e.g., "Rob knows that John knows...") and to coordinate actions where one agent's knowledge is a strict precondition for another agent's physical movement.

Limitations and Future Directions

Despite its success, KAMP faced significant challenges regarding computational complexity. The possible-worlds approach is powerful but leads to a rapid expansion of the search space as the chain of inference grows. Appelt noted that future iterations would require more sophisticated pruning criteria to determine which paths of reasoning are worth pursuing.

Additionally, while KAMP was motivated by the needs of natural language processing, the system focused primarily on the planning logic. The author suggested that the next logical step would be the full integration of KAMP with a language generation system capable of translating planned INFORM acts into natural English utterances, such as deciding whether to say "The clock is in the hall" or simply "It's 3:00."

Conclusion

KAMP was a landmark system in AI planning, moving the field beyond simple physical manipulation toward a more nuanced understanding of multi-agent interaction. By treating knowledge as a first-class citizen in the planning process, it laid the groundwork for modern research in human-robot interaction and communicative agents.

Summary updated

BibTeX
@inproceedings{appelt1980planner,
  author = {Douglas E. Appelt},
  title = {{A Planner for Reasoning about Knowledge and Action}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure