Self-Organizing Transport Networks : Decentralized Optimization based on Genetic Programming

Abstract

The goal of this thesis is transport network optimization. Transport networks are defined as network topologies in which entities are processed by nodes and successively forwarded to the next node on a link. Capacity restrictions on both nodes and links may apply. Examples include urban traffic (vehicles/signalized intersections), IP networks (packets/routers), and automated production systems (items/workstations). The control and optimization of such networks, e.g. minimizing entity waiting times, particularly requires determining which of potentially multiple entities waiting at a node should be processed next. Such decisions or general rules to base such decisions on can be imposed and altered if need be by a central authority based on global knowledge of the network state. In such centralized solutions, entity processing as conducted by the nodes typically is subject to constraints such as fixed signal plans, which are periodically applied in urban traffic; without implementing such constraints, dynamically determining node behaviour would be computationally infeasible. In contrast, a self-organizing transport network as proposed in this thesis relies on decision rules that require local data like traffic densities and current queue lengths as their only input. Genetic programming is used to evolve such rules, which – once deployed – can be autonomously applied by the nodes to dynamically prioritize waiting entities without contacting a central server. Such a decentralized network control is scalable and robust. Furthermore, empirical results indicate that the performance is similar to or even better than centrally controlled systems: among multiple nodes, the synchronization of entity processing is achieved implicitly. The nodes may be unable to base entity prioritization on global traffic data; this, however, is compensated for by the absence of processing constraints such as fixed signal plans.

Das Ziel dieser Arbeit ist die Optimierung so genannter Transport-Netzwerke, also von Netzwerk-Topologien, in denen Knoten Entitäten „bearbeiten“ und anschließend zum nächsten Knoten weiterleiten, wobei sowohl für das „Bearbeiten“ der Entitäten an den Knoten als auch für das Durchqueren der Kanten Kapazitätsbeschränkungen gelten können. Beispiele für solche Netzwerke sind Stadtverkehr (Autos, ampelgesteuerte Kreuzungen), IP-Netzwerke (IP-Pakete, Router) und automatische Produktionssysteme (Werkstücke, Maschinen). Als Teil von Steuerung und ggf. Optimierung solcher Netzwerke, also z.B. der Minimierung der Wartezeiten der Entitäten, muss insbesondere definiert werden, welche von potenziell mehreren zu einem Zeitpunkt an einem Knoten wartenden Entitäten als nächste „bearbeitet“ und weitergeleitet werden sollen. Diese Entscheidung kann von einem zentralen Server bzw. auf Basis von allgemeinen Regeln getroffen werden, die von einem zentralen Server festgesetzt und bei Bedarf geändert werden; hierfür muss der Server den Zustand des Netzwerkes (z.B. mittlere Flüsse, Verteilung der Entitäten) kennen. Bei Anwendung einer Zentralsteuerung erfolgt die Bearbeitung der Entitäten durch die Knoten typischerweise nicht beliebig flexibel: Für das Handeln der Knoten gelten Einschränkungen, z.B. in Form von sich zyklisch wiederholenden festen Ampelphasen im Stadtverkehr. Dies ist ein notwendiges Zugeständnis, um den Rechenaufwand der zentralen Instanz zu beschränken – andernfalls wäre eine dynamische, zentrale Steuerung nicht möglich. Im Gegensatz dazu erfolgt die Priorisierung der „Bearbeitung“ der Entitäten in den Knoten eines in dieser Arbeit vorgeschlagenen „selbstorganisierenden Transport-Netzwerks“ vollständig autonom und dezentral, also ohne Kommunikation mit einer zentralen Instanz. Im Rahmen seiner Programmlogik zur Priorisierung der Entitäten kann der Knoten somit ausschließlich auf lokal verfügbare Daten zurückgreifen, z.B. auf die Längen seiner Warteschlangen. Eine solche Netzwerksteuerung ist skalierbar und robust. Hinsichtlich der Wartezeiten der Entitäten lassen sich vergleichbare oder sogar bessere Ergebnisse als bei typischen zentralen Steuerungsansätzen erzielen: Die Synchronisation der Knoten erfolgt implizit und das Fehlen globaler Netzwerkzustandsdaten wird durch die zusätzliche Flexibilität der Knoten, die nicht z.B. an feste Schaltpläne gebunden sind, kompensiert.