Fox, Maria


Boosting Search Guidance in Problems with Semantic Attachments

AAAI Conferences

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.


Deterministic versus Probabilistic Methods for Searching for an Evasive Target

AAAI Conferences

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 filtering 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 difficult 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 find 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.


PDDL+ Planning with Temporal Pattern Databases

AAAI Conferences

The introduction of PDDL+ allowed more accurate representations of complex real-world problems of interest to the scientific community. However, PDDL+ problems are notoriously challenging to planners, requiring more advanced heuristics. We introduce the Temporal Pattern Database (TPDB), a new domain-independent heuristic technique designed for PDDL+ domains with mixed discrete/continuous behaviour, non-linear system dynamics, processes, and events. The pattern in the TPDB is obtained through an abstraction based on time and state discretisation. Our approach combines constraint relaxation and abstraction techniques, and uses solutions to the relaxed problem, as a guide to solving the concrete problem with a discretisation fine enough to satisfy the continuous model's constraints.


A Compilation of the Full PDDL+ Language into SMT

AAAI Conferences

Planning in hybrid systems is important for dealing with real-world applications. PDDL+ supports this representation of domains with mixed discrete and continuous dynamics, and supports events and processes modelling exogenous change. Motivated by numerous SAT-based planning approaches, we propose an approach to PDDL+ planning through SMT, describing an SMT encoding that captures all the features of the PDDL+ problem as published by Fox and Long. The encoding can be applied on domains with nonlinear continuous change. We apply this encoding in a simple planning algorithm, demonstrating excellent results on a set of benchmark problems.


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

AAAI Conferences

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.


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

AAAI Conferences

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.


Heuristic Planning for Hybrid Systems

AAAI Conferences

Planning in hybrid systems has been gaining research interest in the Artificial Intelligence community in recent years. Hybrid systems allow for a more accurate representation of real world problems, though solving them is very challenging due to complex system dynamics and a large model feature set. We developed DiNo, a new planner designed to tackle problems set in hybrid domains.DiNo is based on the discretise and validate approach and uses the novel Staged Relaxed Planning Graph+ (SRPG+) heuristic.


Heuristic Planning for PDDL+ Domains

AAAI Conferences

Planning with hybrid domains modelled in PDDL+ has been gaining research interest in the Automated Planning community in recent years. Hybrid domain models capture a more accurate representation of real world problems that involve continuous processes than is possible using discrete systems. However, solving problems represented as PDDL+ domains is very challenging due to the construction of complex system dynamics, including non-linear processes and events. In this paper we introduce DiNo, a new planner capable of tackling complex problems with non-linear system dynamics governing the continuous evolution of states. DiNo is based on the discretise-and-validate approach and uses the novel Staged Relaxed Planning Graph+ (SRPG+) heuristic, which is introduced in this paper. Although several planners have been developed to work with subsets of PDDL+ features, or restricted forms of processes, DiNo is currently the only heuristic planner capable of handling non-linear system dynamics combined with the full PDDL+ feature set.


A Compilation of the Full PDDL+ Language into SMT

AAAI Conferences

Planning in hybrid systems is important for dealing with real world applications. PDDL+ supports this representation of domains with mixed discrete and continuous dynamics, and supports events and processes modeling exogenous change. Motivated by numerous SAT-based planning approaches, we propose an approach to PDDL+ planning through SMT, describing an SMT encoding that captures all the features of the PDDL+ problem as published by Fox and Long (2006). The encoding can be applied on domains with nonlinear continuous change. We apply this encoding in a simple planning algorithm, demonstrating excellent results on a set of benchmark problems.


Planning with Numeric Timed Initial Fluents

AAAI Conferences

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.