Abstract
The use of AI planning beyond demonstration examples has proven to be challenging for expressive problems with numerous components. This happens primarily because the state space of a problem is prone to exponential expansion the more features are added. In such problems, current techniques either find poor-quality solutions or none at all.Our approach, named RALSTP, identifies the agents in a problem and uses them for decompositions and relaxations that can exponentially increase the scale of solvable problems. Perhaps surprisingly, our method also increases the quality of the solutions. Our technique is domain-independent, fully automatic and PDDL compatible.
Our thesis introduces new AI Planning technical concepts along with automated extraction procedures that output data used as ’advice’ for the recursive decomposition and abstraction of a planning problem. These concepts consist of formal definitions for the agents, the agent dependency relationships and classification as well as for the necessary and unnecessary static environments. A new type of ’relaxed’ landmark based on the agents it may contain is introduced and used to create a novel goal clustering method based on the common landmarks found between the individual backchaining of each top-level goal. We also present a new framework for evaluating the difficulty of a planning problem according to the quantity and entanglement among the agents and the expressed dynamic and static environments.
RALSTP is evaluated on International Planning Competition (IPC) benchmark prob-lems against a broad range of state-of-the-art planners. The evaluation shows huge benefits in scale and solution quality over the other planners, particularly in the larger, more difficult, problems.
| Date of Award | 1 Dec 2023 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Derek Long (Supervisor) |