h1

TY  - THES
AU  - Winkler, Melanie
TI  - Algorithms for online buffering problems and applications to the power control of a hybrid electric vehicle
CY  - Aachen
M1  - RWTH-CONV-144089
SP  - VIII, 152 S. : Ill., graph. Darst.
PY  - 2013
N1  - Zsfassung in engl. und dt. Sprache. - Prüfungsjahr: 2013. - Publikationsjahr: 2014
N1  - Aachen, Techn. Hochsch., Diss., 2013
AB  - In many situations we have to make repeated decisions in an uncertain environment. Those decisions include to choose a route to drive to work, when to refuel a car or when to purchase and sell shares in the stock market. In each of those settings we decide which actions we take, although we do not possess complete information about the situation. Since part of the missing information might influence the optimal decision, we often make suboptimal choices when examined in hindsight. Furthermore, the actions we take in one time step might influence the options available in the future and can, therefore, avoid optimal choices in the future. In this thesis we introduce and analyze algorithms for Online Buffering problems, i.e., the problem of making repeated decisions in an uncertain environment to manage a buffer. In Online Buffering a sequence of demands and prices of a resource is revealed over time. In each time step we are given the current price and demand, but no information about future prices and demands. Based on this information, we have to decide which amount of the resource we want to purchase. We can store units for a later usage in a buffer. The goal is to use the buffer, s.t. the costs to fulfill the demands are minimized. The costs of a strategy are compared to the costs of purchasing the requested amount in each time step. Since we have no information about future prices and demands, it is impossible to achieve costs which are as low as in the situation where all prices and demands are known beforehand. We study Online Buffering in different settings. First, we show how to use simple threshold algorithms to solve the problem in a stochastic input model. In this model the prices of the resource are generated by a random walk. The decision which amount the algorithm purchases in a time step, depends on the thresholds of the algorithm and the fact whether the price is above, in between or below those thresholds. We show that the threshold algorithm which achieves the lowest expected costs in that setting, is one which fills the buffer if the price equals the lowest price possible, and uses units from the buffer if the price for the resource is above that. We analyze this algorithm quantitatively, i.e., we calculate its expected cost based on the set of possible prices and the size of the buffer. The results in the stochastic input model are not transferable to an input model in which the prices are generated more realistically. We, therefore, study Online Buffering using regret minimization algorithms for online learning, i.e., a cost model which makes no assumptions about prices. Online learning algorithms are equipped with a set of experts, where each expert represents a strategy to solve the problem. The algorithm chooses a strategy from this set in each time step and copies its action. In online learning, we account the algorithm with the cost of the selected expert. Unfortunately, for some problems, such as Online Buffering, switching between experts might cause additional costs which are not considered in the costs of those algorithms. For Online Buffering, those cost results from a difference in the filling levels of the storage of the algorithm and that assumed by the chosen expert. This difference makes it necessary to buy additional units to fulfill the demands. Standard online learning algorithms do not consider those costs. They, therefore, do not perform well for Online Buffering problems. In this thesis, we introduce regret minimization algorithms which also choose their actions based on those additional costs and achieve low costs for Online Buffering problems. Since the algorithms which achieve the lowest expected costs are numerically unstable, we present a variation of one of the algorithms that has slightly higher expected costs but is numerically stable and can be used in an implementation of online learning for Online Buffering. In the second part of this thesis we simulate the presented algorithms as control strategies in a hybrid electric vehicle, i.e., a vehicle equipped with both a combustion engine and an electrical engine. The electrical engine can store energy produced by the combustion engine in a battery and use energy from this buffer to drive the vehicle. A control strategy decides how to split the amount of energy required to drive the vehicle between the two engines. The costs of the control strategy are measured as the amount of fuel it consumes. We show in the simulations, that the results of the threshold algorithms achieved in the stochastic price model cannot be attained in this application. The results for online learning algorithms also hold when those algorithms are applied as control strategies in a hybrid electric vehicle. We show that using those algorithms equipped with a suitable set of experts as control strategies can achieve a lower fuel consumption than using standard control strategies in the simulated hybrid electric vehicle.
KW  - Hybridfahrzeug (SWD)
KW  - Online-Algorithmus (SWD)
LB  - PUB:(DE-HGF)11
UR  - https://publications.rwth-aachen.de/record/229115
ER  -