BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Christos G. Cassandras

Christos G. Cassandras appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCSystems and Controleess.SYRoboticsArtificial IntelligenceNetworking and Internet Architectureeess.SPHuman-Computer InteractionLogic in Computer ScienceMachine LearningMultiagent Systems

Catalog footprint

What is connected

44works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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

44 published item(s)

preprint2022arXiv

Control Barrier Functions for Systems with Multiple Control Inputs

Control Barrier Functions (CBFs) are becoming popular tools in guaranteeing safety for nonlinear systems and constraints, and they can reduce a constrained optimal control problem into a sequence of Quadratic Programs (QPs) for affine control systems. The recently proposed High Order Control Barrier Functions (HOCBFs) work for arbitrary relative degree constraints. One of the challenges in a HOCBF is to address the relative degree problem when a system has multiple control inputs, i.e., the relative degree could be defined with respect to different components of the control vector. This paper proposes two methods for HOCBFs to deal with systems with multiple control inputs: a general integral control method and a method which is simpler but limited to specific classes of physical systems. When control bounds are involved, the feasibility of the above mentioned QPs can also be significantly improved with the proposed methods. We illustrate our approaches on a unicyle model with two control inputs, and compare the two proposed methods to demonstrate their effectiveness and performance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Feasibility Guaranteed Traffic Merging Control Using Control Barrier Functions

We consider the merging control problem for Connected and Automated Vehicles (CAVs) aiming to jointly minimize travel time and energy consumption while providing speed-dependent safety guarantees and satisfying velocity and acceleration constraints. Applying the joint optimal control and control barrier function (OCBF) method, a controller that optimally tracks the unconstrained optimal control solution while guaranteeing the satisfaction of all constraints is efficiently obtained by transforming the optimal tracking problem into a sequence of quadratic programs (QPs). However, these QPs can become infeasible, especially under tight control bounds, thus failing to guarantee safety constraints. We solve this problem by deriving a control-dependent feasibility constraint corresponding to each CBF constraint which is added to each QP and we show that each such modified QP is guaranteed to be feasible. Extensive simulations of the merging control problem illustrate the effectiveness of this feasibility guaranteed controller.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minimax Multi-Agent Persistent Monitoring of a Network System

We investigate the problem of optimally observing a finite set of targets using a mobile agent over an infinite time horizon. The agent is tasked to move in a network-constrained structure to gather information so as to minimize the worst-case uncertainty about the internal states of the targets. To do this, the agent has to decide its sequence of target-visits and the corresponding dwell-times at each visited target. For a given visiting sequence, we prove that in an optimal dwelling time allocation the peak uncertainty is the same among all the targets. This allows us to formulate the optimization of dwelling times as a resource allocation problem and to solve it using a novel efficient algorithm. Next, we optimize the visiting sequence using a greedy exploration process, using heuristics inspired by others developed in the context of the traveling salesman problem. Numerical results are included to illustrate the contributions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Self-Triggered Coordination Control of Connected Automated Vehicles in Traffic Networks

In this paper, a self-triggered scheme is proposed to optimally control the traffic flow of Connected and Automated Vehicles (CAVs) at conflict areas of a traffic network with the main aim of reducing the data exchange among CAVs in the control zone and at the same to minimize the travel time and energy consumption. The safety constraints and the vehicle limitations are considered using the Control Barrier Function (CBF) framework and a self-triggered scheme is proposed using the CBF constraints. Moreover, modified CBF constraints are developed to ensure a minimum inter-event interval for the proposed self-triggered schemes. Finally, it is shown through a simulation study that the number of data exchanges among CAVs is significantly reduced using the proposed self-triggered schemes in comparison with the standard time-triggered framework.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sequential Cooperative Energy and Time-Optimal Lane Change Maneuvers for Highway Traffic

