Source author record

Richard M. Murray

Richard M. Murray appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

17works
18topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2022arXiv

OUTformation: Distributed Data-Gathering with Feedback under Unknown Environment and Communication Delay Constraints

Towards the informed design of large-scale distributed data-gathering architectures under real-world assumptions such as nonzero communication delays and unknown environment dynamics, this paper considers the effects of allowing feedback communication from the central processor to external sensors. Using simple but representative state-estimation examples, we investigate fundamental tradeoffs between the mean-squared error (MSE) of the central processor's estimate of the environment state, and the total power expenditure per sensor under more conventional architectures without feedback (INformation) versus those with broadcast feedback (OUTformation). The primary advantage of enabling feedback is that each sensor's understanding of the central processor's estimate improves, which enables each sensor to determine when and what parts of its current observations to transmit. We use theory to demonstrate conditions in which OUTformation maintains the same MSE as INformation with less power expended on average, and conditions in which OUTformation obtains less MSE than INformation at additional power cost. These performance tradeoffs are also considered under settings where environments undergo less variation, and sensors implement random backoff times to prevent transmission collisions. Our results are supported via numerical studies, which show that the properties derived in theory still hold even when some of the simplifying assumptions are removed.

preprint2022arXiv

Robust Safe Control Synthesis with Disturbance Observer-Based Control Barrier Functions

In a complex real-time operating environment, external disturbances and uncertainties adversely affect the safety, stability, and performance of dynamical systems. This paper presents a robust stabilizing safety-critical controller synthesis framework with control Lyapunov functions (CLFs) and control barrier functions (CBFs) in the presence of disturbance. A high-gain input observer method is adapted to estimate the time-varying unmodelled dynamics of the CBF with an error bound using the first-order time derivative of the CBF. This approach leads to an easily tunable low order disturbance estimator structure with a design parameter as it utilizes only the CBF constraint. The estimated unknown input and associated error bound are used to ensure robust safety and exponential stability by formulating a CLF-CBF quadratic program. The proposed method is applicable to both relative degree one and higher relative degree CBF constraints. The efficacy of the proposed approach is demonstrated using a numerical simulations of an adaptive cruise control system and a Segway platform with an external disturbance.

preprint2022arXiv

Towards Better Test Coverage: Merging Unit Tests for Autonomous Systems

We present a framework for merging unit tests for autonomous systems. Typically, it is intractable to test an autonomous system for every scenario in its operating environment. The question of whether it is possible to design a single test for multiple requirements of the system motivates this work. First, we formally define three attributes of a test: a test specification that characterizes behaviors observed in a test execution, a test environment, and a test policy. Using the merge operator from contract-based design theory, we provide a formalism to construct a merged test specification from two unit test specifications. Temporal constraints on the merged test specification guarantee that non-trivial satisfaction of both unit test specifications is necessary for a successful merged test execution. We assume that the test environment remains the same across the unit tests and the merged test. Given a test specification and a test environment, we synthesize a test policy filter using a receding horizon approach, and use the test policy filter to guide a search procedure (e.g. Monte-Carlo Tree Search) to find a test policy that is guaranteed to satisfy the test specification. This search procedure finds a test policy that maximizes a pre-defined robustness metric for the test while the filter guarantees a test policy for satisfying the test specification. We prove that our algorithm is sound. Furthermore, the receding horizon approach to synthesizing the filter ensures that our algorithm is scalable. Finally, we show that merging unit tests is impactful for designing efficient test campaigns to achieve similar levels of coverage in fewer test executions. We illustrate our framework on two self-driving examples in a discrete-state setting.

preprint2021arXiv

Time-Optimal Navigation in Uncertain Environments with High-Level Specifications

Mixed observable Markov decision processes (MOMDPs) are a modeling framework for autonomous systems described by both fully and partially observable states. In this work, we study the problem of synthesizing a control policy for MOMDPs that minimizes the expected time to complete the control task while satisfying syntactically co-safe Linear Temporal Logic (scLTL) specifications. First, we present an exact dynamic programming update to compute the value function. Afterwards, we propose a point-based approximation, which allows us to compute a lower bound of the closed-loop probability of satisfying the specifications. The effectiveness of the proposed approach and comparisons with standard strategies are shown on high-fidelity navigation tasks with partially observable static obstacles.

preprint2020arXiv

Counter-example Guided Learning of Bounds on Environment Behavior

