Sylvie Thiébaux

ECAI Conference 2025 Conference Paper

An Operator-Centric Trustable Decision-Making Tool for Planning Ground Logistic Operations of Beluga Aircraft

• Rebecca Eifler
• Nika Beriachvili
• Arthur Bit-Monnot
• Dillon Z. Chen
• Jan Eisenhut
• Jörg Hoffmann 0001
• Sylvie Thiébaux
• Florent Teichteil-Königsbuch

This paper presents the demonstrator developed in the TUPLES European Union research project for assisting human operators at Airbus to plan Beluga cargo ground logistic operations. The demonstrator features techniques providing robust, explainable, and safe decisions, which all contribute to making our decision-support system trusted by the operators. We have also worked on various planning methods to scale up to the size of the real industrial problem, including hybrid machine learning and symbolic algorithms. We demonstrate the software that was tested by Airbus operators during a user study in Finkenwerder’s production site in May 2025.

ECAI Conference 2025 Conference Paper

Effective Data Generation and Feature Selection in Learning for Planning

• Mingyu Hao
• Dillon Z. Chen
• Felipe W. Trevizan
• Sylvie Thiébaux

Previous studies have shown that leveraging data beyond optimal training plans improves the learning of search guidance for planning. Specifically, state ranking information can be extracted from states on optimal plan traces and their siblings. In this paper, we generalise this approach by extracting additional rankings from the A⋆ search tree for generating optimal training plans. As in the previous approach, we incur no additional search effort and negligible computational overhead for data extraction. However, extracting more data in this way may introduce many redundant features and states which slows down training. We formalise the problem of sound, redundant feature pruning and show that it is NP-complete to solve. Furthermore, we introduce several algorithms and approximations for redundant feature pruning. Experiments show that rankings learned by extracting more data from search trees for generating optimal training plans improve planner coverage. However, pairing with unsound pruning methods often results in diminishing performance, while our sound feature pruning methods provide consistent improvements across tested domains.

ECAI Conference 2024 Conference Paper

Decision-Focused Learning to Predict Action Costs for Planning

• Jayanta Mandi
• Marco Foschini
• Daniel Höller
• Sylvie Thiébaux
• Jörg Hoffmann 0001
• Tias Guns

In many automated planning applications, action costs can be hard to specify. An example is the time needed to travel through a certain road segment, which depends on many factors, such as the current weather conditions. A natural way to address this issue is to learn to predict these parameters based on input features (e. g. , weather forecasts) and use the predicted action costs in automated planning afterward. Decision-Focused Learning (DFL) has been successful in learning to predict the parameters of combinatorial optimization problems in a way that optimizes solution quality rather than prediction quality. This approach yields better results than treating prediction and optimization as separate tasks. In this paper, we investigate for the first time the challenges of implementing DFL for automated planning in order to learn to predict the action costs. There are two main challenges to overcome: (1) planning systems are called during gradient descent learning, to solve planning problems with negative action costs, which are not supported in planning. We propose novel methods for gradient computation to avoid this issue. (2) DFL requires repeated planner calls during training, which can limit the scalability of the method. We experiment with different methods approximating the optimal plan as well as an easy-to-implement caching mechanism to speed up the learning process. As the first work that addresses DFL for automated planning, we demonstrate that the proposed gradient computation consistently yields significantly better plans than predictions aimed at minimizing prediction error; and that caching can temper the computation requirements.

ICAPS Conference 2024 Conference Paper

Explaining the Space of SSP Policies via Policy-Property Dependencies: Complexity, Algorithms, and Relation to Multi-Objective Planning

• Marcel Steinmetz
• Sylvie Thiébaux
• Daniel Höller
• Florent Teichteil-Königsbuch

Stochastic shortest path (SSP) problems are a common framework for planning under uncertainty. However, the reactive structure of their solution policies is typically not easily comprehensible by an end-user, nor do planners justify the reasons behind their choice of a particular policy over others. To strengthen confidence in the planner

NeurIPS Conference 2024 Conference Paper

Graph Learning for Numeric Planning

• Dillon Z. Chen
• Sylvie Thiébaux

Graph learning is naturally well suited for use in symbolic, object-centric planning due to its ability to exploit relational structures exhibited in planning domains and to take as input planning instances with arbitrary number of objects. Numeric planning is an extension of symbolic planning in which states may now also exhibit numeric variables. In this work, we propose data-efficient and interpretable machine learning models for learning to solve numeric planning tasks. This involves constructing a new graph kernel for graphs with both continuous and categorical attributes, as well as new optimisation methods for learning heuristic functions for numeric planning. Experiments show that our graph kernels are vastly more efficient and generalise better than graph neural networks for numeric planning, and also yield competitive coverage performance over domain-independent numeric planners.

IJCAI Conference 2024 Conference Paper

Guiding GBFS through Learned Pairwise Rankings

• Mingyu Hao
• Felipe Trevizan
• Sylvie Thiébaux
• Patrick Ferber
• Jörg Hoffmann