We derive optimal control policies for a Connected Automated Vehicle (CAV) and cooperating neighboring CAVs to carry out a lane change maneuver consisting of a longitudinal phase where the CAV properly positions itself relative to the cooperating neighbors and a lateral phase where it safely changes lanes. In contrast to prior work on this problem, where the CAV "selfishly" seeks to minimize its maneuver time, we seek to ensure that the fast-lane traffic flow is minimally disrupted (through a properly defined metric) and that highway throughput is improved by optimally selecting the cooperating vehicles. We show that analytical solutions for the optimal trajectories can be derived and are guaranteed to satisfy safety constraints for all vehicles involved in the maneuver. When feasible solutions do not exist, we include a time relaxation method trading off a longer maneuver time with reduced disruption. Our analysis is also extended to multiple sequential maneuvers. Simulation results where the controllers are implemented show their effectiveness in terms of safety guarantees and up to 35% throughput improvement compared to maneuvers with no vehicle cooperation.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Event-Driven Receding Horizon Control of Energy-Aware Dynamic Agents For Distributed Persistent Monitoring

This paper addresses the persistent monitoring problem defined on a network where a set of nodes (targets) needs to be monitored by a team of dynamic energy-aware agents. The objective is to control the agents' motion to jointly optimize the overall agent energy consumption and a measure of overall node state uncertainty, evaluated over a finite period of interest. To achieve these objectives, we extend an established event-driven Receding Horizon Control (RHC) solution by adding an optimal controller to account for agent motion dynamics and associated energy consumption. The resulting RHC solution is computationally efficient, distributed and on-line. Finally, numerical results are provided highlighting improvements compared to an existing RHC solution that uses energy-agnostic first-order agents.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

High Order Control Lyapunov-Barrier Functions for Temporal Logic Specifications

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Adaptive Control Barrier Functions for Safety-Critical Systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bridging the Gap between Optimal Trajectory Planning and Safety-Critical Control with Applications to Autonomous Vehicles

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Combined Eco-Routing and Power-Train Control of Plug-In Hybrid Electric Vehicles in Transportation Networks

We study the problem of eco-routing for Plug-In Hybrid Electric Vehicles (PHEVs) to minimize the overall energy consumption cost. We propose an algorithm which can simultaneously calculate an energy-optimal route (eco-route) for a PHEV and an optimal power-train control strategy over this route. In order to show the effectiveness of our method in practice, we use a HERE Maps API to apply our algorithms based on traffic data in the city of Boston with more than 110,000 links. Moreover, we validate the performance of our eco-routing algorithm using speed profiles collected from a traffic simulator (SUMO) as input to a high-fidelity energy model to calculate energy consumption costs. Our results show significant energy savings (around 12%) for PHEVs with a near real-time execution time for the algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Comparison of Centralized and Decentralized Approaches in Cooperative Coverage Problems with Energy-Constrained Agents

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Congestion-aware Routing and Rebalancing of Autonomous Mobility-on-Demand Systems in Mixed Traffic

This paper studies congestion-aware route-planning policies for Autonomous Mobility-on-Demand (AMoD) systems, whereby a fleet of autonomous vehicles provides on-demand mobility under mixed traffic conditions. Specifically, we first devise a network flow model to optimize the AMoD routing and rebalancing strategies in a congestion-aware fashion by accounting for the endogenous impact of AMoD flows on travel time. Second, we capture reactive exogenous traffic consisting of private vehicles selfishly adapting to the AMoD flows in a user-centric fashion by leveraging an iterative approach. Finally, we showcase the effectiveness of our framework with two case-studies considering the transportation sub-networks in Eastern Massachusetts and New York City. Our results suggest that for high levels of demand, pure AMoD travel can be detrimental due to the additional traffic stemming from its rebalancing flows, while the combination of AMoD with walking or micromobility options can significantly improve the overall system performance.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Decentralized Optimal Control in Multi-lane Merging for Connected and Automated Vehicles

We address the problem of optimally controlling Connected and Automated Vehicles (CAVs) arriving from two multi-lane roads and merging at multiple points where the objective is to jointly minimize the travel time and energy consumption of each CAV subject to speed-dependent safety constraints, as well as speed and acceleration constraints. This problem was solved in prior work for two single-lane roads. A direct extension to multi-lane roads is limited by the computational complexity required to obtain an explicit optimal control solution. Instead, we propose a general framework that converts a multi-lane merging problem into a decentralized optimal control problem for each CAV in a less-conservative way. To accomplish this, we employ a joint optimal control and barrier function method to efficiently get an optimal control for each CAV with guaranteed satisfaction of all constraints. Simulation examples are included to compare the performance of the proposed framework to a baseline provided by human-driven vehicles with results showing significant improvements in both time and energy metrics.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Non-convex Optimization of Multi-agent Systems Using Boosting Functions to Escape Local Optima: Theory and Applications

