1,720,976 research outputs found
An Effective Polynomial Technique for Compiling Conditional Effects Away
Full text linkThe paper introduces a novel polynomial compilation technique for the sound and complete removal of conditional effects in classical planning problems. Similar to Nebel’s polynomial compilation of conditional effects, our solution also decomposes each action with conditional effects into several simpler actions. However, it does so more effectively by exploiting the actual structure of the given conditional effects. We characterise such a structure using a directed graph and leverage it to significantly reduce the number of additional atoms required, thereby shortening the size of valid plans. Our experimental analysis indicates that this approach enables the effective use of polynomial compilations, offering benefits in terms of modularity and reusability of existing planners. It also demonstrates that a compilation-based approach can be more efficient, either independently or in synergy with state-of-the-art optimal planners that directly support conditional effects
Optimised Variants of Polynomial Compilation for Conditional Effects in Classical Planning
No full textConditional effects are a key feature in classical planning, enabling the description of actions whose outcomes are statedependent. It is well known that removing conditional effects in a polynomial way necessarily increases the size of a valid plan by a polynomial factor. However, preserving the exact plan size requires encoding the problem exponentially. The paper proposes and empirically evaluates optimisations for existing polynomial compilations. These optimisations aim to make the resulting compilations more suitable for planners while limiting the increase in plan size, which is inevitable if we want to keep the compilation polynomial. Specifically, the paper introduces a polynomial compilation technique that expands conditional effects when their number is below a certain threshold and sequentialises them otherwise. Additionally, the paper demonstrates that even straightforward optimisations can have a notable impact
Translations from Discretised PDDL+ to Numeric Planning
No full textHybrid PDDL+ models are amongst the most advanced models of systems and the resulting problems are notoriously difficult for planning engines to cope with. An additional limiting factor for the exploitation of PDDL+ approaches in real-world applications is the restricted number of domain-independent planning engines that can reason upon those models. With the aim of deepening the understanding of PDDL+ models, in this work we study a novel mapping between a time discretisation of PDDL+ and numeric planning as for PDDL2.1 (level 2). The proposed mapping not only clarifies the relationship between these two formalisms, but also enables the use of a wider pool of engines, thus fostering the use of hybrid planning in real-world applications. Our experimental analysis shows the usefulness of the proposed translation, and demonstrates the potential of the approach for improving the solvability of complex PDDL+ instances
A Practical Approach to Discretised PDDL+ Problems by Translation to Numeric Planning
No full textpddl+ models are advanced models of hybrid systems and the resulting problems are notoriously difficult for planning engines to cope with. An additional limiting factor for the exploitation of pddl+ approaches in real-world applications is the restricted number of domain-independent planning engines that can reason upon those models. With the aim of deepening the understanding of pddl+ models, in this work, we study a novel mapping between a time discretisation of pddl+ and numeric planning as for pddl2.1 (level 2). The proposed mapping not only clarifies the relationship between these two formalisms but also enables the use of a wider pool of engines, thus fostering the use of hybrid planning in real-world applications. Our experimental analysis shows the usefulness of the proposed translation and demonstrates the potential of the approach for improving the solvability of complex pddl+ instances
Fixing Plans for PDDL+ Problems: Theoretical and Practical Implications
No full textThe plan, execution, and replan framework has proven to be extremely valuable in complex real-world applications, where the dynamics of the environment cannot be fully encoded in the domain model. However, this comes at the cost of regenerating plans from scratch, which can be expensive when expressive formalisms like PDDL+ are used. Given the complexity of generating PDDL+ plans, it would be ideal to reuse as much as possible of an existing plan, rather than generating a new one from scratch every time. To support more effective exploitation of the plan, execution, and replan framework in PDDL+, in this paper, we introduce the problem of discretised PDDL+ plan fixing, which allows one to fix existing plans according to some defined constraints. We demonstrate the theoretical implications of the introduced notion and introduce reformulations to address the problem using domain-independent planning engines. Our results show that such reformulations can outperform replanning from scratch and unlock planning engines to solve more problems with fine-grained discretisations
A Structure-Sensitive Translation from Hybrid to Numeric Planning
No full textpddl+ is an expressive planning formalism that enables the modelling of hybrid domains with both discrete and continuous dynamics. However, its expressiveness makes this language notoriously difficult to handle natively. To address this challenge, translations from time-discrete pddl+ into numeric pddl2.1 have been proposed as a way to reframe the rich expressiveness of pddl+ into a simpler and more manageable formalism. In this work, we first analyse existing translations and provide a means to compare them in terms of induced state space and the size of the reformulated tasks. Secondly, we propose a novel translation leveraging the structure of the problem to generate a compact reformulation. Our experimental results indicate that the novel translation outperforms the existing ones on a range of benchmarks
A Sound (But Incomplete) Polynomial Translation from Discretised PDDL+ to Numeric Planning
No full textpddl+ is an expressive planning formalism that enables the modelling of domains having both discrete and continuous dynamics. Recently, two mappings for translating discretised pddl+ problems into a numeric a-temporal task have been proposed. Such translations produce a task of exponential or polynomial size w.r.t. the size of the native task. In this work, starting from the above-mentioned polynomial translation, we introduce a sound but not generally complete variant that has the potential to improve the performance of numeric planning engines. We define the subclass of problems where the variant is safely applicable, and we assess the advantages of such a translation
- …
