Seminar "Reasoning, Planning, and Scheduling with Uncertainty"

Submitted by Till Hofmann on 13. January 2018 - 13:46

In this seminar, we will study uncertainty in the context of reasoning, planning, and scheduling. For reasoning about actions, we will look into stochastic extensions of the Situation Calculus, a well-known formalism for reasoning about dynamic domains. In the classical Situation Calculus, all actions are deterministic. In this seminar, we will learn about extensions that allow non-deterministic and probabilistic actions. For planning, we will investigate probabilistic extensions to classical planning frameworks such as the Planning Domain Definition Language (PDDL) and compare them to Markov Decision Processes (MDPs). For scheduling, we will learn about mechanisms for solving scheduling problems with probabilistic task durations.

Participation

Students of Bachelor and Master programs can participate in this seminar. For Master Informatik students, the seminar belongs to the fields Data and Information Management. Certain topics may also be suitable for the field Theoretical Computer Science, please contact us beforehand. For Master Software Systems Engineering (SSE) students, it belongs to the fields Theoretical Foundations of SSE and Data and Information Management.

Places are allocated centrally from 19.01.2018 until 02.02.2018. In your application please clearly indicate your prior knowledge of the subject (see the requirements section). We won't be able to consider your application otherwise. The number of available slots is limited.

Requirements

Knowledge of the fundamental concepts of Artificial Intelligence is strongly recommended, an understanding of knowledge representation and logic will be helpful. Relevant courses include Introduction into Artificial Intelligence, Knowledge Representation, and Mathematical Logic.

Topics

[1] Hakan Younes and Michael Littman. PPDDL1.0: An extension to PDDL for expressing planning domains with probabilistic effects. Technical report, Carnegie Mellon University, Pittsburgh, PA, USA, 2004. [ .pdf ]
We desribe a variation of the planning domain definition language, PDDL, that permits the modeling of probabilistic planning problems with rewards. This language, PPDDL1.0, was used as the input language for the probabilistic track of the 4th International Planning Competition. We provide the complete syntax for PPDDL1.0 and give a semantics of PPDDL1.0 planning problems in terms of Markov decision processes.

Keywords: markov decision processes,pddl,probabilistic planning
[2] Liana Marinescu and Andrew Coles. Heuristic Guidance for Forward-Chaining Planning with Numeric Uncertainty. In Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS 2016), volume 285, pages 1694-1695, 2016. [ DOI | http ]
Uncertainty hinders many interesting applications of planning – it may come in the form of sensor noise, unpredictable environments, or known limitations in problem models. In this paper we explore heuristic guidance for forward-chaining planning with continuous random variables, while ensuring a probability of plan success. We extend the Metric Relaxed Planning Graph heuristic to capture a model of uncertainty, providing better guidance in terms of heuristic estimates and dead-end detection. By tracking the accumulated error on nu- meric values, our heuristic is able to check if preconditions in the planning graph are achievable with a sufficient degree of confidence; it is also able to consider acting to reduce the accumulated error. Results indicate that our approach offers improvements in performance compared to prior work where a less-informed relaxation was used.

Keywords: Technical Papers: Main Track
[3] Enrico Scala, Patrik Haslum, Sylvie Thiebaux, and Miquel Ramirez. Interval-Based Relaxation for General Numeric Planning. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI), 2016. [ .pdf ]
We generalise the interval-based relaxation to sequential numeric planning problems with non-linear conditions and effects, and cyclic dependencies. This effectively removes all the limi-tations on the problem placed in previous work on numeric planning heuristics, and even allows us to extend the planning language with a wider set of mathematical functions. Heuristics obtained from the generalised relaxation are pruning-safe. We derive one such heuristic and use it to solve discrete-time control-like planning problems with autonomous processes. Few planners can solve such problems, and search with our new heuristic compares favourably with them.

[4] C. Yoo, R. Fitch, and S. Sukkarieh. Provably-correct stochastic motion planning with safety constraints. In 2013 IEEE International Conference on Robotics and Automation, pages 981-986, May 2013. [ DOI ]
Formal methods based on the Markov decision process formalism, such as probabilistic computation tree logic (PCTL), can be used to analyse and synthesise control policies that maximise the probability of mission success. In this paper, we consider a different objective. We wish to minimise time-to-completion while satisfying a given probabilistic threshold of success. This important problem naturally arises in motion planning for outdoor robots, where high quality mobility prediction methods are available but stochastic path planning typically relies on an arbitrary weighted cost function that attempts to balance the opposing goals of finding safe paths (minimising risk) while making progress towards the goal (maximising reward). We propose novel algorithms for model checking and policy synthesis in PCTL that (1) provide a quantitative measure of safety and completion time for a given policy, and (2) synthesise policies that minimise completion time with respect to a given safety threshold. We provide simulation results in a stochastic outdoor navigation domain that illustrate policies with varying levels of risk.

