Improving Execution Concurrency in Partial-Order Plans via Block-Substitution
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.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Execution Flexibility in Automated Planning: A Comparative Evaluation of Deordering and Reordering Strategies
This study covers foundational concepts for enhancing plan-execution flexibility, including partial-order planning, the producer-consumer-threat formalism, and a range of deordering and reordering strategies. Creating a …
Improving Plan Execution Flexibility using Block-Substitution
Partial-order plans in AI planning facilitate execution flexibility due to their less-constrained nature. Maximizing plan flexibility has been studied through the notions of plan deordering, and plan reordering. Plan deo…
FoldA: Computing Partial-Order Alignments Using Directed Net Unfoldings
Conformance checking is a fundamental task of process mining, which quantifies the extent to which the observed process executions match a normative process model. The state-of-the-art approaches compute alignments by ex…
Execution-State Capsules: Graph-Bound Execution-State Checkpoint and Restore for Low-Latency, Small-Batch, On-Device Physical-AI Serving
Mainstream LLM serving systems reuse prefix work mainly through paged or radix key-value (KV) caches. This is highly effective for high-throughput, high-concurrency serving, but it manages only one positional fragment of…
Reducing Inference Latency with Concurrent Architectures for Image Recognition
Satisfying the high computation demand of modern deep learning architectures is challenging for achieving low inference latency. The current approaches in decreasing latency only increase parallelism within a layer. This…
Neural Architecture Search