We propose a new approach based on ranking to learn to guide Greedy Best-First Search (GBFS). As previous ranking approaches, ours is based on the observation that directly learning a heuristic function is overly restrictive, and that GBFS is capable of efficiently finding good plans for a much more flexible class of total quasi-orders over states. In order to learn an optimal ranking function, we introduce a new ranking framework capable of leveraging any neural network regression model and efficiently handling the training data through batching. Compared with previous ranking approaches for planning, ours does not require complex loss functions and allows training on states outside the optimal plan with minimal overhead. Our experiments on the domains of the latest planning competition learning track show that our approach substantially improves the coverage of the underlying neural network models without degrading plan quality.

AAAI Conference 2024 Conference Paper

Learning Domain-Independent Heuristics for Grounded and Lifted Planning

• Dillon Z. Chen
• Sylvie Thiébaux
• Felipe Trevizan

We present three novel graph representations of planning tasks suitable for learning domain-independent heuristics using Graph Neural Networks (GNNs) to guide search. In particular, to mitigate the issues caused by large grounded GNNs we present the first method for learning domain-independent heuristics with only the lifted representation of a planning task. We also provide a theoretical analysis of the expressiveness of our models, showing that some are more powerful than STRIPS-HGN, the only other existing model for learning domain-independent heuristics. Our experiments show that our heuristics generalise to much larger problems than those in the training set, vastly surpassing STRIPS-HGN heuristics.

ICAPS Conference 2024 Conference Paper

Learning Generalised Policies for Numeric Planning

• Ryan Xiao Wang
• Sylvie Thiébaux

We extend Action Schema Networks (ASNets) to learn generalised policies for numeric planning, which features quantitative numeric state variables, preconditions and effects. We propose a neural network architecture that can reason about the numeric variables both directly and in context of other variables. We also develop a dynamic exploration algorithm for more efficient training, by better balancing the exploration versus learning tradeoff to account for the greater computational demand of numeric teacher planners. Experimentally, we find that the learned generalised policies are capable of outperforming traditional numeric planners on some domains, and the dynamic exploration algorithm to be on average much faster at learning effective generalised policies than the original ASNets training algorithm.

ICAPS Conference 2024 Conference Paper

Neuro-Symbolic Learning of Lifted Action Models from Visual Traces

• Kai Xi 0001
• Stephen Gould
• Sylvie Thiébaux

Model-based planners rely on action models to describe available actions in terms of their preconditions and effects. Nonetheless, manually encoding such models is challenging, especially in complex domains. Numerous methods have been proposed to learn action models from examples of plan execution traces. However, high-level information, such as state labels within traces, is often unavailable and needs to be inferred indirectly from raw observations. In this paper, we aim to learn lifted action models from visual traces --- sequences of image-action pairs depicting discrete successive trace steps. We present ROSAME, a differentiable neuRO-Symbolic Action Model lEarner that infers action models from traces consisting of probabilistic state predictions and actions. By combining ROSAME with a deep learning computer vision model, we create an end-to-end framework that jointly learns state predictions from images and infers symbolic action models. Experimental results demonstrate that our method succeeds in both tasks, using different visual state representations, with the learned action models often matching or even surpassing those created by humans.

SoCS Conference 2024 Conference Paper

Novelty Heuristics, Multi-Queue Search, and Portfolios for Numeric Planning

• Dillon Z. Chen
• Sylvie Thiébaux

Heuristic search is a powerful approach for solving planning problems and numeric planning is no exception. In this paper, we boost the performance of heuristic search for numeric planning with various powerful techniques orthogonal to improving heuristic informedness: numeric novelty heuristics, the Manhattan distance heuristic, and exploring the use of multi-queue search and portfolios for combining heuristics.

ICAPS Conference 2024 Conference Paper

Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning

• Dillon Z. Chen
• Felipe W. Trevizan
• Sylvie Thiébaux

Current approaches for learning for planning have yet to achieve competitive performance against classical planners in several domains, and have poor overall performance. In this work, we construct novel graph representations of lifted planning tasks and use the WL algorithm to generate features from them. These features are used with classical machine learning methods which have up to 2 orders of magnitude fewer parameters and train up to 3 orders of magnitude faster than the state-of-the-art deep learning for planning models. Our novel approach, WL-GOOSE, reliably learns heuristics from scratch and outperforms the hFF heuristic in a fair competition setting. It also outperforms or ties with LAMA on 4 out of 10 domains on coverage and 7 out of 10 domains on plan quality. WL-GOOSE is the first learning for planning model which achieves these feats. Furthermore, we study the connections between our novel WL feature generation method, previous theoretically flavoured learning architectures, and Description Logic Features for planning.

ICAPS Conference 2023 Conference Paper

Fast and Robust Resource-Constrained Scheduling with Graph Neural Networks

• Florent Teichteil-Königsbuch
• Guillaume Povéda
• Guillermo González de Garibay Barba
• Tim Luchterhand
• Sylvie Thiébaux