Keywords: Markov processes;control system synthesis;formal verification;mobile robots;path planning;probabilistic logic;probability;trees (mathematics);Markov decision process formalism;PCTL;arbitrary weighted cost function;control policy analysis;control policy synthesis;formal methods;mission success probability maximisation;mobility prediction methods;model checking;outdoor robots;probabilistic computation tree logic;probabilistic success threshold;provably-correct stochastic motion planning;quantitative safety measure;reward maximisation;risk levels;risk minimisation;safety constraints;safety threshold;stochastic outdoor navigation domain;stochastic path planning;time-to-completion minimisation;Mobile communication;Robots
[5] Alberto Camacho, Christian Muise, and Sheila A. McIlraith. From FOND to Robust Probabilistic Planning : Computing Compact Policies that Bypass Avoidable Deadends. In Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS 2016), pages 65-69, 2016. [ http ]
We address the class of probabilistic planning problems where the objective is to maximize the probability of reaching a prescribed goal. The complexity of probabilistic planning problems makes it difficult to compute high quality solutions for large instances, and existing algorithms either do not scale, or do so at the expense of the solution quality. We leverage core similarities between probabilistic and fully observable non-deterministic (FOND) planning to construct a sound, offline probabilistic planner, ProbPRP, that exploits algorithmic advances from state-of-the-art FOND planner, PRP, to compute compact policies that are guaranteed to bypass avoidable deadends. We evaluate ProbPRP on a selection of benchmarks used in past probabilistic planning competitions. The results show that ProbPRP, in many cases, outperforms the state of the art, computing substantially more robust policies and at times doing so orders of magnitude faster.

Keywords: Technical Papers: Main Track
[6] Brent Mombourquette, Christian Muise, and Sheila A. McIlraith. Logical Filtering and Smoothing: State Estimation in Partially Observable Domains. In Proceedings of the 31st Conference on Artificial Intelligence (AAAI 2017), pages 3613-3621, 2017. [ http ]
State estimation is the task of estimating the state of a partially observable dynamical system given a sequence of executed actions and observations. In logical settings, state estimation can be realized via logical filtering, which is exact but can be intractable. We propose logical smoothing, a form of backwards reasoning that works in concert with approximated logical filtering to refine past beliefs in light of new observations. We characterize the notion of logical smoothing together with an algorithm for backwards-forwards state estimation. We also present an approximation of our smoothing algorithm that is space efficient. We prove properties of our algorithms, and experimentally demonstrate their behaviour, contrasting them with state estimation methods for planning. Smoothing and backwards-forwards reasoning are important techniques for reasoning about partially observable dynamical systems, introducing the logical analogue of effective techniques from control theory and dynamic programming.

Keywords: Planning and Scheduling
[7] Vaishak Belle. Probabilistic Planning by Probabilistic Programming. In AAAI Workshop on Planning and Inference, 2018. [ arXiv | http ]
Automated planning is a major topic of research in artificial intelligence, and enjoys a long and distinguished history. The classical paradigm assumes a distinguished initial state, comprised of a set of facts, and is defined over a set of actions which change that state in one way or another. Planning in many real-world settings, however, is much more involved: an agent's knowledge is almost never simply a set of facts that are true, and actions that the agent intends to execute never operate the way they are supposed to. Thus, probabilistic planning attempts to incorporate stochastic models directly into the planning process. In this article, we briefly report on probabilistic planning through the lens of probabilistic programming: a programming paradigm that aims to ease the specification of structured probability distributions. In particular, we provide an overview of the features of two systems, HYPE and ALLEGRO, which emphasise different strengths of probabilistic programming that are particularly useful for complex modelling issues raised in probabilistic planning. Among other things, with these systems, one can instantiate planning problems with growing and shrinking state spaces, discrete and continuous probability distributions, and non-unique prior distributions in a first-order setting.

[8] Manuel Biscaia and Paulo Mateus. A Temporal Logic for Planning under Uncertainty. In Proceedings of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference, pages 1-11, 2013. [ http ]
Dealing with uncertainty in the context of planning has been an active research subject in AI. Addressing the case when uncertainty evolves over time can be difficult. In this work, we provide a solution to this problem by proposing a temporal logic to reason about quantities and probability. For this logic, we provide a PSPACE SAT algorithm together with a complete calculus. The algorithm enables us to perform planning under uncertainty via SAT, extending a technique used for classic planning. We can show that any obtained plan will have certain properties (desired or undesired). The calculus can also be used to derive the impossibility of a plan, given a set of specification.

