View source for Minimally Constrained Testing for Autonomy with Temporal Logic Specifications

{{Paper
|Title=Minimally Constrained Testing for Autonomy with Temporal Logic Specifications
|Authors=Apurva Badithela, Josefine Graebener, Richard M. Murray
|Source=RSS 2022 Workshop on Envisioning an Infrastructure for Multi-Robot and Collaborative Autonomy Testing and Evaluation
|Abstract=In this paper, we study automated test generation for discrete decision-making modules in autonomous systems. First, we consider a subset of Linear Temporal Logic to represent formal requirements on the system and the test environment. The system specification captures requirements for the system under test while the test specification captures basic attributes of the test environment known to the system, and additional structure provided by a test engineer, which is unknown to the system. Second, a game graph representing the high-level interaction between the system and the test environment is constructed from transition systems modeling the system and the test environment. We provide an algorithm that finds the projection of the acceptance conditions of the system and test specifications on the game graph. Finally, to ensure that the system meets the test specification in addition to satisfying the system specification, we present a framework to construct a minimally constrained test. Specifically, we formulate this as a multi-commodity network flows problem, and present two optimizations to solve for the minimally constrained test. We conclude with future directions on applying these algorithms to constrain test environments in self-driving applications.
|URL=http://www.cds.caltech.edu/~murray/preprints/bgm22-rss.pdf
|Type=Conference paper
|ID=2022m
|Tag=BGM22-rss_workshop
|Funding=AFOSR T&E
}}