Consider an agent who seeks to traverse the shortest path in a graph having random edge weights. If the agent has no side information about the realizations of the edge weights, it should simply take the path of least average length. We consider a generalization of this framework whereby the agent has access to a limited amount of side information about the edge weights ahead of choosing a path. We define a notion of information and information capacity, provide bounds on the agent's performance relative to the amount of side information it receives, and offer algorithms for optimizing information within a capacity constraint. The results are based on a new graph reduction for shortest path optimization that strikes a balance between the amount of information about the graph's topology and the distribution of the edge weights used to compute performance bounds.
Consider an agent who seeks to traverse the shortest path in a graph having random edge weights. If the agent has no side information about the realizations of the edge weights, it should simply take the path of least average length, a deterministic optimization. We consider a generalization of this framework whereby the agent has access to a limited amount of side information about the edge weights as it traverses the graph. Specifically, we define a notion of side information and capacity, and we provide bounds on the agent's performance relative to the total amount of side information it receives. The results are based in a graph reduction for shortest path optimization and an abstraction of sequential decision-making.
Consider an agent who seeks to traverse the shortest path in a graph having random edge weights. If the agent has no side information about the realizations of the edge weights, it should simply take the path of least average length, a deterministic optimization. We consider a generalization of this framework whereby the agent has access to a limited amount of side information about the edge weights ahead of choosing a path. Specifically, we define a notion of information and information capacity, provide bounds on the agent's performance relative to the amount of side information it receives, and offer algorithms for optimizing information within a capacity constraint. The results are based on a new graph reduction for shortest path optimization that strikes a balance between the amount of information about the graph and the distribution of the edge weights used to compute performance bounds.
The problem of finding an optimal path in an uncertain graph arises in numerous applications, including network routing, path-planning for vehicles, and the control of finite-state systems. While techniques in robust and stochastic programming can be employed to compute, respectively, worst-case and average-optimal solutions to the shortest-path problem, we consider an alternative problem where the agent that traverses the graph can request limited information about the graph before choosing a path to traverse.
In this paper, we define and quantify a notion of information that is compatible to this performance-based framework, bound the performance of the agent subject to a bound on the capacity of the information it can request, and present algorithms for optimizing information.
In this note, we prove that dynamic programming value iteration converges uniformly for discrete-time homogeneous systems and continuous-time switched homogeneous systems. For discrete-time homogeneous systems, rather than discounting the cost function (which exponentially decreases the weights of the cost of future actions), we show that such systems satisfy approximate dynamic programming conditions recently developed by Rantzer, which provides a uniform bound on the convergence rate of value iteration over a compact set. For continuous-time switched homogeneous system, we present a transformation that generates an equivalent discrete-time homogeneous system with an additional ``sampling'' input for which discrete-time value iteration is compatible, and we further show that the inclusion of homogeneous switching costs results in a continuous value function.
In this paper, we present a method for designing discrete-time state-feedback controllers for a class of continuous-time switched homogeneous systems which includes switched linear systems as a special case. A discrete-time approximate value iteration over a quantization of the unit sphere is used to compute an approximation of the continuous-time value function over the entire unbounded state space. Properties of the value function and its approximations are elicited and used to provide conditions under which state-feedback controllers with provable guarantees in stability and performance can be constructed. To illustrate the results, the methodology is applied to an example switched system possessing two unstable modes, one of which is nonlinear.
The growing stringency of fuel economy, emissions, and drivability requirements has led to proliferation of existing and future powertrain systems with multiple discrete operating modes. The design of systematic approaches to the development of optimal and robust control systems for such powertrains is motivated by the need to mitigate a potentially significant increase in the strategy development times and costs, as well as in calibration complexity. To address this issue, we propose a new approach for controlling switched systems, such as powertrain systems with multiple operating modes, that reduces the complexity of computing a continuous and discrete control law to a linear programming problem in finding an optimal set of states to track in each operating mode. The controller methodology is designed to be practical and suitable for practical applications while, under appropriate conditions, providing approximately optimal performance. An application to the direct injection stratified charge engine, which can operate in either stratified or homogeneous combustion mode, is given to illustrate the main ideas.
Many of the existing techniques for controlling switched systems either require the solution to a complex optimization problem or significant sacrifices to either stability or performance to offer practical controllers. In [13], it is shown that stabilizing, practical controllers with meaningful performance guarantees can be constructed for a specific class of hybrid systems by parameterizing the controller actions by a finite set. We extend this approach to the control of controllable switched systems by constraining the switching portion of the control input and fixing the feedback controller for each subsystem. We show that, under reasonable assumptions, the resulting system is guaranteed to converge to the target while providing meaningful performance. We apply our approach to the direct-injection stratified charge (DISC) engine and compare the results to that of a model predictive controller designed for the same application.
In this paper, a means for controlling the torque and air-to-fuel ratio of the direct injection stratified charge (DISC) engine using multiparametric-quadratic programming (MP-QP) techniques is presented. The approach explicitly guarantees constraint satisfaction and zero-offset, asymptotic tracking to the optimal admissible output with respect to the target reference. The results are compared to an existing controller for the same application.
In this paper, we present an approach for controlling switched systems that reduces the complexity of determining both a control input and mode sequence to a dynamic programming problem in finding an optimal set of states to track in each operating mode, using custom controllers in each mode to perform such tracking. The results are focused on an application to the direct injection stratified charge (DISC) engine, which uses two modes of operation to provide a tradeoff between power and fuel economy. In this application, a new type of torque and air-tofuel ratio controller, based on multi-parametric quadratic programming, is utilized.
Several genetic algorithms have been designed for the problem of scheduling task graphs onto multiprocessors, the primary distinction among most of them being the chromosomal representation used for a schedule. However, these existing approaches are monolithic as they attempt to scan the entire solution space without consideration to techniques that can reduce the complexity of the optimization. In this paper, a genetic algorithm based in a bi-chromosomal representation and capable of being incorporated into a cluster/merging optimization framework is proposed, and it is experimentally shown to outperform a leading genetic algorithm for scheduling.
He received his Master's Degree from MIT and his Bachelor's Degree from the University of Maryland, both in Electrical Engineering. While at UMD, he earned the Guha Award for best undergraduate thesis in Electrical Engineering and Economics.
My hobbies and interests include photography, history, politics, and technology. For two terms (2004-2006), I served as the Chairperson of the Thirsty Ear Pub, a popular pub located on the MIT campus.