There is a growing interest in building autonomous systems that interact with complex environments. The difficulty associated with obtaining an accurate model for such environments poses a challenge to the task of assessing and guaranteeing the system's performance. We present a data-driven solution that allows for a system to be evaluated for specification conformance without an accurate model of the environment. Our approach involves learning a conservative reactive bound of the environment's behavior using data and specification of the system's desired behavior. First, the approach begins by learning a conservative reactive bound on the environment's actions that captures its possible behaviors with high probability. This bound is then used to assist verification, and if the verification fails under this bound, the algorithm returns counter-examples to show how failure occurs and then uses these to refine the bound. We demonstrate the applicability of the approach through two case-studies: i) verifying controllers for a toy multi-robot system, and ii) verifying an instance of human-robot interaction during a lane-change maneuver given real-world human driving data.

preprint2020arXiv

Formal Test Synthesis for Safety-Critical Autonomous Systems based on Control Barrier Functions

The prolific rise in autonomous systems has led to questions regarding their safe instantiation in real-world scenarios. Failures in safety-critical contexts such as human-robot interactions or even autonomous driving can ultimately lead to loss of life. In this context, this paper aims to provide a method by which one can algorithmically test and evaluate an autonomous system. Given a black-box autonomous system with some operational specifications, we construct a minimax problem based on control barrier functions to generate a family of test parameters designed to optimally evaluate whether the system can satisfy the specifications. To illustrate our results, we utilize the Robotarium as a case study for an autonomous system that claims to satisfy waypoint navigation and obstacle avoidance simultaneously. We demonstrate that the proposed test synthesis framework systematically finds those sequences of events (tests) that identify points of system failure.

preprint2020arXiv

Learning Pose Estimation for UAV Autonomous Navigation andLanding Using Visual-Inertial Sensor Data

In this work, we propose a new learning approach for autonomous navigation and landing of an Unmanned-Aerial-Vehicle (UAV). We develop a multimodal fusion of deep neural architectures for visual-inertial odometry. We train the model in an end-to-end fashion to estimate the current vehicle pose from streams of visual and inertial measurements. We first evaluate the accuracy of our estimation by comparing the prediction of the model to traditional algorithms on the publicly available EuRoC MAV dataset. The results illustrate a $25 \%$ improvement in estimation accuracy over the baseline. Finally, we integrate the architecture in the closed-loop flight control system of Airsim - a plugin simulator for Unreal Engine - and we provide simulation results for autonomous navigation and landing.

preprint2016arXiv

A multi-paradigm language for reactive synthesis

This paper proposes a language for describing reactive synthesis problems that integrates imperative and declarative elements. The semantics is defined in terms of two-player turn-based infinite games with full information. Currently, synthesis tools accept linear temporal logic (LTL) as input, but this description is less structured and does not facilitate the expression of sequential constraints. This motivates the use of a structured programming language to specify synthesis problems. Transition systems and guarded commands serve as imperative constructs, expressed in a syntax based on that of the modeling language Promela. The syntax allows defining which player controls data and control flow, and separating a program into assumptions and guarantees. These notions are necessary for input to game solvers. The integration of imperative and declarative paradigms allows using the paradigm that is most appropriate for expressing each requirement. The declarative part is expressed in the LTL fragment of generalized reactivity(1), which admits efficient synthesis algorithms, extended with past LTL. The implementation translates Promela to input for the Slugs synthesizer and is written in Python. The AMBA AHB bus case study is revisited and synthesized efficiently, identifying the need to reorder binary decision diagrams during strategy construction, in order to prevent the exponential blowup observed in previous work.

preprint2015arXiv

An Iterative Abstraction Algorithm for Reactive Correct-by-Construction Controller Synthesis

In this paper, we consider the problem of synthesizing correct-by-construction controllers for discrete-time dynamical systems. A commonly adopted approach in the literature is to abstract the dynamical system into a Finite Transition System (FTS) and thus convert the problem into a two player game between the environment and the system on the FTS. The controller design problem can then be solved using synthesis tools for general linear temporal logic or generalized reactivity(1) specifications. In this article, we propose a new abstraction algorithm. Instead of generating a single FTS to represent the system, we generate two FTSs, which are under- and over-approximations of the original dynamical system. We further develop an iterative abstraction scheme by exploiting the concept of winning sets, i.e., the sets of states for which there exists a winning strategy for the system. Finally, the efficiency of the new abstraction algorithm is illustrated by numerical examples.

preprint2015arXiv

Convex Optimal Uncertainty Quantification