Resource-Constrained Project Scheduling Problems (RCPSPs) are NP-complete, which makes it challenging to efficiently solve large instances and robustify solutions in the presence of uncertainty. To remedy this, we learn to efficiently mimic the solutions produced by Constraint Programming (CP) solver, using a Graph Neural Network (GNN) architecture designed to capture the structure of RCPSPs. Since the GNN solution may violate constraints, we ensure schedule feasibility at inference time by extracting the task ordering from the GNN schedule and post-processing it with the well-known Schedule Generation Scheme (SGS). We find that SIREN, the resulting algorithm, produces schedules that are of higher quality than those produced by the CP solver within the same computation time budget. The speed and solution quality of SIREN make it suitable as a component of an on-line scenario-based optimisation procedure for RCPSPs with stochastic durations. This leads to the SERENE system, which robustly selects, in real-time, the best next tasks to start in order to minimise the average makespan over the scenarios. Empirically, SERENE achieves better average makespan over different realisations of uncertainty than deterministic algorithms that continuously reschedule on the basis of either the worst, best or average task durations.

IJCAI Conference 2023 Conference Paper

Formal Explanations of Neural Network Policies for Planning

• Renee Selvey
• Alban Grastien
• Sylvie Thiébaux

Deep learning is increasingly used to learn policies for planning problems, yet policies represented by neural networks are difficult to interpret, verify and trust. Existing formal approaches to post-hoc explanations provide concise reasons for a single decision made by an ML model. However, understanding planning policies require explaining sequences of decisions. In this paper, we formulate the problem of finding explanations for the sequence of decisions recommended by a learnt policy in a given state. We show that, under certain assumptions, a minimal explanation for a sequence can be computed by solving a number of single decision explanation problems which is linear in the length of the sequence. We present experimental results of our implementation of this approach for ASNet policies for classical planning domains.

AAAI Conference 2023 Conference Paper

Heuristic Search for Multi-Objective Probabilistic Planning

• Dillon Z. Chen
• Felipe Trevizan
• Sylvie Thiébaux

Heuristic search is a powerful approach that has successfully been applied to a broad class of planning problems, including classical planning, multi-objective planning, and probabilistic planning modelled as a stochastic shortest path (SSP) problem. Here, we extend the reach of heuristic search to a more expressive class of problems, namely multi-objective stochastic shortest paths (MOSSPs), which require computing a coverage set of non-dominated policies. We design new heuristic search algorithms MOLAO* and MOLRTDP, which extend well-known SSP algorithms to the multi-objective case. We further construct a spectrum of domain-independent heuristic functions differing in their ability to take into account the stochastic and multi-objective features of the problem to guide the search. Our experiments demonstrate the benefits of these algorithms and the relative merits of the heuristics.

ICAPS Conference 2022 Conference Paper

Admissible Heuristics for Multi-Objective Planning

• Florian Geißer
• Patrik Haslum
• Sylvie Thiébaux
• Felipe W. Trevizan

Planning problems of practical relevance commonly include multiple objectives that are difficult to weight a priori. Several heuristic search algorithms computing the Pareto front of non-dominated solutions have been proposed to handle these multi-objective (MO) planning problems. However, the design of informative admissible heuristics to guide these algorithms has not received the same level of attention. The standard practice is to use the so-called ideal point combination, which applies a single-objective heuristic to each objective independently, without capturing any of the trade-offs between them. This paper fills this gap: we extend several classes of classical planning heuristics to the multi-objective case, in such a way as to reflect the tradeoffs underlying the various objectives. We find that MO abstraction heuristics achieve overall the best performance, but that not every MO generalisation pays off.

JAIR Journal 2020 Journal Article

ASNets: Deep Learning for Generalised Planning

• Sam Toyer
• Sylvie Thiébaux
• Felipe Trevizan
• Lexing Xie

In this paper, we discuss the learning of generalised policies for probabilistic and classical planning problems using Action Schema Networks (ASNets). The ASNet is a neural network architecture that exploits the relational structure of (P)PDDL planning problems to learn a common set of weights that can be applied to any problem in a domain. By mimicking the actions chosen by a traditional, non-learning planner on a handful of small problems in a domain, ASNets are able to learn a generalised reactive policy that can quickly solve much larger instances from the domain. This work extends the ASNet architecture to make it more expressive, while still remaining invariant to a range of symmetries that exist in PPDDL problems. We also present a thorough experimental evaluation of ASNets, including a comparison with heuristic search planners on seven probabilistic and deterministic domains, an extended evaluation on over 18,000 Blocksworld instances, and an ablation study. Finally, we show that sparsity-inducing regularisation can produce ASNets that are compact enough for humans to understand, yielding insights into how the structure of ASNets allows them to generalise across a domain.

ICAPS Conference 2020 Conference Paper

Learning Domain-Independent Planning Heuristics with Hypergraph Networks

• William Shen
• Felipe W. Trevizan
• Sylvie Thiébaux

We present the first approach capable of learning domain-independent planning heuristics entirely from scratch. The heuristics we learn map the hypergraph representation of the delete-relaxation of the planning problem at hand, to a cost estimate that approximates that of the least-cost path from the current state to the goal through the hypergraph. We generalise Graph Networks to obtain a new framework for learning over hypergraphs, which we specialise to learn planning heuristics by training over state/value pairs obtained from optimal cost plans. Our experiments show that the resulting architecture, STRIPS-HGNs, is capable of learning heuristics that are competitive with existing delete-relaxation heuristics including LM-cut. We show that the heuristics we learn are able to generalise across different problems and domains, including to domains that were not seen during training.

