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 wellknown 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 nondeterministic 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 ForwardChaining Planning with Numeric
Uncertainty.
In Proceedings of the TwentySixth International Conference on
Automated Planning and Scheduling (ICAPS 2016), volume 285, pages
16941695, 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 forwardchaining 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 deadend 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 lessinformed relaxation was used. Keywords: Technical Papers: Main Track 
[3] 
Enrico Scala, Patrik Haslum, Sylvie Thiebaux, and Miquel Ramirez.
IntervalBased Relaxation for General Numeric Planning.
In Proceedings of the 22nd European Conference on Artificial
Intelligence (ECAI), 2016.
[ .pdf ]
We generalise the intervalbased relaxation to sequential numeric planning problems with nonlinear conditions and effects, and cyclic dependencies. This effectively removes all the limitations 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 pruningsafe. We derive one such heuristic and use it to solve discretetime controllike 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.
Provablycorrect stochastic motion planning with safety constraints.
In 2013 IEEE International Conference on Robotics and
Automation, pages 981986, 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 timetocompletion 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;provablycorrect stochastic motion planning;quantitative safety measure;reward maximisation;risk levels;risk minimisation;safety constraints;safety threshold;stochastic outdoor navigation domain;stochastic path planning;timetocompletion 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 TwentySixth International Conference on
Automated Planning and Scheduling (ICAPS 2016), pages 6569, 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 nondeterministic (FOND) planning to construct a sound, offline probabilistic planner, ProbPRP, that exploits algorithmic advances from stateoftheart 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 36133621, 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 backwardsforwards 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 backwardsforwards 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 realworld 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 nonunique prior distributions in a firstorder setting.

[8] 
Manuel Biscaia and Paulo Mateus.
A Temporal Logic for Planning under Uncertainty.
In Proceedings of the TwentySixth International Florida
Artificial Intelligence Research Society Conference, pages 111, 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(14):393431, 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, JoostPieter Katoen, and Erika Abraham.
PROPhESY: A PRObabilistic ParamEter SYnthesis Tool.
In Proceedings of the 22nd International Conference on Compuer
Aided Verification (CAV), pages 214231, 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 stateoftheart 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 frontend 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 LPbased
priority policies.
Journal of the ACM, 46(6):924942, 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 online according to given probability distributions. The aim is to find a scheduling policy that minimizes the objective in expectation. Motivated by the success of LPbased 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 LPbased analysis also yields an additive performance guarantee for the WSEPT rule which implies both a worstcase 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.