In this paper, we investigate the application of heuristics based on Graph Neural Networks (GNNs) to lifted numeric planning problems, an area that has been relatively unexplored. Building upon the GNN approach for learning general policies proposed by Ståhlberg, Bonet, and Geffner (2022b), we extend the architecture to make it sensitive to the numeric components inherent in the planning problems we address. We achieve this by observing that, although the state space of a numeric planning problem is infinite, the finite subgoal structure of the problem can be incorporated into the architecture, enabling the construction of a finite structure. Instead of learning general policies, we train our models to serve as heuristics within a best-first search algorithm. We explore various configurations of this architecture and demonstrate that the resulting heuristics are highly informative and, in certain domains, offer a better trade-off between guidance and computational cost compared to state-of-the-art heuristics.

In real-world scenarios, the successful execution of an agent’s planned actions is not always guaranteed, as actions may fail in unpredictable ways that are not explicitly modeled. To address this challenge, the concept of Resilient Planning and the RESPLAN framework were introduced focusing on the generation of k-resilient plans that enable an agent to reach its goals even in the presence of up to k execution failures. In this paper, we propose a new version of the RESPLAN planning algorithm based on two significant enhancements. The first incorporates landmarks into a pruning strategy, enabling the planner to avoid unnecessary explorations and yielding substantial performance gains, especially when no resilient plan exists. The second introduces a planning adaptation strategy exploiting regressed state formulas to support the search process during (re)planning, reducing the number of iterations required when a resilient plan does exist. We compare our methods against RESPLAN and other baselines, demonstrating substantial improvements across multiple domains.

In recent years, various studies have been carried out to assess whether Large Language Models (LLMs) possess different reasoning capabilities, including those required in automated planning. Typically, these studies provide the LLM with a planning domain and a problem, specified by an initial state and a goal, and require the LLM model to generate a plan solving the problem. Despite this common configuration, such studies significantly differ in the used models, the information provided to the model, the possible involvement of symbolic planners, and the experimental approaches used for the evaluation. Motivated by the growing interest in LLMs and in the understanding of their reasoning abilities, in this work we offer a concise review of recent studies on using LLMs for planning. We outline the main research trends and discuss their most notable findings. Furthermore, we identify key challenges and highlight critical aspects to consider when evaluating a LLM in terms of learning to plan and generating solution plans.

Transformer-based architectures have revolutionized natural language processing and represent a significant promise for advancing policy learning in generalized planning tasks. In particular, PlanGPT demonstrated remarkable results in generating solution plans in different planning domains. For each domain, it is trained on a domain-specific dataset composed of randomly generated planning problems and corresponding solution plans. This work proposes a novel extension to the PlanGPT framework by incorporating macro-actions, high-level actions that encapsulate sequences of primitive actions, which are a well-established technique in classical planning known to improve planning efficiency by guiding exploration through shortcuts. Leveraging this concept, we investigate the impact of macro-actions on the learning process of PlanGPT and whether they mitigate the occurrence of violated preconditions caused by complex object relationships, particularly in domains where these interactions frequently lead to invalid plans due to precondition violations. Experimental results indicate that integrating macroactions improves coverage in several challenging domains and reduces generation time, highlighting the enhanced learning capabilities of PlanGPT when supported by macro-actions.

In this paper, we investigate the application of heuristics based on Graph Neural Networks (GNNs) to lifted numeric planning problems, an area that has been relatively unexplored. Building upon the GNN approach for learning general policies proposed by Staahlberg et al., we extend the architecture to make it sensitive to the numeric components inherent in the planning problems we address. We achieve this by observing that, although the state space of a numeric planning problem is infinite, the finite subgoal structure of the problem can be incorporated into the architecture, allowing for the construction of only a finite number of nodes. Instead of learning general policies, we train our models to function as a heuristic within a best-first search algorithm. We explore various configurations of this architecture and demonstrate that the resulting heuristics are highly informative and, in certain domains, offer a better trade-off between guidance and computational cost compared to other inductive and deductive heuristics.

We study planning for temporally extended goals expressed in Pure-Past Linear Temporal Logic ( ppltl ) in the context of deterministic (i.e., classical) and fully observable nondeterministic (FOND) domains. ppltl is the variant of Linear-time Temporal Logic on finite traces ( ltl f ) that refers to the past rather than the future. Although ppltl is as expressive as ltl f , we show that it is computationally much more effective for planning. In particular, we show that checking the validity of a plan for a ppltl formula is Markovian. This is achieved by introducing a linear number of additional propositional variables that capture the validity of the entire formula in a modular fashion. The solution encoding introduces only a linear number of new fluents proportional to the size of the ppltl goal and does not require any additional spurious action. We implement our solution technique in a system called Plan4Past , which can be used alongside state-of-the-art classical and FOND planners. Our empirical analysis demonstrates the practical effectiveness of Plan4Past in both classical and FOND problems, showing that the resulting planner performs overall better than other planning approaches for ltl f goals.

