Author name cluster

Chiara Piacentini

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers

2 author rows

JAIR Journal 2022 Journal Article

The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions

Ryo Kuroiwa
Alexander Shleyfman
Chiara Piacentini
Margarita P. Castro
J. Christopher Beck

The LM-cut heuristic, both alone and as part of the operator counting framework, represents one of the most successful heuristics for classical planning. In this paper, we generalize LM-cut and its use in operator counting to optimal numeric planning with simple conditions and simple numeric effects, i.e., linear expressions over numeric state variables and actions that increase or decrease such variables by constant quantities. We introduce a variant of hmaxhbd (a previously proposed numeric hmax heuristic) based on the delete-relaxed version of such planning tasks and show that, although inadmissible by itself, our variant yields a numeric version of the classical LM-cut heuristic which is admissible. We classify the three existing families of heuristics for this class of numeric planning tasks and introduce the LM-cut family, proving dominance or incomparability between all pairs of existing max and LM-cut heuristics for numeric planning with simple conditions. Our extensive empirical evaluation shows that the new LM-cut heuristic, both on its own and as part of the operator counting framework, is the state-of-the-art for this class of numeric planning problem.

PDF Details DOI

AIJ Journal 2021 Journal Article

A unifying look at sequence submodularity

Sara Bernardini
Fabio Fagnani
Chiara Piacentini

Several real-world problems in engineering and applied science require the selection of sequences that maximize a given reward function. Optimizing over sequences as opposed to sets requires exploring an exponentially larger search space and can become prohibitive in most cases of practical interest. However, if the objective function is submodular (intuitively, it exhibits a diminishing return property), the optimization problem becomes more manageable. Recently, there has been increasing interest in sequence submodularity in connection with applications such as recommender systems and online ad allocation. However, mostly ad hoc models and solutions have emerged within these applicative contexts. In consequence, the field appears fragmented and lacks coherence. In this paper, we offer a unified view of sequence submodularity and provide a generalized greedy algorithm that enjoys strong theoretical guarantees. We show how our approach naturally captures several application domains, and our algorithm encompasses existing methods, improving over them.

Details DOI

ICAPS Conference 2021 Conference Paper

LM-cut and Operator Counting Heuristics for Optimal Numeric Planning with Simple Conditions

Ryo Kuroiwa 0002
Alexander Shleyfman
Chiara Piacentini
Margarita P. Castro
J. Christopher Beck

We consider optimal numeric planning with numeric conditions consisting of linear expressions of numeric state variables and actions that increase or decrease numeric state variables by constant quantities. We build on previous research to introduce a new variant of the numeric hmax heuristic based on the delete-relaxed version of such planning tasks. Although our hmax heuristic is inadmissible, it yields a numeric version of the classical LM-cut heuristic which is admissible. Further, we prove that our LM-cut heuristic neither dominates nor is dominated by the existing numeric heuristic hmax(hbd). We show that admissibility also holds when integrating the numeric cuts into the operator-counting (OC) heuristic producing an admissible numeric version of the OC heuristic. Through experiments, we demonstrate that both these heuristics compete favorably with the state-of-the-art heuristics: in particular, while sometimes expanding more nodes than other heuristics, numeric OC solves 19 more problem instances than the next closest heuristic.

Details

JAIR Journal 2020 Journal Article

Solving Delete Free Planning with Relaxed Decision Diagram Based Heuristics

Margarita Paz Castro
Chiara Piacentini
Andre Augusto Cire
J. Christopher Beck

We investigate the use of relaxed decision diagrams (DDs) for computing admissible heuristics for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the introduction of two novel DD encodings for a DFP task: a multivalued decision diagram that includes the sequencing aspect of the problem and a binary decision diagram representation of its sequential relaxation. We present construction algorithms for each DD that leverage these different perspectives of the DFP task and provide theoretical and empirical analyses of the associated heuristics. We further show that relaxed DDs can be used beyond heuristic computation to extract delete-free plans, find action landmarks, and identify redundant actions. Our empirical analysis shows that while DD-based heuristics trail the state of the art, even small relaxed DDs are competitive with the linear programming heuristic for the DFP task, thus, revealing novel ways of designing admissible heuristics.

PDF Details DOI

ICAPS Conference 2020 Conference Paper

Through the Lens of Sequence Submodularity

Sara Bernardini
Fabio Fagnani
Chiara Piacentini

Details

JAIR Journal 2019 Journal Article

Autonomous Target Search with Multiple Coordinated UAVs

Chiara Piacentini
Sara Bernardini
J. Christopher Beck

Search and tracking is the problem of locating a moving target and following it to its destination. In this work, we consider a scenario in which the target moves across a large geographical area by following a road network and the search is performed by a team of unmanned aerial vehicles (UAVs). We formulate search and tracking as a combinatorial optimization problem and prove that the objective function is submodular. We exploit this property to devise a greedy algorithm. Although this algorithm does not offer strong theoretical guarantees because of the presence of temporal constraints that limit the feasibility of the solutions, it presents remarkably good performance, especially when several UAVs are available for the mission. As the greedy algorithm suffers when resources are scarce, we investigate two alternative optimization techniques: Constraint Programming (CP) and AI planning. Both approaches struggle to cope with large problems, and so we strengthen them by leveraging the greedy algorithm. We use the greedy solution to warm start the CP model and to devise a domain-dependent heuristic for planning. Our extensive experimental evaluation studies the scalability of the different techniques and identifies the conditions under which one approach becomes preferable to the others.

