Christos G. Cassandras

Christos. G. Cassandras, Xuchao Lin, Xu Chu Ding

We propose an optimal control framework for persistent monitoring problems where the objective is to control the movement of mobile nodes to minimize an uncertainty metric in a given mission space. For multi agent in a one-dimensional mission space, we show that the optimal solution is obtained in terms of a sequence of switching locations and waiting time on these switching points, thus reducing it to a parametric optimization problem. Using Infinitesimal Perturbation Analysis (IPA) we obtain a complete solution through a gradient-based algorithm. We also discuss a receding horizon controller which is capable of obtaining a near-optimal solution on-the-fly.

Christos G. Cassandras, Xu Chu Ding, Xuchao Lin

We propose an optimal control framework for persistent monitoring problems where the objective is to control the movement of mobile agents to minimize an uncertainty metric in a given mission space. For a single agent in a one-dimensional space, we show that the optimal solution is obtained in terms of a sequence of switching locations, thus reducing it to a parametric optimization problem. Using Infinitesimal Perturbation Analysis (IPA) we obtain a complete solution through a gradient-based algorithm. We also discuss a receding horizon controller which is capable of obtaining a near-optimal solution on-the-fly. We illustrate our approach with numerical examples.

Yasaman Khazaeni, Christos G. Cassandras

In previous work, a Cooperative Receding Horizon (CRH) controller was developed for solving cooperative multi-agent problems in uncertain environments. In this paper, we overcome several limitations of this controller, including potential instabilities in the agent trajectories and poor performance due to inaccurate estimation of a reward-to-go function. We propose an event-driven CRH controller to solve the maximum reward collection problem (MRCP) where multiple agents cooperate to maximize the total reward collected from a set of stationary targets in a given mission space. Rewards are non-increasing functions of time and the environment is uncertain with new targets detected by agents at random time instants. The controller sequentially solves optimization problems over a planning horizon and executes the control for a shorter action horizon, where both are defined by certain events associated with new information becoming available. In contrast to the earlier CRH controller, we reduce the originally infinite-dimensional feasible control set to a finite set at each time step. We prove some properties of this new controller and include simulation results showing its improved performance compared to the original one.

Yanfeng Geng, Christos G. Cassandras

We address the traffic light control problem for multiple intersections in tandem by viewing it as a stochastic hybrid system and developing a Stochastic Flow Model (SFM) for it. Using Infinitesimal Perturbation Analysis (IPA), we derive on-line gradient estimates of a cost metric with respect to the controllable green and red cycle lengths. The IPA estimators obtained require counting traffic light switchings and estimating car flow rates only when specific events occur. The estimators are used to iteratively adjust light cycle lengths to improve performance and, in conjunction with a standard gradient-based algorithm, to obtain optimal values which adapt to changing traffic conditions. Simulation results are included to illustrate the approach.

Jing Zhang, Sepideh Pourazarm, Christos G. Cassandras et al.

In earlier work (Zhang et al., 2016) we used actual traffic data from the Eastern Massachusetts transportation network in the form of spatial average speeds and road segment flow capacities in order to estimate Origin-Destination (OD) flow demand matrices for the network. Based on a Traffic Assignment Problem (TAP) formulation (termed "forward problem"), in this paper we use a scheme similar to our earlier work to estimate initial OD demand matrices and then propose a new inverse problem formulation in order to estimate user cost functions. This new formulation allows us to efficiently overcome numerical difficulties that limited our prior work to relatively small subnetworks and, assuming the travel latency cost functions are available, to adjust the values of the OD demands accordingly so that the flow observations are as close as possible to the solutions of the forward problem. We also derive sensitivity analysis results for the total user latency cost with respect to important parameters such as road capacities and minimum travel times. Finally, using the same actual traffic data from the Eastern Massachusetts transportation network, we quantify the Price of Anarchy (POA) for a much larger network than that in Zhang et al. (2016).

