Algorithms for online buffering problems and applications to the power control of a hybrid electric vehicle

Winkler, Melanie; Vöcking, Berthold

doi:urn:nbn:de:hbz:82-opus-49560

Algorithms for online buffering problems and applications to the power control of a hybrid electric vehicle = Algorithmen für das Online-Buffering-Problem und deren Anwendungen zur Antriebssteuerung eines Hybridfahrzeugs

Winkler, Melanie (Author)

2013 & 2014

Verantwortlichkeitsangabevorgelegt von Melanie Winkler

ImpressumAachen 2013

UmfangVIII, 152 S. : Ill., graph. Darst.

Aachen, Techn. Hochsch., Diss., 2013

Zsfassung in engl. und dt. Sprache. - Prüfungsjahr: 2013. - Publikationsjahr: 2014

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Vöcking, Berthold (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2013-12-16

Online
URN: urn:nbn:de:hbz:82-opus-49560
URL: https://publications.rwth-aachen.de/record/229115/files/4956.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Hybridfahrzeug (Genormte SW) ; Online-Algorithmus (Genormte SW) ; Informatik (frei) ; Regret-Minimierung (frei) ; Online Algorithmen (frei) ; online algorithms (frei) ; hybrid electric vehicle (frei) ; Regretminimization (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In unserem Alltag müssen wir oft Entscheidungen treffen, ohne über genaue Informationen über die aktuelle Situation zu verfügen. Dies können zum Beispiel Entscheidungen darüber sein, wann wir unser Auto betanken oder wann wir Aktien kaufen oder verkaufen wollen. In allen beschriebenen Situationen können wir zum Zeitpunkt der Entscheidung nicht abschätzen, ob wir uns mit zusätzlichen Informationen über die Gegebenheiten genauso entschieden hätten. Entscheidungen, die wir zum aktuellen Zeitpunkt treffen können weiterhin Entscheidungsmöglichkeiten in der Zukunft beeinflussen. In dieser Arbeit untersuchen wir Algorithmen für so genannte Online Buffering Probleme, welche eine Strategie für wiederholte Entscheidungen im Speichermanagement bieten. Im Online Buffering werden über die Zeit verteilt Preise eines Produkts bekannt gegeben und zu jedem Zeitpunkt wird eine bestimmte Menge dieses Produktes benötigt. Zu jedem Zeitpunkt sind nur Preise und Mengen bekannt, zu welchen das Produkt zum aktuellen und zu vergangenen Zeitpunkten verfügbar war, bzw. welche zu diesen Zeitpunkten angefordert wurden. Wir haben keine Informationen über zukünftige Preise und Anforderungsmengen. Basierend auf den gegebenen Informationen müssen wir festlegen, welche Menge des Produktes zum aktuellen Zeitpunkt gekauft werden soll. Wir können zusätzlich gekaufte Einheiten in einem Speicher fester Größe bis zu deren Verbrauch deponieren. Zu jedem Zeitpunkt müssen wir durch Einkauf oder Nutzen von Einheiten im Speicher in der Lage sein, die aktuelle Anforderung zu erfüllen. Ziel ist es, alle Anforderungen möglichst günstig abzudecken. Es ist dabei generell nicht möglich, die Kosten der Lösung zu erreichen, welche möglich ist, falls Anforderungsmengen und Preise im Vorhinein bekannt sind. Wir untersuchen Online Buffering in verschiedenen Preismodellen. In einem ersten Ansatz betrachten wir Threshold-Algorithmen in einem stochastischen Eingabemodell. Die Preise werden von einem Random Walk erzeugt. Die Entscheidung, welche Menge der Algorithmus zu einem Zeitpunkt einkauft, wird über Thresholds, d.h. einfache Grenzentscheidungen (ist der Preis unterhalb oder oberhalb einer bestimmten Grenze) getroffen. Wir zeigen, dass der Algorithmus, welcher den Speicher füllt, sobald der kleinstmögliche Preis erreicht ist und Einheiten aus dem Speicher nutzt, wenn der Preis darüber liegt, die kleinsten erwarteten Kosten erreicht. Wir analysieren diesen Algorithmus auch quantitativ, d.h. wir berechnen seine erwarteten Kosten pro Zeitschritt abhängig von der Größe des Speichers und der Anzahl verschiedener Preise. Die Ergebnisse für dieses Eingabemodell lassen sich jedoch nicht auf andere Preismodelle übertragen. Wir nutzen daher Regret-Minimierung in Lernalgorithmen, um Ergebnisse zu erzielen, welche eine weitreichendere Gültigkeit haben. Lernalgorithmen treffen keine Annahmen über das Preismodell. Ein Lernalgorithmus erhält eine Menge von Experten (Strategien), welche das gegebene Problem lösen können. Zu jedem Zeitpunkt wählt der Algorithmus einen der Experten aus und kopiert die Aktionen des Experten. In Standardlernalgorithmen entsprechen die Kosten des Algorithmus zu jedem Zeitpunkt denen des gewählten Experten. Für Probleme wie zum Beispiel das Online Buffering entstehen jedoch zusätzliche Kosten, welche dadurch bedingt sind, dass sich der Speicherzustand des Experten von dem des Algorithmus unterscheidet. Dies kann dazu führen, dass der Algorithmus zusätzliche Einheiten kaufen muss um den aktuellen Bedarf zu decken. Da diese Kosten bei der Auswahl der Experten nicht beachtet werden, erreichen diese Algorithmen für Standardlernsituationen zwar niedrige Kosten, schaffen dies aber nicht für Online Buffering Probleme. In dieser Arbeit präsentieren wir Algorithmen, welche bei ihren Entscheidungen die zusätzlichen Kosten berücksichtigen und für Online Buffering niedrige Kosten erreichen können. Im zweiten Teil der Arbeit werden die vorgestellten Algorithmen als Kontrollstrategie in einem Hybridauto simuliert. Ein Hybridauto ist ein Fahrzeug mit zwei Motoren, einem Verbrennungsmotor und einem Elektromotor. Der Elektromotor wird genutzt, um Energie überschüssige Energie in der Batterie zu speichern oder um Energie aus der Batterie zu nutzen, um das Fahrzeug anzutreiben. Die Kontrollstrategie muss entscheiden, wie die zum aktuellen Zeitpunkt benötigte Energie zwischen den beiden Motoren aufgeteilt wird. Die Kosten der Kontrollstrategie entsprechen dem Benzinverbrauch des Fahrzeugs. Wir werden zeigen, dass die Ergebnisse der Threshold-Algorithmen nicht auf die Anwendung als Kontrollstrategie übertragen werden können. Die Ergebnisse für die präsentierten Lernalgorithmen können jedoch auch in unseren Simulationen erreicht werden. Wenn diese Strategien mit der richtigen Expertenmenge ausgestattet sind, ist es sogar möglich den Benzinverbrauch, welcher von Standardkontrollstrategien erreicht wird, noch weiter zu verbessern.

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.

Fulltext:
PDF