Robustness Computation of Dynamic Controllability in Probabilistic Temporal Networks with Ordinary Distributions

Robustness Computation of Dynamic Controllability in Probabilistic Temporal Networks with Ordinary Distributions

Michael Saint-Guillain, Tiago Stegun Vaquero, Jagriti Agrawal, Steve Chien

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 4168-4175. https://doi.org/10.24963/ijcai.2020/576

Most existing works in Probabilistic Simple Temporal Networks (PSTNs) base their frameworks on well-defined probability distributions. This paper addresses on PSTN Dynamic Controllability (DC) robustness measure, i.e. the execution success probability of a network under dynamic control. We consider PSTNs where the probability distributions of the contingent edges are ordinary distributed (e.g. non-parametric, non-symmetric). We introduce the concepts of dispatching protocol (DP) as well as DP-robustness, the probability of success under a predefined dynamic policy. We propose a fixed-parameter pseudo-polynomial time algorithm to compute the exact DP-robustness of any PSTN under NextFirst protocol, and apply to various PSTN datasets, including the real case of planetary exploration in the context of the Mars 2020 rover, and propose an original structural analysis.
Keywords:
Planning and Scheduling: Planning under Uncertainty
Planning and Scheduling: Robot Planning
Planning and Scheduling: Temporal and Hybrid planning