Yasaman Khazaeni, Christos G. Cassandras

We consider event-driven methods in a general framework for the control and optimization of multi-agent systems, viewing them as stochastic hybrid systems. Such systems often have feasible realizations in which the events needed to excite an on-line event-driven controller cannot occur, rendering the use of such controllers ineffective. We show that this commonly happens in environments which contain discrete points of interest which the agents must visit. To address this problem in event-driven gradient-based optimization problems, we propose a new metric for the objective function which creates a potential field guaranteeing that gradient values are non-zero when no events are present and which results in eventual event excitation. We apply this approach to the class of cooperative multi-agent data collection problems using the event-driven Infinitesimal Perturbation Analysis (IPA) methodology and include numerical examples illustrating its effectiveness.

Wei Xiao, Christos G. Cassandras, Calin A. Belta

It has been shown that optimizing quadratic costs while stabilizing affine control systems to desired (sets of) states subject to state and control constraints can be reduced to a sequence of Quadratic Programs (QPs) by using Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs). In this paper, we employ machine learning techniques to ensure the feasibility of these QPs, which is a challenging problem, especially for high relative degree constraints where High Order CBFs (HOCBFs) are required. To this end, we propose a sampling-based learning approach to learn a new feasibility constraint for CBFs; this constraint is then enforced by another HOCBF added to the QPs. The accuracy of the learned feasibility constraint is recursively improved by a recurrent training algorithm. We demonstrate the advantages of the proposed learning approach to constrained optimal control problems with specific focus on a robot control problem and on autonomous driving in an unknown environment.

James Queeney, Erhan Can Ozcan, Ioannis Ch. Paschalidis et al.

Robustness and safety are critical for the trustworthy deployment of deep reinforcement learning. Real-world decision making applications require algorithms that can guarantee robust performance and safety in the presence of general environment disturbances, while making limited assumptions on the data collection process during training. In order to accomplish this goal, we introduce a safe reinforcement learning framework that incorporates robustness through the use of an optimal transport cost uncertainty set. We provide an efficient implementation based on applying Optimal Transport Perturbations to construct worst-case virtual state transitions, which does not impact data collection during training and does not require detailed simulator access. In experiments on continuous control tasks with safety constraints, our approach demonstrates robust performance while significantly improving safety at deployment time compared to standard safe reinforcement learning.

James Queeney, Ioannis Ch. Paschalidis, Christos G. Cassandras

We develop a new class of model-free deep reinforcement learning algorithms for data-driven, learning-based control. Our Generalized Policy Improvement algorithms combine the policy improvement guarantees of on-policy methods with the efficiency of sample reuse, addressing a trade-off between two important deployment requirements for real-world control: (i) practical performance guarantees and (ii) data efficiency. We demonstrate the benefits of this new class of algorithms through extensive experimental analysis on a broad range of simulated control tasks.

Rui Chen, Christos G. Cassandras, Amin Tahmasbi-Sarvestani

We derive optimal control policies for a Connected and Automated Vehicle (CAV) cooperating with neighboring CAVs to implement a highway lane change maneuver. We optimize the maneuver time and subsequently minimize the associated energy consumption of all cooperating vehicles in this maneuver. We prove structural properties of the optimal policies which simplify the solution derivations and lead to analytical optimal control expressions. The solutions, when they exist, are guaranteed to satisfy safety constraints for all vehicles involved in the maneuver. Simulation results show the effectiveness of the proposed solution and significant performance improvements compared to maneuvers performed by human-driven vehicles.

Rui Chen, Christos G. Cassandras

We extend Stochastic Flow Models (SFMs), used for a large class of discrete event and hybrid systems, by including the delays which typically arise in flow movement. We apply this framework to the multi-intersection traffic light control problem by including transit delays for vehicles moving from one intersection to the next. Using Infinitesimal Perturbation Analysis (IPA) for this SFM with delays, we derive new on-line gradient estimates of several congestion cost metrics with respect to the controllable green and red cycle lengths. The IPA estimators are used to iteratively adjust light cycle lengths to improve performance and, in conjunction with a standard gradient-based algorithm, to obtain optimal values which adapt to changing traffic conditions. We introduce two new cost metrics to better capture congestion and show that the inclusion of delays in our analysis leads to improved performance relative to models that ignore delays.