ICAPS Conference 2020 Conference Paper

Optimal and Heuristic Approaches for Constrained Flight Planning under Weather Uncertainty

• Florian Geißer
• Guillaume Povéda
• Felipe W. Trevizan
• Manon Bondouy
• Florent Teichteil-Königsbuch
• Sylvie Thiébaux

Aircraft flight planning is impacted by weather uncertainties. Existing approaches to flight planning are either deterministic and load additional fuel to account for uncertainty, or probabilistic but have to plan in 4D space. If constraints are imposed on the flight plan these methods provide no formal guarantees that the constraints are actually satisfied. We investigate constrained flight planning under weather uncertainty on discrete airways graphs and model this problem as a Constrained Stochastic Shortest Path (C-SSP) problem. Transitions are generated on-the-fly by the underlying aircraft performance model. As this prevents us from using off-the-shelf C-SSP solvers, we generalise column-generation methods stemming from constrained deterministic path planning to the probabilistic case. This results in a novel method which is complete but computationally expensive. We therefore also discuss deterministic and heuristic approaches which average over weather uncertainty and handle constraints by scalarising a multi-objective cost function. We evaluate and compare these approaches on real flight routes subject to real weather forecast data and a realistic aircraft performance model.

JAIR Journal 2020 Journal Article

Subgoaling Techniques for Satisficing and Optimal Numeric Planning

• Enrico Scala
• Patrik Haslum
• Sylvie Thiébaux
• Miquel Ramirez

This paper studies novel subgoaling relaxations for automated planning with propositional and numeric state variables. Subgoaling relaxations address one source of complexity of the planning problem: the requirement to satisfy conditions simultaneously. The core idea is to relax this requirement by recursively decomposing conditions into atomic subgoals that are considered in isolation. Such relaxations are typically used for pruning, or as the basis for computing admissible or inadmissible heuristic estimates to guide optimal or satisificing heuristic search planners. In the last decade or so, the subgoaling principle has underpinned the design of an abundance of relaxation-based heuristics whose formulations have greatly extended the reach of classical planning. This paper extends subgoaling relaxations to support numeric state variables and numeric conditions. We provide both theoretical and practical results, with the aim of reaching a good trade-off between accuracy and computation costs within a heuristic state-space search planner. Our experimental results validate the theoretical assumptions, and indicate that subgoaling substantially improves on the state of the art in optimal and satisficing numeric planning via forward state-space search.

SoCS Conference 2019 Conference Paper

Guiding Search with Generalized Policies for Probabilistic Planning

• William Shen
• Felipe W. Trevizan
• Sam Toyer
• Sylvie Thiébaux
• Lexing Xie

We examine techniques for combining generalized policies with search algorithms to exploit the strengths and overcome the weaknesses of each when solving probabilistic planning problems. The Action Schema Network (ASNet) is a recent contribution to planning that uses deep learning and neural networks to learn generalized policies for probabilistic planning problems. ASNets are well suited to problems where local knowledge of the environment can be exploited to improve performance, but may fail to generalize to problems they were not trained on. Monte-Carlo Tree Search (MCTS) is a forward-chaining state space search algorithm for optimal decision making which performs simulations to incrementally build a search tree and estimate the values of each state. Although MCTS can achieve state-of-the-art results when paired with domain-specific knowledge, without this knowledge, MCTS requires a large number of simulations in order to obtain reliable state-value estimates. By combining ASNets with MCTS, we are able to improve the capability of an ASNet to generalize beyond the distribution of problems it was trained on, as well as enhance the navigation of the search space by MCTS.

AAAI Conference 2018 Conference Paper

Action Schema Networks: Generalised Policies With Deep Learning

• Sam Toyer
• Felipe Trevizan
• Sylvie Thiébaux
• Lexing Xie

In this paper, we introduce the Action Schema Network (AS- Net): a neural network architecture for learning generalised policies for probabilistic planning problems. By mimicking the relational structure of planning problems, ASNets are able to adopt a weight sharing scheme which allows the network to be applied to any problem from a given planning domain. This allows the cost of training the network to be amortised over all problems in that domain. Further, we propose a training method which balances exploration and supervised training on small problems to produce a policy which remains robust when evaluated on larger problems. In experiments, we show that ASNet’s learning capability allows it to significantly outperform traditional non-learning planners in several challenging domains.

IJCAI Conference 2018 Conference Paper

Operator Counting Heuristics for Probabilistic Planning

• Felipe Trevizan
• Sylvie Thiébaux
• Patrik Haslum

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. In this paper, we present a generalization of the operator-counting family of heuristics to Stochastic Shortest Path problems (SSPs) that is able to represent the probability of the actions outcomes. Our experiments show that the equivalent of the net change heuristic in this generalized framework obtains significant run time and coverage improvements over other state-of-the-art heuristics in different planners.

UAI Conference 2017 Conference Paper

Efficient solutions for Stochastic Shortest Path Problems with Dead Ends

• Felipe W. Trevizan
• Florent Teichteil-Königsbuch
• Sylvie Thiébaux

