• Die Behandlung von Unsicherheit als Schlüssel zum Erfolg

    Verwandte im Geiste: Deep Learning und Qualicision

Bei komplexen Anwendungen in der Produktionssteuerung der Automobilindustrie kommt Künstliche Intelligenz in Form der Qualicision-Technologie weltweit an über 120 Produktionslinien zur Berechnung von Produktionsreihenfolgen zum Tragen.

Wegen der enormen kombinatorischen Komplexität der dort zu lösenden Fragestellungen gibt es bei diesen Lösungen die unerlässliche Notwendigkeit, die prozessbedingte kombinatorische Unsicherheit zu beherrschen.

Hierbei ist der Bezug zu Deep Learning stark. Genau wie bei Qualicision besteht bei Deep Learning ebenfalls der Bedarf nach gesteuertem Umgang mit kombinatorischer Komplexität und demzufolge auch nach Behandlung der kombinatorischen Unsicherheit.

Methoden der Künstlichen Intelligenz (KI) sind ein fester Bestandteil von PSI-Produkten:

  • Neuronale Netze werden im Bereich der Lastprognose in Energieübertragungsnetzen eingesetzt.

  • Monte-Carlo-Methoden finden beim Pipeline-Management im Umfeld Gas und Öl Anwendung,

  • Lösungen für die Metallindustrie verwenden Optimierungsheuristiken wie Simulated Annealing.

  • In der Prozess­industrie stehen in den Bereichen Chemie und Pharma kombinatorische Such­verfahren im Fokus.

  • Erweiterte Fuzzy-Logik wird bei komplexen Sequenzierungs­aufgaben sowie Regelungs­aufgaben und in der industriellen Bildverarbeitung eingesetzt.

Deep Learning löst kombinatorisch hochkomplexes Problem

Wie beide Technologien zusammen hängen, kann man anhand der nachfolgenden Gegenüberstellung erkennen. Als Beispiele sollen keine Geringeren als die beiden viel beachteten Lösungen AlphaGO und AlphaGO Zero dienen.

Beide Methoden haben das kombinatorisch hochkomplexe Problem der algorithmischen Beherrschung des asiatischen Spiels Go auf beeindruckende Weise gelöst. Offensichtlich schließt die Komplexität des Spiels Go mit einer kombinatorischen Größenordnung von zwei zur Potenz eintausendzweihundert eine vollständige Suche aus. Zum Vergleich: Das bereits früher gelöste Problem des maschinellen Schachspiels hat eine Komplexität von zwei hoch vierhundert.

Wie gelingt AlphaGO dennoch die Lösung? Grob gesprochen wird Go als eine Sequenz von Zügen im Sinne eines Markov-Entscheidungsprozesses verstanden und modelliert.

Dabei wurde die in den letzten Jahren enorm gestiegene Geschwindigkeit von Rechensystemen in Verbindung mit einer sehr intelligenten Verknüpfung von einem Monte-Carlo-Tree-Search (MCTS) mit zwei Deep Neural Networks zu einer Architektur zusammengeführt, wobei sich die Trainingsdauer über mehrere Zeitwochen erstreckte und durch massives Parallelrechnen unterstützt wurde.

Am Ende lief beispielsweise AlphaGO mit vierzig sogenannten Search Threads auf 1202 CPUs und 176 GPUs in der Parallelarchitekturausprägung.

Gelernte Wahrscheinlichkeitsverteilung

Dabei wurde algorithmisch das MCTS-Verfahren in der Breitensuche, also bei der Auswahl des nächsten in Frage kommenden Zuges, durch das sogenannte Policy Neural Network begrenzt. Das Policy Network gibt eine gelernte Wahrscheinlichkeitsverteilung bei der Suche nach bestmöglichen Zügen, ausgehend von einer gegebenen Stellung, aus.

In der Tiefensuche kommt zur Begrenzung des Suchraums das sogenannte Value Network zum Einsatz, das Abschätzungen speichert, um die Gangbarkeit eines Knoten bestmöglich abzuschätzen, ohne die darunterliegende Subtiefe explizit durchlaufen zu müssen.

In einer Initialisierungsphase wurde das Policy Network von AlphaGO mit ca. dreißig Millionen von Menschen gespielten Positionen des im Internet verfügbaren KGS Go-Servers trainiert.

Das Value Network hat Bewertungen von Zustandsknoten gelernt, indem das Programm immer wieder gegen sich selbst gespielt hat und auf diese Weise stärker Gewinn versprechende Knoten von weniger Gewinn versprechenden Knoten unterscheiden konnte und diese Unterscheidung durch Spielen weiterer Millionen von Partien gegen sich selbst verbesserte.

