DFKI Forschungsbereich Algorithmic Business and Production veröffentlicht anspruchsvolles Daten-Benchmark-Set für CP-SAT-Solver und Reinforcement Learning

Kabelbäume werden in einer Vielzahl von industriellen Produkten eingesetzt. Beispielsweise werden Kabelbäume in Autos benötigt, um viele bisher mechanische Funktionen wie das Bewegen von Sitzen oder das Öffnen von Fenstern zu automatisieren und neue Funktionen wie sprachgesteuerte Navigation oder ein Onboard-Entertainment-System hinzuzufügen. Die Herstellung von Kabelbäumen beruht in der Regel auf billiger Handarbeit in Niedriglohnländern, wo Menschen Kabel nach einem Schaltplan in Kabelbäume stecken. Es gibt nur wenige automatisierte Fertigungslösungen, die auf komplexen Robotermaschinen beruhen, wie z. B. die Zeta-Maschine der Komax AG, Schweiz.

Diese Maschinen führen eine Abfolge von Verkabelungsvorgängen aus, die hochqualifizierte Techniker durch Analyse des Verkabelungsplans entwickeln. Mit der anhaltenden Tendenz zur kundenspezifischen und ressourceneffizienten Just-in-Time-Fertigung müssen kleinere Chargengrößen von Kabelbäumen gefertigt werden, was einen häufigen Wechsel der Verkabelungspläne erfordert, für die Verkabelungssequenzen sofort abgeleitet werden sollten. Die Skalierung des menschlichen Fachwissens auf solche häufigen Änderungen ist schlichtweg unmöglich, was das wachsende Interesse an der intelligenten automatisierten Fertigung von Kabelbäumen erklärt. Dieses Interesse wird auch durch die weitere Miniaturisierung der Kabelbäume genährt, die deren manuelle Fertigung unmöglich machen wird.

In Zusammenarbeit mit der Hochschule Luzern und der Komax AG, Schweiz, haben Forscher des DFKI eine automatisierte Lösung für das Problem der optimalen Bestückungsreihenfolge für ein gegebenes und festes Layout gefunden, das Cable Tree Wiring Problem CTW genannt. Sie haben ein anspruchsvolles Benchmark-Set von 205 realen und 73 künstlichen Instanzen zusammengestellt. Mehrere moderne CP-, OMT- und MIP-Solver wurden mit diesem Benchmark-Set verglichen, und ein Artikel, der die Problemformalisierung und Benchmark-Ergebnisse enthält, ist im Constraints Journal Cable tree wiring - benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints | SpringerLink erschienen. Beim Benchmarking auf diesem Benchmark-Set haben die CP-Solver besser abgeschnitten als die anderen getesteten Solver-Typen. Insbesondere der IBM Cplex CP und der Google OR-Tools CP-SAT Solver zeigten eine beeindruckende Performance, wobei Cplex der einzige getestete Solver war, der für jede Instanz in des Benchmark-Sets Lösungen fand, und OR-Tools mehr optimale Lösungen fand als alle anderen getesteten Solver.

Algorithmic Business and Production hat außerdem das CTW-Benchmark-Set zur MiniZinc Challenge 2020 beigesteuert, einem jährlichen Wettbewerb für Constraint Programming Solver. Das komplette Benchmark-Set ist online verfügbar unter https://github.com/kw90/ctw_translation_toolchain. Der Benchmark-Satz könnte auch für andere Bereiche der KI interessant sein, da Standard Maschinelle Lernverfahren (ML) und Reinforcement Learning Verfahren (RL) mit den vielen Dead-End States zu kämpfen haben: Zustände, von denen aus der Endzustand (alle Kabel wurden erfolgreich eingesteckt) nicht mehr erreicht werden kann.