We address the problem of multiple local optima arising due to non-convex objective functions in cooperative multi-agent optimization problems. To escape such local optima, we propose a systematic approach based on the concept of boosting functions. The underlying idea is to temporarily transform the gradient at a local optimum into a boosted gradient with a non-zero magnitude. We develop a Distributed Boosting Scheme (DBS) based on a gradient-based optimization algorithm using a novel optimal variable step size mechanism so as to guarantee convergence. Even though our motivation is based on the coverage control problem setting, our analysis applies to a broad class of multi-agent problems. Simulation results are provided to compare the performance of different boosting functions families and to demonstrate the effectiveness of the boosting function approach in attaining improved (still generally local) optima.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Explainability of Intelligent Transportation Systems using Knowledge Compilation: a Traffic Light Controller Case

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Joint Pricing and Rebalancing of Autonomous Mobility-on-Demand Systems

This paper studies optimal pricing and rebalancing policies for Autonomous Mobility-on-Demand (AMoD) systems. We take a macroscopic planning perspective to tackle a profit maximization problem while ensuring that the system is load-balanced. We begin by describing the system using a dynamic fluid model to show the existence and stability of an equilibrium (i.e., load balance) through pricing policies. We then develop an optimization framework that allows us to find optimal policies in terms of pricing and rebalancing. We first maximize profit by only using pricing policies, then incorporate rebalancing, and finally we consider whether the solution is found sequentially or jointly. We apply each approach on a data-driven case study using real taxi data from New York City. Depending on which benchmarking solution we use, the joint problem (i.e., pricing and rebalancing) increases profits by 7% to 40%

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multi-Agent Persistent Monitoring of Targets with Uncertain States

We address the problem of persistent monitoring, where a finite set of mobile agents has to persistently visit a finite set of targets. Each of these targets has an internal state that evolves with linear stochastic dynamics. The agents can observe these states, and the observation quality is a function of the distance between the agent and a given target. The goal is then to minimize the mean squared estimation error of these target states. We approach the problem from an infinite horizon perspective, where we prove that, under some natural assumptions, the covariance matrix of each target converges to a limit cycle. The goal, therefore, becomes to minimize the steady state uncertainty. Assuming that the trajectory is parameterized, we provide tools for computing the steady state cost gradient. We show that, in one-dimensional (1D) environments with bounded control and non-overlapping targets, when an optimal control exists it can be represented using a finite number of parameters. We also propose an efficient parameterization of the agent trajectories for multidimensional settings using Fourier curves. Simulation results show the efficacy of the proposed technique in 1D, 2D and 3D scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimal Composition of Heterogeneous Multi-Agent Teams for Coverage Problems with Performance Bound Guarantees

We consider the problem of determining the optimal composition of a heterogeneous multi-agent team for coverage problems by including costs associated with different agents and subject to an upper bound on the maximal allowable number of agents. We formulate a resource allocation problem without introducing additional non-convexities to the original problem. We develop a distributed Projected Gradient Ascent (PGA) algorithm to solve the optimal team composition problem. To deal with non-convexity, we initialize the algorithm using a greedy method and exploit the submodularity and curvature properties of the coverage objective function to derive novel tighter performance bound guarantees on the optimization problem solution. Numerical examples are included to validate the effectiveness of this approach in diverse mission space configurations and different heterogeneous multi-agent collections. Comparative results obtained using a commercial mixed-integer nonlinear programming problem solver demonstrate both the accuracy and computational efficiency of the distributed PGA algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Multi-Agent Coverage Control with Energy Depletion and Repletion

