Probabilistic verification of coordinated multi-robot missions

Abstract. Robots are increasingly used to perform a wide variety of tasks, especially those involving dangerous or inaccessible locations. As the complexity of such tasks grow, robots are being deployed in teams, with complex coordination schemes aimed at maximizing the chance of mission success. Such teams operate under inherently uncertain condi-tions – the robots themselves fail, and have to continuously adapt to changing environmental conditions. A key challenge facing robotic mis-sion designers is therefore to construct a mission – i.e., specify number and type of robots, number and size of teams, coordination and plan-ning mechanisms etc. – so as to maximize some overall utility, such as the probability of mission success. In this paper, we advocate, formal-ize, and empirically justify an approach to compute quantitative utility of robotic missions using probabilistic model checking. We show how to express a robotic demining mission as a restricted type of discrete time Markov chain (called αPA), and its utility as either a linear temporal logic formula or a reward. We prove a set of compositionality theorems that enable us to compute the utility of a system composed of several αPAs by combining the utilities of each αPA in isolation. This ame-liorates the statespace explosion problem, even when the system being verified is composed of a large number of robots. We validate our ap-proach empirically, using the probabilistic model checker prism.