Exploiting inference in temporal planning problems with concurrency

Abstract

Temporal planning has become an increasingly popular area of research in recent years. Much of this is because the modelling of many real world problems requires the consideration of time and how actions interact and depend on one another. A key phenomenon that modelling with time allows us to accommodate when planning is the notion of concurrency, where actions occur simultaneously. Required Concurrency is where certain actions must occur in parallel due to one or more dependencies between actions. Dealing with concurrency in temporal planning requires careful reasoning when making choices about which actions to use during search. Inference can be used to assist in problem solving when there is required concurrency because certain actions must occur at the same time. The research presented in this thesis explores how problems of required concurrency can be solved using more inference and less search. Specifically, the work focuses on pair-wise cases of required concurrency. Novel techniques are presented for detecting required concurrency. In addition, new infer and search algorithms capable of exploiting inference from these detections and reducing search are developed. The algorithms for pattern detection, the combined infer and search strategies, along with the inference engine that powers them are implemented as an extension of POPF. We present an evaluation of the practical benefit from this new planner that we call POPI. Additionally, we present a formal analysis provably showing which unique types of required concurrency exist between pairs of durative actions.

Date of Award	1 Dec 2019
Original language	English
Awarding Institution	King's College London
Supervisor	Derek Long (Supervisor) & Maria Fox (Supervisor)