We develop a hybrid system model to describe the behavior of multiple agents cooperatively solving an optimal coverage problem under energy depletion and repletion constraints. The model captures the controlled switching of agents between coverage (when energy is depleted) and battery charging (when energy is replenished) modes. It guarantees the feasibility of the coverage problem by defining a guard function on each agent's battery level to prevent it from dying on its way to a charging station. The charging station plays the role of a centralized scheduler to solve the contention problem of agents competing for the only charging resource in the mission space. The optimal coverage problem is transformed into a parametric optimization problem to determine an optimal recharging policy. This problem is solved through the use of Infinitesimal Perturbation Analysis (IPA), with simulation results showing that a full recharging policy is optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Data-driven Estimation of Origin-Destination Demand and User Cost Functions for the Optimization of Transportation Networks

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).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Event excitation for event-driven control and optimization of multi-agent systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Event-driven Trajectory Optimization for Data Harvesting in Multi-Agent Systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal control for a robotic exploration, pick-up and delivery problem

This paper addresses an optimal control problem for a robot that has to find and collect a finite number of objects and move them to a depot in minimum time. The robot has fourth-order dynamics that change instantaneously at any pick-up or drop-off of an object. The objects are modeled by point masses with a-priori unknown locations in a bounded two-dimensional space that may contain unknown obstacles. For this hybrid system, an Optimal Control Problem (OCP) is approximately solved by a receding horizon scheme, where the derived lower bound for the cost-to-go is evaluated for the worst and for a probabilistic case, assuming a uniform distribution of the objects. First, a time-driven approximate solution based on time and position space discretization and mixed integer programming is presented. Due to the high computational cost of this solution, an alternative event-driven approximate approach based on a suitable motion parameterization and gradient-based optimization is proposed. The solutions are compared in a numerical example, suggesting that the latter approach offers a significant computational advantage while yielding similar qualitative results compared to the former. The methods are particularly relevant for various robotic applications like automated cleaning, search and rescue, harvesting or manufacturing.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Energy-Efficient Downlink Transmission Scheduling for Real-Time Wireless Networks

It has been shown that using appropriate channel coding schemes in wireless environments, transmission energy can be significantly reduced by controlling the packet transmission rate. This paper seeks optimal solutions for downlink transmission control problems, motivated by this observation and by the need to minimize energy consumption in real-time wireless networks. Our problem formulation deals with a more general setting than the paper authored by Gamal et. al., in which the MoveRight algorithm is proposed. The MoveRight algorithm is an iterative algorithm that converges to the optimal solution. We show that even under the more general setting, the optimal solution can be efficiently obtained through an approach decomposing the optimal sample path through certain "critical tasks" which in turn can be efficiently identified. We include simulation results showing that our algorithm is significantly faster than the MoveRight algorithm. We also discuss how to utilize our results and receding horizon control to perform on-line transmission scheduling where future task information is unknown.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Event-Driven Multi-Agent Persistent Monitoring of a Finite Set of Targets

We consider the problem of controlling the movement of multiple cooperating agents so as to minimize an uncertainty metric associated with a finite number of targets. In a one-dimensional mission space, we adopt an optimal control framework and show that the solution is reduced to a simpler parametric optimization problem: determining a sequence of locations where each agent may dwell for a finite amount of time and then switch direction. This amounts to a hybrid system which we analyze using Infinitesimal Perturbation Analysis (IPA) to obtain a complete on-line solution through an event-driven gradient-based algorithm which is also robust with respect to the uncertainty model used. The resulting controller depends on observing the events required to excite the gradient-based algorithm, which cannot be guaranteed. We solve this problem by proposing a new metric for the objective function which creates a potential field guaranteeing that gradient values are non-zero. This approach is compared to an alternative graph-based task scheduling algorithm for determining an optimal sequence of target visits. Simulation examples are included to demonstrate the proposed methods.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Personalized Cancer Therapy Design: Robustness vs. Optimality

