Minimally Constrained Testing for Autonomy with Temporal Logic Specifications

From Murray Wiki
Jump to navigationJump to search
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
Tag BGM22-rss_workshop
ID 2022m
Funding AFOSR T&E