Search

The wide availability of data coupled with the computational advances in artificial intelligence and machine learning promise to enable many future technologies such as autonomous driving. While there has been a variety of successful demonstrations of these technologies, critical system failures have repeatedly been reported. Even if rare, such system failures pose a serious barrier to adoption without a rigorous risk assessment. This article presents a framework for the systematic and rigorous risk verification of systems. We consider a wide range of system specifications formulated in signal temporal logic (STL) and model the system as a stochastic process, permitting discrete-time and continuous-time stochastic processes. We then define the STL robustness risk as the risk of lacking robustness against failure. This definition is motivated as system failures are often caused by missing robustness to modeling errors, system disturbances, and distribution shifts in the underlying data generating process. Within the definition, we permit general classes of risk measures and focus on tail risk measures such as the value-at-risk and the conditional value-at-risk. While the STL robustness risk is in general hard to compute, we propose the approximate STL robustness risk as a more tractable notion that upper bounds the STL robustness risk. We show how the approximate STL robustness risk can accurately be estimated from system trajectory data. For discrete-time stochastic processes, we show under which conditions the approximate STL robustness risk can even be computed exactly. We illustrate our verification algorithm in the autonomous driving simulator CARLA and show how a least risky controller can be selected among four neural network lane-keeping controllers for five meaningful system specifications. [ABSTRACT FROM AUTHOR]

In this article, we design algorithms to protect swarm-robotics applications against sensor denial-of-service attacks on robots. We focus on applications requiring the robots to jointly select actions, e.g., which trajectory to follow, among a set of available actions. Such applications are central in large-scale robotic applications, such as multirobot motion planning for target tracking. But the current attack-robust algorithms are centralized. In this article, we propose a general-purpose distributed algorithm toward robust optimization at scale, with local communications only. We name it distributed robust maximization (DRM). DRM proposes a divide-and-conquer approach that distributively partitions the problem among cliques of robots. Then, the cliques optimize in parallel, independently of each other. We prove DRM achieves a close-to-optimal performance. We demonstrate DRM’s performance in Gazebo and MATLAB simulations, in scenarios of active target tracking with swarms of robots. In the simulations, DRM achieves computational speed-ups, being 1 to 2 orders faster than the centralized algorithms. Yet, it nearly matches the tracking performance of the centralized counterparts. Since, DRM overestimates the number of attacks in each clique, in this article, we also introduce an improved distributed robust maximization (IDRM) algorithm. IDRM infers the number of attacks in each clique less conservatively than DRM by leveraging three-hop neighboring communications. We verify IDRM improves DRM’s performance in simulations. [ABSTRACT FROM AUTHOR]

This paper develops a notion of approximation for a class of stochastic hybrid systems that includes, as special cases, both jump linear stochastic systems and linear stochastic hybrid automata. Our approximation framework is based on the recently developed notion of the so-called stochastic simulation functions. These Lyapunov-like functions can be used to rigorously quantify the distance or error between a system and its approximate abstraction. For the class of jump linear stochastic systems and linear stochastic hybrid automata, we show that the computation of stochastic simulation functions can be cast as a tractable linear matrix inequality problem. This enables us to compute the modeling error incurred by abstracting some of the continuous dynamics, or by neglecting the influence of stochastic noise, or even the influence of stochastic discrete jumps. Index Terms--Approximation, bisimulation, stochastic hybrid systems, verification.

In this article, we address a multi-robot planning problem in environments with partially unknown semantics. The environment is assumed to have a known geometric structure (e.g., walls) and to be occupied by static labeled landmarks with uncertain positions and classes. This modeling approach gives rise to an uncertain semantic map generated by semantic simultaneous localization and mapping algorithms. Our goal is to design control policies for robots equipped with noisy perception systems so that they can accomplish collaborative tasks captured by global temporal logic specifications. To specify missions that account for environmental and perceptual uncertainty, we employ a fragment of linear temporal logic (LTL), called co-safe LTL, defined over perception-based atomic predicates modeling probabilistic satisfaction requirements. The perception-based LTL planning problem gives rise to an optimal control problem, solved by a novel sampling-based algorithm, that generates open-loop control policies that are updated online to adapt to a continuously learned semantic map. We provide extensive experiments to demonstrate the efficiency of the proposed planning architecture. [ABSTRACT FROM AUTHOR]

Control of mobile networks raises fundamental and novel problems in controlling the structure of the resulting dynamic graphs. In particular, in applications involving mobile sensor networks and multiagent systems, a great new challenge is the development of distributed motion algorithms that guarantee connectivity of the overall network. Motivated by the inherently discrete nature of graphs as combinatorial objects, we address this challenge using a key control decomposition. First, connectivity control of the network structure is performed in the discrete space of graphs and relies on local estimates of the network topology used, along with algebraic graph theory, to verify link deletions with respect to connectivity. Tie breaking, when multiple such link deletions can violate connectivity, is achieved by means of gossip algorithms and distributed market-based control. Second, motion control is performed in the continuous configuration space, where nearest-neighbor potential fields are used to maintain existing links in the network. Integration of the earlier controllers results in a distributed, multiagent, hybrid system, for which we show that the resulting motion always ensures connectivity of the network, while it reconfigures toward certain secondary objectives. Our approach can also account for communication time delays as well as collision avoidance and is illustrated in nontrivial computer simulations. Index Terms--Distributed control, dynamic networks, graph connectivity, hybrid systems.