Intermittent Androgen Suppression (IAS) is a treatment strategy for delaying or even preventing time to relapse of advanced prostate cancer. IAS consists of alternating cycles of therapy (in the form of androgen suppression) and off-treatment periods. The level of prostate specific antigen (PSA) in a patient's serum is frequently monitored to determine when the patient will be taken off therapy and when therapy will resume. In spite of extensive recent clinical experience with IAS, the design of an ideal protocol for any given patient remains one of the main challenges associated with effectively implementing this therapy. We use a threshold-based policy for optimal IAS therapy design that is parameterized by lower and upper PSA threshold values and is associated with a cost metric that combines clinically relevant measures of therapy success. We apply Infinitesimal Perturbation Analysis (IPA) to a Stochastic Hybrid Automaton (SHA) model of prostate cancer evolution under IAS and derive unbiased estimators of the cost metric gradient with respect to various model and therapy parameters. These estimators are subsequently used for system analysis. By evaluating sensitivity estimates with respect to several model parameters, we identify critical parameters and demonstrate that relaxing the optimality condition in favor of increased robustness to modeling errors provides an alternative objective to therapy design for at least some patients.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Solving A Class of Discrete Event Simulation-based Optimization Problems Using "Optimality in Probability"

We approach a class of discrete event simulation-based optimization problems using optimality in probability, an approach which yields what is termed a "champion solution". Compared to the traditional optimality in expectation, this approach favors the solution whose actual performance is more likely better than that of any other solution; this is an effective alternative to the traditional optimality sense, especially when facing a dynamic and nonstationary environment. Moreover, using optimality in probability is computationally promising for a class of discrete event simulation-based optimization problems, since it can reduce computational complexity by orders of magnitude compared to general simulation-based optimization methods using optimality in expectation. Accordingly, we have developed an "Omega Median Algorithm" in order to effectively obtain the champion solution and to fully utilize the efficiency of well-developed off-line algorithms to further facilitate timely decision making. An inventory control problem with nonstationary demand is included to illustrate and interpret the use of the Omega Median Algorithm, whose performance is tested using simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Optimal Control Approach for the Data Harvesting Problem

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Infinitesimal Perturbation Analysis for Personalized Cancer Therapy Design

We use a Stochastic Hybrid Automaton (SHA) model of prostate cancer evolution under intermittent androgen suppression (IAS) to study a threshold-based policy for therapy design. IAS is currently one of the most widely used treatments for advanced prostate cancer. Patients undergoing IAS are submitted to cycles of treatment (in the form of androgen deprivation) and off-treatment periods in an alternating manner. One of the main challenges in IAS is to optimally design a therapy scheme, i.e., to determine when to discontinue and recommence androgen suppression. The level of prostate specific antigen (PSA) in a patient's serum is frequently monitored to determine when the patient will be taken off therapy and when therapy will resume. The threshold-based policy we propose is parameterized by lower and upper PSA threshold values and is associated with a cost metric that combines clinically relevant measures of therapy success. Using Infinitesimal Perturbation Analysis (IPA), we derive unbiased gradient estimators of this cost metric with respect to the controllable PSA threshold values based on actual data and show how these estimators can be used to adaptively adjust controllable parameters so as to improve therapy outcomes based on the cost metric defined.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lifetime Maximization of Wireless Sensor Networks with a Mobile Source Node

We study the problem of routing in sensor networks where the goal is to maximize the network's lifetime. Previous work has considered this problem for fixed-topology networks. Here, we add mobility to the source node, which requires a new definition of the network lifetime. In particular, we redefine lifetime to be the time until the source node depletes its energy. When the mobile node's trajectory is unknown in advance, we formulate three versions of an optimal control problem aiming at this lifetime maximization. We show that in all cases, the solution can be reduced to a sequence of Non- Linear Programming (NLP) problems solved on line as the source node trajectory evolves.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Dynamic Formation Control of Multi-Agent Systems in Environments with Obstacles

We address the optimal dynamic formation problem in mobile leader-follower networks where an optimal formation is generated to maximize a given objective function while continuously preserving connectivity. We show that in a convex mission space, the connectivity constraints can be satisfied by any feasible solution to a mixed integer nonlinear optimization problem. When the optimal formation objective is to maximize coverage in a mission space cluttered with obstacles, we separate the process into intervals with no obstacles detected and intervals where one or more obstacles are detected. In the latter case, we propose a minimum-effort reconfiguration approach for the formation which still optimizes the objective function while avoiding the obstacles and ensuring connectivity. We include simulation results illustrating this dynamic formation process.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A New Event-Driven Cooperative Receding Horizon Controller for Multi-agent Systems in Uncertain Environments

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An Optimal Control Approach to the Multi-Agent Persistent Monitoring Problem in Two-Dimensional Spaces