Ehsan Sabouni, H. M. Sabbir Ahmad, Vittorio Giammarino et al.

Optimal control methods provide solutions to safety-critical problems but easily become intractable. Control Barrier Functions (CBFs) have emerged as a popular technique that facilitates their solution by provably guaranteeing safety, through their forward invariance property, at the expense of some performance loss. This approach involves defining a performance objective alongside CBF-based safety constraints that must always be enforced. Unfortunately, both performance and solution feasibility can be significantly impacted by two key factors: (i) the selection of the cost function and associated parameters, and (ii) the calibration of parameters within the CBF-based constraints, which capture the trade-off between performance and conservativeness. %as well as infeasibility. To address these challenges, we propose a Reinforcement Learning (RL)-based Receding Horizon Control (RHC) approach leveraging Model Predictive Control (MPC) with CBFs (MPC-CBF). In particular, we parameterize our controller and use bilevel optimization, where RL is used to learn the optimal parameters while MPC computes the optimal control input. We validate our method by applying it to the challenging automated merging control problem for Connected and Automated Vehicles (CAVs) at conflicting roadways. Results demonstrate improved performance and a significant reduction in the number of infeasible cases compared to traditional heuristic approaches used for tuning CBF-based controllers, showcasing the effectiveness of the proposed method.

H. M. Sabbir Ahmad, Ehsan Sabouni, Alexander Wasilkoff et al.

We address the problem of safe policy learning in multi-agent safety-critical autonomous systems. In such systems, it is necessary for each agent to meet the safety requirements at all times while also cooperating with other agents to accomplish the task. Toward this end, we propose a safe Hierarchical Multi-Agent Reinforcement Learning (HMARL) approach based on Control Barrier Functions (CBFs). Our proposed hierarchical approach decomposes the overall reinforcement learning problem into two levels learning joint cooperative behavior at the higher level and learning safe individual behavior at the lower or agent level conditioned on the high-level policy. Specifically, we propose a skill-based HMARL-CBF algorithm in which the higher level problem involves learning a joint policy over the skills for all the agents and the lower-level problem involves learning policies to execute the skills safely with CBFs. We validate our approach on challenging environment scenarios whereby a large number of agents have to safely navigate through conflicting road networks. Compared with existing state of the art methods, our approach significantly improves the safety achieving near perfect (within 5%) success/safety rate while also improving performance across all the environments.

H M Sabbir Ahmad, Ehsan Sabouni, Wei Xiao et al.

We address the security of a network of Connected and Automated Vehicles (CAVs) cooperating to navigate through a conflict area. Adversarial attacks such as Sybil attacks can cause safety violations resulting in collisions and traffic jams. In addition, uncooperative (but not necessarily adversarial) CAVs can also induce similar adversarial effects on the traffic network. We propose a decentralized resilient control and coordination scheme that mitigates the effects of adversarial attacks and uncooperative CAVs by utilizing a trust framework. Our trust-aware scheme can guarantee safe collision free coordination and mitigate traffic jams. Simulation results validate the theoretical guarantee of our proposed scheme, and demonstrate that it can effectively mitigate adversarial effects across different traffic scenarios.

James Queeney, Ioannis Ch. Paschalidis, Christos G. Cassandras

In real-world decision making tasks, it is critical for data-driven reinforcement learning methods to be both stable and sample efficient. On-policy methods typically generate reliable policy improvement throughout training, while off-policy methods make more efficient use of data through sample reuse. In this work, we combine the theoretically supported stability benefits of on-policy algorithms with the sample efficiency of off-policy algorithms. We develop policy improvement guarantees that are suitable for the off-policy setting, and connect these bounds to the clipping mechanism used in Proximal Policy Optimization. This motivates an off-policy version of the popular algorithm that we call Generalized Proximal Policy Optimization with Sample Reuse. We demonstrate both theoretically and empirically that our algorithm delivers improved performance by effectively balancing the competing goals of stability and sample efficiency.

