Improving Execution Concurrency in Partial-Order Plans via Block-Substitution

• URL: http://arxiv.org/abs/2406.18615v1
• Date: Tue, 25 Jun 2024 23:36:13 GMT
• Title: Improving Execution Concurrency in Partial-Order Plans via Block-Substitution
• Authors: Sabah Binte Noor, Fazlul Hasan Siddiqui,
• Abstract summary: A Partial-Order Plan (POP) allows two actions with no ordering between them, thus providing the flexibility of executing actions in different sequences. This work formalizes the conditions for non-concurrency constraints to transform a POP into a parallel plan. 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Interactive and Expressive Code-Augmented Planning with Large Language Models [62.799579304821826]
  Large Language Models (LLMs) demonstrate strong abilities in common-sense reasoning and interactive decision-making. Recent techniques have sought to structure LLM outputs using control flow and other code-adjacent techniques to improve planning performance. We propose REPL-Plan, an LLM planning approach that is fully code-expressive and dynamic.
  arXiv  Detail & Related papers  (2024-11-21T04:23:17Z)
• Temporal Planning via Interval Logic Satisfiability for Autonomous Systems [0.0]
  We consider formulations of temporal planning where intervals are associated with both action and fluent atoms and relations between these are given as sentences in Allen's Interval Logic. We propose a notion of planning graphs that can account for complex relations between actions and fluents as a Constraint Programming (CP) model. We demonstrate our algorithm outperforms existing PDDL 2.1 planners in the case studies.
  arXiv  Detail & Related papers  (2024-06-14T02:21:53Z)
• Improving Plan Execution Flexibility using Block-Substitution [0.0]
  Partial-order plans in AI planning facilitate execution flexibility due to their less-constrained nature. Plan deordering removes unnecessary action orderings within a plan, while plan reordering modifies them arbitrarily to minimize action orderings. This study, in contrast with traditional plan deordering and reordering strategies, improves a plan's flexibility by substituting its subplans with actions outside the plan for a planning problem.
  arXiv  Detail & Related papers  (2024-06-05T09:30:48Z)
• Some Orders Are Important: Partially Preserving Orders in Top-Quality Planning [15.20541905857507]
  We propose specifying a subset of actions the orders between which are important, interpolating between the top-quality and unordered top-quality planning problems. We explore the ways of adapting partial order reduction search pruning techniques to address this new computational problem.
  arXiv  Detail & Related papers  (2024-04-01T22:10:12Z)
• TwoStep: Multi-agent Task Planning using Classical Planners and Large Language Models [7.653791106386385]
  Two-agent planning goal decomposition leads to faster planning times than solving multi-agent PDDL problems directly. We find that LLM-based approximations of subgoals can achieve similar multi-agent execution steps than those specified by human experts.
  arXiv  Detail & Related papers  (2024-03-25T22:47:13Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Tree-Planner: Efficient Close-loop Task Planning with Large Language Models [63.06270302774049]
  Tree-Planner reframes task planning with Large Language Models into three distinct phases. Tree-Planner achieves state-of-the-art performance while maintaining high efficiency.
  arXiv  Detail & Related papers  (2023-10-12T17:59:50Z)
• Enhancing Temporal Planning Domains by Sequential Macro-actions (Extended Version) [2.064612766965483]
  Temporal planning is an extension of classical planning involving concurrent execution of actions and alignment with temporal constraints. Our work contributes a general concept of sequential temporal macro-actions that guarantees the applicability of obtained plans. Our experiments yield improvements in terms of obtained satisficing plans as well as plan quality for the majority of tested planners and domains.
  arXiv  Detail & Related papers  (2023-07-22T13:50:34Z)
• Learning Multi-Agent Intention-Aware Communication for Optimal Multi-Order Execution in Finance [96.73189436721465]
  We first present a multi-agent RL (MARL) method for multi-order execution considering practical constraints. We propose a learnable multi-round communication protocol, for the agents communicating the intended actions with each other. Experiments on the data from two real-world markets have illustrated superior performance with significantly better collaboration effectiveness.
  arXiv  Detail & Related papers  (2023-07-06T16:45:40Z)
• AdaPlanner: Adaptive Planning from Feedback with Language Models [56.367020818139665]
  Large language models (LLMs) have recently demonstrated the potential in acting as autonomous agents for sequential decision-making tasks. We propose a closed-loop approach, AdaPlanner, which allows the LLM agent to refine its self-generated plan adaptively in response to environmental feedback. To mitigate hallucination, we develop a code-style LLM prompt structure that facilitates plan generation across a variety of tasks, environments, and agent capabilities.
  arXiv  Detail & Related papers  (2023-05-26T05:52:27Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.