This paper studies an approach to planning with PDDL3 constraints involving mixed propositional and numeric conditions, as well as metric time constraints. We show how the whole PDDL3 with instantaneous actions can be compiled away into a numeric planning problem without PDDL3 constraints, enabling the use of any state-of-the-art numeric planner that is agnostic to the existence of PDDL3. Our solution exploits the concept of regression. In addition to a basic compilation, we present an optimized variant based on the observation that it is possible to make the compilation sensitive to the structure of the problem to solve; this can be done by reasoning on the interactions between the problem actions and the constraints. The resulting optimization substantially reduces the size of the planning task. We experimentally observe that our approach significantly outperforms existing state-of-the-art planners supporting the same class of constraints over known benchmark domains, settling a new state-of-the-art planning system for PDDL3.

The 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.

In this paper, we introduce Shielded FOND planning (S-FOND), which is the problem of computing a strategy to reach a final-state goal while preserving a safety specification called shield. In particular, we characterize shields as Pure-Past Linear Temporal Logic formulas that must hold in every prefix of a state trace induced by a solution strategy, thus capturing the whole safety fragment of Linear Temporal Logic formulas over finite traces. We propose three solution encodings for handling S-FOND problems: the first, which is our baseline, simply views a shield as a temporally extended goal; the second, instead, blocks the execution of further actions when the shield gets violated, and the third prevents the execution of actions that could violate the shield by using the notion of regression. We formally prove the correctness of each encoding and experimentally prove their effectiveness over a set of benchmark shields.

Transformer-based architectures, such as T5, BERT and GPT, have demonstrated revolutionary capabilities in Natural Language Processing. Several studies showed that deep learning models using these architectures not only possess remarkable linguistic knowledge, but they also exhibit forms of factual knowledge, common sense, and even programming skills. However, the scientific community still debates about their reasoning capabilities, which have been recently tested in the context of automated AI planning; the literature presents mixed results, and the prevailing view is that current transformer-based models may not be adequate for planning. In this paper, we address this challenge differently. We introduce a GPT-based model customised for planning (PLANGPT) to learn a general policy for classical planning by training the model from scratch with a dataset of solved planning instances. Once PLANGPT has been trained for a domain, it can be used to generate a solution plan for an input problem instance in that domain. Our training procedure exploits automated planning knowledge to enhance the performance of the trained model. We build and evaluate our GPT model with several planning domains, and we compare its performance w.r.t. other recent deep learning techniques for generalised planning, demonstrating the effectiveness of the proposed approach.

We propose R-latplan, a system that learns reliable symbolic (PDDL) representations of an agent's actions from noisy visual observations, and without explicit human expert knowledge. R-latplan builds upon Latplan, a model that also learns PDDL representations of actions from images. However, Latplan does not ensure that the learned actions correspond to the actual agent's actions and does not map the learned actions to the agent's actual capabilities. There is, therefore, a substantial risk that a learned action could be impossible due to the domain's physics or the agent's capability. R-latplan receives input pairs of (noisy) images representing the states before/after the agent's action is performed in the domain. Contrary to Latplan, it uses a transition identifier function that identifies the class of a transition and associates it as an action label for the pair of images. Our experimental analysis shows that: (1) R-latplan produces reliable PDDL models in which each action can be directly connected to an agent's high level actuators and lead to visually correct states (the agent does not hallucinate), (2) R-latplan generated PDDL models lead to a domain-independent planner to find optimal plans on each benchmarks considered, (3) R-latplan is robust against mislabeled transitions, i.e. if errors are introduced in the transition identifier function.

Conditional effects are a key feature in classical planning, enabling the description of actions whose outcomes are state-dependent. It is well known that the polynomial removal of conditional effects necessarily increases the size of a valid plan by a polynomial factor while preserving exactly the plan size requires an exponential encoding of the problem. 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.

Autonomous agents embedded in a physical environment need the ability to recognize objects and their properties from sensory data. Such a perceptual ability is often implemented by supervised machine learning models, which are pre-trained using a set of labelled data. In real-world, open-ended deployments, however, it is unrealistic to assume to have a pre-trained model for all possible environments. Therefore, agents need to dynamically learn/adapt/extend their perceptual abilities online, in an autonomous way, by exploring and interacting with the environment where they operate. This paper describes a way to do so, by exploiting symbolic planning. Specifically, we formalize the problem of automatically training a neural network to recognize object properties as a symbolic planning problem (using PDDL). We use planning techniques to produce a strategy for automating the training dataset creation and the learning process. Finally, we provide an experimental evaluation in both a simulated and a real environment, which shows that the proposed approach is able to successfully learn how to recognize new object properties.

