Biblio
In this paper, we propose a convex programming based method to address a long-standing problem of inner-approximating backward reachable sets of state-constrained polynomial systems subject to time-varying uncertainties. The backward reachable set is a set of states, from which all trajectories starting will surely enter a target region at the end of a given time horizon without violating a set of state constraints in spite of the actions of uncertainties. It is equal to the zero sublevel set of the unique Lipschitz viscosity solution to a Hamilton-Jacobi partial differential equation (HJE). We show that inner approximations of the backward reachable set can be formed by zero sublevel sets of its viscosity supersolutions. Consequently, we reduce the inner-approximation problem to a problem of synthesizing polynomial viscosity supersolutions to this HJE. Such a polynomial solution in our method is synthesized by solving a single semidefinite program. We also prove that polynomial solutions to the formulated semidefinite program exist and can produce a convergent sequence of inner approximations to the interior of the backward reachable set in measure under appropriate assumptions. This is the main contribution of this paper. Several illustrative examples demonstrate the merits of our approach.
DATE is a leading international event providing unique networking opportunities, bringing together designers and design automation users, researchers and vendors, as well as specialists in hardware and software design, test and manufacturing of electronic circuits and systems.
Highly automated driving will be a novel experience for many users and may cause uncertainty and discomfort for them. An efficient real-time detection of user uncertainty during automated driving may trigger adaptation strategies, which could enhance the driving experience and subsequently the acceptance of highly automated driving. In this study, we compared three different models to classify a user’s uncertainty regarding an automated vehicle’s capabilities and traffic safety during overtaking maneuvers based on experimental data from a driving-simulator study. By combining physiological, contextual and user-specific data, we trained three different deep neural networks to classify user uncertainty during overtaking maneuvers on different sets of input features. We evaluated the models based on metrics like the classification accuracy and F1 Scores. For a purely context-based model, we used features such as the Time-Headway and Time-To-Collision of cars on the opposing lane. We demonstrate how the addition of user heart rate and related physiological features can improve the classification accuracy compared to a purely context-based uncertainty model. The third model included user-specific features to account for inter-user differences regarding uncertainty in highly automated vehicles. We argue that a combination of physiological, contextual and user-specific information is important for an effectual uncertainty detection that accounts for inter-user differences.
In this paper, we propose an approach how connected and highly automated vehicles can perform cooperative maneuvers such as lane changes and left-turns at urban intersections where they have to deal with human-operated vehicles and vulnerable road users such as cyclists and pedestrians in so-called mixed traffic. In order to support cooperative maneuvers the urban intersection is equipped with an intelligent controller which has access to different sensors along the intersection to detect and predict the behavior of the traffic participants involved. Since the intersection controller cannot directly control all road users and – not least due to the legal situation – driving decisions must always be made by the vehicle controller itself, we focus on a decentralized control paradigm. In this context, connected and highly automated vehicles use some carefully selected game theory concepts to make the best possible and clear decisions about cooperative maneuvers. The aim is to improve traffic efficiency while maintaining road safety at the same time. Our first results obtained with a prototypical implementation of the approach in a traffic simulation are promising.
The possible interactions between a controller and its environment can naturally be modelled as the arena of a two-player game, and adding an appropriate winning condition permits to specify desirable behavior. The classical model here is the positional game, where both players can (fully or partially) observe the current position in the game graph, which in turn is indicative of their mutual current states. In practice, neither sensing and actuating the environment through physical devices nor data forwarding to and from the controller and signal processing in the controller are instantaneous. The resultant delays force the controller to draw decisions before being aware of the recent history of a play and to submit these decisions well before they can take effect asynchronously. It is known that existence of a winning strategy for the controller in games with such delays is decidable over finite game graphs and with respect to ω-regular objectives. The underlying reduction, however, is impractical for non-trivial delays as it incurs a blow-up of the game graph which is exponential in the magnitude of the delay. For safety objectives, we propose a more practical incremental algorithm successively synthesizing a series of controllers handling increasing delays and reducing the game-graph size in between. It is demonstrated using benchmark examples that even a simplistic explicit-state implementation of this algorithm outperforms state-of-the-art symbolic synthesis algorithms as soon as non-trivial delays have to be handled. We furthermore address the practically relevant cases of non-order-preserving delays and bounded message loss, as arising in actual networked control, thereby considerably extending the scope of regular game theory under delay.
In this paper we study the problem of computing robust invariant sets for state-constrained perturbed polynomial systems within the Hamilton-Jacobi reachability framework. A robust invariant set is a set of states such that every possible trajectory starting from it never violates the given state constraint, irrespective of the actual perturbation. The main contribution of this work is to describe the maximal robust invariant set as the zero level set of the unique Lipschitz-continuous viscosity solution to a Hamilton-Jacobi-Bellman (HJB) equation. The continuity and uniqueness property of the viscosity solution facilitates the use of existing numerical methods to solve the HJB equation for an appropriate number of state variables in order to obtain an approximation of the maximal robust invariant set. We furthermore propose a method based on semi-definite programming to synthesize robust invariant sets. Some illustrative examples demonstrate the performance of our methods.
Hybrid automata are an elegant formal model seamlessly integrating differential equations representing continuous dynamics with automata capturing switching behavior. Since the introduction of the computational model more than a quarter of a century ago [Maler et al. 1992], its algorithmic verification has been an area of intense research. Within this note, which is dedicated to Oded Maler (1957--2018) as one of the inventors of the model, we are trying to delineate major lines of attack to the reachability problem for hybrid automata. Due to its relation to system safety, the reachability problem is a prototypical verification problem for hybrid discrete-continuous system dynamics.
We present a method based on the Hamilton-Jacobi framework that is able to compute over- and under-approximations of reachable sets for autonomous dynamical systems beyond polynomial dynamics. The method does not resort to user-supplied candidate polynomials, but rather relies on an expansion of the evolution function whose convergence in compact state space is guaranteed. Over- and under-approximations of the reachable state space up to any designated precision can consequently be obtained based on truncations of that expansion. As the truncations used in computing over- and under-approximations as well as their associated error bounds agree, double-sided enclosures of the true reach-set can be computed in a single sweep. We demonstrate the precision of the enclosures thus obtained by comparison of benchmark results to related simulations.
Vehicular ad-hoc networks (VANETs) offer a diverse set of applications and therefore gain more and more attention from both academic and industrial communities. However, the deployment of VANETs is not very straight-forward. One challenge is highlighted by an uphill task of establishing and subsequently sustaining a robust communication. The need to obviate extra relay infrastructure in dynamically fluctuating topologies plus concurring shielding obstacles only magnifies this arduous task. In this context, information about traffic-density and about its estimated progress are valuable assets to tackle this issue. This paper proposes a novel routing protocol called Traffic Aware Segment-based Routing (TASR) protocol. The proposed protocol comprises two major parts: 1) Real-time vehicular traffic information for route selection allows for calculating the Expected Connectivity Degree (ECD) on different segments, and 2) a new forwarding method based on geographical information transfers packets from source to destination node. The new metric ECD takes vehicle densities into account, estimating the connectivity on each segment and thus the connectivity of nodes and data delivery ratio for transmitting packets. Furthermore, extensive simulations help analyzing the efficiency of TASR, indicating that it outperforms competing routing protocols.
This paper presents a combined Nonlinear Model Predictive Control (NMPC) for position and velocity tracking of underactuated surface vessels, and collision avoidance of static and dynamic objects into a single control scheme with sideslip angle compensation and environmental disturbances counteraction. A three-degree-of-freedom (3-DOF) dynamic model is used with only two control variables: namely, surge force and yaw moment. External environmental forces are considered as constant or slowly varying disturbances with respect to the inertial frame, and hence nonlinear for the body frame of the vessel. Nonlinear disturbance observer (NDO) is used to estimate these disturbances in order to be fed into the prediction model and enhance the robustness of the controller. A nonlinear optimization problem is formulated to minimize the deviation of the vessel states from a time varying reference generated over a finite horizon by a virtual vessel. Sideslip angle is considered in the cost function formulation to account for tracking error caused by the transverse external force in the absence of sway control force. Collision avoidance is embedded into the trajectory tracking control problem as a time-varying nonlinear constraint of position states to account for static and dynamic obstacles. MATLAB simulations are used to assess the validity of the proposed technique.
Emerging industrial platforms such as the Internet of Things (IoT), Industrial Internet (II) in the US and Industrie 4.0 in Europe have tremendously accelerated the development of new generations of Cyber-Physical Systems (CPS) that integrate humans and human organizations (H-CPS) with physical and computation processes and extend to societal-scale systems such as traffic networks, electric grids, or networks of autonomous systems where control is dynamically shifted between humans and machines. Although such societal-scale CPS can potentially affect many aspect of our lives, significant societal strains have emerged about the new technology trends and their impact on how we live. Emerging tensions extend to regulations, certification, insurance, and other societal constructs that are necessary for the widespread adoption of new technologies. If these systems evolve independently in different parts of the world, they will ‘hard-wire’ the social context in which they are created, making interoperation hard or impossible, decreasing reusability, and narrowing markets for products and services. While impacts of new technology trends on social policies have received attention, the other side of the coin – to make systems adaptable to social policies – is nearly absent from engineering and computer science design practice. This paper focuses on technologies that can be adapted to varying public policies and presents (1) hard problems and technical challenges and (2) some recent research approaches and opportunities. The central goal of this paper is to discuss the challenges and opportunities for constructing H-CPS that can be parameterized by social context. The focus in on three major application domains: connected vehicles, transactive energy systems, and unmanned aerial vehicles.Abbreviations: CPS: Cyber-physical systems; H-CPS: Human-cyber-physical systems; CV: Connected vehicle; II: Industrial Internet; IoT: Internet of Things