Many planning problems require maximizing the probability of goal satisfaction as well as minimizing the expected cost to reach the goal. To model and solve such problems, there have been several attempts at extending Stochastic Shortest Path problems (SSPs) to deal with dead ends and optimize a dual optimization criterion. Unfortunately these extensions lack either theoretical robustness or practical efficiency. We study a new, perhaps more natural optimization criterion capturing these problems, the Min-Cost given MaxProb (MCMP) criterion. This criterion leads to the minimum expected cost policy among those with maximum success probability, and accurately accounts for the cost and risk of reaching dead ends. Moreover, it lends itself to efficient solution methods that build on recent heuristic search algorithms for the dual representation of stochastic shortest paths problems. Our experiments show up to one order of magnitude speedup over the state of the art.

IJCAI Conference 2017 Conference Paper

Landmarks for Numeric Planning Problems

• Enrico Scala
• Patrik Haslum
• Daniele Magazzeni
• Sylvie Thiébaux

The paper generalises the notion of landmarks for reasoning about planning problems involving propositional and numeric variables. Intuitively, numeric landmarks are regions in the metric space defined by the problem whose crossing is necessary for its resolution. The paper proposes a relaxation-based method for their automated extraction directly from the problem structure, and shows how to exploit them to infer what we call disjunctive and additive hybrid action landmarks. The justification of such a disjunctive representation results from the intertwined propositional and numeric structure of the problem. The paper exercises their use in two novel admissible LP-Based numeric heuristics, and reports experiments on cost-optimal numeric planning problems. Results show the heuristics are more informed and effective than previous work for problems involving a higher number of (sub)goals.

ICAPS Conference 2017 Conference Paper

Occupation Measure Heuristics for Probabilistic Planning

• Felipe W. Trevizan
• Sylvie Thiébaux
• Patrik Haslum

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. To remedy this situation, we explore the use of occupation measures, which represent the expected number of times a given action will be executed in a given state of a policy. By relaxing the well-known linear program that computes them, we derive occupation measure heuristics -- the first admissible heuristics for stochastic shortest path problems (SSPs) taking probabilities into account. We show that these heuristics can also be obtained by extending recent operator-counting heuristic formulations used in deterministic planning. Since the heuristics are formulated as linear programs over occupation measures, they can easily be extended to more complex probabilistic planning models, such as constrained SSPs (C-SSPs). Moreover, their formulation can be tightly integrated into i-dual, a recent LP-based heuristic search algorithm for (constrained) SSPs, resulting in a novel probabilistic planning approach in which policy update and heuristic computation work in unison. Our experiments in several domains demonstrate the benefits of these new heuristics and approach.

ICAPS Conference 2016 Conference Paper

Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems

• Felipe W. Trevizan
• Sylvie Thiébaux
• Pedro Henrique de Rodrigues Quemel e Assis Santana
• Brian Williams 0001

We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, which, to the best of our knowledge, is the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments on a suite of PPDDL problems augmented with constraints show that these features enable i-dual to achieve up to two orders of magnitude improvement in run-time and memory over linear programming algorithms.

ECAI Conference 2016 Conference Paper

Interval-Based Relaxation for General Numeric Planning

• Enrico Scala
• Patrik Haslum
• Sylvie Thiébaux
• Miquel Ramírez

We generalise the interval-based relaxation to sequential numeric planning problems with non-linear conditions and effects, and cyclic dependencies. This effectively removes all the limitations on the problem placed in previous work on numeric planning heuristics, and even allows us to extend the planning language with a wider set of mathematical functions. Heuristics obtained from the generalised relaxation are pruning-safe. We derive one such heuristic and use it to solve discrete-time control-like planning problems with autonomous processes. Few planners can solve such problems, and search with our new heuristic compares favourably with them.

ICAPS Conference 2016 Conference Paper

Numeric Planning with Disjunctive Global Constraints via SMT

• Enrico Scala
• Miquel Ramírez
• Patrik Haslum
• Sylvie Thiébaux

This paper describes a novel encoding for sequential numeric planning into the problem of determining the satisfiability of a logical theory T. We introduce a novel technique, orthogonal to existing work aiming at producing more succinct encodings that enables the theory solver to roll up an unbounded yet finite number of instances of an action into a single plan step, greatly reducing the horizon at which T models valid plans. The technique is then extended to deal with problems featuring disjunctive global constraints, in which the state space becomes a non-convex n dimensional polytope. In order to empirically evaluate the encoding, we build a planner, SPRINGROLL, around a state–of–the–art off– the–shelf SMT solver. Experiments on a diverse set of domains are finally reported, and results show the generality and efficiency of the approach.

AAAI Conference 2016 Conference Paper

RAO*: An Algorithm for Chance-Constrained POMDP’s

• Pedro Rodrigues Quemel e Assis Santana
• Sylvie Thiébaux
• Brian Williams

Autonomous agents operating in partially observable stochastic environments often face the problem of optimizing expected performance while bounding the risk of violating safety constraints. Such problems can be modeled as chance-constrained POMDP’s (CC- POMDP’s). Our first contribution is a systematic derivation of execution risk in POMDP domains, which improves upon how chance constraints are handled in the constrained POMDP literature. Second, we present RAO∗, a heuristic forward search algorithm producing optimal, deterministic, finite-horizon policies for CC- POMDP’s. In addition to the utility heuristic, RAO∗ leverages an admissible execution risk heuristic to quickly detect and prune overly-risky policy branches. Third, we demonstrate the usefulness of RAO∗ in two challenging domains of practical interest: power supply restoration and autonomous science agents.