Wei Xiao, Calin Belta, Christos G. Cassandras

This paper addresses the problem of safety-critical control for systems with unknown dynamics. It has been shown that stabilizing affine control systems to desired (sets of) states while optimizing quadratic costs subject to state and control constraints can be reduced to a sequence of quadratic programs (QPs) by using Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs). Our recently proposed High Order CBFs (HOCBFs) can accommodate constraints of arbitrary relative degree. One of the main challenges in this approach is obtaining accurate system dynamics, which is especially difficult for systems that require online model identification given limited computational resources and system data. In order to approximate the real unmodelled system dynamics, we define adaptive affine control dynamics which are updated based on the error states obtained by real-time sensor measurements. We define a HOCBF for a safety requirement on the unmodelled system based on the adaptive dynamics and error states, and reformulate the safety-critical control problem as the above mentioned QP. Then, we determine the events required to solve the QP in order to guarantee safety. We also derive a condition that guarantees the satisfaction of the HOCBF constraint between events. We illustrate the effectiveness of the proposed framework on an adaptive cruise control problem and compare it with the classical time-driven approach.

Wei Xiao, Calin A. Belta, Christos G. Cassandras

Recent work has shown that stabilizing an affine control system to a desired state while optimizing a quadratic cost subject to state and control constraints can be reduced to a sequence of Quadratic Programs (QPs) by using Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs). In our own recent work, we defined High Order CBFs (HOCBFs) for systems and constraints with arbitrary relative degrees. In this paper, in order to accommodate initial states that do not satisfy the state constraints and constraints with arbitrary relative degree, we generalize HOCBFs to High Order Control Lyapunov-Barrier Functions (HOCLBFs). We also show that the proposed HOCLBFs can be used to guarantee the Boolean satisfaction of Signal Temporal Logic (STL) formulae over the state of the system. We illustrate our approach on a safety-critical optimal control problem (OCP) for a unicycle.

James Queeney, Ioannis Ch. Paschalidis, Christos G. Cassandras

In order for reinforcement learning techniques to be useful in real-world decision making processes, they must be able to produce robust performance from limited data. Deep policy optimization methods have achieved impressive results on complex tasks, but their real-world adoption remains limited because they often require significant amounts of data to succeed. When combined with small sample sizes, these methods can result in unstable learning due to their reliance on high-dimensional sample-based estimates. In this work, we develop techniques to control the uncertainty introduced by these estimates. We leverage these techniques to propose a deep policy optimization approach designed to produce stable performance even when data is scarce. The resulting algorithm, Uncertainty-Aware Trust Region Policy Optimization, generates robust policy updates that adapt to the level of uncertainty present throughout the learning process.

Wei Xiao, Calin Belta, Christos G. Cassandras

It has been shown that satisfying state and control constraints while optimizing quadratic costs subject to desired (sets of) state convergence for affine control systems can be reduced to a sequence of quadratic programs (QPs) by using Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs). One of the main challenges in this approach is ensuring the feasibility of these QPs, especially under tight control bounds and safety constraints of high relative degree. In this paper, we provide sufficient conditions for guranteed feasibility. The sufficient conditions are captured by a single constraint that is enforced by a CBF, which is added to the QPs such that their feasibility is always guaranteed. The additional constraint is designed to be always compatible with the existing constraints, therefore, it cannot make a feasible set of constraints infeasible - it can only increase the overall feasibility. We illustrate the effectiveness of the proposed approach on an adaptive cruise control problem.

Xiangyu Meng, Xinmiao Sun, Christos G. Cassandras et al.

