Abstract
In classical AI planning, agents often rely on generalized plans to achieve goals efficiently. However, these plans typically guarantee the final state rather than the safety of intermediate steps. This paper explores the formal validation of such plans when new, situational constraints are introduced. We compare two fundamental strategies—"Prove-Ahead" (pre-calculating safety via regression) and "Prove-As-You-Go" (step-by-step verification)—and analyze their relative merits in environments with incomplete information.
Introduction
Autonomous agents frequently utilize "generalized plans" or macro-operators to streamline goal achievement. While these plans are robust for reaching a target state, they often lack the flexibility to account for dynamic or temporary constraints added after the plan's inception. For instance, a robot might have a standard procedure for navigating a facility, but a new safety rule might prohibit entering specific zones under certain conditions. Validating that a plan remains safe throughout its execution, rather than just at its conclusion, is critical for reliable autonomous behavior.
The Challenge of Intermediate Constraints
The core problem lies in ensuring that every intermediate state in a plan satisfies a set of constraints. Consider a robot, Robbie, with a standard plan to quench thirst.
If a new constraint is introduced—such as "do not enter the kitchen if it is currently being cleaned"—the standard validation of the goal (thirst quenched) is insufficient. The agent must verify that the go to kitchen action does not violate the new constraint given the current state of the world. This is particularly challenging in environments where the agent's knowledge base (KB) is incomplete.
Methodology
The paper formalizes the validation process using first-order logic and situation calculus, identifying two primary paradigms:
1. Prove-Ahead (Regression-Based)
This approach involves "moving the constraint backward" through the plan's operators using regression. By doing so, the agent generates a set of new preconditions for the initial state. If the initial state satisfies these regressed preconditions, the entire plan is guaranteed to be safe regarding the new constraint. This method is advantageous for constraints that are checked frequently across different plans, as the regressed preconditions can be amortized over many executions.
2. Prove-As-You-Go (Step-by-Step)
In this paradigm, the agent performs a step-by-step verification. For each operator in the plan, the agent attempts to prove that the constraint holds in the resulting state, assuming it held in the previous state. This method can leverage "state information" that becomes available during execution (e.g., sensor data), which might not have been predictable during a pre-calculation phase.
Comparative Analysis
While both methods share the same theoretical computational complexity, their practical performance varies based on the specificity of the agent's knowledge:
- Information Advantage: "Prove-As-You-Go" is often more effective in specific scenarios because it utilizes real-time state information. It is simpler to verify a constraint using current data (like a speedometer reading) than to derive a general proof covering all possible conditions.
- Search Focus: "Prove-As-You-Go" focuses only on states that actually occur during plan execution. In contrast, "Prove-Ahead" may expend resources checking potential violations in states that the plan never reaches.
- The Two-Round Penalty: "Prove-Ahead" often experiences a delay in detecting failures because it requires two rounds of logic: first regressing the constraint and then checking the resulting preconditions against the world.
- Explanation and Tagging: "Prove-Ahead" makes it more difficult for an agent to explain why a plan was rejected. Because constraints are merged into complex preconditions, identifying the specific rule that caused a failure requires a more sophisticated "second-order" tagging system.
Conclusion
The choice between "Prove-Ahead" and "Prove-As-You-Go" depends on the operational context. While "Prove-Ahead" offers benefits for frequently reused operators, "Prove-As-You-Go" is generally more efficient and adaptable to real-time information. Future research should address more complex constraints involving state transformations and investigate heuristic methods for prioritizing constraint checks based on their perceived importance or likelihood of violation.
Summary updated