TLDR: This research paper introduces ‘plan disruption’ as a new objective in automated planning, focusing on finding plans that minimally alter the initial state to achieve goals, alongside minimizing action costs. It proposes two methods: ‘Lazy Plan Disruption’ for accurate but computationally intensive optimization, and ‘Eager Plan Disruption’ for more efficient but approximate optimization. Experimental results show that these methods can effectively balance plan cost and disruption, offering valuable insights for real-world applications where preserving initial conditions is important.
In the realm of automated planning, the traditional focus has largely been on finding the most efficient sequence of actions to achieve a goal, typically by minimizing the total cost of these actions. However, a new perspective is emerging that considers not just the cost of actions, but also how much the initial state of a system is altered to reach the desired goal. This novel concept, termed ‘plan disruption’, is the subject of a recent research paper by Alberto Pozanco, Marianela Morales, Daniel Borrajo, and Manuela Veloso from J.P. Morgan AI Research. Their work introduces this important objective and proposes methods to integrate it into planning processes.
Understanding Plan Disruption
Imagine a scenario where a truck needs to deliver packages. There might be multiple ways to complete the deliveries, all with the same minimum number of actions (cost-optimal). However, one plan might leave the truck in a completely different location from where it started, while another might return it to its original depot. The latter plan would be considered to have lower ‘plan disruption’ because it makes fewer changes to the initial state beyond what’s necessary to achieve the primary goals.
Formally, plan disruption is defined as the number of propositions (or facts) that differ between the initial state and the final state after a plan is executed. This is measured using the symmetric difference between the two sets of fluents (facts). Minimizing plan disruption means finding plans that require the least amount of alteration to the initial conditions, a property highly desirable in applications like employee scheduling, project management, or logistics, where preserving certain initial elements can be crucial for future tasks or operational stability.
Balancing Cost and Disruption: Two Approaches
The researchers propose two main ‘compilations’ – ways to reformulate the planning problem – to jointly optimize both the sum of action costs and plan disruption. These methods allow planners to find solutions that balance these two objectives, with a customizable weight (ω) determining the importance of disruption relative to action costs.
Lazy Plan Disruption
The ‘Lazy Plan Disruption’ compilation is designed for accuracy. It assesses the plan disruption only after all the primary goals have been achieved. This approach involves extending the planning task with additional ‘fluents’ (propositions) and ‘actions’ to keep track of changes from the initial state. For instance, it introduces actions that incur a penalty (increase cost) if a fluent’s truth value changes from its initial state. While highly accurate in measuring actual plan disruption, this method significantly increases the complexity of the planning task, often requiring much longer execution times.
Eager Plan Disruption
In contrast, the ‘Eager Plan Disruption’ compilation prioritizes search efficiency. Instead of waiting until the end, it continuously monitors changes to the initial state throughout the planning process. This is achieved by modifying the cost of original actions to include a penalty based on the immediate additions and deletions of fluents relative to the initial state. This approach is simpler, as it doesn’t introduce new actions or fluents, only adjusts existing action costs. However, because it’s a continuous, ‘eager’ check against the initial state, it might not always perfectly reflect the final plan disruption, potentially introducing some inaccuracies.
Experimental Insights
The paper evaluates these two compilations across a wide range of benchmark planning tasks. The findings highlight a clear trade-off:
- Efficiency: The eager compilation performs almost as efficiently as solving the standard planning task (which only optimizes action cost). The lazy compilation, due to its increased complexity, often requires orders of magnitude more execution time, making it less suitable for larger problems.
- Effectiveness: Both compilations successfully generate plans with lower disruption values compared to standard cost-optimal plans, especially when plan disruption is given a higher weight (ω). The lazy compilation consistently produces plans with the lowest possible disruption, as it accurately calculates the metric. The eager compilation, while effective, can sometimes yield plans with slightly higher disruption than the true minimum due to its approximate nature.
- Trade-offs: In tasks where there’s sufficient diversity in possible plans, the compilations effectively demonstrate the ability to balance plan cost and disruption. For example, in a SATELLITE task, a plan that was cost-optimal had high disruption, but by using the compilations, plans could be found with significantly lower disruption, sometimes at a slightly increased action cost, showcasing the ability to prioritize one objective over the other.
Also Read:
- CausalPlan: Enhancing LLM Agent Collaboration Through Causal Reasoning
- LOOP: A New Approach to Reliable Planning in Autonomous Systems
Conclusion and Future Directions
The research successfully introduces plan disruption as a valuable objective in automated planning, offering a new dimension for evaluating plan quality. The proposed lazy and eager compilations provide practical ways to optimize for this metric, each with its own strengths and weaknesses regarding accuracy and computational cost. While the lazy approach offers precise disruption minimization, its scalability is a challenge. The eager approach, though less accurate, provides a more scalable solution. This work opens avenues for future research, particularly in exploring these reformulated tasks with satisficing planners to further understand the trade-off between scalability and suboptimality. You can read the full research paper here.
