Chanceconstrained probabilistic simple temporal problems

Scheduling under uncertainty is essential to many au-tonomous systems and logistics tasks. Probabilistic methods for solving temporal problems exist which quantify and attempt to minimize the probability of schedule failure. These methods are overly conserva-tive, resulting in a loss in schedule utility. Chance con-strained formalism address over-conservatism by im-posing bounds on risk, while maximizing utility subject to these risk bounds. In this paper we present the probabilistic Simple Tem-poral Network (pSTN), a probabilistic formalism for representing temporal problems with bounded risk and a utility over event timing. We introduce a constrained optimisation algorithm for pSTNs that achieves com-pactness and efficiency through a problem encoding in terms of a parameterised STNU and its reformula-tion as a parameterised STN. We demonstrate through a car sharing application that our chance-constrained ap-proach runs in the same time as the previous probabilis-tic approach, yields solutions with utility improvements of at least 5 % over previous arts, while guaranteeing op-eration within the specified risk bound