Abstract
Transformational Analogy (TA) is the process of adapting a previously successful plan to solve a new problem. While empirical evidence suggests TA is highly efficient, theoretical complexity results often categorize plan adaptation as more difficult than planning from scratch. This paper introduces TransUCP, a formal framework that unifies TA methods. We demonstrate that the high complexity associated with TA is a byproduct of the "minimal modification" constraint. By utilizing a satisficing approach, TransUCP bypasses these theoretical hurdles, aligning formal analysis with practical performance.
Introduction: The Paradox of Plan Adaptation
In automated planning, Transformational Analogy (TA) allows agents to modify existing plans—adding, removing, or changing actions—to fit new goals. Systems like CHEF and SPA have historically demonstrated that adapting old plans is significantly faster than generating new ones from scratch. However, a seminal 1995 study by Nebel and Koehler presented a paradox: they proved that plan adaptation is PSPACE-complete or NP-complete, theoretically making it harder than "from-scratch" planning.
This paper resolves this tension by providing a precise, general framework to analyze TA. The authors argue that the field's previous lack of a formal foundation made it difficult to distinguish between worst-case theoretical scenarios and real-world algorithmic behavior.
The TransUCP Framework
The authors propose TransUCP, an extension of the Universal Classical Planning (UCP) framework. Unlike standard planners that only add constraints (refinement), TransUCP incorporates "retractions"—the systematic removal of steps or constraints that are no longer valid for the new goal.
To manage these retractions effectively, TransUCP employs purpose tags. These tags track the rationale behind every modification (e.g., satisfying a specific precondition or resolving a conflict). When a part of the plan needs to be undone, purpose tags allow the system to retract specific steps without indiscriminately breaking the entire plan structure. The algorithm treats adaptation as a search through a "PlanPool," moving "down" to refine plans and "up" to retract flawed steps.
Complexity and the "Minimalist Trap"
The core theoretical contribution of this work is identifying the "Minimalist Trap." Previous complexity proofs relied on the assumption of minimal plan modification (MODSAT), which requires an algorithm to reuse the absolute maximum number of steps from the original plan.
The authors show that practical TA does not require minimality; it requires a valid solution. By shifting from an optimization problem (finding the most similar plan) to a satisficing problem (finding any valid plan), TransUCP avoids the NP-hard search for minimality. This explains why empirical systems remain fast: they are "greedy" and willing to discard more of the old plan than strictly necessary to reach a solution quickly.
Empirical Illustration: The Logistics Domain
The framework's properties are illustrated using the Logistics Transportation Domain, a classic planning benchmark involving the movement of packages via trucks and airplanes.
In empirical tests across 10 randomly generated problems, TransUCP consistently produced non-minimal plans. This validation confirms that the algorithm prioritizes finding a functional solution over maintaining strict adherence to the original plan's structure, thereby bypassing the theoretical complexity barriers identified in earlier research.
Conclusion and Future Work
TransUCP serves as a powerful analytical tool for defining and studying Transformational Analogy variants. While it clarifies the complexity paradox, it also opens new avenues for research, such as identifying the "tipping point" where adaptation becomes more or less efficient than planning from scratch. Future work aims to extend this formal rigor to other Case-Based Reasoning (CBR) methods to better understand their underlying properties.
Summary updated