A multi-agent coverage problem is considered with energy-constrained agents. The objective of this paper is to compare the coverage performance between centralized and decentralized approaches. To this end, a near-optimal centralized coverage control method is developed under energy depletion and repletion constraints. The optimal coverage formation corresponds to the locations of agents where the coverage performance is maximized. The optimal charging formation corresponds to the locations of agents with one agent fixed at the charging station and the remaining agents maximizing the coverage performance. We control the behavior of this cooperative multi-agent system by switching between the optimal coverage formation and the optimal charging formation. Finally, the optimal dwell times at coverage locations, charging time, and agent trajectories are determined so as to maximize coverage over a given time interval. In particular, our controller guarantees that at any time there is at most one agent leaving the team for energy repletion.

Wei Xiao, Christos G. Cassandras, Calin A. Belta

We address the problem of optimizing the performance of a dynamic system while satisfying hard safety constraints at all times. Implementing an optimal control solution is limited by the computational cost required to derive it in real time, especially when constraints become active, as well as the need to rely on simple linear dynamics, simple objective functions, and ignoring noise. The recently proposed Control Barrier Function (CBF) method may be used for safety-critical control at the expense of sub-optimal performance. In this paper, we develop a real-time control framework that combines optimal trajectories generated through optimal control with the computationally efficient CBF method providing safety guarantees. We use Hamiltonian analysis to obtain a tractable optimal solution for a linear or linearized system, then employ High Order CBFs (HOCBFs) and Control Lyapunov Functions (CLFs) to account for constraints with arbitrary relative degrees and to track the optimal state, respectively. We further show how to deal with noise in arbitrary relative degree systems. The proposed framework is then applied to the optimal traffic merging problem for Connected and Automated Vehicles (CAVs) where the objective is to jointly minimize the travel time and energy consumption of each CAV subject to speed, acceleration, and speed-dependent safety constraints. In addition, when considering more complex objective functions, nonlinear dynamics and passenger comfort requirements for which analytical optimal control solutions are unavailable, we adapt the HOCBF method to such problems. Simulation examples are included to compare the performance of the proposed framework to optimal solutions (when available) and to a baseline provided by human-driven vehicles with results showing significant improvements in all metrics.

Salomón Wollenstein-Betech, Christian Muise, Christos G. Cassandras et al.

Usage of automated controllers which make decisions on an environment are widespread and are often based on black-box models. We use Knowledge Compilation theory to bring explainability to the controller's decision given the state of the system. For this, we use simulated historical state-action data as input and build a compact and structured representation which relates states with actions. We implement this method in a Traffic Light Control scenario where the controller selects the light cycle by observing the presence (or absence) of vehicles in different regions of the incoming roads.

Wei Xiao, Calin Belta, Christos G. Cassandras

Recent work showed that stabilizing affine control systems to desired (sets of) states while optimizing quadratic costs and observing state and control constraints can be reduced to quadratic programs (QP) by using control barrier functions (CBF) and control Lyapunov functions. In our own recent work, we defined high order CBFs (HOCBFs) to accommodating systems and constraints with arbitrary relative degrees, and a penalty method to increase the feasibility of the corresponding QPs. In this paper, we introduce adaptive CBF (AdaCBFs) that can accommodate time-varying control bounds and dynamics noise, and also address the feasibility problem. Central to our approach is the introduction of penalty functions in the definition of an AdaCBF and the definition of auxiliary dynamics for these penalty functions that are HOCBFs and are stabilized by CLFs. We demonstrate the advantages of the proposed method by applying it to a cruise control problem with different road surfaces, tires slipping, and dynamics noise.

Wei Xiao, Calin A. Belta, Christos G. Cassandras