Insgesamt ist auf diese Weise eine sogenannte Reinforcement Learning Architektur entstanden mit MCTS als Suchverfahren und zwei Deep Neural Networks als Zugwahlnetzwerk (Policy Network) und dem Suchtiefebegrenzungsnetzwerk (Value Network). Dieses faszinierende Verfahren konvergiert und funktioniert hervorragend.

In der späteren Version AlphaGO Zero wurde dann nur noch mit einem einzigen für beide Zwecke verschalteten Neuronalen Netz gegen sich selbst gespielt, so dass das Verfahren die von Menschen gespielten Partien als Input nicht mehr benötigte.

Allerdings machen sich AlphaGO und AlphaGO Zero die Tatsache zu Nutze, dass die Spielregeln von Go klar definiert sind und der Satz der Regeln per Definition fest ist.

Auszug aus dem japanischen Regelwerk zum Go-Spiel

Bei dem Brettspiel Go geht es darum, durch Umzingeln mit eigenen Steinen (weiß oder schwarz) auf einem Spielbrett mehr Gebiete in Besitz zu nehmen als der Gegner. Das Spielbrett besteht aus einem Gitter von 19 horizontalen und 19 vertikalen Linien mit 361 Kreuzungen. Über eine Linie benachbarte leere Punkte nennt man Freiheiten (grüne Vierecke).

In den oberen Abbildungen hat der weiße Stein 4 Freiheiten. Die schwarze Kette hat 6 Freiheiten. Keine Gruppe von Steinen ohne eine Freiheit (horizontal oder vertikal benachbarter leerer Punkt) kann auf der Tafel existieren. Alle gegnerischen Steine ohne Freiheit (Gefangene) werden entfernt.

In der unteren Abbildung kann Weiß am Zug durch Setzen des Steines auf die grün markierte Freiheit die schwarze 2-er Kette schlagen.
Weitere Spielregeln und -strategien (Japanische Regeln von 1989)

Die sogenannte Spielbaumkomplexität kann man in etwa mit 21.200 abschätzen.

Ziehen und Freiheiten

Schlagen

