Logical Regression for Planning with Axioms | AI Research

Logical Regression for Planning with Axioms
In automated planning, logical regression is a technique used to determine the most general conditions required for an action to successfully achieve a specific goal. While this is straightforward in basic planning, it becomes significantly more difficult when a domain includes "axioms"—rules that define how certain variables are derived from others. This paper introduces a new methodology to approximate logical regression in the presence of these axioms. By limiting the regression to "partial states"—which focus only on the necessary variables rather than the entire state—the authors provide a more efficient way to monitor plan execution and recover from unexpected environmental changes.

Handling Axioms in Planning

Axioms are powerful tools that allow planners to define complex conditions and reduce the search space, but they are often excluded from planning systems due to their computational complexity. The authors address this by creating an "Axiom Aware Approximate Regression" (AAAR). This method calculates the minimal set of basic variables needed to ensure that both the action's preconditions and the relevant axioms are satisfied. By focusing on these essential variables, the system avoids the expensive task of recalculating every axiom from scratch during the planning process.

Improving Execution Monitoring

To test the effectiveness of their approach, the authors applied their regression method to an execution monitoring framework. In this setting, an agent monitors its progress as it executes a plan. If the environment changes unexpectedly, the agent must decide whether to continue or attempt to recover. Because the AAAR method produces minimal partial states, it allows the agent to ignore irrelevant variables. The results show that this approach can reduce the number of variables the monitor needs to track by up to 70%, making the decision-making process much more efficient.

Robustness and Recovery

The study demonstrates that this form of regression significantly improves the robustness of plan execution. By generalizing the conditions under which a plan is considered valid, the execution monitor can successfully recover from unexpected state changes without needing to restart the planning process from the beginning. In their tests, the authors found that the system was able to recover in over 50% of scenarios across several different domains, proving that the approximation is both practical and effective for real-world, unpredictable environments.

Considerations for Implementation

The authors note that their approach relies on a "context state"—a known, valid state—to guide the regression calculation. Because the goal state itself might contain derived variables that cannot be used directly in the regression formula, the system uses a specialized "goal-achieving action" to convert the goal into a usable format. While the method is highly effective, it is important to note that some variations of the algorithm may face limitations when dealing with specific types of stratified axioms, particularly when the system needs to confirm whether a derived variable is false.