ICAPS Conference 2014 Conference Paper

Optimal Planning with Global Numerical State Constraints

• Franc Ivankovic
• Patrik Haslum
• Sylvie Thiébaux
• Vikas Shivashankar
• Dana S. Nau

Automating the operations of infrastructure networks such as energy grids and oil pipelines requires a range of planning and optimisation technologies. However, current planners face significant challenges in responding to this need. Notably, they are unable to model and reason about the global numerical state constraints necessary to capture flows and similar physical phenomena occurring in these networks. A single discrete control action can affect the flow throughout the network in a way that may depend on the entire network topology. Determining whether preconditions, goals and invariant conditions are satisfied requires solving a system of numerical constraints after each action application. This paper extends domain-independent optimal planning to this kind of reasoning. We present extensions of the formalism, relaxed plans, and heuristics, as well as new search variants and experimental results on two problem domains.

TCS Journal 2014 Journal Article

Recent advances in unfolding technique

• Blai Bonet
• Patrik Haslum
• Victor Khomenko
• Sylvie Thiébaux
• Walter Vogler

We propose a new, and to date the most general, framework for Petri net unfolding, which broadens its applicability, makes it easier to use, and increases its efficiency. In particular: (i) we propose a user-oriented view of the unfolding technique, which simply tells which information will be preserved in the final prefix and how to declare an event a cut-off in the algorithm, while hiding the technical parameters like the adequate order; (ii) the notion of the adequate order is generalised to a well-founded relation, and the requirement that it must refine ⊂ is replaced by a weaker one; and (iii) the order in which the unfolding algorithm selects the possible extensions of the prefix is entirely disentangled from the cut-off condition. We demonstrate the usefulness of the developed theory on some case studies.

IJCAI Conference 2013 Conference Paper

Planning with MIP for Supply Restoration in Power Distribution Systems

• Sylvie Thiébaux
• Carleton Coffrin
• Hassan Hijazi
• John Slaney

IJCAI Conference 2013 Conference Paper

Randomized Load Control: A Simple Distributed Approach for Scheduling Smart Appliances

• Menkes van den Briel
• Paul Scott
• Sylvie Thiébaux

A significant portion of the electricity network capacity is built to run only a few days a year when demand peaks. As a result, expensive power generation plants and equipment costing millions of dollars are sitting idle most of the time, which increases costs for everyone. We present randomized load control, a simple distributed approach for scheduling smart appliances. Randomized load control schedules the start time of appliances that are programmed to run within a specified time window, so that the aggregate load achieves a given ideal load. Our results show that we do achieve the given ideal load to a great extent. This is remarkable as the approach is completely distributed and preserves customer privacy as the scheduling happens within each house or building separately.

ICAPS Conference 2012 Conference Paper

CP and MIP Methods for Ship Scheduling with Time-Varying Draft

• Elena Kelareva
• Sebastian Brand
• Philip Kilby
• Sylvie Thiébaux
• Mark Wallace 0001

Existing ship scheduling approaches either ignore constraints on ship draft (distance between the waterline and the keel), or model these in very simple ways, such as a constant draft limit that does not change with time. However, in most ports the draft restriction changes over time due to variation in environmental conditions. More accurate consideration of draft constraints would allow more cargo to be scheduled for transport on the same set of ships. We present constraint programming (CP) and mixed integer programming (MIP) models for the problem of scheduling ships at a port with time-varying draft constraints so as to optimise cargo throughput at the port. We also investigate the effect of several variations to the CP model, including a model containing sequence variables, and a model with ordered inputs. Our model allows us to solve realistic instances of the problem to optimality in a very short time, and produces better schedules than both scheduling with constant draft, and manual scheduling approaches used in practice at ports.

ICAPS Conference 2012 Conference Paper

Minimal Landmarks for Optimal Delete-Free Planning

• Patrik Haslum
• John K. Slaney
• Sylvie Thiébaux

We present a simple and efficient algorithm to solve delete-free planning problems optimally and calculate the h+ heuristic. The algorithm efficiently computes a minimum-cost hitting set for a complete set of disjunctive action landmarks generated on the fly. Unlike other recent approaches, the landmarks it generates are guaranteed to be set-inclusion minimal. In almost all delete-relaxed IPC domains, this leads to a significant coverage and runtime improvement.

ECAI Conference 2010 Conference Paper

A Decentralised Symbolic Diagnosis Approach

• Anika Schumann
• Yannick Pencolé
• Sylvie Thiébaux

This paper considers the diagnosis of large discrete-event systems consisting of many components. The problem is to determine, online, all failures and states that explain a given sequence of observations. Several model-based diagnosis approaches deal with this problem but they usually have either poor time performance or result in space explosion. Recent work has shown that both problems can be tackled when encoding diagnosis approaches symbolically by means of binary decision diagrams. This paper further improves upon these results and presents a decentralised symbolic diagnosis method that computes the diagnosis information for each component off-line and then combines them on-line. Experimental results show that our method provides significant improvements over existing approaches.

