Planning Under Uncertainty with Techniques from Operations Research

Abstract

Planning under uncertainty is the task of making decisions to achieve a goal, subject to some element of uncertainty. In particular, this thesis considers Stochastic Shortest Path problems (SSPs), where an agent must move between states using actions with a predefined probability distribution of next states. SSPs are a well-established problem that can be used to model real-world problems, e.g., penetration testing in cybersecurity, ecological management, and power management.

The planning community specialises in this type of problem, and has produced the state-of-the-art algorithms for solving them. Orthogonally, Operations Research (OR) is a broader, more established discipline whose scope also includes planning under uncertainty. Thus, there is an intersection of these fields at planning under uncertainty, and at this intersection there are deep links between the formulations, techniques, and fundamental algorithms of planning and OR. This connection bridges the two disciplines, allowing the two communities to share results and insights.

This thesis focuses on SSPs and some of its generalisations under the lens of OR, with the aim of strengthening the connections between the two disciplines, and improving state-of-the-art planning algorithms with techniques from OR. With this approach, this thesis presents four contributions to the study of SSPs, three of which result in novel algorithms that achieve state-of-the-art performance. The first contribution strengthens the connection between guided search and constraint generation and building on this, defines CG-iLAO*, the first algorithm that is able to use heuristics to avoid actions as well as states, resulting in state-of-the-art performance. The second contribution is a new way to solve SSPs via a sequence of deterministic planning problems, which gives a better understanding of SSPs and opens the door to solving more difficult variants of SSPs. The last two contributions relate to Constrained SSPs, a generalisation of SSPs with additional constraints over secondary costs. These apply Lagrangian relaxation and constraint generation, respectively, producing state-of-the-art algorithms for their contexts. Show more