Abstract
The vast majority of real-world domains feature both discrete and continuous be-haviour to some extent. Translating them into Automated Planning problems is diÿcult, and requires a very expressive modelling language. Furthermore, solving problems in these hybrid domains is challenging for planners due to non-linear sys-tem dynamics, vast search spaces, and a wide range of domain features. Despite these obstacles, planning in hybrid domains has been a growing area in Artificial Intelligence. Eÿcient heuristics are key to solving problems in hybrid domains. This dissertation describes research into domain-independent heuristics designed specifically for mixed discrete-continuous planning problems defined in the PDDL+ modelling language with a particular focus on aerospace applications.To tackle hybrid planning problems, we exploit the planning-via-discretisation approach where the continuous dynamics of a model is approximated with uniform time steps and step-functions. Building on previous research in Automated Plan-ning and model checking, we define a set of domain-independent heuristics designed to reason with all aspects of the PDDL+ feature set as well as non-linear system dynamics. First, we present a relaxation-based heuristic, Staged Relaxed Planning Graph+ (SRPG+) inspired by the Relaxed Planning Graph (RPG) approach used in temporal and numerical planning. We also extend the SRPG+ to validation-free discretisation-based planning. Second, we describe the Policy Abstraction Database (PADB), an extension to the Pattern Database (PDB) heuristic for PDDL+ do-mains. It relies on solving an abstracted and relaxed version of the problem and uses the relaxed solution as a guide to solving the original problem. Next, we define the Polyhedra-based PDB (PolyPDB), an abstraction-based heuristic adapted from state-of-the-art model checking techniques and Pattern Databases. Finally, given that while the field of planning in hybrid domains is growing, the range of avail-able benchmark domains is significantly underdeveloped, we discuss the modelling of novel hybrid domains in PDDL+ and innovative uses for the PDDL+ language.
The novel heuristics have been implemented in DiNo, a new heuristic PDDL+ planner. It is based on UPMurphi, a planner set in the planning-as-model-checking paradigm. Results show that our heuristics significantly improve the rate of explo-ration of the search space and facilitate eÿciently finding the goal on a range of novel and existing benchmark PDDL+ domains.
Date of Award | 2018 |
---|---|
Original language | English |
Awarding Institution |
|
Supervisor | Daniele Magazzeni (Supervisor) & Maria Fox (Supervisor) |