Optimal control problems with constraints ensuring safety and convergence to desired states can be mapped onto a sequence of real time optimization problems through the use of Control Barrier Functions (CBFs) and Control Lyapunov Functions (CLFs). One of the main challenges in these approaches is ensuring the feasibility of the resulting quadratic programs (QPs) if the system is affine in controls. The recently proposed penalty method has the potential to improve the existence of feasible solutions to such problems. In this paper, we further improve the feasibility robustness (i.e., feasibility maintenance in the presence of time-varying and unknown unsafe sets) through the definition of a High Order CBF (HOCBF) that works for arbitrary relative degree constraints; this is achieved by a proposed feasibility-guided learning approach. Specifically, we apply machine learning techniques to classify the parameter space of a HOCBF into feasible and infeasible sets, and get a differentiable classifier that is then added to the learning process. The proposed feasibility-guided learning approach is compared with the gradient-descent method on a robot control problem. The simulation results show an improved ability of the feasibility-guided learning approach over the gradient-decent method to determine the optimal parameters in the definition of a HOCBF for the feasibility robustness, as well as show the potential of the CBF method for robot safe navigation in an unknown environment.

Wei Xiao, Christos G. Cassandras

This paper addresses the optimal control of Connected and Automated Vehicles (CAVs) arriving from two roads at a merging point where the objective is to jointly minimize the travel time and energy consumption of each CAV. The solution guarantees that a speed-dependent safety constraint is always satisfied, both at the merging point and everywhere within a control zone which precedes it. We first analyze the case of no active constraints and prove that under certain conditions the safety constraint remains inactive, thus significantly simplifying the determination of an explicit decentralized solution. When these conditions do not apply, an explicit solution is still obtained that includes intervals over which the safety constraint is active. Our analysis allows us to study the tradeoff between the two objective function components (travel time and energy within the control zone). Simulation examples are included to compare the performance of the optimal controller to a baseline with human-driven vehicles with results showing improvements in both metrics.

Yasaman Khazaeni, Christos G. Cassandras

We propose a new event-driven method for on-line trajectory optimization to solve the data harvesting problem: in a two-dimensional mission space, N mobile agents are tasked with the collection of data generated at M stationary sources and delivery to a base with the goal of minimizing expected collection and delivery delays. We define a new performance measure that addresses the event excitation problem in event-driven controllers and formulate an optimal control problem. The solution of this problem provides some insights on its structure, but it is computationally intractable, especially in the case where the data generating processes are stochastic. We propose an agent trajectory parameterization in terms of general function families which can be subsequently optimized on line through the use of Infinitesimal Perturbation Analysis (IPA). Properties of the solutions are identified, including robustness with respect to the stochastic data generation process and scalability in the size of the event set characterizing the underlying hybrid dynamical system. Explicit results are provided for the case of elliptical and Fourier series trajectories and comparisons with a state-of-the-art graph-based algorithm are given.

Yasaman Khazaeni, Christos G. Cassandras

We propose a new method for trajectory planning to solve the data harvesting problem. In a two-dimensional mission space, $N$ mobile agents are tasked with the collection of data generated at $M$ stationary sources and delivery to a base aiming at minimizing expected delays. An optimal control formulation of this problem provides some initial insights regarding its solution, but it is computationally intractable, especially in the case where the data generating processes are stochastic. We propose an agent trajectory parameterization in terms of general function families which can be subsequently optimized on line through the use of Infinitesimal Perturbation Analysis (IPA). Explicit results are provided for the case of elliptical and Fourier series trajectories and some properties of the solution are identified, including robustness with respect to the data generation processes and scalability in the size of an event set characterizing the underlying hybrid dynamic system.

Jing Wang, Daniel Rossell, Christos G. Cassandras et al.

We present five methods to the problem of network anomaly detection. These methods cover most of the common techniques in the anomaly detection field, including Statistical Hypothesis Tests (SHT), Support Vector Machines (SVM) and clustering analysis. We evaluate all methods in a simulated network that consists of nominal data, three flow-level anomalies and one packet-level attack. Through analyzing the results, we point out the advantages and disadvantages of each method and conclude that combining the results of the individual methods can yield improved anomaly detection results.