In the real world, the execution of the actions planned for an agent is never guaranteed to succeed, as they can fail in a number of unexpected ways that are not explicitly captured in the planning model. Based on these observations, we introduce the task of finding plans for classical planning that are resilient to action execution failures. We refer to this problem as Resilient Planning and to its solutions as K-resilient plans; such plans guarantee that an agent will always be able to reach its goals (possibly by replanning alternative sequences of actions) as long as no more than K failures occur along the way. We also present RESPLAN, a new algorithm for Resilient Planning, and we compare its performance to methods based on compiling Resilient Planning to Fully-Observable-Non-Deterministic (FOND) planning.

Recently, Pure-Past Temporal Logic (PPLTL) has proven highly effective in specifying temporally extended goals in deterministic planning domains. In this paper, we show its effectiveness also for fully observable nondeterministic (FOND) planning, both for strong and strong-cyclic plans. We present a notably simple encoding of FOND planning for PPLTL goals into standard FOND planning for final-state goals. The encoding only introduces few fluents (at most linear in the PPLTL goal) without adding any spurious action and allows planners to lazily build the relevant part of the deterministic automaton for the goal formula on-the-fly during the search. We formally prove its correctness, implement it in a tool called Plan4Past, and experimentally show its practical effectiveness.

Autonomous agents embedded in a physical environment need the ability to correctly perceive the state of the environment from sensory data. In partially observable environments, certain properties can be perceived only in specific situations and from certain viewpoints that can be reached by the agent by planning and executing actions. For instance, to understand whether a cup is full of coffee, an agent, equipped with a camera, needs to turn on the light and look at the cup from the top. When the proper situations to perceive the desired properties are unknown, an agent needs to learn them and plan to get in such situations. In this paper, we devise a general method to solve this problem by evaluating the confidence of a neural network online and by using symbolic planning. We experimentally evaluate the proposed approach on several synthetic datasets, and show the feasibility of our approach in a real-world scenario that involves noisy perceptions and noisy actions on a real robot.

Most ML-based applications for COVID-19 assess the general conditions of a patient trained and tested on cohorts of patients collected over a short period of time and are capable of providing an alarm a few days in advance, helping clinicians in emergency situations, monitor hospitalised patients and identify potentially critical situations at an early stage. However, the pandemic continues to evolve due to new variants, treatments, and vaccines; considering datasets over short periods could not capture this aspect. In addition, these applications often avoid dealing with the uncertainty associated with the prediction provided by machine learning models, potentially causing costly mistakes. In this work, we present a system based on Recurrent Neural Networks (RNN) for the daily estimate of the prognosis of COVID-19 patients that is built and tested using data collected over a long period of time. Our system achieves high predictive performance and uses an algorithm to effectively determine and discard those patients for whom RNN cannot predict the prognosis with sufficient confidence.

In multi-agent planning, preserving the agents' privacy has become an increasingly popular research topic. For preserving the agents' privacy, agents jointly compute a plan that achieves mutual goals by keeping certain information private to the individual agents. Unfortunately, this can severely restrict the accuracy of the heuristic functions used while searching for solutions. It has been recently shown that, for centralized planning, blind search algorithms such as width-based search can solve instances of many existing domains in low polynomial time when they feature atomic goals. Moreover, the performance of goal-oriented search can be improved by combining it with width-based search. In this paper, we investigate the usage of width-based search in the context of (decentralised) collaborative multi-agent privacy-preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that width-based search is a very effective approach over several benchmark domains, even when the search is driven by heuristics that roughly estimate the distance from goal states, computed without using the private information of other involved agents. Moreover, we show that the use of width-based techniques can significantly reduce the number of messages transmitted among the agents, better preserving their privacy and improving their performance. An experimental study presented in the paper analyses the effectiveness of our techniques, and compares them with the state-of-the-art of collaborative multi-agent planning.

Case-based planning is an approach to planning where previous planning experience provides guidance to solving new problems. Such a guidance can be extremely useful, or even necessary, when the new problem is very hard to solve, or the stored previous experience is highly valuable, because, e.g., it was provided or validated by human experts, and the system should try to reuse it as much as possible. To do so, a case-based planning system stores in a library previous planning experience in the form of already encountered problems and their solutions. The quality of such a plan library critically influences the performance of the planner, and therefore it needs to be carefully designed and created. For this reason, it is also important to update the library during the lifetime of the system, as the type of problems being addressed may evolve or differ from the ones the library was originally designed for. Moreover, like in general case-based reasoning, the library needs to be maintained at a manageable size, otherwise the computational cost of querying it grows excessively, making the entire approach ineffective. In this paper, we formally define the problem of maintaining a library of cases, discuss which criteria should drive the maintenance, study the computational complexity of the maintenance problem, and propose offline techniques to reduce an oversized library that optimize different criteria. Moreover, we introduce a complementary online approach that attempts to limit the growth of the library, and we consider the combination of offline and online techniques to ensure the best performance of the case-based planner. Finally, we experimentally show the practical effectiveness of the offline and online methods for reducing the library.

