Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Diplomarbeit

Entwicklung regelbasierter Bewegungsmodelle für Zellularautomaten mit JBoss-Drools

Christian Brunner

Motivation

BeeJamA (Bee Inspired Traffic Jam Avoidance) ist ein dezentraler Algorithmus zur Stauvermeidung in (Straßen-) Verkehrsszenarien. Im Laufe der letzten drei Jahre ist mit studentischer Beteiligung (Projektgruppen, abgeschlossene Diplomarbeiten) ein verteilter Verkehrssimulator zur Analyse verteilter Routingalgorithmen in komplexen Verkehrsszenarien (Ruhrgebiet) entwickelt worden. Der Simulation liegt ein Verkehrsbewegungsmodell zugrunde, welches auf einem diskreten Zellularautomaten basiert, dem sogenannten Nagel-Schreckenberg Modell. Individuelle Fahrzeugbewegungen werden uber elementare Regeln definiert, die sequentiell abgearbeitet werden (Beschleunigen, Abbremsen, Sicherheitsabstand einhalten, "Rechts-vor-Links" Regel, auf Bremslichter reagieren etc.). Für die Nachbildung von realistischem Fahrverhalten ist eine große Zahl von Regeln notwendig. Dennoch stellt das diskrete Nagel-Schreckenberg Modell aufgrund seiner Einfachheit derzeit die einzige Möglichkeit dar, große Verkehrssysteme in Echtzeit und realistisch zu modellieren. Beispiele hierfür sind das OLSIM-Verkehrsprognosesystem für den Autobahnverkehr in NRW [6] und abgeschlossene Simulationen des vollständigen Schweizer Straßenverkehrs in Echtzeit [17, 7].

Aufgabenstellung

Im Rahmen dieser Diplomarbeit sollen die Regeln des, in der Simulationsumgebung verwendeten, Nagel-Schreckenberg Bewegungsmodells für den (Distributed-) Traffic Simulator auf eine Regelmaschine abgebildet werden. Durch die Verwendung eines komfortabel zu analysierenden (Bewegungs-) Regelsystems ließen sich unterschiedliche Erweiterungen des Bewegungsmodells implementieren und direkt miteinander vergleichen. Der Simulator ließe sich so ebenfalls für andere Verkehrssysteme (z.B. Schienenverkehr, Fußgängerverkehr, etc.) einsetzen, für die ebenfalls Zellularautomatenmodelle existieren.

Alle bis jetzt entwickelten Regelsysteme sind nicht konfliktfrei. Das Bedeutet, dass nicht in allen Situationen gewährleistet werden kann, dass ein in der Realität zu beobachtendes Verhalten auch so in der Simulation angenommen wird. Dieses kann gar zu Fehlern im Simulator führen, wenn z.B. eine Zelle durch bestimmte Regelkonstellationen mit zwei Fahrzeuge besetzt wird. Das Aufdecken solch einer Regelkonstellation zusammen mit den genutzten Regeln hilft dem Entwickler, derartige Fehler zu erkennen. Das Programm kann zusätzlich Empfehlungen geben, welche Regel problematisch in diesem Sinne sein könnte und ggf. Lösungsvorschläge unterbreiten.

Literatur

[1] Apache license, version 2.0. http://www.apache.org/licenses/LICENSE-2.0.html.

[2] Drools-analytics module. http://wiki.jboss.org/wiki/RuleAnalyticsModule.

[3] Drools-solver module. http://users.telenet.be/geoffrey/tmp/solver/manual/html single/#d4e12.

[4] Jboss rules user guide. http://downloads.jboss.com/drools/docs/4.0.7.19894.GA/html/index.html.

[5] Jboss rules user guide: rules chapter. http://downloads.jboss.com/drools/docs/4.0.7.19894.GA/html/

[6] Olsim: A new generation of traffic information systems. http://www.billingpreis.mpg.de/hbp03/OLSIM.pdf.

[7] Verkehrsdynamik und urbane Systeme. http://www2.tu-berlin.de/fb10/ISS/FG4/archive/sim-archive/publications/phyblae/printed.pdf.

[8] XSpirit. http://www.xspirit.de/.

[9] R. Barlovic, L. Santen, A. Schadschneider, and M. Schreckenberg. Metastable states in cellular automata for traffic flow, 1998.

