Die auf arXiv veröffentlichte Arbeit „A 1000× Faster LLM-enhanced Algorithm For Path Planning in Large-scale Grid Maps“ von Forschenden der National University of Defense Technology in China stellt einen neuen Algorithmus vor, der die Effizienz der Pfadplanung auf großen Gitterkarten erheblich steigern soll. Der Ansatz iLLM-A* kombiniert ein Sprachmodell mit einem optimierten A*-Algorithmus und soll die Suchzeit im Vergleich zu bestehenden Methoden um mehr als den Faktor 1000 reduzieren. Davon könnten potenzielle Anwendungsfelder wie autonome Robotik, Logistikplanung und die KI-Steuerung in komplexen Simulationen oder Videospielen profitieren.

Die Pfadplanung in großen, gitterbasierten Umgebungen stellt für traditionelle Wegfindungsalgorithmen wie A* und Dijkstra eine erhebliche rechnerische Herausforderung dar. Mit zunehmender Kartengröße steigen Zeit- und Speicherkomplexität überproportional an, was Echtzeitanwendungen in Bereichen wie Robotik oder der Simulation komplexer Systeme erschwert. Forscher stellen nun mit iLLM-A* einen hybriden Ansatz vor, der diese Beschränkungen adressiert.

Skalierungsgrenzen bestehender Algorithmen

Die Studie analysiert zunächst die Schwächen des bisherigen State-of-the-Art-Ansatzes LLM-A*. Dieser nutzt ein Large Language Model (LLM), um eine Sequenz von Wegpunkten zu generieren, zwischen denen dann der A*-Algorithmus kürzere, lokale Pfade sucht. Obwohl dieser Ansatz den globalen Suchraum reduziert, identifizierten die Forscher drei wesentliche Engpässe, die seine Leistung auf großen Karten (definiert als N ≥ 200, wobei N die Kantenlänge des Gitters ist) limitieren:

• Die Verwendung linearer Listen für die OPEN– und CLOSED-Mengen (im Prinzip die Listen der möglichen und der bereits besuchten Wegpunkte) im A*-Algorithmus führt zu einer hohen Zeitkomplexität bei Such- und Einfügeoperationen.
• Die global geführten Listen wachsen mit der Kartengröße stark an, was zu einem hohen Speicherverbrauch führt.
• LLMs neigen zur „räumlichen Illusion“ und generieren stochastische Wegpunkte, die redundant sein oder von der optimalen Route abweichen können, was den nachfolgenden A*-Suchprozess ineffizient macht.

Der von dem Team vorgestellte Algorithmus iLLM-A* (innovative LLM-enhanced A*) begegnet diesen drei Punkten mit gezielten Optimierungen:

• Die CLOSED-Liste wurde durch eine Hash-basierte Datenstruktur ersetzt. Dies reduziert die Komplexität der Abfrage, ob ein Knoten bereits expandiert wurde, von der Größenordnung O(N) auf durchschnittlich O(1).
• Eine verzögerte Aktualisierungsstrategie für die Heuristikwerte in der OPEN-Liste vermeidet kostspielige Neuberechnungen für den gesamten Listenumfang.
• Die Forscher setzen eine zweistufige Kollisionserkennung ein. Zunächst prüft ein rechenschonender Test mittels Axis-Aligned Bounding Boxes (AABB) auf potenzielle Kollisionen. Nur bei Überschneidung der Bounding Boxes wird eine präzise, aber aufwendigere Kollisionsprüfung durchgeführt.

Inkrementelles Lernen zur Erzeugung von Wegpunkten

Um die Qualität der vom LLM generierten Wegpunkte zu verbessern, haben die Forscher einen dynamischen Lernprozess implementiert: Dazu nutzt das System eine erweiterbare Few-Shot-Beispieldatenbank. Nachdem das LLM für eine Trainingskarte Wegpunkte generiert und der Algorithmus einen Pfad geplant hat, wird dieser Pfad anhand vordefinierter Metriken evaluiert. Diese Kriterien umfassen die Abweichung von der optimalen Pfadlänge sowie den Zeit- und Speicherverbrauch im Vergleich zu einer reinen A*-Lösung. Nur wenn der geplante Pfad die Qualitäts-Schwellenwerte erfüllt, wird das Paar aus Karte und generierten Wegpunkten als valides Beispiel in die Datenbank aufgenommen. Dies ermöglicht dem LLM, seine Strategie zur Wegpunkterzeugung iterativ an diverse Umgebungen anzupassen.