ICAPS Conference 2010 Conference Paper

Cost-Optimal Factored Planning: Promises and Pitfalls

• Eric Fabre
• Loïg Jezequel
• Patrik Haslum
• Sylvie Thiébaux

Factored planning methods aim to exploit locality to efficiently solve large but "loosely coupled" planning problems by computing solutions locally and propagating limited information between components. However, all factored planning methods presented so far work with representations that require certain parameters to be bounded (e. g. number of coordination points between local plans considered); the satisfaction of those bounds by a given problem instance is difficult to establish a priori, and the influence of those parameters on the problem complexity is unclear. We present an instance of the factored planning framework using a representation of the (regular) sets of local plans by finite automata, which does not require any such bound. By substituting weighted automata, we can even do factored cost-optimal planning. We test an implementation of the method on the few standard planning benchmarks that we have found to be amenable to factoring. We show that this method runs in polynomial time under conditions similar to those considered in previous work, but not only under those conditions. Thus, what constitutes an essential measure of "factorability" remains obscure.

AIJ Journal 2009 Journal Article

Advances in automated plan generation

• Maria Fox
• Sylvie Thiébaux

ICAPS Conference 2006 Conference Paper

Concurrent Probabilistic Planning in the Graphplan Framework

• Iain Little
• Sylvie Thiébaux

We consider the problem of planning optimally in potentially concurrent probabilistic domains: actions have probabilistic effects and may execute in parallel under certain conditions; we seek a contingency plan that maximises the probability of reaching the goal. The Graphplan framework has proven to be highly successful at solving classical planning problems, but has not previously been applied to probabilistic planning in its entirety. We present an extension of the full framework to probabilistic domains that demonstrates a method of efficiently finding optimal contingency plans using a goal regression search. Paragraph, the resulting planner, is competitive with the state of the art, producing acyclic or cyclic plans that optionally exploit a problem's potential for concurrency.

AIJ Journal 2005 Journal Article

In defense of PDDL axioms

• Sylvie Thiébaux
• Jörg Hoffmann
• Bernhard Nebel

There is controversy as to whether explicit support for pddl-like axioms and derived predicates is needed for planners to handle real-world domains effectively. Many researchers have deplored the lack of precise semantics for such axioms, while others have argued that it might be best to compile them away. We propose an adequate semantics for pddl axioms and show that they are an essential feature by proving that it is impossible to compile them away if we restrict the growth of plans and domain descriptions to be polynomial. These results suggest that adding a reasonable implementation to handle axioms inside the planner is beneficial for the performance. Our experiments confirm this suggestion.

ICAPS Conference 2005 Conference Paper

Search Control in Planning for Temporally Extended Goals

• Froduald Kabanza
• Sylvie Thiébaux

Current techniques for reasoning about search control knowledge in AI planning, such as those used in TLPlan, TALPlanner, or SHOP2, assume that search control knowledge is conditioned upon and interpreted with respect to a fixed set of goal states. Therefore, these techniques can deal with reachability goals but do not apply to temporally extended goals, such as goals of achieving a condition whenever a certain fact becomes true. Temporally extended goals convey several intermediate reachability goals to be achieved at different point of execution, sometimes with cyclic executions; that is, the notion of goal state becomes dynamic. In this paper, we describe a method for reasoning about search control knowledge in the presence of temporally extended goals. Given such a goal, we generate an equivalent Buchi automaton---an automaton recognising the language of the executions satisfying the goal---and interpret control knowledge over this automaton and the world state trajectories generated by a forward search planner. This method is implemented and experimented with as an extension of the TLPlan planner, which incidentally becomes capable of handling cyclic goals.

ICAPS Conference 2004 Conference Paper

Decision-Theoretic Military Operations Planning

• Douglas Aberdeen
• Sylvie Thiébaux
• Lin Zhang

Military operations planning involves concurrent actions, resource assignment, and conflicting costs. Individual tasks sometimes fail with a known probability, promoting a decision-theoretic approach. The planner must choose between multiple tasks that achieve similar outcomes but have different costs. The military domain is particularly suited to automated methods because hundreds of tasks, specified by many planning staff, need to be quickly and robustly coordinated. The authors are not aware of any previous planners that handle all characteristics of the operations planning domain in a single package. This paper shows that problems with such features can be successfully approached by realtime heuristic search algorithms, operating on a formulation of the problem as a Markov decision process. Novel automatically generated heuristics, and classic caching methods, allow problems of interesting sizes to be handled. Results are presented on data provided by the Australian Defence Science and Technology Organisation.

UAI Conference 2004 Conference Paper

Exploiting First-Order Regression in Inductive Policy Selection

• Charles Gretton
• Sylvie Thiébaux

We consider the problem of computing optimal generalised policies for relational Markov decision processes. We describe an approach combining some of the benefits of purely inductive techniques with those of symbolic dynamic programming methods. The latter reason about the optimal value function using first-order decision theoretic regression and formula rewriting, while the former, when provided with a suitable hypotheses language, are capable of generalising value functions or policies for small instances. Our idea is to use reasoning and in particular classical first-order regression to automatically generate a hypotheses language dedicated to the domain at hand, which is then used as input by an inductive solver. This approach avoids the more complex reasoning of symbolic dynamic programming while focusing the inductive solver's attention on concepts that are specifically relevant to the optimal value function for the domain considered.