PDF Details DOI

ICAPS Conference 2019 Conference Paper

Relaxed BDDs: An Admissible Heuristic for Delete-Free Planning Based on a Discrete Relaxation

Margarita P. Castro
Chiara Piacentini
André A. Ciré
J. Christopher Beck

We investigate the use of relaxed binary decision diagrams (BDDs) as an alternative to linear programming (LP) for computing an admissible heuristic for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the introduction of a novel BDD encoding, a construction algorithm for the sequential relaxation of a DFP task and a study of the effectiveness of relaxed BDD heuristics, both from a theoretical and practical perspective. We further show that relaxed BDDs can be used beyond heuristic computation to extract delete-free plans, find action landmarks, and identify redundant actions. Our empirical analysis shows that while BDD-based heuristics trail the state of the art, even small relaxed BDDs are competitive with the LP heuristic for the DFP task.

Details

ICAPS Conference 2018 Conference Paper

Compiling Optimal Numeric Planning to Mixed Integer Linear Programming

Chiara Piacentini
Margarita P. Castro
André A. Ciré
J. Christopher Beck

Compilation techniques in planning reformulate a problem into an alternative encoding for which efficient, off-the-shelf solvers are available. In this work, we present a novel mixed-integer linear programming (MILP) compilation for cost-optimal numeric planning with instantaneous actions. While recent works on the problem are restricted to actions that modify variables present in simple numeric conditions, our MILP formulation, in addition, handles linear conditions and linear action effects on numeric state variables. Such problems are particularly challenging due to the state-dependency of the action effects. Experiments show that our approach, in addition to being the state of the art for the more general problem class, is competitive with heuristic search-based planners on domains with only simple numeric conditions.

Details

AAAI Conference 2018 Conference Paper

Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning

Chiara Piacentini
Margarita Castro
Andre Cire
J. Christopher Beck

Linear programming has been successfully used to compute admissible heuristics for cost-optimal classical planning. Although one of the strengths of linear programming is the ability to express and reason about numeric variables and constraints, their use in numeric planning is limited. In this work, we extend linear programming-based heuristics for classical planning to support numeric state variables. In particular, we propose a model for the interval relaxation, coupled with landmarks and state equation constraints. We consider both linear programming models and their harder-tosolve, yet more informative, integer programming versions. Our experimental analysis shows that considering an NP- Hard heuristic often pays off and that A∗ search using our integer programming heuristics establishes a new state of the art in cost-optimal numeric planning.

PDF Details

ICAPS Conference 2017 Conference Paper

Boosting Search Guidance in Problems with Semantic Attachments

Sara Bernardini
Maria Fox 0001
Derek Long
Chiara Piacentini

Most applications of planning to real problems involve complex and often non-linear equations, including matrix operations. PDDL is ill-suited to express such calculations since it only allows basic operations between numeric fluents. To remedy this restriction, a generic PDDL planner can be connected to a specialised advisor, which equips the planner with the ability to carry out sophisticated mathematical operations. Unlike related techniques based on semantic attachment, our planner is able to exploit an approximation of the numeric information calculated by the advisor to compute informative heuristic estimators. Guided by both causal and numeric information, our planning framework outperforms traditional approaches, especially against problems with numeric goals. We provide evidence of the power of our solution by successfully solving four completely different problems.

Details

AAAI Conference 2017 Conference Paper

Deterministic versus Probabilistic Methods for Searching for an Evasive Target

Sara Bernardini
Maria Fox
Derek Long
Chiara Piacentini

Several advanced applications of autonomous aerial vehicles in civilian and military contexts involve a searching agent with imperfect sensors that seeks to locate a mobile target in a given region. Effectively managing uncertainty is key to solving the related search problem, which is why all methods devised so far hinge on a probabilistic formulation of the problem and solve it through branch-and-bound algorithms, Bayesian ﬁltering or POMDP solvers. In this paper, we consider a class of hard search tasks involving a target that exhibits an intentional evasive behaviour and moves over a large geographical area, i. e. , a target that is particularly difﬁcult to track down and uncertain to locate. We show that, even for such a complex problem, it is advantageous to compile its probabilistic structure into a deterministic model and use standard deterministic solvers to ﬁnd solutions. In particular, we formulate the search problem for our uncooperative target both as a deterministic automated planning task and as a constraint programming task and show that in both cases our solution outperforms POMDPs methods.

PDF Details

ICAPS Conference 2016 Conference Paper

Leveraging Probabilistic Reasoning in Deterministic Planning for Large-Scale Autonomous Search-and-Tracking

Sara Bernardini
Maria Fox 0001
Derek Long
Chiara Piacentini