We address the persistent monitoring problem in two-dimensional mission spaces where the objective is to control the trajectories of multiple cooperating agents to minimize an uncertainty metric. In a one-dimensional mission space, we have shown that the optimal solution is for each agent to move at maximal speed and switch direction at specific points, possibly waiting some time at each such point before switching. In a two-dimensional mission space, such simple solutions can no longer be derived. An alternative is to optimally assign each agent a linear trajectory, motivated by the one-dimensional analysis. We prove, however, that elliptical trajectories outperform linear ones. With this motivation, we formulate a parametric optimization problem in which we seek to determine such trajectories. We show that the problem can be solved using Infinitesimal Perturbation Analysis (IPA) to obtain performance gradients on line and obtain a complete and scalable solution. Since the solutions obtained are generally locally optimal, we incorporate a stochastic comparison algorithm for deriving globally optimal elliptical trajectories. Numerical examples are included to illustrate the main result, allow for uncertainties modeled as stochastic processes, and compare our proposed scalable approach to trajectories obtained through off-line computationally intensive solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Energy-aware Vehicle Routing in Networks with Charging Nodes

We study the problem of routing vehicles with energy constraints through a network where there are at least some charging nodes. We seek to minimize the total elapsed time for vehicles to reach their destinations by determining routes as well as recharging amounts when the vehicles do not have adequate energy for the entire journey. For a single vehicle, we formulate a mixed-integer nonlinear programming (MINLP) problem and derive properties of the optimal solution allowing it to be decomposed into two simpler problems. For a multi-vehicle problem, where traffic congestion effects are included, we use a similar approach by grouping vehicles into subflows. We also provide an alternative flow optimization formulation leading to a computationally simpler problem solution with minimal loss in accuracy. Numerical results are included to illustrate these approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Escaping Local Optima in a Class of Multi-Agent Distributed Optimization Problems: A Boosting Function Approach

We address the problem of multiple local optima commonly arising in optimization problems for multi-agent systems, where objective functions are nonlinear and nonconvex. For the class of coverage control problems, we propose a systematic approach for escaping a local optimum, rather than randomly perturbing controllable variables away from it. We show that the objective function for these problems can be decomposed to facilitate the evaluation of the local partial derivative of each node in the system and to provide insights into its structure. This structure is exploited by defining "boosting functions" applied to the aforementioned local partial derivative at an equilibrium point where its value is zero so as to transform it in a way that induces nodes to explore poorly covered areas of the mission space until a new equilibrium point is reached. The proposed boosting process ensures that, at its conclusion, the objective function is no worse than its pre-boosting value. However, the global optima cannot be guaranteed. We define three families of boosting functions with different properties and provide simulation results illustrating how this approach improves the solutions obtained for this class of distributed optimization problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Infinitesimal Perturbation Analysis for Quasi-Dynamic Traffic Light Controllers

We consider the traffic light control problem for a single intersection modeled as a stochastic hybrid system. We study a quasi-dynamic policy based on partial state information defined by detecting whether vehicle backlogs are above or below certain controllable thresholds. Using Infinitesimal Perturbation Analysis (IPA), we derive online gradient estimators of a cost metric with respect to these threshold parameters and use these estimators to iteratively adjust the threshold values through a standard gradient-based algorithm so as to improve overall system performance under various traffic conditions. Results obtained by applying this methodology to a simulated urban setting are also included.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Optimal Routing of Energy-aware Vehicles in Networks with Inhomogeneous Charging Nodes

We study the routing problem for vehicles with limited energy through a network of inhomogeneous charging nodes. This is substantially more complicated than the homogeneous node case studied in [1]. We seek to minimize the total elapsed time for vehicles to reach their destinations considering both traveling and recharging times at nodes when the vehicles do not have adequate energy for the entire journey. We study two versions of the problem. In the single vehicle routing problem, we formulate a mixed-integer nonlinear programming (MINLP) problem and show that it can be reduced to a lower dimensionality problem by exploiting properties of an optimal solution. We also obtain a Linear Programming (LP) formulation allowing us to decompose it into two simpler problems yielding near-optimal solutions. For a multi-vehicle problem, where traffic congestion effects are included, we use a similar approach by grouping vehicles into "subflows". We also provide an alternative flow optimization formulation leading to a computationally simpler problem solution with minimal loss in accuracy. Numerical results are included to illustrate these approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximate IPA: Trading Unbiasedness for Simplicity

