Optimizing Robotic Team Performance with Probabilistic Model Checking

October 2014

Optimizing Robotic Team Performance with Probabilistic Model Checking

Authors:

Sagar Chaki, Joseph Andrew Giampapa, David Kyle, and John P. Lehoczky

Abstract:

We present an approach to analytically construct a robotic team, i.e., team members and deployment order, that achieves a specific task with quantified probability of success. We assume that each robot is Markovian, and that robots interact with each other via communication only. Our approach is based on probabilistic model checking (PMC). We first construct a set of Discrete Time Markov Chains (DTMCs) that each capture a specific “projection” of the behavior of an individual robot. Next, given a specific team, we construct the DTMC for its behavior by combining the projection DTMCs appropriately. Finally, we use PMC to evaluate the performance of the team. This procedure is repeated for multiple teams, the best one is selected. In practice, the projection DTMCs are constructed by observing the behavior of individual robots a finite number of times, which introduces an error in our results. We present an approach - based on sampling using the Dirichlet distribution - to quantify this error. We prove the correctness of our approach formally, and also validate it empirically on a mine detection task by a team of communicating Kilobots.

Notes:

This material is based upon work funded and supported by the Department of Defense under Contract No. FA8721-05-C-0003 with Carnegie Mellon University for the operation of the Software Engineering Institute, a federally funded research and development center. This material has been approved for public release and unlimited distribution. DM-0001326. http://dx.doi.org/10.1007/978-3-319-11900-7_12
@conference{Chaki-2014-7949,
author = {Sagar Chaki And Joseph Andrew Giampapa And David Kyle And John P. Lehoczky},
title = {Optimizing Robotic Team Performance with Probabilistic Model Checking},
booktitle = {Proceedings of 4th International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR '14)},
year = {2014},
month = {October},
editor = {Davide Brugali, Jan F. Broenink, Torsten Kroeger, Bruce A. MacDonald},
pages = {134 - 145},
publisher = {Springer International Publishing},
address = {Switzerland},
keywords = {Optimization, Autonomous Robot Team Performance, Probabilistic Model Checking, Discrete Time Markov Chain, DTMC, Behavioral Assurance},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.