Distributed motion planning of multiple agents raises fundamental and novel problems in control theory and robotics. In particular, in applications such as coverage by mobile sensor networks or multiple target tracking, a great new challenge is the development of motion planning algorithms that dynamically assign targets or destinations to multiple homogeneous agents, not relying on any a priori assignment of agents to destinations. In this paper, we address this challenge using two novel ideas. First, distributed multidestination potential fields are developed that are able to drive every agent to any available destination. Second, nearest neighbor coordination protocols are developed ensuring that distinct agents are assigned to distinct destinations. Integration of the overall system results in a distributed, multiagent, hybrid system for which we show that the mutual exclusion property of the final assignment is guaranteed for almost all initial conditions. Furthermore, we show that our dynamic assignment algorithm will converge after exploring at most a polynomial number of assignments, dramatically reducing the combinatorial nature of purely discrete assignment problems. Our scalable approach is illustrated with nontrivial computer simulations. Index Terms--Distributed control, hybrid systems, motion planning, multiagent assignment problems.

This paper presents a methodology for safety verification of continuous and hybrid systems in the worst-case and stochastic settings. In the worst-case setting, a function of state termed barrier certificate is used to certify that all trajectories of the system starting from a given initial set do not enter an unsafe region. No explicit computation of reachable sets is required in the construction of barrier certificates, which makes it possible to handle nonlinearity, uncertainty, and constraints directly within this framework. In the stochastic setting, our method computes an upper bound on the probability that a trajectory of the system reaches the unsafe set, a bound whose validity is proven by the existence of a barrier certificate. For polynomial systems, barrier certificates can be constructed using convex optimization, and hence the method is computationally tractable. Some examples are provided to illustrate the use of the method. Index Terms--Barrier certificates, hybrid systems, nonlinear systems, safety verification, stochastic systems, sum of squares optimization.

The control of mobile networks of multiple agents raises fundamental and novel problems in controlling the structure of the resulting dynamic graphs. In this paper, we consider the problem of controlling a network of agents so that the resulting motion always preserves the connectivity property of the network. In particular, the connectivity condition is translated to differentiable constraints on individual agent motion by considering the dynamics of the Laplacian matrix and its spectral properties. Artificial potential fields are then used to drive the agents to configurations away from the undesired space of disconnected networks while avoiding collisions with each other. We conclude by illustrating a class of interesting problems that can be achieved while preserving connectivity constraints. Index Terms--Dynamic graphs, graph connectivity, Laplacian matrix, potential fields.

This note analyzes the stability properties of a group of mobile agents that align their velocity vectors, and stabilize their inter-agent distances, using decentralized, nearest-neighbor interaction rules, exchanging information over networks that change arbitrarily (no dwell time between consecutive switches). These changes introduce discontinuities in the agent control laws. To accommodate for arbitrary switching in the topology of the network of agent interactions we employ nonsmooth analysis. The main result is that regardless of switching, convergence to a common velocity vector and stabilization of inter-agent distances is still guaranteed as long as the network remains connected at all times. Index Terms--Algebraic graph theory, cooperative control, multiagent systems, nonsmooth systems.

Established system relationships for discrete systems, such as language inclusion, simulation, and bisimulation, require system observations to be identical. When interacting with the physical world, modeled by continuous or hybrid systems, exact relationships are restrictive and not robust. In this paper, we develop the first framework of system approximation that applies to both discrete and continuous systems by developing notions of approximate language inclusion, approximate simulation, and approximate bisimulation relations. We define a hierarchy of approximation pseudo-metrics between two systems that quantify the quality of the approximation, and capture the established exact relationships as zero sections. Our approximation framework is compositional for a synchronous composition operator. Algorithms are developed for computing the proposed pseudo-metrics, both exactly and approximately. The exact algorithms require the generalization of the fixed point algorithms for computing simulation and bisimulation relations, or dually, the solution of a static game whose cost is the so-called branching distance between the systems. Approximations for the pseudo-metrics can be obtained by considering Lyapunov-like functions called simulation and bisimulation functions. We illustrate our approximation framework in reducing the complexity of safety verification problems for both deterministic and nondeterministic continuous systems. Index Terms--Abstraction, approximation, bisimulation, metrics, transition systems.

The control of complex systems poses new challenges that fall beyond the traditional methods of control theory. One of these challenges is given by the need to control, coordinate and synchronize the operation of several interacting submodules within a system. The desired objectives are no longer captured by usual control specifications such as stabilization or output regulation. Instead, we consider specifications given by linear temporal logic (LTL) formulas. We show that existence of controllers for discrete-time controllable linear systems and LTL specifications can be decided and that such controllers can be effectively computed. The closed-loop system is of hybrid nature, combining the original continuous dynamics with the automatically synthesized switching logic required to enforce the specification. Index Terms--Automatic synthesis, discrete-time, linear control systems, hybrid systems, linear time logic.