Automated planning is a prominent Artificial Intelligence (AI) challenge that has been extensively studied for decades, which has led to the development of powerful domain-independent planning systems. The performance of domain-independent planning systems are strongly affected by the structure of the search space, that is dependent on the application domain and on its encoding.This paper proposes and investigates a novel way of combining machine learning and heuristic search to improve domain-independent planning. On the learning side, we use learning to predict the plan cost of a good solution for a given instance. On the planning side, we propose a bound-sensitive heuristic function that exploits such a prediction in a state-space planner. Our function combines the input prediction (derived inductively) with some pieces of information gathered during search (derived deductively). As the prediction can sometimes be grossly inaccurate, the function also provides means to recognise when the provided information is actually misguiding the search. Our experimental analysis demonstrates the usefulness of the proposed approach in a standard heuristic best-first search schema.

In automated planning the ability of expressing constraints on the structure of the desired plans is important to deal with solution quality, as well as to express control knowledge. In PDDL3, this is supported through state-trajectory constraints corresponding to a class of LTLf formulae. In this paper, first we introduce a formalism to express trajectory constraints over actions in the plan, rather than over traversed states; Then we investigate compilation-based methods to deal with such constraints in propositional planning, and propose a new simple effective method. Finally, we experimentally study the usefulness of our action-trajectory constraints as a tool to express control knowledge. The experimental results show that the performance of a classical planner can be significantly improved by exploiting knowledge expressed by action constraints and handled by our compilation method, while the same knowledge turns out to be less beneficial when specified as state constraints and handled by two state-of-the-art systems supporting state constraints.

During 2020 and 2021, managing limited healthcare resources and hospital beds has been a fundamental aspect of the fight against the COVID-19 pandemic. Predicting in advance the length of stay, and in particular identifying whether a patient is going to stay in the hospital longer or less than a week, can provide important support in handling resources allocation. However, there have been significant changes in terms of containment measures, virus diffusion, new treatments, vaccines, and new variants of SARS-CoV-2 during the last period. These changes pose several conceptual drift issues that can limit the usefulness of machine learning in this context. In this work, we present a machine learning system trained and tested using data from more than 6000 hospitalised patients in northern Italy, distributed over almost two years of pandemic. We show how machine learning can be effective even by analysing data over this long period of time, also exploiting a model that predicts the patient's outcome in terms of discharge or death. Furthermore, learning from data that also consider deceased patients is a common issue in predicting the length of stay because they have severe conditions similar to patients with a long stay period, but may actually have a very short duration of hospitalisation. For this purpose, we present a method for handling data from alive and deceased patients, exploiting more patient records, increasing the robustness of the model and its performance in this task. Finally, we investigate the features that are most relevant to the prediction of the simplified length of stay.

The aim of decentralised multi-agent (DMA) planning is to coordinate a set of agents to jointly achieve a goal while preserving their privacy. Blind search algorithms, such as width-based search, have recently proved to be very effective in the context of centralised automated planning, especially when combined with goal-oriented techniques. In this paper, we discuss a recent line of research in which the usage of width-based search has been extensively studied in the context of DMA planning, addressing the challenges related to the agents' privacy and performance.

We propose an approach to learn an extensional representation of a discrete deterministic planning domain from observations in a continuous space navigated by the agent actions. This is achieved through the use of a perception function providing the likelihood of a real-value observation being in a given state of the planning domain after executing an action. The agent learns an extensional representation of the domain (the set of states, the transitions from states to states caused by actions) and the perception function on-line, while it acts for accomplishing its task. In order to provide a practical approach that can scale up to large state spaces, a “draft” intensional (PDDL-based) model of the planning domain is used to guide the exploration of the environment and learn the states and state transitions. The proposed approach uses a novel algorithm to (i) construct the extensional representation of the domain by interleaving symbolic planning in the PDDL intensional representation and search in the state transition graph of the extensional representation; (ii) incrementally refine the intensional representation taking into account information about the actions that the agent cannot execute. An experimental analysis shows that the novel approach can scale up to large state spaces, thus overcoming the limits in scalability of the previous work.

