arXiv:2406.18615v1 Announce Type: new
Abstract: Partial-order plans in AI planning facilitate execution flexibility and several other tasks, such as plan reuse, modification, and decomposition, due to their less constrained nature. A Partial-Order Plan (POP) allows two actions with no ordering between them, thus providing the flexibility of executing actions in different sequences. This flexibility can be further extended by enabling parallel execution of actions in a POP to reduce its overall execution time. While extensive studies exist on improving the flexibility of a POP by optimizing its action orderings through plan deordering and reordering, there has been limited focus on the flexibility of executing actions concurrently in a plan. Execution concurrency in a POP can be achieved by incorporating action non-concurrency constraints, specifying which actions can not be executed in parallel. This work formalizes the conditions for non-concurrency constraints to transform a POP into a parallel plan. We also introduce an algorithm to enhance the plan’s concurrency by optimizing resource utilization through substitutions of its subplans with respect to the corresponding planning task. Our algorithm employs block deordering that eliminates orderings in a POP by encapsulating coherent actions in blocks, and then exploits blocks as candidate subplans for substitutions. Experiments over the benchmark problems from International Planning Competitions (IPC) exhibit significant improvement in plan concurrency, specifically, with improvement in 25% of the plans, and an overall increase of 2.1% in concurrency.
Enhancing Flexibility in AI Planning with Partial-Order Plans and Execution Concurrency
AI planning plays a crucial role in facilitating execution flexibility in various tasks such as plan reuse, modification, and decomposition. Partial-Order Plans (POPs) particularly enable this flexibility due to their less constrained nature. Unlike total-order plans, a POP allows for two actions to have no specific ordering between them, thereby providing the flexibility to execute actions in different sequences.
However, the flexibility of POPs can be further extended by incorporating execution concurrency, which enables parallel execution of actions in a plan. By specifying action non-concurrency constraints, which define actions that cannot be executed in parallel, the overall execution time of a POP can be significantly reduced.
This article introduces a formalization of the conditions for non-concurrency constraints to transform a POP into a parallel plan. By identifying actions that cannot be executed concurrently, this approach enhances the plan’s flexibility by allowing for simultaneous execution of unrelated actions. The algorithm proposed in this work optimizes resource utilization through substitutions of subplans, which are encapsulated coherent actions, to improve plan concurrency.
The algorithm utilizes block deordering to eliminate orderings within a POP. By grouping coherent actions into blocks, the algorithm can then identify blocks that can be substituted and executed in parallel, thus enhancing concurrency. Experimental results conducted on benchmark problems from International Planning Competitions (IPC) show a significant improvement in plan concurrency, with a 25% improvement in individual plans and an overall increase in concurrency of 2.1%.
This research brings together various disciplines, showcasing the multi-disciplinary nature of the concepts explored. It combines principles from AI planning, optimization, and resource utilization to enhance the flexibility and efficiency of planning systems. By incorporating execution concurrency into the already flexible framework of POPs, this work contributes to the field of AI planning by providing new insights and techniques to handle complex planning scenarios.