In this paper, we present a computational framework for automatic generation of provably correct control laws for planar robots in polygonal environments. Using polygon triangulation and discrete abstractions, we map continuous motion planning and control problems, specified in terms of triangles, to computationally inexpensive problems on finite-state-transition systems. In this framework, discrete planning algorithms in complex environments can be seamlessly linked to automatic generation of feedback control laws for robots with underactuation constraints and control bounds. We focus on fully actuated kinematic robots with velocity bounds and (underactuated) unicycles with forward and turning speed bounds. Index Terms--Bisimulation, control, discrete abstraction, hybrid system (HS), motion planning, triangulation.

Formations of multi-agent systems, such as mobile robots, satellites and aircraft, require individual agents to satisfy their kinematic equations while constantly maintaining interagent constraints. In this paper, we develop a systematic framework for studying formation motion feasibility of multi-agent systems. In particular, we consider formations wherein all the agents cooperate to enforce the formation. We determine algebraic conditions that guarantee formation feasibility given the individual agent kinematics. Our framework also enables us to obtain lower dimensional control systems describing the group kinematics while maintaining all formation constraints. Index Terms--Formations, motion feasibility, multi-agent.

The paper investigates the stability properties of mobile agent formations which are based on leader following. We derive nonlinear gain estimates that capture how leader behavior affects the interconnection errors observed in the formation. Leader-to-formation stability (LFS) gains quantify error amplification, relate interconnection topology to stability and performance, and offer safety bounds for different formation topologies. Analysis based on the LFS gains provides insight to error propagation and suggests ways to improve the safety, robustness, and performance characteristics of a formation. Index Terms--Formation stability, graph theory, input-to-state stability, interconnected systems.

Mechanical control systems are an especially interesting and important class of nonlinear control systems. They posses a rich mathematical structure and yet, physical considerations reveal extremely important for the solution of a large class of control problems. In this note, we broaden the applicability of design methodologies developed for mechanical control systems by rendering nonlinear control systems, mechanical by a proper choice of feedback. In particular, we characterize which control systems can be transformed to Hamiltonian control systems by a feedback transformation. Index Terms--Hamiltonian systems, nonlinear systems, feedback transformation.

In this paper, we consider the problem of constructing abstractions of affine control systems that preserve reachability properties, and, in particular, local accessibility. In this framework, showing local accessibility of the higher level, abstracted model is equivalent to showing local accessibility of the, more detailed, lower level model. Given an affine control system and a smooth surjective map, we present a canonical construction for extracting an affine control system describing the trajectories of the abstracted variables. We then obtain conditions on the abstraction maps that render the original and abstracted system equivalent from a local accessibility point of view. Such consistent hierarchies of accessibility preserving abstractions of nonlinear control systems are then considered for various classes of affine control systems including linear, bilinear, drift free, and strict feedback systems. Index Terms--Abstraction, affine control systems, hierarchies, local accessibility.

Emerging applications of collaborative autonomy, such as multitarget tracking, unknown map exploration, and persistent surveillance, require robots plan paths to navigate an environment while maximizing the information collected via on-board sensors. In this article, we consider such information acquisition tasks but in adversarial environments, where attacks may temporarily disable the robots’ sensors. We propose the first receding horizon algorithm, aiming for robust and adaptive multirobot planning against any number of attacks, which we call Resilient Active Information acquisitioN (RAIN). RAIN calls, in an online fashion, a robust trajectory planning (RTP) subroutine that plans attack-robust control inputs over a look-ahead planning horizon. We quantify RTP’s performance by bounding its suboptimality. We base our theoretical analysis on notions of curvature introduced in combinatorial optimization. We evaluate RAIN in three information acquisition scenarios: multitarget tracking, occupancy grid mapping, and persistent surveillance. The scenarios are simulated in C++ and a unity-based simulator. In all simulations, RAIN runs in real time, and exhibits superior performance against a state-of-the-art baseline information acquisition algorithm, even in the presence of a high number of attacks. We also demonstrate RAIN’s robustness and effectiveness against varying models of attacks (worst case and random), as well as varying replanning rates. [ABSTRACT FROM AUTHOR]

Air Traffic Management (ATM) of the future allows for the possibility of free flight, in which aircraft choose their own optimal routes, altitudes, and velocities. The safe resolution of trajectory conflicts between aircraft is necessary to the success of such a distributed control system. In this paper, we present a method to synthesize provably safe conflict resolution maneuvers. The method models the aircraft and the maneuver as a hybrid control system and calculates the maximal set of safe initial conditions for each aircraft so that separation is assured in the presence of uncertainties in the actions of the other aircraft. Examples of maneuvers using both speed and heading changes are worked out in detail. Index Terms - Air traffic management, conflict resolution, hybrid systems, verification.