Internationales Verkehrswesen (72) 2 | 2020 56 Intelligente Park platzsuche mit Machine Learning Ein Konzept für die Verringerung des innerstädtischen Parksuchverkehrs Computersimulation, Geodaten, Geomarketing, Künstliche Intelligenz, Maschinelles Lernen, Parkplatzsuche, Wahrscheinlichkeit Besonders in Innenstadtgebieten ist die Parkplatzsuche sehr zeitaufwendig, und je länger sie dauert, desto schädlicher wird sie für die Umwelt. In Spitzenzeiten beträgt der Parksuchverkehr in den Innenstädten geschätzt bis zu einem Drittel des eigentlichen Verkehrs. Wie lässt sich die Parkplatzsuche also effizienter gestalten? Wissenschaftlerinnen und Wissenschaftler des Fraunhofer-Instituts für Intelligente Analyse- und Informationssysteme IAIS haben zusammen mit Partnern in dem Forschungsprojekt „Geiser“ daran gearbeitet, Geo- und Sensordaten für Anwendungen des Alltags besser nutzbar zu machen. Alexander Kister W ie lässt sich der Parksuchverkehr in den Innenstädten reduzieren? Ideen und Ansätze dazu gibt es schon länger - etwa mit Sensoren, die am Ort messen, ob ein Parkplatz belegt oder frei ist. Autofahrer könnten diese Daten abfragen und gezielt zu einem freien Parkplatz in der Nähe ihres Ziels navigieren. 1 Allerdings wären Aufbau und Instandhaltung eines solchen flächendeckenden Parkplatzsensoren-Netzwerkes mit einem hohen Zeit- und Kostenaufwand verbunden. Wissenschaftler*innen des Fraunhofer-Instituts für Intelligente Analyse- und Informationssysteme IAIS und ihre Partner haben in dem Forschungsprojekt „Geiser“ (siehe Infobox) daran gearbeitet, Geo- und Sensordaten für Anwendungen des Alltags besser nutzbar zu machen. Dabei wurde in Kooperation mit dem Unterneh- Foto: Mabel Amber / pixabay.de TECHNOLOGIE Wissenschaft Internationales Verkehrswesen (72) 2 | 2020 57 Wissenschaft TECHNOLOGIE men TomTom der Prototyp eines intelligenten Parkassistenten entwickelt, der auch ohne Sensoren vorhersagen kann, wo und mit welcher Wahrscheinlichkeit ein freier Parkplatz zu finden sein wird. Im Gegensatz zu anderen Lösungen wird hier keine zusätzliche Hardware benötigt: Der Assistent kann perspektivisch in Navigationsgeräte integriert oder via Smartphone genutzt werden. Dank Verfahren des maschinellen Lernens lernt der Assistent kontinuierlich hinzu und wird, auch wenn anfangs nur wenige Daten vorliegen, mit der Zeit immer zuverlässiger. Dieser Parkplatz ist zu 96 Prozent frei! Ortsansässige Fahrer finden in der Regel schneller einen Parkplatz als ortsfremde Fahrer. Das zeigt, dass die Beobachtung der üblichen Parksituation in einer bestimmten Region hilfreich für die Parkplatzsuche ist. Dieses Erfahrungswissen soll für den smarten Parkassistenten genutzt werden. Ziel ist es, ein Computersystem zu entwickeln, das in der Lage ist, Vorhersagen darüber zu treffen, ob in einem Straßenabschnitt ein Parkplatz frei sein wird oder nicht. Vorhersagen mit Hilfe eines Computers zu treffen, ist die wesentliche Aufgabe des Maschinellen Lernens, weshalb auch der „Geiser“-Prototyp diese Technologie nutzt. 2 Die initiale Schätzung als Anfangspunkt Welche Beobachtungen über die Parkplatzbelegung lassen sich also als Grundlage für das maschinelle Lernsystem verwenden? Auf den ersten Blick erscheinen die Fahrwege der Nutzer von Navigationssystemen als gute Quelle. In der Praxis zeigt sich aber, dass das Navigationssystem häufig vor Erreichen des Parkplatzes ausgeschaltet wird - und die Daten folglich gar nicht zur Verfügung stehen. Wesentlicher Grund ist die wiederholt freundliche, aber nervtötende Aufforderung des Systems, man möge bitte umkehren („Wenn möglich, bitte wenden“). Bisher erkennen die Systeme nämlich nicht, dass der Fahrer auf Parkplatzsuche ist. Der im Forschungsprojekt entwickelte Ansatz kann die Möglichkeiten der Navigationssysteme ergänzen oder erweitern: Auf Basis einer initialen Schätzung wird ein Parkplatz-Assistent erstellt, der seine Vorhersagequalitäten im Laufe der Nutzung stetig verbessert. Die Aufgaben des Parkassistenten sollen sein: 1. Den Nutzer in kürzester Zeit so nah wie möglich an sein Ziel bringen 2. Ständig bessere Schätzungen der Parkwahrscheinlichkeiten lernen Zwischen diesen beiden Zielen besteht jedoch ein grundsätzlicher Konflikt: Um Ziel 2 (ständig dazulernen) zu erreichen, müsste der Assistent den Autofahrer gezielt in solchen Straßen suchen lassen, für die nur wenige Beobachtungen vorliegen - selbst dann, wenn sein Algorithmus sich schon relativ sicher ist, dass in der Nähe des Ziels ein Parkplatz frei ist. Der Assistent würde damit Ziel 1 zuwiderhandeln. Um dieses Problem zu vermeiden, wählt der Algorithmus einen Mittelweg. Zufälle berücksichtigen Für Autofahrer erscheint die Parkplatzsuche häufig wie ein Glückspiel. Selbst in Gegenden mit vielen Parkplätzen kann man Pech haben und keinen freien Platz finden. Diese Zufälligkeit muss bei der Konzeption eines Parkassistenten berücksichtigt werden. Gleichzeitig gibt es aber zu manchen Straßen auch ein spezifisches Vorwissen: Zum Beispiel ist die Wahrscheinlichkeit, an einer Stadtautobahn parken zu können, sehr gering, weil am Straßenrand von Autobahnen in der Regel keine Parkplätze existieren. Die drei Komponenten des Parkassistenten Der Parkassistent kann als aktives lernendes System in Navigationsgeräte oder Smartphones implementiert werden. Er hat im wesentlichen drei interagierende Komponenten: den Speicher, den Aktor und den Lernalgorithmus. Der Speicher Im Speicher befindet sich das Wissen des Systems. Um die Zufälligkeit der Parkplatzbelegung zu berücksichtigen, wird das Wissen durch die Parameter eines probabilistischen Modells repräsentiert. Dieses Modell nimmt an, dass die Wahrscheinlichkeit, in einem gegebenen Straßenabschnitt zu einer gegebenen Tageszeit parken zu können, zwar unbekannt, aber (zumindest für einen längeren Zeitraum) fix ist. Liegen genügend Erkenntnisse - also Beobachtungen von Parkversuchen für einen Straßenabschnitt in einem bestimmten Zeitraum - vor, kann die Parkwahrscheinlichkeit durch die Häufigkeit der Parkerfolge abgeschätzt werden. Doch in der Regel liegen zu wenige Beobachtungen vor. Um auch in einem solchen Fall eine Aussage treffen zu können, bietet sich das Bayesian Framework an (siehe Infobox). So ist es möglich, einer Straße nicht nur einen einzigen Schätzwert für die Parkwahrscheinlichkeit zuzuordnen: Das System kann Wahrscheinlichkeiten, die plausibler erscheinen als andere, auch höher gewichten. 3 HINTERGRUND Bayesian Framework - Berechnung bedingter Wahrscheinlichkeiten Im Bayesian Framework wird das Wissen über unbekannte Größen nicht durch einen einzigen Schätzwert, sondern durch eine Gewichtung aller möglichen Ausprägungen der Größe dargestellt. Diese Gewichtung, die im Rahmen des Frameworks üblicherweise als Dichte bezeichnet wird, wird vom Lernalgorithmus abhängig von den bisher gemachten Beobachtungen berechnet: Je mehr Beobachtungen vorliegen, desto stärker konzentriert sich die Dichte auf einen Wert, und je weniger Punkte vorliegen, desto größer ist die Varianz der zur Dichte gehörenden Verteilung. Der Lernalgorithmus, der dieses leistet, ergibt sich aus dem Satz von Bayes. Die Dichte selbst ist durch zwei Parameter repräsentiert und diese Parameter repräsentieren das Wissen des lernenden Systems. [3] HINTERGRUND Forschungsprojekt „Geiser“ Das Projekt „Geiser“ wurde vom Bundesministerium für Wirtschaft und Energie (BMWi) gefördert und im Jahr 2019 abgeschlossen. In dem Konsortium aus Großunternehmen sowie kleinen und mittleren Unternehmen wurde eine offene, cloudbasierte Plattform zur Akquise, Transformation, Speicherung, Integration, Qualitätssicherung, Verarbeitung und Auslieferung von auf Geo- und Sensordaten basierenden Diensten entwickelt. Die beteiligten Partner waren USU Software AG, Universität Leipzig, YellowMap AG, metaphacts GmbH, Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS und TomTom. www.projekt-geiser.de Internationales Verkehrswesen (72) 2 | 2020 58 TECHNOLOGIE Wissenschaft Das System integriert also immer neue Beobachtungen in seinen Wissensstand. Es muss jedoch am Anfang, wenn noch keine (eigenen) Beobachtungen vorliegen, einen initialen Wissensstand vorweisen. Dieses initiale Wissen wird auch Vorwissen genannt und kann sehr konkret sein, wie im obigen Beispiel der Stadtautobahn, oder sehr vage. Das Vorwissen ist dann „am vagsten“, wenn jede Parkwahrscheinlichkeit von 0 bis 1 mit gleicher Wahrscheinlichkeit in Frage kommt (dies entspricht der Dichte der Uniformenverteilung über [0,1]). Um Vorwissen für den Parkassistenten zu finden, lohnt es sich, sich noch einmal in die Situation eines ortsfremden Fahrers zu versetzen: Der ortsfremde Fahrer kann das Wissen, das er in anderen Städten gesammelt hat, auf die unbekannte Stadt übertragen, so ist etwa die Parkplatzsuche in dicht bebauten Wohngebieten nach Feierabend in der Regel schwer. Um das Vorwissen des Parkplatzassistenten zu definieren, verwenden wir daher die Distanzen zu Points of Interest (POIs), um eine Straße zu charakterisieren. Die POIs werden in einer Ontologie erfasst, und mit Hilfe eines probabilistischen Modells wird eine initiale Dichte über die Parkwahrscheinlichkeiten errechnet. Der Aktor Der Aktor hat die Aufgabe, dem Nutzer auf Basis des aktuellen Wissensstands eine Suchroute vorzuschlagen. Die Definition dieses Aktors beeinflusst entscheidend, inwieweit die obigen zwei Ziele erreicht werden. Der Aktor nutzt das Prinzip des Thomson Sampling, um einen Ausgleich zwischen den obigen zwei Zielen zu erreichen. Das Thomson Sampling ist eine besondere Art, das Wissen, das unser Assistent als Dichten über mögliche Parkwahrscheinlichkeiten modelliert, zu verwenden: Bevor der Aktor eine Aktion ausführt, wird von jeder Dichte über die Parkwahrscheinlichkeiten ein Sample gezogen. Dieses Sample ergibt eine Straßenkarte mit möglichen Parkwahrscheinlichkeiten. Der Aktor verwendet nun die vom Sampler erzeugte Karte, um darauf eine Parkplatzsuchroute zu berechnen. Der Lernalgorithmus Der Lernalgorithmus verwendet die beim Befolgen der vom Aktor vorgeschlagenen Suchroute gemachten Beobachtungen, um die im Speicher befindliche Information zu ergänzen. Um zu verstehen, wie der Ausgleich zwischen den oben genannten Zielen 1 und 2 geschieht, stellen wir uns vor, dass der Aktor den Sampler nicht nur einmal, sondern zweimal anfragt. Liegt im Speicher schon viel Wissen über den Kartenausschnitt vor, werden sich die vom Sampler erzeugten Karten kaum unterscheiden; liegt wenig Wissen vor, ist es sehr wahrscheinlich, dass sich die erzeugten Karten stark unterscheiden. Das bedeutet: Unterscheiden sich die Karten sehr wenig, werden sich die Suchrouten kaum unterscheiden; unterscheiden sie sich stark, ergeben sich sehr unterschiedliche Suchrouten. Im Anwendungsfall wird vom Sampler nur eine einzige Karte erzeugt, und der Aktor empfiehlt dem Fahrer die gemäß dieser Karte optimale Suchroute. Hält der Fahrer an und parkt, werden die während der Suche gemachten Beobachtungen mithilfe eines Lernalgorithmus in das probabilistische Modell des Speichers integriert. Computersimulation mit zwei Versuchsanordnungen In einer Computersimulation wird ein Teil des Berliner Prenzlauer Bergs als Testgebiet definiert. Da es keine Daten über die tatsächlichen Parkwahrscheinlichkeiten gibt, werden diese mit einem geeigneten Verfahren ausgelost. Dazu wird der ungünstigste Fall hinsichtlich des Vorwissens betrachtet, nämlich der, dass es kein konkretes Wissen gibt. Für den Versuch wird angenommen, dass im Testgebiet 50 Parkplatzsuchen durchgeführt werden. Während dieser 50 Versuche wird das Wissen über die Parkwahrscheinlichkeiten immer weiter aktualisiert. Jede Suche wird durch ihren Ausgangspunkt und ihren Zielpunkt bestimmt. Da in der Simulation nur ein Kartenausschnitt betrachtet wurde, befinden sich die Ausgangspunkte auf den Straßen am Rande des Gebiets und die Zielpunkte innerhalb des Gebiets. Dabei werden zwei Versuchsanordnungen betrachtet: 1. Eine Suche wird mehrmals durchgeführt, d. h. ein Fahrer versucht mehrmals, von einem fixen Ausgangspunkt zu einem fixen Ziel zu fahren. 2. Für jede der 50 Suchen werden ein anderer Ausgangspunkt und ein anderes Ziel ausgelost. In den Versuchsanordnungen sind zwei Größen von Interesse: Suchdauer und Wissensstand, wobei die erste Versuchsanordnung verwendet wird, um die Suchdauer zu untersuchen, da bei zufälliger Wahl von Start und Ziel die Suchdauern schon allein aufgrund dieser Parameter schwanken. Die Suchdauer setzt sich zusammen aus der Fahrdauer und dem anschließenden Fußweg. Diese Suchdauer ist selbst bei Kenntnis der tatsächlichen Parkwahrscheinlichkeiten zufällig. Es ist also interessant, wie lange die Suche im Mittel dauert. Um den Lernfortschritt zu untersuchen, werden diese Größen als Funktionen der Versuchsanzahl betrachtet. Bild 1 zeigt, dass mit steigender Versuchsanzahl die mittlere Suchdauer sinkt. Der Vergleich zwischen dem Median und dem Mittel der Suchdauer zeigt, dass an- Bild 1: Mittlere Suchdauer, abhängig von der Anzahl der Parkversuche (wobei Start und Ziel über alle 50 Versuche fix sind) Internationales Verkehrswesen (72) 2 | 2020 59 Wissenschaft TECHNOLOGIE fangs der Mittelwert sehr stark von Ausreißern, d. h. außergewöhnlich langen Suchen, beeinflusst wird. Bei der zweiten Versuchsanordnung wird der Wissenszuwachs betrachtet. Hier wird die Varianz der Verteilungen über die Parkwahrscheinlichkeiten als das Maß für Wissen verwendet. Je kleiner diese Varianz ist, desto sicherer ist sich der Algorithmus. Bild 2 zeigt Statistiken über die Varianz der Parkwahrscheinlichkeiten. Die Gesamtheit, auf die sich diese Statistiken beziehen, sind alle Straßenabschnitte des Testgebiets. Mit zunehmender Versuchszahl sinkt die Varianz, was bedeutet, dass das Wissen wächst. Besonders interessant sind hier die Quantile: Das 50-Prozent- Quantil ist der Varianzwert, für den eine Hälfte der Straßen eine größere Varianz und die andere Hälfte eine kleinere Varianz besitzt. Die niedrigeren Quantile sinken mit der Anzahl der Parkversuche, wobei das 25-Prozent- Quantil schneller sinkt als das 50-Prozent-Quantil. Ausblick Damit KI-Systeme zuverlässig funktionieren, werden viele und vor allem qualitativ hochwertige Daten benötigt. In vielen Situationen liegen aber nicht genug Daten vor. Im „Geiser“-Projekt wurde eine Lösung erarbeitet, die es KI-Systemen ermöglicht, auch mit kleinen Datenmengen anwendungstaugliche Ergebnisse zu produzieren. Dabei steht das maschinelle Lernen im Fokus: So kann der intelligente Parkassistent trotz geringer Datengrundlage seine Prognosen zu wahrscheinlich freien Parkplätzen fortlaufend verbessern. Je länger der Assistent im Einsatz ist, desto zuverlässiger wird er. Dieser Ansatz ist innovativ, weil er in allen Szenarien zum Einsatz kommen kann, in denen es zwar an historischen Daten mangelt, es aber möglich ist, in der Einsatzzeit Daten zu sammeln. ■ 1 „In Spitzenzeiten beträgt der Parksuchverkehr in den Innenstädten bis zu einem Drittel des eigentlichen Verkehrs, also ein Drittel der Autofahrer fahren nur herum, weil sie einen Parkplatz suchen.“ Prof. Dr. Barbara Lenz in: Schmickler, Marion (2019): Jedes dritte Auto auf Parkplatzsuche. Tagesschau 23.03.2019. www.tagesschau.de/ inland/ verkehrswende-interview-101.html (Abruf am 14.04.2020) 2 In der Publikation „Prediction Machines“ [1] wird der Begriff „Vorhersage“ knapp als das Auffüllen von Wissenslücken definiert. Eine Vorhersage beruht also immer auf bestehendem Wissen, das verwendet wird, um noch nicht gemachte Beobachtungen vorherzusagen. Das bereits bestehende Wissen liegt in der Regel schon als Datensatz vor. 3 Matt Taddy, Vice President of Economic Technology and Chief Economist for North America bei Amazon, beschreibt die Fähigkeit, kontinuierlich Daten zu erzeugen und von diesen zu lernen, als eine wesentliche Eigenschaft von KI-Systemen: „Beyond ML and domain structure, the third pillar of AI is data generation. I’m using the term ‘generation’ here, instead of a more passive term like ‘collection’, to highlight that AI systems require an active strategy to keep a steady stream of new and useful information flowing into the composite learning algorithms”. [2] LITERATUR [1] Agrawal, Ajay; Gans, Joshua; Goldfarb, Avi (2018): Prediction machines: the simple economics of artificial intelligence. Harvard Business Press [2] Taddy, Matt (2018): The technological elements of artificial intelligence. No. w24301. National Bureau of Economic Research [3] Mehr zum Satz von Bayes: de.wikipedia.org/ wiki/ Satz_von_Bayes Alexander Kister, Dr. Data Scientist, Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS, Sankt Augustin alexander.kister@iais.fraunhofer.de WEITERBILDUNG ONLINE Datenanalyse und Maschinelles Lernen Als Teil der größten Organisation für anwendungsorientierte Forschung in Europa ist das Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS mit Sitz in Sankt Augustin bei Bonn eines der führenden Wissenschaftsinstitute auf den Gebieten Künstliche Intelligenz, Maschinelles Lernen und Big Data in Deutschland und Europa. Zum Schulungsangebot des Fraunhofer IAIS gehört die Weiterbildung zum „Data Scientist“. Die einbis zweitägigen interaktiven Online-Schulungen mit maximal zwölf Teilnehmenden erlauben es, auf individuelle Bedürfnisse einzugehen. Weitere Informationen unter: www.iais.fraunhofer.de/ online-datascientist Bild 2: Statistiken (bezogen auf das Versuchsgebiet) über die Varianz der Straßen Trialog Publishers Verlagsgesellschaft | Schliffkopfstraße 22 | D-72270 Baiersbronn Tel.: +49 7449 91386.36 | Fax: +49 7449 91386.37 | office@trialog.de | www.trialog-publishers.de Redaktionsleitung: Tel.: +49 7449 91386.44 eberhard.buhl@trialog.de redaktion@internationales-verkehrswesen.de