Keywords: Uncertain Reasoning Special Track
[9] Paulo Mateus, António Pacheco, Javier Pinto, Amílcar Sernadas, and Cristina Sernadas. Probabilistic Situation Calculus. Annals of Mathematics and Artificial Intelligence, 32(1-4):393-431, 2001. [ DOI ]
In this article we propose a Probabilistic Situation Calculus logical language to represent and reason with knowledge about dynamic worlds in which actions have uncertain effects. Uncertain effects are modeled by dividing an action into two subparts: a deterministic (agent produced) input and a probabilistic reaction (produced by nature). We assume that the probabilities of the reactions have known distributions. Our logical language is an extension to Situation Calculae in the style proposed by Raymond Reiter. There are three aspects to this work. First, we extend the language in order to accommodate the necessary distinctions (e.g., the separation of actions into inputs and reactions). Second, we develop the notion of Randomly Reactive Automata in order to specify the semantics of our Probabilistic Situation Calculus. Finally, we develop a reasoning system in MATHEMATICA capable of performing temporal projection in the Probabilistic Situation Calculus.

Keywords: Mathematica,Probabilistic automata,Probability logic,Situation Calculus,Theory of action
[10] Christian Dehnert, Sebastian Junges, Nils Jansen, Florian Corzilius, Matthias Volk, Harold Bruintjes, Joost-Pieter Katoen, and Erika Abraham. PROPhESY: A PRObabilistic ParamEter SYnthesis Tool. In Proceedings of the 22nd International Conference on Compuer Aided Verification (CAV), pages 214-231, 2010. [ http ]
We present PROPhESY, a tool for analyzing parametric Markov chains (MCs). It can compute a rational function (i.e., a fraction of two polynomials in the model parameters) for reachability and expected reward objectives. Our tool outperforms state-of-the-art tools and supports the novel feature of conditional probabilities. PROPhESY supports incremental automatic parameter synthesis (using SMT techniques) to determine “safe” and “unsafe” regions of the parameter space. All values in these regions give rise to instantiated MCs satisfying or violating the (conditional) probability or expected reward objective. PROPhESY features a web front-end supporting visualization and user- guided parameter synthesis. Experimental results show that PROPhESY scales to MCs with millions of states and several parameters.

[11] Rolf H. Möhring, Marc Uetz, and Andreas S. Schulz. Approximation in stochastic scheduling: the power of LP-based priority policies. Journal of the ACM, 46(6):924-942, 1999. [ DOI ]
We consider the problem to minimize the total weighted completion time of a set of jobs with individual release dates which have to be scheduled on identical parallel machines. Job processing times are not known in advance, they are realized on-line according to given probability distributions. The aim is to find a scheduling policy that minimizes the objective in expectation. Motivated by the success of LP-based approaches to deterministic scheduling, we present a polyhedral relaxation of the performance space of stochastic parallel machine scheduling. This relaxation extends earlier relaxations that have been used, among others, by Hall et al. [1997] in the deterministic setting. We then derive constant performance guarantees for priority policies which are guided by optimum LP solutions, and thereby generalize previous results from deterministic scheduling. In the absence of release dates, the LP-based analysis also yields an additive performance guarantee for the WSEPT rule which implies both a worst-case performance ratio and a result on its asymptotic optimality, thus complementing previous work by Weiss [1990]. The corresponding LP lower bound generalizes a previous lower bound from deterministic scheduling due to Eastman et al. [1964], and exhibits a relation between parallel machine problems and corresponding problems with only one fast single machine. Finally, we show that all employed LPs can be solved in polynomial time by purely combinatorial algorithms.

Additional information

Introductory Meeting
The introductory meeting will take place in the beginning of the semester, the exact date will be announced. Participation is compulsory.
Seminar Procedure
Besides writing your own term paper, you are asked to review other students' term papers. We will use a conference management system (e.g., EasyChair) for this procedure. It will involve strict deadlines. Meeting these deadlines is mandatory. At the end of the seminar each student needs to give a talk on his topic in front of the other students and members of our group. Attendance of these talks and participation in the discussions is mandatory.
Seminar Date
The seminar will be held as a block seminar on two or three days, likely during the semester break.
Typesetting
You may use this LaTeX template for your term paper.
General Info
Please read and understand our general information and suggestions on seminars!
Library Tour
The Computer Science Library offers guided tours on how to find literature in the library and how to prepare a seminar. Interested students should enlist for a tour in the preliminary discussion.