ECAI Conference 2004 Conference Paper

Symbolic Models for Diagnosing Discrete-Event Systems

• Anika Schumann
• Yannick Pencolé
• Sylvie Thiébaux

ICAPS Conference 2003 Conference Paper

GPT Meets PSR

• Blai Bonet
• Sylvie Thiébaux

We present a case study in confronting the GPT generalpurpose planner with the challenging power supply restoration (PSR) benchmark for contingent planning. PSR is derived from a real-world problem, and the difficulty of modeling and solving it contrasts with that of the purely artificial benchmarks commonly used in the literature. This confrontation leads us to improve general techniques for contingent planning, to provide a PDDL-syle encoding of PSR which we hope to see used in planning competitions, and to report the first results on generating optimal policies for PSR.

UAI Conference 2003 Conference Paper

Implementation and Comparison of Solution Methods for Decision Processes with Non-Markovian Rewards

• Charles Gretton
• David Price
• Sylvie Thiébaux

This paper examines a number of solution methods for decision processes with non-Markovian rewards (NMRDPs). They all exploit a temporal logic specification of the reward function to automatically translate the NMRDP into an equivalent Markov decision process (MDP) amenable to well-known MDP solution methods. They differ however in the representation of the target MDP and the class of MDP solution methods to which they are suited. As a result, they adopt different temporal logics and different translations. Unfortunately, no implementation of these methods nor experimental let alone comparative results have ever been reported. This paper is the first step towards filling this gap. We describe an integrated system for solving NMRDPs which implements these methods and several variants under a common interface; we use it to compare the various approaches and identify the problem features favoring one over the other

UAI Conference 2002 Conference Paper

Anytime State-Based Solution Methods for Decision Processes with non-Markovian Rewards

• Sylvie Thiébaux
• Froduald Kabanza
• John K. Slaney

A popular approach to solving a decision process with non-Markovian rewards (NMRDP) is to exploit a compact representation of the reward function to automatically translate the NMRDP into an equivalent Markov decision process (MDP) amenable to our favorite MDP solution method. The contribution of this paper is a representation of non-Markovian reward functions and a translation into MDP aimed at making the best possible use of state-based anytime algorithms as the solution method. By explicitly constructing and exploring only parts of the state space, these algorithms are able to trade computation time for policy quality, and have proven quite effective in dealing with large MDPs. Our representation extends future linear temporal logic (FLTL) to express rewards. Our translation has the effect of embedding model-checking in the solution method. It results in an MDP of the minimal size achievable without stepping outside the anytime framework, and consequently in better policies by the deadline.

ECAI Conference 2002 Conference Paper

Solving Power Supply Restoration Problems with Planning via Symbolic Model Checking

• Piergiorgio Bertoli
• Alessandro Cimatti
• John K. Slaney
• Sylvie Thiébaux

AIJ Journal 2001 Journal Article

Blocks World revisited

• John Slaney
• Sylvie Thiébaux

Contemporary AI shows a healthy trend away from artificial problems towards real-world applications. Less healthy, however, is the fashionable disparagement of “toy” domains: when properly approached, these domains can at the very least support meaningful systematic experiments, and allow features relevant to many kinds of reasoning to be abstracted and studied. A major reason why they have fallen into disrepute is that superficial understanding of them has resulted in poor experimental methodology and consequent failure to extract useful information. This paper presents a sustained investigation of one such toy: the (in)famous Blocks World planning problem, and provides the level of understanding required for its effective use as a benchmark. Our results include methods for generating random problems for systematic experimentation, the best domain-specific planning algorithms against which AI planners can be compared, and observations establishing the average plan quality of near-optimal methods. We also study the distribution of hard/easy instances, and identify the structure that AI planners must be able to exploit in order to approach Blocks World successfully.

ECAI Conference 2000 Conference Paper

Estimating the Hardness of Optimisation

• John K. Slaney
• Sylvie Thiébaux
• Philip Kilby

ECAI Conference 1998 Conference Paper

On the Hardness of Decision and Optimisation Problems

• John K. Slaney
• Sylvie Thiébaux

UAI Conference 1996 Conference Paper

Supply Restoration in Power Distribution Systems: A Case Study in Integrating Model-Based Diagnosis and Repair Planning

• Sylvie Thiébaux
• Marie-Odile Cordier
• Olivier Jehl
• Jean-Paul Krivine

Integrating diagnosis and repair is particularly crucial when gaining sufficient information to discriminate between several candidate diagnoses requires carrying out some repair actions. A typical case is supply restoration in a faulty power distribution system. This problem, which is a major concern for electricity distributors, features partial observability, and stochastic repair actions which are more elaborate than simple replacement of components. This paper analyses the difficulties in applying existing work on integrating model-based diagnosis and repair and on planning in partially observable stochastic domains to this real-world problem, and describes the pragmatic approach we have retained so far.