[10] Zeynep Bay, Sven Becker, Sven Böttcher, Christian Brunner, Armin Büscher, Thomas Fürst, Anca Manuela Lazarescu, Elisei Rotaru, Sebastian Senge, Bastian Steinbach, Funda Yilmaz, and Thomas Zimmermann. Endbericht der Projektgruppe - Stauvermeidung durch online Verkehrsplanung STOP. Universität Dortmund, 2007.

[11] Charles L. Forgy. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence, 19(1):17–37, 1982.

[12] Hubert Klüpfel. A Cellular Automaton Model for Crowd Movement and Egress Simulation. PhD thesis, University Duisburg–Essen, 2003. http://deposit.ddb.de/cgi-bin/dokserv?idn=96883180x.

[13] Anca Manuela Lazarescu. Entwicklung einer alternativen Darstellung der Netzebenefür das verteilte Verkehrsrouting in BeeJamA. Master’s thesis, Technische Universität Dortmund, 2009.

[14] J.F. Lemmer. Generalized Bayesian updating of incompletely specified distributions. Large Scale Syst.-Theory Appl., 1:51–68, 1983.

[15] KePing Li, ZiYou Gao, and Bin Ning. Cellular automaton model for railway traffic. J. Comput. Phys., 209(1):179–192, 2005.

[16] Francesco M. Malvestuto. Decomposing complex contingency tables to reduce storage requirements. In Roger E. Cubitt, Brian Cooper, and Gultekin Ozsoyoglu, editors, Proceedings of the Third International Workshop on Statistical and Scientific Database Management, July 22-24, 1986, Grand Duchy of Luxembourg, Luxembourg, pages 66–71. EUROSTAT, 1986.

[17] K. Nagel N. Cetin. A large-scale agent-based traffic microsimulation based on queue model. http://www.strc.ch, 2003.

[18] Alun D Preece. Validation of knowledge-based systems: The state-of-the-art in north america, the journal for the integrated. Study of Artificial Intelligence Cognitive Science and Applied Epistomology, 11, 1994.

[19] W. Rödder and G. Kern-Isberner. Lia Sombi und entropie-optimale Informationsverarbeitung mit der Expertensystem-Shell SPIRIT. OR Spektrum, 19(3):41–46, 1997.

[20] Sebastian Senge. Simulative Evaluation von Straßenverkehrsroutingalgorithmen. Master’s thesis, Technische Universit ̈t Dortmund, 2008.

[21] Peter Tondl. Dezentrale Verteilung von Verkehrsinformationen durch Fahrzeug-Fahrzeug-Kommunikation. Shaker Verlag Aachen, 2006.

[22] Horst F. Wedde, Sebastian Lehnhoff, Bernhard van Bonn, Z. Bay, S. Becker, S. Boettcher, C. Brunner, A. Buescher, T. Fuerst, A. M. Lazarescu, E. Rotaru, S. Senge, B. Steinbach, F. Yilmaz, and T. Zimmermann. Highly Dynamic and Adaptive Traffic Congestion Avoidance in Real-Time Inspired by Honey Bee Behavior. PEARL 2007 - Informatik Aktuell - Mobilitaet und Echtzeit, Springer, Boppard, Germany, 2007.

[23] Horst F. Wedde, Sebastian Lehnhoff, Bernhard van Bonn, Z. Bay, S. Becker, S. Boettcher, C. Brunner, A. Buescher, T. Fuerst, A. M. Lazarescu, E. Rotaru, S. Senge, B. Steinbach, F. Yilmaz, and T. Zimmermann. Highly Dynamic and Scalable VANET Routing for Avoiding Traffic Congestions. VANET 2007 - Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks, ACM Press, Montreal, Canada, 2007.

[24] Horst F. Wedde, Sebastian Lehnhoff, Bernhard van Bonn, Z. Bay, S. Becker, S. Boettcher, C. Brunner, A. Buescher, T. Fuerst, A. M. Lazarescu, E. Rotaru, S. Senge, B. Steinbach, F. Yilmaz, and T. Zimmermann. A Novel Class of Multi-Agent Algorithms for Highly Dynamic Transport Planning Inspired by Honey Bee Behavior. ETFA07 - Proceedings of the 12th conference on emerging technologies and factory automation, IEEE Press, Patras, 2007.

[25] Mario Wündsch. Entwicklung einer verteilten Simulationsumgebung zur Analyse dezentraler Routingalgorithmen in dynamischen Verkehrsszenarien. Master’s thesis, Technische Universität Dortmund, 2007.

Zur Publikation...
Weitere Publikationen zu BeeJamA...