Despite significant advances in Large Language Models (LLMs), planning tasks still present challenges for LLM-based agents. Existing planning methods face two key limitations: heavy constraints and cascading errors. To address these limitations, we propose a novel parallel planning paradigm, which Decomposes, Plans for subtasks in Parallel, and Merges subplans into a final plan (DPPM). Specifically, DPPM decomposes the complex task based on constraints into subtasks, generates the subplan for each subtask in parallel, and merges them into a global plan. In addition, our approach incorporates a verification and refinement module, enabling error correction and conflict resolution. Experimental results demonstrate that DPPM significantly outperforms existing methods in travel planning tasks.

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.

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 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. We exploit block deordering, which eliminates orderings in a POP by encapsulating coherent actions in blocks, to construct action blocks as candidate subplans for substitutions. In addition, this paper introduces a pruning technique for eliminating redundant actions within a BDPO plan. We also evaluate our approach when combined with MaxSAT-based reorderings. Our experimental result demonstrates a significant improvement in plan execution flexibility on the benchmark problems from International Planning Competitions (IPC), maintaining good coverage and execution time.

Autonomous robots, such as robot office couriers, need con-trol routines that support flexible task execution and effective action planning. This paper describes X FRM LEARN,a system that learns structured symbolic robot action plansfor navigation tasks. Given a navigation task, X FRM LEARN learns to structure continuous navigation behavior and represents the learned structure as compact and transparent plans.The structured plans are obtained by starting with monolithical default plans that are optimized for average performance and adding subplans to improve the navigation performance for the given task. Compactness is achieved by incorporating only subplans that achieve significant performance gains.The resulting plans support action planning and opportunistic task execution. X FRM LEARN is implemented and extensively evaluated on an autonomous mobile robot.

Plan-based story generation has operationalized concepts from the Belief-Desire-Intention (BDI) theory of mind to create goal-driven character agents with explainable behavior. However, these character agents are limited in that they do not capture the dynamic nature of intentions. To address this limitation, we define a plan-based intention revision model and propose an evaluation using the QUEST cognitive model to assess the explainability of an intention revision.

DSIPE supports a human planner. Although their requirements overlap for this mission, they each have independent goals (other missions to be performed or supported), capabilities, and resources. We extended SIPE-2's internal plan representation Throughout the planning process, each planning system monitors the local cell's planning activity for constraints and subgoals that might be relevant to other planning cells and notifies the cells of this information. For example, the naval planning cell might notify the Marine Corps planner that a particular landing area will be swept of mines by a specified time. Currently, the only constraints that are monitored in this way are the postconditions.

We propose techniques for efficiently determining optimal solutions to large logistics planning domain problems. We map a problem instance to a directed graph and show that no more than one vehicle per weakly connected component of the graph is needed for an optimal solution. We propose techniques for efficiently finding the vehicles which must be employed for an optimal solution. Also we develop a strong admissible heuristic based on the analysis of a directed graph, the cycles of which represent situations in the problem state in which a vehicle must visit a location more than once. To the best of our knowledge, ours is the first method that determines optimal solutions for large logistics instances (including the largest instances in the IPC 1998 and IPC 2000 problem sets).

Capturing and exploiting structural knowledge of planning problems has shown to be a successful strategy for making the planning process more efficient. Plans can be decomposed into its constituent coherent subplans, called blocks, that encapsulate some effects and preconditions, reducing interference and thus allowing more deordering of plans. According to the nature of blocks, they can be straightforwardly transformed into useful macro-operators (shortly, macros). Macros are well known and widely studied kind of structural knowledge because they can be easily encoded in the domain model and thus exploited by standard planning engines. In this paper, we introduce a method, called BloMa, that learns domain-specific macros from plans, decomposed into macro-blocks which are extensions of blocks, utilising structural knowledge they capture. In contrast to existing macro learning techniques, macro-blocks are often able to capture high-level activities that form a basis for useful longer macros (i.e. those consisting of more original operators). Our method is evaluated by using the IPC benchmarks with state-of-the-art planning engines, and shows considerable improvement in many cases.

This work describes an approach that automatically extracts standard metadata information from e-learning contents, combines it with the student preferences/goals and creates PDDL planning domains+problems.These PDDL problems can be solved by current planners, although we motivate the use and benefits of case-based planning techniques, to obtain fully tailored learning routes that significantly enhance the learning process. During the execution of a given route, a monitoring phase is used to detect discrepancies, i.e. flaws that prevent the student from continuing with the original plan. In such a situation, an adaptation mechanism becomes necessary to fix the flaws, while also trying to minimise the differences between the original and the new route. We have integrated this approach on top of Moodle and experimented with 100 benchmark problems to evaluate the quality, scalability and viability of the system.

The judicious use of abstraction can help planning agents to identify key interactions between actions, and resolve them, without getting bogged down in details. However, ignoring the wrong details can lead agents into building plans that do not work, or into costly backtracking and replanning once overlooked interdependencies come to light. We claim that associating systematically-generated summary information with plans' abstract operators can ensure plan correctness, even for asynchronously-executed plans that must be coordinated across multiple agents, while still achieving valuable efficiency gains. In this paper, we formally characterize hierarchical plans whose actions have temporal extent, and describe a principled method for deriving summarized state and metric resource information for such actions. We provide sound and complete algorithms, along with heuristics, to exploit summary information during hierarchical refinement planning and plan coordination. Our analyses and experiments show that, under clearcut and reasonable conditions, using summary information can speed planning as much as doubly exponentially even for plans involving interacting subproblems.