The automated learning of action models is widely recognised as a key and compelling challenge to address the difficulties of the manual specification of planning domains. Most state-of-the-art methods perform this learning offline from an input set of plan traces generated by the execution of (successful) plans. However, how to generate informative plan traces for learning action models is still an open issue. Moreover, plan traces might not be available for a new environment. In this paper, we propose an algorithm for learning action models online, incrementally during the execution of plans. Such plans are generated to achieve goals that the algorithm decides online in order to obtain informative plan traces and reach states from which useful information can be learned. We show some fundamental theoretical properties of the algorithm, and we experimentally evaluate the online learning of the action models over a large set of IPC domains.

Multi-task learning approaches have shown significant improvements in different fields by training different related tasks simultaneously. The multi-task model learns common features among different tasks where they share some layers. However, it is observed that the multi-task learning approach can suffer performance degradation with respect to single task learning in some of the natural language processing tasks, specifically in sequence labelling problems. To tackle this limitation we formulate a simple but effective approach that combines multi-task learning with transfer learning. We use a simple model that comprises of bidirectional long-short term memory and conditional random field. With this simple model, we are able to achieve better F1-score compared to our single task and the multi-task models as well as state-of-the-art multi-task models.

Radiological reports are a valuable source of textual information, which can be exploited to improve clinical care and to support research. Such information can be extracted and put into a structured form using machine learning techniques. Some of them rely not only on the classification labels but also on the manual annotation of relevant snippets, which is a time consuming job and requires domain experts. In this paper, we apply deep learning techniques and in particular Long Short Term Memory (LSTM) networks to perform such a task relying only on the classification labels. We focus on the classification of chest computed tomography reports in Italian according to a classification schema proposed for this task by the radiologists of Spedali Civili di Brescia. Each report is classified according to such schema using a combination of neural network classifiers. The resulting system is a novel classification system, which we compare to a previous system based on standard machine learning techniques which used annotations of relevant snippets.

In the last decade, the major private IT companies have developed lots of cloud platforms for Natural Language Understanding (NLU), that are widely used for research and commercial purposes. One of the main reasons for the success of NLU platforms is because they allow to simplify the Chatbots or Spoken Dialogue Systems (SDS) development and, in many cases, without knowledge about programming languages. In this paper, we present a general description and a taxonomy that brings together features and constraints of different cloud-based NLU services available on the market. Furthermore, we provide an evaluation and a comparison concerning the ability to recognise the underlying intents of different sentences. The sentences used are a collection of requests made by users in Italian on an e-learning platform. This analysis wants to help the company, owner of the e-learning platform, to understand in which NLU platform it is better to build a chatbot for the Italian language aiming at answering the most frequently asked questions.

Compressed Path Databases (CPDs) are a leading technique for optimal pathfinding in graphs with static edge costs. In this work we investigate CPDs as admissible heuristic functions and we apply them in two distinct settings: problems where the graph is subject to dynamically changing costs, and anytime settings where deliberation time is limited. Conventional heuristics derive cost-to-go estimates by reasoning about a tentative and usually infeasible path, from the current node to the target. CPD-based heuristics derive cost-to-go estimates by computing a concrete and usually feasible path. We exploit such paths to bound the optimal solution, not just from below but also from above. We demonstrate the benefit of this approach in a range of experiments on standard gridmaps and in comparison to Landmarks, a popular alternative also developed for searching in explicit state-spaces.

In multi-agent planning, agents jointly compute a plan that achieves mutual goals, keeping certain information private to the individual agents. Agents' coordination is achieved through the transmission of messages, but they can be a source of privacy leakage as they can permit a malicious agent to collect information about other agents' search processes and states. In this paper, we investigate the usage of novelty techniques in the context of (decentralised) multi-agent privacy preserving planning, addressing the challenges related to the agents' privacy and performance. In particular, we show that novelty based techniques allow a significant reduction on the number of messages transmitted among agents, increasing their privacy levels and also their performances. An experimental study analyses the effectiveness of our techniques and compares them with the state of-the-art. Finally, we examine the robustness of our approach considering different delays in the messages transmission as would occur in overloaded networks, due for example to massive attacks or critical situations.

Over the last years, the planning community has formalised several models and approaches to multi-agent (MA) propositional planning. One of the main motivations in MA planning is that some or all agents have private knowledge that cannot be communicated to other agents during the planning process and the plan execution. We argue that the existing models of the multi-agent planning task do not maintain the agents’ privacy when a (strict) subset of the involved agents share confidential knowledge, or when the identity/existence of at least one agent is confidential. In this paper, first we propose a model of the MA-planning tasks that preserves the privacy of the involved agents when this happens. Then we investigate an algorithm based on best first search for our model that uses some new heuristics providing a trade-off between accuracy and agents’ privacy. Finally, an experimental study compares the effectiveness of using the proposed heuristics.