Search-And-Tracking (SaT) is the problem of searching for a mobile target and tracking it once it is found. Since SaT platforms face many sources of uncertainty and operational constraints, progress in the field has been restricted to simple and unrealistic scenarios. In this paper, we propose a new hybrid approach to SaT that allows us to successfully address large-scale and complex SaT missions. The probabilistic structure of SaT is compiled into a deterministic planning model and Bayesian inference is directly incorporated in the planning mechanism. Thanks to this tight integration between automated planning and probabilistic reasoning, we are able to exploit the power of both approaches. Planning provides the tools to efficiently explore big search spaces, while Bayesian inference, by readily combining prior knowledge with observable data, allows the planner to make more informed and effective decisions. We offer experimental evidence of the potential of our approach.

Details

ICAPS Conference 2016 Conference Paper

Solving Realistic Unit Commitment Problems Using Temporal Planning: Challenges and Solutions

Chiara Piacentini
Daniele Magazzeni
Derek Long
Maria Fox 0001
Chris J. Dent

When facing real world planning problems, standard planners are often inadequate and enhancement of the current techniques are required. In this paper we present the challenges that we have faced in solving the Unit Commitment (UC) problem, a well-known problem in the electrical power industry for which current best methods are based on Mixed Integer Programming (MIP). Typical UC instances involve hundreds or even thousands of generating units, pushing the scalability of state of the art planners beyond their limits. Furthermore, UC is characterised by state-dependent action costs, a feature that not many domain independent planners can efficiently handle. In this paper we focus on the challenge of making domain-independent planning competitive with the MIP method on realistic-sized UC instances. We present the results of our investigation into modelling the UC problem as a temporal planning problem, and show how we scaled up from handling fewer than 10 generating units to more than 400, obtaining solutions almost as high quality as those generated by MIP. We conclude by discussing future directions for temporal planning in this domain, that lie beyond what can be modelled and solved using MIP methods.

Details

AIJ Journal 2015 Journal Article

An extension of metric temporal planning with application to AC voltage control

Chiara Piacentini
Varvara Alimisis
Maria Fox
Derek Long

In this paper we explore the deployment of planning techniques to solve a new class of metric temporal planning problems, characterised by the need to manage both plan trajectory constraints and uncontrollable numeric events. This combination gives rise to challenges not previously solved in state-of-the-art planners. We introduce new planning methods to handle these challenges, and demonstrate our approach using a real application domain: voltage control in Alternating Current (AC) electrical networks. Embedding electricity networks in a domain description presents important modelling challenges. We introduce an encapsulated type, Network, the implementation of which is hidden from the planner. The effects of actions trigger complex updates to the state of the network. We distinguish between the direct effects of planned actions, and the indirect effects triggered by them, and we propose a method for integrating a specialised external AC power equation solver with a planner. We consider a new heuristic function that takes into account the next uncontrollable event, and its interaction with active trajectory constraints, when determining the actions that are helpful in a state. This lookahead heuristic also exploits an abstraction of the encapsulated Network type to obtain more informative distance estimates. We conduct experiments to evaluate the benefits of the lookahead heuristic, showing that our approach scales very well with the size of the network and the number of controllable components of the network.

Details DOI

AAAI Conference 2015 Conference Paper

Planning with Numeric Timed Initial Fluents

Chiara Piacentini
Maria Fox
Derek Long

Numeric Timed Initial Fluents represent a new feature in PDDL that extends the concept of Timed Initial Literals to numeric fluents. They are particularly useful to model independent functions that change through time and influence the actions to be applied. Although they are very useful to model real world problems, they are not systematically defined in the family of PDDL languages and they are not implemented in any generic PDDL planner, except for POPF2 and UPMurphi. In this paper we present an extension of the planner POPF2 (POPF-TIF) to handle problems with numeric Timed Initial Fluents. We propose and evaluate two contributions: the first is based on improvements of the heuristic evaluation, while the second considers alternative search algorithms based on a mixture of Enforced Hill Climbing and Best First Search.

PDF Details

ICAPS Conference 2013 Conference Paper

Combining a Temporal Planner with an External Solver for the Power Balancing Problem in an Electricity Network

Chiara Piacentini
Varvara Alimisis
Maria Fox 0001
Derek Long

The electricity network balancing problem consists of ensuring that the electricity demands of the consumers are met by the committed supply. Constraints are imposed on the different elements of the network, so that damage to the equipment is prevented when transformers are stepped up or down, or generation is increased. We consider this problem within zones, which are sub-networks constructed using carefully chosen decomposition principles. The automation of decision making in electricity networks is a step forward in their management which is necessary for coping with the increase in power system complexity that we expect in the near term. In this paper we explore the deployment of planning techniques to solve the zone-balancing problem. Embedding electricity networks in a domain description presents new challenges for planning. The key point is that the propagation of information requires complex updates to the state when an action is applied. We have developed a method in which the computation of the critical numeric quantities is performed calling an external power flow equation solver, demonstrating a clean interface between the planner and this domain-specific computation. This solver allows us to move the power flow computations outside of the planning process and update the values efficiently. We also examine a second important feature of this problem, which is the interaction between exogenous events and constraints over the entire plan trajectory within a zone.

Details