Search

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.

Future hybrid electric vehicles (HEVs) may use path-dependent operating policies to improve fuel economy. In our previous work, we developed a dynamic programming (DP) algorithm for prescribing the battery state of charge (SoC) set-point, which in combination with a novel approach of route decomposition, has been shown to reduce fuel consumption over selected routes. In this paper, we propose and illustrate a receding horizon control (RHC) strategy for the on-board optimization of the fuel consumption. As compared to the DP approach, the computational requirements of the RHC strategy are lower. In addition, the RHC strategy is capable of correcting for differences between characteristics of a predicted route and a route actually traveled. Our numerical results indicate that the fuel economy potential of the RHC solution can approach that of the DP solution., Ford Motor Company

The paper examines path-dependent control of Hybrid Electric Vehicles (HEVs). In this approach we seek to improve HEV fuel economy by optimizing charging and discharging of the vehicle battery depending on the forecasted vehicle route. The route is decomposed into a series connection of route segments with (partially) known properties. The dynamic programming is used as a tool to quantify the benefits offered by route information availability., Ford Motor Company

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010., Cataloged from PDF version of thesis., Includes bibliographical references (p. 92-93)., Information about a random event (termed the source) is typically treated as a (possibly noisy) function of that event. Information has a destination, an agent, that uses the information to make a decision. In traditional communication systems design, it is usually assumed that the agent uses the information to produce an estimate of the source, and that estimate is in turn used to make the decision. Consequently, the typical objective of communication-systems design is to construct the communication system so that the joint distribution between the source and the information is "optimal" in the sense that it minimizes the average error of the estimate. Due to resource limitations such as cost, power, or time, estimation quality is constrained in the sense that the set of allowable joint distribution is bounded in mutual information. In the context of an agent using information to make decisions, however, such metrics may not be appropriate. In particular, the true value of information is determined by how it impacts the average payoff of the agent's decisions, not its estimation accuracy. To this end, mutual information may not the most convenient measure of information quantity since its relationship to decision quality may be very complicated, making it difficult to develop algorithms for information optimization. In this thesis, we study the value of information in an instance of an uncertain decision framework: shortest path optimization on a graph with random edge weights., (cont.) Specifically, we consider an agent that seeks to traverse the shortest path of a graph subject to some side information it receives about the edge weights in advance of and during its travel. In this setting, decision quality is determined by the average length of the paths the agent chooses, not how often the agent decodes the optimal path. For this application, we define and quantify a notion of information that is compatible with this problem, bound the performance of the agent subject to a bound on the amount of information available to it, study the impact of spreading information sequentially over partial decisions, and provide algorithms for information optimization. Meaningful, analytic performance bounds and practical algorithms for information optimization are obtained by leveraging a new type of geometric graph reduction for shortest path optimization as well as an abstraction of the geometry of sequential decision making., by Michael David Rinehart., Ph.D.

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 ldquosamplingrdquo 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., Ford Motor Company (Ford Research and Advanced Engineering)

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005., This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections., Includes bibliographical references (p. 83-85)., 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., by Michael David Rinehart., S.M.