Optimal uncertainty quantification (OUQ) is a framework for numerical extreme-case analysis of stochastic systems with imperfect knowledge of the underlying probability distribution. This paper presents sufficient conditions under which an OUQ problem can be reformulated as a finite-dimensional convex optimization problem, for which efficient numerical solutions can be obtained. The sufficient conditions include that the objective function is piecewise concave and the constraints are piecewise convex. In particular, we show that piecewise concave objective functions may appear in applications where the objective is defined by the optimal value of a parameterized linear program.

preprint2015arXiv

Symbolic construction of GR(1) contracts for synchronous systems with full information

This work proposes a symbolic algorithm for the construction of assume-guarantee specifications that allow multiple agents to cooperate. Each agent is assigned goals expressed in a fragment of linear temporal logic known as generalized reactivity of rank 1 (GR(1)). These goals may be unrealizable, unless additional assumptions are made by each agent about the behavior of the other agents. The proposed algorithm constructs weakly fair assumptions for each agent, to ensure that they can cooperate successfully. A necessary requirement is that the given goals be cooperatively satisfiable. We prove that there exist games for which the GR(1) fragment with liveness properties over states is not sufficient to ensure realizability from any state in the cooperatively winning set. The obstruction is due to circular dependencies of liveness goals. To prevent circularity, we introduce nested games as a formalism to express specifications with conditional assumptions. The algorithm is symbolic, with fixpoint structure similar to the GR(1) synthesis algorithm, implying time complexity polynomial in the number of states, and linear in the number of recurrence goals.

preprint2013arXiv

Biomolecular resource utilization in elementary cell-free gene circuits

We present a detailed dynamical model of the behavior of transcription-translation circuits in vitro that makes explicit the roles played by essential molecular resources. A set of simple two-gene test circuits operating in a cell-free biochemical 'breadboard' validate this model and highlight the consequences of limited resource availability. In particular, we are able to confirm the existence of biomolecular 'crosstalk' and isolate its individual sources. The implications of crosstalk for biomolecular circuit design and function are discussed.

preprint2012arXiv

Synthesis of Reactive Protocols for Vehicle-to-Vehicle Communication

We present a synthesis method for communication protocols for active safety applications that satisfy certain formal specifications on quality of service requirements. The protocols are developed to provide reliable communication services for automobile active safety applications. The synthesis method transforms a specification into a distributed implementation of senders and receivers that together satisfy the quality of service requirements by transmitting messages over an unreliable medium. We develop a specification language and an execution model for the implementations, and demonstrate the viability of our method by developing a protocol for a traffic scenario in which a car runs a red light at a busy intersection.

preprint2011arXiv

Noise Propagation in Biological and Chemical Reaction Networks

We describe how noise propagates through a network by calculating the variance of the outputs. Using stochastic calculus and dynamical systems theory, we study the network topologies that accentuate or alleviate the effect of random variance in the network for both directed and undirected graphs. Given a linear tree network, the variance in the output is a convex function of the poles of the individual nodes. Cycles create correlations which in turn increase the variance in the output. Feedforward and feedback have a limited effect on noise propagation when the respective cycles is sufficiently long. Crosstalk between the elements of different pathways helps reduce the output noise, but makes the network slower. Next, we study the differences between disturbances in the inputs and disturbances in the network parameters, and how they propagate to the outputs. Finally, we show how noise correlations can affect the steady state of the system in chemical reaction networks with reactions of two or more reactants, each of which may be affected by independent or correlated noise sources.

preprint2010arXiv

Networks with the Smallest Average Distance and the Largest Average Clustering

We describe the structure of the graphs with the smallest average distance and the largest average clustering given their order and size. There is usually a unique graph with the largest average clustering, which at the same time has the smallest possible average distance. In contrast, there are many graphs with the same minimum average distance, ignoring their average clustering. The form of these graphs is shown with analytical arguments. Finally, we measure the sensitivity to rewiring of this architecture with respect to the clustering coefficient, and we devise a method to make these networks more robust with respect to vertex removal.

preprint2010arXiv

Quantification and Minimization of Crosstalk Sensitivity in Networks

Crosstalk is defined as the set of unwanted interactions among the different entities of a network. Crosstalk is present in various degrees in every system where information is transmitted through a means that is accessible by all the individual units of the network. Using concepts from graph theory, we introduce a quantifiable measure for sensitivity to crosstalk, and analytically derive the structure of the networks in which it is minimized. It is shown that networks with an inhomogeneous degree distribution are more robust to crosstalk than corresponding homogeneous networks. We provide a method to construct the graph with the minimum possible sensitivity to crosstalk, given its order and size. Finally, for networks with a fixed degree sequence, we present an algorithm to find the optimal interconnection structure among their vertices.