Minimally Constrained Testing for Autonomy with Temporal Logic Specifications

Title	Minimally Constrained Testing for Autonomy with Temporal Logic Specifications
Authors	Apurva Badithela, Josefine Graebener and 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.
Type	Conference paper
URL	http://www.cds.caltech.edu/~murray/preprints/bgm22-rss.pdf
DOI
Tag	BGM22-rss_workshop
ID	2022m
Funding	AFOSR T&E
Flags