When Perturbation Analysis (PA) yields unbiased sensitivity estimators for expected-value performance functions in discrete event dynamic systems, it can be used for performance optimization of those functions. However, when PA is known to be unbiased, the complexity of its estimators often does not scale with the system's size. The purpose of this paper is to suggest an alternative approach to optimization which balances precision with computing efforts by trading off complicated, unbiased PA estimators for simple, biased approximate estimators. Furthermore, we provide guidelines for developing such estimators, that are largely based on the Stochastic Flow Modeling framework. We suggest that if the relative error (or bias) is not too large, then optimization algorithms such as stochastic approximation converge to a (local) minimum just like in the case where no approximation is used. We apply this approach to an example of balancing loss with buffer-cost in a finite-buffer queue, and prove a crucial upper bound on the relative error. This paper presents the initial study of the proposed approach, and we believe that if the idea gains traction then it may lead to a significant expansion of the scope of PA in optimization of discrete event systems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Network Anomaly Detection: A Survey and Comparative Analysis of Stochastic and Deterministic Methods

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Quasi-dynamic Traffic Light Control for a Single Intersection

We address the traffic light control problem for a single intersection by viewing it as a stochastic hybrid system and developing a Stochastic Flow Model (SFM) for it. We adopt a quasi-dynamic control policy based on partial state information defined by detecting whether vehicle backlog is above or below a certain threshold, without the need to observe an exact vehicle count. The policy is parameterized by green and red cycle lengths which depend on this partial state information. Using Infinitesimal Perturbation Analysis (IPA), we derive online gradient estimators of an average traffic congestion metric with respect to these controllable green and red cycle lengths when the vehicle backlog is above or below the threshold. The estimators are used to iteratively adjust light cycle lengths so as to improve performance and, in conjunction with a standard gradient-based algorithm, to seek optimal values which adapt to changing traffic conditions. Simulation results are included to illustrate the approach and quantify the benefits of quasidynamic traffic light control over earlier static approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A General Framework for Modeling and Online Optimization of Stochastic Hybrid Systems

We extend the definition of a Stochastic Hybrid Automaton (SHA) to overcome limitations that make it difficult to use for on-line control. Since guard sets do not specify the exact event causing a transition, we introduce a clock structure (borrowed from timed automata), timer states, and guard functions that disambiguate how transitions occur. In the modified SHA, we formally show that every transition is associated with an explicit element of an underlying event set. This also makes it possible to uniformly treat all events observed on a sample path of a stochastic hybrid system and generalize the performance sensitivity estimators derived through Infinitesimal Perturbation Analysis (IPA). We eliminate the need for a case-by-case treatment of different event types and provide a unified set of matrix IPA equations. We illustrate our approach by revisiting an optimization problem for single node finite-capacity stochastic flow systems to obtain performance sensitivity estimates in this new setting.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Multi-intersection Traffic Light Control Using Infinitesimal Perturbation Analysis

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Timeout Control in Distributed Systems Using Perturbation Analysis: Multiple Communication Links

Timeout control is a simple mechanism used when direct feedback is either impossible, unreliable, or too costly, as is often the case in distributed systems. Its effectiveness is determined by a timeout threshold parameter and our goal is to quantify the effect of this parameter on the system behavior. In this paper, we extend previous results to the case where there are N transmitting nodes making use of a common communication link bandwidth. After deriving the stochastic hybrid model for this problem, we apply Infinitesimal Perturbation Analysis to find the derivative estimates of aggregate average goodput of the system. We also derive the derivative estimate of the goodput of a transmitter with respect to its own timeout threshold which can be used for local and hence, distributed optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An Optimal Control Approach for the Persistent Monitoring Problem

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.

0 citations0 reviewsNo code linkedOpen access