Empirisch fundierte Selektion der Wegpunkte

Eine empirische Untersuchung der Forscher zeigte, dass eine hohe Anzahl von Wegpunkten den Rechenaufwand überproportional erhöht, ohne die Pfadqualität signifikant zu verbessern. Basierend auf diesen Ergebnissen wurde eine einfache, effektive Auswahlregel implementiert: Wenn das LLM mehr als zwei Wegpunkte generiert, verwenden sie für die anschließende A*-Suche ausschließlich die ersten beiden Wegpunkte, die am nächsten zum Startpunkt liegen. Dadurch minimiert sich die Anzahl der auszuführenden A*-Suchläufe und damit der Gesamtaufwand erheblich.

Die Evaluation auf verschiedenen Kartengrößen (N = 50 bis 450) zeigte laut den Forschern eine deutliche Überlegenheit von iLLM-A* gegenüber den Vergleichsmethoden (A*, Opt-A*, LLM-A*). iLLM-A* erzielte in den Untersuchungen bei der Suchzeit des kürzesten Wegs eine durchschnittliche Beschleunigung um den Faktor 1000 im Vergleich zu LLM-A*. In extremen Fällen lag die Beschleunigung sogar bei einem Faktor von knapp 2350 gegenüber LLM-A*. Der Speicherbedarf konnte um bis zu 58,6 Prozent im Vergleich zu LLM-A* reduziert werden. Auf einer Karte mit N=450 benötigte iLLM-A* 3,62 MByte, während der optimierte A*-Algorithmus (Opt-A*) allein 28,67 MByte belegte. Ferner wiesen die von iLLM-A* generierten Pfade eine geringere durchschnittliche Abweichung von der optimalen Länge auf (104,39 Prozent vs. 107,94 Prozent bei LLM-A*). Dabei war die Standardabweichung der Pfadlänge signifikant geringer, was auf eine höhere Stabilität und Vorhersagbarkeit der Ergebnisse hindeute, sagt das Forschungsteam.

Sollte sich diese massive Reduktion von Rechenzeit und Speicherbedarf auf die Wegfindung in komplexen Umgebungen anwenden lassen, eröffnet dies weitreichende Anwendungsmöglichkeiten. Konkrete Szenarien reichen von der dynamischen Navigation autonomer Roboter in der Logistik über die intelligente Steuerung von Charakteren in großen Videospielwelten bis zu schnellen Simulationen in digitalen Zwillingen.

(vza)

Der oberste Gerichtshof der USA hat mit einer einzeiligen Anordnung den Antrag von Google auf eine Aussetzung des Urteils aus dem Rechtsstreit gegen Epic lapidar abgelehnt. Eine Begründung teilte der Supreme Court dabei nicht mit. Damit muss der US-Konzern nach eigener Aussage nun rasch damit beginnen, das Urteil umzusetzen: In dem Antrag bei dem Gericht hatte Google erklärt, dass die Pflicht zu Änderungen im Play Store am 22. Oktober in Kraft treten wird, wenn kein Aufschub gewährt wird. Google will derweil aber nicht aufgeben und hat gegenüber US-Medien versichert, trotz der Enttäuschung über die Entscheidung weiter gerichtlich gegen die Vorgaben vorgehen zu wollen. Der Chef von Epic Games hat die Entscheidung dagegen begrüßt.

Google wehrt sich mit Händen und Füßen

In der Auseinandersetzung geht es um das weitreichende Urteil gegen Google, das ein Geschworenengericht im Dezember 2023 gefällt hat. In allen Punkten hatte das Gericht dabei dem Spielekonzern Epic Games recht gegeben. Das Unternehmen hinter „Fortnite“ und der Unreal Engine hatte Google vor Gericht das Ausnutzen seines Android-Monopols und geschäftsfeindliche Praktiken vorgeworfen. Geklagt hatte der Konzern, nachdem er den Rauswurf von „Fortnite“ aus dem Play Store mit einem kalkulierten Regelbruch provoziert hatte. Im Laufe des Verfahrens argumentierte Epic etwa mit milliardenschweren Absprachen, die Google mit Geräteherstellern wie Samsung geschlossen hat, damit der eigene App-Store auf den Geräten der Hersteller bevorzugt wird.