Agent planning programs are finite-state programs, possibly containing loops, whose atomic instructions consist of a guard, a maintenance goal, and an achievement goal, which act as precondition-invariance-postcondition assertions in program specification. The execution of such programs requires generating plans that meet the goals specified in the atomic instructions, while respecting the program control flow. Recently, De Giacomo et al. (2016) presented a technique, based on iteratively solving classical planning problems with action costs, for realizing planning programs in deterministic domains. Such a technique works generally well for domains with no or very few dead-end states. In this paper, we propose an enhancement of this technique to handle deterministic domains that have potentially many dead-end states, and we study the effectiveness of our technique through an experimental analysis.

Admissible heuristics are essential for optimal planning in the context of search algorithms like A*, and they can also be used in the context of suboptimal planning in order to find quality-bounded solutions. In satisfacing planning, on the other hand, admissible heuristics are not exploited by the best-first search algorithms of existing planners even when a time window is available for improving the first solution found. For example, in the well-know planner LAMA, better solutions within such a time window are sought by restarting a Weighted-A* search guided by inadmissible heuristics, each time a better solution is found. In this paper, we investigate the use of admissible heuristics in the context of LAMA for pruning nodes that cannot lead to better solutions. The revised search of LAMA is experimentally evaluated using two alternative admissible heuristics for pruning and three types of problems: planning with soft goals, planning with action costs, and planning with both action costs and soft goals. Soft goals are compiled into hard goals following the approach of Keyder and Geffner. The empirical results show that the use of admissible heuristics in LAMA can be of great help to improve the planner performance.

Partial delete relaxation methods, like red-black planning, are extremely powerful, allowing in principle to force relaxed plans to behave like real plans in the limit. Alas, that power has so far been chained down by the computational overhead of the use as heuristic functions, necessitating to compute a relaxed plan on every search state. For red-black planning in particular, this has entailed an exclusive focus on tractable fragments. We herein unleash the power of red-black planning on two applications not necessitating such a restriction: (i) generating seed plans for plan repair, and (ii) proving planning task unsolvability. We introduce a method allowing to generate red-black plans for arbitrary inputs — intractable red-black planning — and we evaluate its use for (i) and (ii). With (i), our results show promise and outperform standard baselines in several domains. With (ii), we obtain substantial, in some domains dramatic, improvements over the state of the art.

Case-based planning can fruitfully exploit knowledge gained by solving a large number of problems, storing the corresponding solutions in a plan library and reusing them for solving similar planning problems in the future. Case-based planning is very effective when similar reuse candidates can be e fficiently and effectively chosen. In this paper, we study an innovative technique based on planning problem features for efficiently retrieving solved planning problems (and relative plans) from large plan libraries. A problem feature is a characteristic –usually provided under the form of a number– of the instance that can be automatically derived from the problem specification, domain and search space analyses, or different problem encodings. Given a planning problem to solve, its features are extracted and compared to those of problems stored in the case base, in order to identify most similar problems. Since the use of existing planning features is not always able to effectively distinguish between problems within the same planning domain, we introduce a large number of new features. An experimental analysis in this paper investigates the best set of features to be exploited for retrieving plans in case-based planning, and shows that our feature-based retrieval approach can significantly improve the performance of a state-of-the-art case-based planning system.

Combining the complementary strengths of several algorithms through portfolio approaches has been demonstrated to be effective in solving a wide range of AI problems. Notably, portfolio techniques have been prominently applied to suboptimal (satisficing) AI planning. Here, we consider the construction of sequential planner portfolios for (domain-independent) optimal planning. Specifically, we introduce four techniques (three of which are dynamic) for per-instance planner schedule generation using problem instance features, and investigate the usefulness of a range of static and dynamic techniques for combining planners. Our extensive experimental analysis demonstrates the benefits of using static and dynamic sequential portfolios for optimal planning, and provides insights on the most suitable conditions for their fruitful exploitation.

We address planning with always preferences in propositional domains, proposing a new compilation schema for translating a STRIPS problem enriched with always preferences (and possibly also soft goals) into a STRIPS problem with action costs. Our method allows many STRIPS planners to effectively address planning with always preferences and soft goals. An experimental analysis indicates that such basic planners are competitive with current planners using techniques specifically developed to handle always preferences.

Case-based planning (CBP) is an approach to planning where previous planning experience stored in a case base provides guidance to solving new problems. Such a guidance can be extremely useful when the new problem is very hard to solve, or the stored previous experience is highly valuable (because, e.g. it was provided and/or validated by human experts) and the system should try to reuse it as much as possible. In this work, we address CBP in PDDL domains with real-valued fluents, action durations and timed-initial literals, which are essential to model real-world planning problems involving continuous resources and temporal constraints. We propose some new heuristic techniques for retrieving a plan from a library of existing plans that is promising for solving a new planning problem encountered by the CBP system, i.e. that can be efficiently adapted to solve the new problem. The effectiveness of these techniques, which derive much of their power from the proposed use of the numerical/temporal information in the planning problem specification and in the library plans, is evaluated through an experimental analysis.