Damit ist der Suchraum der Spielpositionen enorm, aber endlich (die Japanese Rules of Go bestehen aus vierzehn Artikeln und etwa zwanzig Vorschriften mit zugehörigen Auslegungskommentaren (siehe "Auszug aus dem japanischen Regelwerk zum Go-Spiel").

Insbesondere ist auch die Anzahl der Steinarten mit zwei überschaubar: Es gibt nur weiße und schwarze Steine. Durch diese Umstände ist die entstehende Kombinatorik, wegen ihrer durch Aufzählung de facto nicht behandelbaren Größe, das unsicherheitsgebende Element des Spiels.

Gutartig an dieser Art der Unsicherheit ist, dass am Ende das Gesetz der Großen Zahlen als geltend angenommen werden kann und sich so in Verbindung mit großer, beeindruckender Rechenleistung die Mittel der Wahrscheinlichkeitsrechnung als Methode zur Behandlung von Unsicherheit nutzen lassen.

Sequenzierung in der Produktion

Vergleichen wir nun Go mit dem Problem der Sequenzierung von Aufträgen in einer Montagelinie. Nicht selten werden in einer Automobilfabrik an einem Tag Fahrzeuge in der Größenordnung von zweitausend aus einer astronomisch großen Auftragsvariantenvielfalt produziert, die so zu sequenzieren sind, dass die technischen Restriktionen der Montagelinien erfüllt werden.

Im Vergleich zu Go sind das in diesem Kontext die Spielregeln, (siehe "Größenordnungen bei der Sequenzierung von Montageaufträgen in Automobilfabriken"). Beispiele hiervon sind Regeln der Art, dass auf zwei Aufträge mit einer Rückfahrkamera mindestens zwei Aufträge folgen müssen, die keine Rückfahrkamera beinhalten. Oder etwa, dass wenn ein weißes Auto in die Sequenz gesetzt wird, mindestens fünf weitere weiße folgen müssen. Haben etliche weiße Autos Rückfahrkameras, so ergibt sich für die zuvor genannte Abstandsregel ein Knobelproblem ähnlich dem in einem Go-Spiel.

Der Unterschied liegt allerdings darin, dass in einer Automobilmontage sehr viele solcher Regeln zu beachten sind, in den meisten Fällen sechzig bis siebzig, manchmal sogar über hundert zuzüglich Auslegungstoleranzen. Zudem erhöhen die Menge der Aufträge und ihre Zusammensetzung (Anzahl Rückfahrkameras, Ledersitze Ja/Nein, unterschiedliche Farben etc.) die Komplexität des Knobelns bei der Sequenzierung dramatisch.

Übertragen auf den Vergleich mit dem Go-Spiel ist die Art der Steine nicht nur nicht wie bei Go auf Zwei nicht festgelegt, sondern die Anzahl der Steinarten ist offen. Sie kann von Tag zu Tag anders sein, weil die Aufträge in ihrer Zusammensetzung von Tag zu Tag variieren können, womit es täglich unterschiedlich viele Auftragsarten gibt.

Größenordnungen bei der Sequenzierung von Montageaufträgen in Automobilfabriken

  • 20.000 Basisvarianten in der Modellpalette
  • 10.000 Teile und Komponenten pro Fahrzeug
  • 200 Sonderausstattungen bestellbar
  • Die Anzahl der theoretisch möglichen Varianten bei allen deutschen Automobil-Herstellern ist 283, also ca. 10.000.000.000.000.000.000.000.000
  • Bei einer Sequenzlänge von 2.000 Positionen ergibt sich eine kaum vorstellbare Anzahl von ca. 220.000 möglichen Sequenzen. Zum Vergleich: Die Anzahl der Atome im Weltall liegt bei etwa 2240 und die Kombinatorik bei Go bei 21.200.

Qualicision Zielkonfliktanalyse

Daher wird in den Qualicision-Sequenzierungslösungen der PSI FLS nicht mit Wahrscheinlichkeitsverteilungen als Methode zur Behandlung von Unsicherheit gearbeitet, sondern mit den Mitteln der sogenannten Qualicision-Zielkonfliktanalyse.

Diese wird genutzt, um in dem Prozess der Berechnung der Sequenz, welcher theoretisch auch als ein Markov-Prozess angesehen werden könnte, den Suchraum sowohl in der Breite als auch in der Tiefe hinsichtlich positiver und negativer Relevanz abzuschätzen.

Die zu Grunde liegende Methodik der Abschätzung beruht hier auf Fuzzy-Logik und den sogenannten Fuzzy-Zielfunktionen (Wirkkurven). Dieser Lösungsweg funktioniert nämlich auch dann, wenn die Spielregeln und die Steinarten von Spiel zu Spiel wechseln.

Wie bereits angeführt ist die Art der Aufträge beim Sequenzieren von Tag zu Tag unterschiedlich. Daher kann auch das Gelten des Gesetzes der Großen Zahlen beim täglichen Sequenzieren zum Lernen nicht genutzt werden. Das gestern Gelernte kann heute schon ungültig sein oder zumindest abweichend.

Kombinatorische Komplexität der Sequenzierung

Betrachtet man die kombinatorische Komplexität der Sequenzierung, so lässt sich diese bei einer Sequenz von zweitausend Auftragspositionen in etwa mit zwei hoch zwanzigtausend abschätzen.

Autonom gesteuerte AGV-Transporte mit einer Qualicision-Optimierung für die modulare Fertigung bei Industrie 4.0 Projekten mit PSI Schwarmfertigung (aus dem BMWi Projekt SMART FACE).

Im Vergleich dazu wie angegeben bei Go mit zwei hoch eintausendzweihundert und Schach zwei hoch vierhundert.

Die kombinatorische Komplexität bei der Sequenzierung in einer Automobilfabrik ist damit im Exponenten um den Faktor Zehn größer als die von Go, also im Ergebnis zwei zur Potenz achtzehntausend astronomisch viel größer – die berühmte Anzahl der Atome im Weltall, zwei hoch zweihundertvierzig erscheint im Vergleich sehr klein.

Auch wenn die in der Sequenzierung de facto zulässigen „Sequenzierungszüge“ durch die Restriktionen der Montagelinie die Kombinatorik reduzieren, ist bei der Sequenzierung die zu behandelnde Unsicherheit (Uncertainty) nicht wie bei Go mit Wahrscheinlichkeiten und Monte-Carlo-Methoden sondern mit Fuzziness behandelt.

Gleichwohl ist die Intelligenz beider Verfahren letztendlich auf die intelligente Behandlung der Unsicherheit zur Begrenzung des Suchraumes zurückzuführen.

So gesehen sind die bei AlphaGO eingesetzten Methoden und Qualicision Verwandte im Geiste, da beide akzeptieren, dass die explizite Behandlung von Unsicherheit der Schlüssel zum Erfolg ist. Arbeiten, wie beide Methoden in Zukunft zu kombinieren sind, laufen bereits.

Es wird eine spannende Zukunft.

Sprechen Sie uns an!

PSI FLS
Fuzzy Logik & Neuro Systeme GmbH
Dr. Rudolf Felix
Geschäftsführer

www.qualicision.de

Fotos (von oben): Sergey Tarasov/Shutterstock.com | Saran Poroong/Shutterstock.com | Suphaksorn Thongwongboot/Shutterstock.com (Montage PSI), Klug, F. Forschungsprojekt SMART FACE