A Caltech Library Service

Synthesizing Reactive Test Environments for Autonomous Systems: Testing Reach-Avoid Specifications with Multi-Commodity Flows

Badithela, Apurva and Graebener, Josefine B. and Ubellacker, Wyatt and Mazumdar, Eric V. and Ames, Aaron D. and Murray, Richard M. (2022) Synthesizing Reactive Test Environments for Autonomous Systems: Testing Reach-Avoid Specifications with Multi-Commodity Flows. . (Unpublished)

[img] PDF - Submitted Version
Creative Commons Attribution Non-commercial Share Alike.


Use this Persistent URL to link to this item:


We study automated test generation for verifying discrete decision-making modules in autonomous systems. We utilize linear temporal logic to encode the requirements on the system under test in the system specification and the behavior that we want to observe during the test is given as the test specification which is unknown to the system. First, we use the specifications and their corresponding non-deterministic Büchi automata to generate the specification product automaton. Second, a virtual product graph representing the high-level interaction between the system and the test environment is constructed modeling the product automaton encoding the system, the test environment, and specifications. The main result of this paper is an optimization problem, framed as a multi-commodity network flow problem, that solves for constraints on the virtual product graph which can then be projected to the test environment. Therefore, the result of the optimization problem is reactive test synthesis that ensures that the system meets the test specifications along with satisfying the system specifications. This framework is illustrated in simulation on grid world examples, and demonstrated on hardware with the Unitree A1 quadruped, wherein dynamic locomotion behaviors are verified in the context of reactive test environments.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Ubellacker, Wyatt0000-0002-4732-6185
Mazumdar, Eric V.0000-0002-1815-269X
Ames, Aaron D.0000-0003-0848-3177
Murray, Richard M.0000-0002-5785-7481
Additional Information:Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0). We acknowledge funding from AFOSR Test and Evaluation Program, grant FA9550-19-1-0302, National Science Foundation award CNS-1932091, and Dow (#227027AT). The authors would like to acknowledge Mani Chandy, Tichakorn Wongpiromsarn, Qiming Zhao, Michel Ingham, Joel Burdick, Leonard Schulman, Shih-Hao Tseng, Ioannis Filippidis, and Ugo Rosolia for insightful discussions.
Group:GALCIT, Center for Autonomous Systems and Technologies (CAST)
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-19-1-0302
Dow Chemical Company227027AT
Record Number:CaltechAUTHORS:20221219-234102223
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:118468
Deposited By: George Porter
Deposited On:21 Dec 2022 18:06
Last Modified:02 Jun 2023 01:29

Repository Staff Only: item control page