In the field of domain-independent planning, several powerful planners implementing different techniques have been developed. However, no one of these systems outperforms all others in every known benchmark domain. In this work, we propose a multi-planner approach that automatically configures a portfolio of planning techniques for each given domain. The configuration process for a given domain uses a set of training instances to: (i) compute and analyze some alternative sets of macro-actions for each planner in the portfolio identifying a (possibly empty) useful set, (ii) select a cluster of planners, each one with the identified useful set of macro-actions, that is expected to perform best, and (iii) derive some additional information for configuring the execution scheduling of the selected planners at planning time. The resulting planning system, called PbP (Portfolio- based Planner), has two variants focusing on speed and plan quality. Different versions of PbP entered and won the learning track of the sixth and seventh International Planning Competitions. In this paper, we experimentally analyze PbP considering planning speed and plan quality in depth. We provide a collection of results that help to understand PbP’s behavior, and demonstrate the effectiveness of our approach to configuring a portfolio of planners with macro-actions.

When designing state-of-the-art, domain-independent planning systems, many decisions have to be made with respect to the domain analysis or compilation performed during preprocessing, the heuristic functions used during search, and other features of the search algorithm. These design decisions can have a large impact on the performance of the resulting planner. By providing many alternatives for these choices and exposing them as parameters, planning systems can in principle be configured to work well on different domains. However, planners are typically used in default configurations that have been chosen because of their good average performance over a set of benchmark domains, with limited experimentation over the potentially huge range of possible configurations. In this work, we propose a general framework for automatically configuring a parameterized planner, and show that substantial performance gains can be achieved. We apply the framework to the well-known LPG planner, which in the context of this work was expanded to 62 parameters and over 6.5 x 10^17 possible configurations. By using this highly parameterized planning system in combination with the state-of-the-art automatic algorithm configuration procedure ParamILS, excellent performance on a broad range of well-known benchmark domains was achieved, as also witnessed by the results of the learning track of the 7th International Planning Competition.

Planning through local search and action graphs is a powerful approach to fully-automated planning which is implemented in the well-known LPG planner. The approach is based on a stochastic local search procedure exploring a space of partial plans and

Fast plan adaptation is important in many AI applications. From a theoretical point of view, in the worst case adapting an existing plan to solve a new problem is no more efficient than a complete regeneration of the plan. However, in practice plan adaptation can be much more efficient than plan generation, especially when the adapted plan can be obtained by performing a limited amount of changes to the original plan. In this paper, we investigate a domain-independent method for plan adaptation that modifies the original plan by replanning within limited temporal windows containing portions of the plan that need to be revised. Each window is associated with a particular replanning subproblem that contains some “heuristic goals” facilitating the plan adaptation, and that can be solved using different planning methods. An experimental analysis shows that, in practice, adapting a given plan for solving a new problem using our techniques can be much more efficient than replanning from scratch.

Despite the recent advances in planning for classical domains, the question of how to use domain knowledge in planning is yet to be completely and clearly answered. Some of the existing planners use domain-independent search heuristics, and some others depend on intensively-engineered domain-specific knowledge to guide the planning process. In this paper, we describe an approach to combine ideas from both of the above schools of thought. We present Duet, our planning system that incorporates the ability of using hierarchical domain knowledge in the form of Hierarchical Task Networks (HTNs) as in SHOP2 [14] and using domain-independent local search techniques as in LPG [8]. In our experiments, Duet was able to solve much larger problems than LPG could solve, with only minimal domain knowledge encoded in HTNs (much less domain knowledge than SHOP2 needed to solve those problems by itself).

Automated planning is a central area of artificial intelligence, involving the design of languages and computational models for reasoning about actions, change and time. In domain-independent planning, a planning problem is specified by the description of an initial world state, a set of desired goals to achieve and a set of possible actions or action schemata (domain operators). A solution of a planning problem is a (partially) ordered set of actions forming a valid plan, whose execution in the initial state transforms it into a world state where the problem goals are satisfied.

The treatment of exogenous events in planning is practically important in many real-world domains where the preconditions of certain plan actions are affected by such events. In this paper we focus on planning in temporal domains with exogenous events that happen at known times, imposing the constraint that certain actions in the plan must be executed during some predefined time windows. When actions have durations, handling such temporal constraints adds an extra difficulty to planning. We propose an approach to planning in these domains which integrates constraint-based temporal reasoning into a graph-based planning framework using local search. Our techniques are implemented in a planner that took part in the 4th International Planning Competition (IPC-4). A statistical analysis of the results of IPC-4 demonstrates the effectiveness of our approach in terms of both CPU-time and plan quality. Additional experiments show the good performance of the temporal reasoning techniques integrated into our planner.