Googles Android-Geschäftsmodell besteht maßgeblich aus der Einnahme von Provisionen, die Google bei jedem über den Play Store getätigten Kauf einstreicht. Alternative App-Stores bedrohen dieses System. Google behauptet zudem, dass ein offener Play Store weniger sicher wäre. Das hat aber nicht verfangen und deshalb wurde Google dazu verpflichtet, seinen Play Store für alternative Stores zu öffnen. Zudem müssen standardmäßig alle Apps auch in alternativen Stores verfügbar sein, solange die Entwickler das nicht aktiv ausschlagen. Google hat nun fast alle Rechtsmittel dagegen ausgeschöpft, noch plant der Konzern aber eine offizielle Berufung vor dem Supreme Court. In dem jetzt abgelehnten Antrag ging es lediglich um eine Aussetzung des Urteils.

(mho)

Deloitte erstattet einem australischen Bundesministerium einen Teil der für einen Prüfbericht kassierten Gage zurück. Grund ist, dass der Bericht offenbar KI-halluzinierte Erfindungen enthielt. Deloitte gibt nun zu, ein generative Sprachmodell eingesetzt zu haben, das mehrere falsche Fußnoten erzeugt und nicht existente Quellen erfunden hat. An den grundsätzlichen Aussagen des Prüfberichts hält Deloitte hingegen fest.

Unter den erfundenen Quellen sind laut Financial Times nicht existierende akademische Studien, die die KI Forschern der Universitäten Lunds und Sydneys angedichtet hat. Das LLM soll eine von Microsoft bereitgestellte Instanz des LLMs GPT 4o von OpenAI sein, die das australische Arbeitsministerium lizenziert hat und in einer Azure-Instanz betreiben lässt.

Wie viel Geld Deloitte vom ursprünglichen Vertragswert von 439.000 australischen Dollar (rund 247.000 Euro) zurückerstattet, sagen die Beteiligten nicht. Sie hätten sich jedenfalls geeinigt. Der auf der Webseite des Ministeriums veröffentlichte Deloitte-Bericht ist am 26. September durch eine bereinigte Version ersetzt worden.

Automatisierte Sozialhilfe-Kürzung kaputt

Diese fällt ein schlechtes Urteil über das von Deloitte geprüfte IT-System namens Targeted Compliance Framework. Seit 2018 bestraft es automatisiert Empfänger von Sozialleistungen, wenn sie verdächtigt werden, bestimmte Auflagen nicht erfüllt zu haben, durch vorübergehenden Entzug der Leistungen. Allerdings hat das System zugrundeliegendes Recht sowie Vorgaben des Ministeriums seit jeher falsch umgesetzt. Zudem werden die Sozialleistungen oft zu lange gestoppt. Umgekehrt ist nicht gesichert, dass eigentlich gestoppte Leistungen nicht vielleicht doch ausgezahlt werden.

Beim Versuch, Fehler zu beheben, wurde ein weiterer Fehler eingebaut. In den geprüften fünf Jahren haben die automatischen Entscheidungen mindestens 1371 arme Australier zu Unrecht bestraft. Allerdings mangelt es auch an Nachverfolgbarkeit, Validierung, Risikomanagement und Aufsicht. Selbst Verfahren vor jenen Gremien, an die sich betroffene Bürger wenden können, sind laut Deloitte nicht transparent und nachvollziehbar.

Demnach gibt es keine Dokumentation der Programmlogik, keine verlässliche Versionierung und keine Standards oder Maßstäbe zur Feststellung der (Fehl)Leistung. Das geprüfte IT-System für automatisierte Entscheidungen über Sozialleistungen ist durchgefallen. Daran ändern auch die von GPT herbeiphantasierten Quellen nichts.

(ds)