We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting 'durative actions' and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called 'Temporal Action Graphs' (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.

This paper addresses the problem of efficiently updating a network of temporal constraints when constraints are removed from or added to an existing network. Such processing tasks are important in many AI applications requiring a temporal reasoning module. First we analyze the relationship between shortest-paths algorithms for directed graphs and arc-consistency techniques. Then we focus on a subclass of STP for which we propose new fast incremental algorithms for consistency checking and for maintaining the feasible times of the temporal variables.

We propose some domain-independent techniques for bringing well-founded partial-order planners closer to practicality. The first two techniques are aimed at improving search control while keeping overhead costs low. One is based on a simple adjustment to the default A* heuristic used by UCPOP to select plans for refinement. The other is based on preferring ``zero commitment'' (forced) plan refinements whenever possible, and using LIFO prioritization otherwise. A more radical technique is the use of operator parameter domains to prune search. These domains are initially computed from the definitions of the operators and the initial and goal conditions, using a polynomial-time algorithm that propagates sets of constants through the operator graph, starting in the initial conditions. During planning, parameter domains can be used to prune nonviable operator instances and to remove spurious clobbering threats. In experiments based on modifications of UCPOP, our improved plan and goal selection strategies gave speedups by factors ranging from 5 to more than 1000 for a variety of problems that are nontrivial for the unmodified version. Crucially, the hardest problems gave the greatest improvements. The pruning technique based on parameter domains often gave speedups by an order of magnitude or more for difficult problems, both with the default UCPOP search strategy and with our improved strategy. The Lisp code for our techniques and for the test problems is provided in on-line appendices.

Describes some simple domain-independent improvements to plan refinement strategies for well-founded partial order planning that promise to bring this style of planning closer to practicality. One suggestion concerns the strategy for selecting plans for refinement among the current (incomplete) candidate plans. We propose an A* heuristic that counts only steps and open conditions, while ignoring "unsafe conditions" (threats). A second suggestion concerns the strategy for selecting open conditions (goals) to be established next in a selected incomplete plan. We propose a variant of a strategy suggested by Peot and Smith (1993) and studied by Joslin and Pollack (1994); the variant gives top priority to unmatchable open conditions (enabling the elimination of the plan), second-highest priority to goals that can only be achieved uniquely and otherwise uses LIFO (last-in, first-out) prioritization. The preference for uniquely achievable goals is a "zero-commitment" strategy in the sense that the corresponding plan refinements are a matter of deductive certainty, involving no guesswork. In experiments based on modifications of UCPOP (Unsafe Conditions Partial Order Planner), we have obtained improvements by factors ranging from 5 to more than 600 for a variety of problems that are nontrivial for the unmodified version. Crucially, the hardest problems give the greatest improvements.

Reasoning about temporal information is an important task in many areas of Artificial Intelligence. In this paper we address the problem of scalability in temporal reasoning by providing a collection of new algorithms for efficiently managing large sets of qualitative temporal relations. We focus on the class of relations forming the Point Algebra (PA-relations) and on a major extension to include binary disjunctions of PA-relations (PA-disjunctions). Such disjunctions add a great deal of expressive power, including the ability to stipulate disjointness of temporal intervals, which is important in planning applications. Our representation of time is based on timegraphs, graphs partitioned into a set of chains on which the search is supported by a metagraph data structure. The approach is an extension of the time representation proposed by Schubert, Taugher and Miller in the context of story comprehension. The algorithms herein enable construction of a timegraph from a given set of PA-relations, querying a timegraph, and efficiently checking the consistency of a timegraph augmented by a set of PA-disjunctions. Experimental results illustrate the efficiency of the proposed approach.

We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O(max(n3, n2 m)) time (for n points and m ≠‐relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.

We describe two domain-independent temporal reasoning systems called TimeGraph I and II which can be used in AI-applications as tools for efficiently managing large sets of relations in the Point Algebra, in the Interval Algebra, and metric information such as absolute times and durations. Our representation of time is based on timegraphs, graphs partitioned into a set of chains on which the search is supported by a metagraph data structure. TimeGraph I was originally developed by Taugher, Schubert and Miller (1990) in the context of story comprehension. TimeGraph II provides useful extensions, including efficient algorithms for handing inequations, and relations expressing point-interval exclusion and interval disjointness. These extensions make the system much more expressive in the representation of qualitative information and suitable for a large class of applications.>