Effizient transportieren

Die Fahrzeuge verfügen über einen Präzisions­mechanismus, um automatische Docking-Manöver auszuführen. Neben dem Andocken an Stationen ermöglicht dieser auch das gegenseitige Verbinden mehrerer Karis-Fahrzeuge, um dadurch sogenannte Cluster zu bilden. Diese Cluster können zum einen die Nutzfläche einzelner Fahrzeuge vergrößern, um zum Beispiel den Transport von Paletten zu ermöglichen, zum anderen aber auch, um die Form von Stetigförderern anzunehmen und damit beispielsweise bei Bedarf kurzfristig einen hohen Warendurchsatz zwischen zwei Stationen einzurichten.

Für die autonome Navigation verfügen die Karis-Roboter über zwei Sick-S300-Laserentfernungsmesser. Weil sich diese in zwei gegenüberliegenden Ecken der quadratischen Grundfläche befinden, kann das Fahrzeug sein gesamtes Umfeld abtasten. Das ermöglicht zum einen das Erkennen von Menschen um das Fahrzeug herum. Zum anderen ist diese 360°-Abtastung aber auch eine wesentliche Grundlage zur Positionierung des Fahrzeugs in seiner Umgebung. Jedes Fahrzeug verfügt außerdem über einen Hodometer, eine Vorrichtung, welche die Radumdrehungen misst, und einen Trägheitssensor (Gyroskop), der die Drehrate des Fahrzeugs, also dessen Orientierung, misst.

Von A nach B kommen

Um eine effiziente Navigation zwischen zwei Punkten zu ermöglichen, benötigt jedes Fahrzeug eine Karte der Umgebung und seine genaue Position auf dieser. Das Karis wertet zu jedem Zeitpunkt die Messungen des Laserscanners und des Trägheitssensors sowie die Radumdrehungen aus, um daraus die wahrscheinlichste Position auf der Karte zu ermitteln. Die Auswertung von gemessener und erwarteter Beobachtung erfolgt dabei prinzipiell in zwei Schritten: Zunächst vergleicht jeder Roboter das gemessene Sensorbild des Laserscanners mit der Erwartung, er befände sich exakt an dieser Position auf der Karte. Hier berechnet der Algorithmus die Distanzen, die der Laserscanner messen würde, wäre er an dieser bestimmten Position und mit dieser bestimmten Orientierung auf der Karte ausgerichtet. Dann verschiebt und rotiert der Roboter mithilfe des Algorithmus‘ alle Partikel entsprechend der erfolgten Verschiebung und Verdrehung des Fahrzeugs.

Da bei Sensormessungen typischerweise Fehler auftreten können, führen Sensoren alle Messungen immer mit Bezug auf empirisch ermittelte Sensormodelle durch. Dazu betrachtet es mehrere Positionen, sogenannte Partikel, und wertet oder siebt diese anhand der Übereinstimmung von erwarteter und tatsächlich eingetretener Sensorbeobachtung an dieser Stelle aus. Da das Karis die Positionen zu jedem Partikel anfangs zufällig wählt, weil es seine Position in der Regel zunächst nicht kennt, heißt diese Methode Monte-Carlo-Verfahren – in Anspielung auf das Roulette im dortigen Kasino. Während des Verfahrens ersetzt das Fahrzeug aufgrund der Bewertung aussortierte Partikel wieder durch neue, ebenfalls zufällig gewählte. Die Lokalisierung kann mithilfe einer vorhandenen Karte, zum Beispiel aus CAD-Daten, erfolgen.

Es ist aber auch möglich, eine Karte vom Roboter selbst erlernen zu lassen. Dazu fährt der Roboter durch die Lagerhalle oder das Gebäude und speichert alle Messungen der Sensoren. Verfahren aus dem Bereich der Slam-Algorithmen (Simultaneous Localization And Mapping) können dann die eigentliche Karte erzeugen. In der Regel ist es empfehlenswert, die Karte immer von dem Roboter erlernen zu lassen, da CAD-Modelle häufig von der realen Situation am jeweiligen Tag abweichen.

Trotz Hindernissen zum Ziel gelangen

Um einen kollisionsfeien Pfad zu einem Ziel zu planen, verwendet der Roboter in der Regel einen Suchalgorithmus, der schrittweise auf der Karte nach einer kollisions­freien Verbindung zu dem Zielpunkt sucht. Ein zu diesem Zweck häufig verwendetes Verfahren ist der sogenannte A*-Algorithmus, der in jedem erdenkbaren Fall die optimale Lösung, also den kürzesten Pfad, findet – solange eine existiert. Die zeitgleiche Navigation mehrerer Roboter in einer räumlich beschränkten Umgebung zählt dabei zu den größten Problemen, da die Rechenzeit, die man zum Ermitteln des optimalen und abgestimmten Gemeinschaftsplans aller Fahrzeuge benötigt, rapide anwächst. Eine Lösung besteht darin, auf Qualität zu verzichten, also auch längere Fahrzeiten in Kauf zu nehmen.

Hat jede Einheit die Hürde der Pfadplanung überwunden, so ist auch die Ausführung derselben ein Problem. Vor allem bei nicht exakt berechenbaren Faktoren wie die Ankunftszeiten der Fahrzeuge, und damit die tatsächliche Dauer einer Aktionsausführung, lassen sich nur schwer vorhersagen. Zusätzlich stehen unzählige Sonderfälle an, wie stark variierende Positionsschätzungen einzelner Roboter, oder dass einzelne Roboter nicht in der Lage sind, ihr Ziel zu erreichen. Außerdem muss der Algorithmus Vorkehrungen enthalten, um potenzielle Deadlock-Situationen, also Situationen, in denen sich Fahrzeuge gegenseitig blockieren, zu verhindern.

Wer macht was wann?

Eine weitere wichtige Frage ist, welches Verfahren Aufgaben, wie den Transport von Behältern zwischen verschiedenen Ladestationen, verteilt. Es muss eine bestimmte Menge von Behältern einer bestimmten Anzahl von Fahrzeugen zuteilen. Ein Verfahren zur Aufgabenverteilung richtet sich dabei immer nach bestimmten Kriterien, wie dem Minimieren der Fahrzeit, und ordnet die Fahrzeuge entsprechend den wartenden Behältern zu.

Eine einfache, dazu geeignete Methode ist das Kontrakt-Netz-Protokoll, bei dem einzelne Stationen als Auktionatoren agieren. Fahrzeuge bieten mit ihren individuellen Kosten, die bei Abholung und Transport eines Behälters anfallen würden, um den Transportauftrag. Kosten sind hier die Fahrtdistanzen zwischen den Zielen und den einzelnen Positionen der Fahrzeuge. Die jeweilige Station erteilt dem Fahrzeug mit der kürzesten Fahrtdistanz den Zuschlag.

Ein solches Verfahren kann nur bedingt zu zufriedenstellenden Resultaten führen. Befinden sich zum Beispiel mehrere Sta­tionen in einem Nahbereich und eine andere weit entfernt, kann diese Methode die Fahrzeuge nicht mehr gleichmäßig auf Stationen und damit auf Behälter mit Waren verteilen. Dieser Fall kann relativ häufig eintreten, da der Transport von Behältern von weit entfernten Stationen für die Fahrzeuge stets vergleichsweise teuer erscheint. Bei ungleichmäßig verteilten Transportaufgaben können so Waren für unbestimmte Zeit liegen bleiben, was letztlich zu unvorhersehbar verzögerten Auslieferungen einzelner Waren führt.

Testen und simulieren

Auf der Logimat 2010 in Stuttgart war das Karis-System drei Tage lang ohne Unterbrechung im Einsatz. Die Fahrzeuge sind dabei im Durchschnitt mehr als 3 km pro Tag kollisionsfrei gefahren. Das gesamte System lief dabei ohne nennenswerte Aussetzer. In einem weiteren Probelauf funktionierte Karis mehrere Tage in einer Halle auf dem Gelände der Uni­versität Freiburg. Dabei haben vier Fahrzeuge über mehrere Tage parallel Transport­aufgaben zwischen drei Sta­tionen ausgeführt. Das System hat außerdem verschiedene Simulationsumgebungen durchlaufen. Insgesamt haben die Wissenschaftler bis zu 100 simulierte Roboter gleichzeitig auf Karten von Logistikzentren und Lagerhallen von Firmen des Karis-Konsortiums getestet. Die Resultate haben gezeigt, dass das System auch für größere Umgebungen und Teamgrößen skalierbar ist.

Bis zum Horizont…

Aufgrund der stark eingeschränkten Leistung existierender Verfahren haben die Beteiligten mit dem Karis-Projekt weiterführende Ansätze entwickelt: Dazu gehört das Verfahren Armo (Adaptive Roadmap Optimization), das das effiziente Planen der Pfade mehrerer gleichzeitig agierender Fahrzeuge erlaubt. Das Verfahren ermöglicht auch die Planung für große Gruppen von Fahrzeugen. Noch wichtiger aber ist, dass es ermöglicht, die Streckenführung der Roboter an die jeweilige Situation anzupassen. Das Verfahren berechnet bei eintretenden Veränderungen automatisch eine neue Straßenkarte, die die aktuelle Verteilung von Hindernissen und die Auftragslage bei den Stationen berücksichtigt.

Dies ist ein Beispiel einer automatisch erzeugten Roadmap aus einer vorher erlernten Karte der Umgebung.Universität Freiburg

Dazu verwendet es einen einfachen Trick: Es erzeugt aus der Umgebungskarte eine sogenannte Roadmap, auf der es dann, ähnlich wie im Straßenverkehr, Fahrzeuge über Kreuzungen mithilfe einfacher Vorfahrtsregeln leitet. Eine Anpassung der Straßenkarte ist beispielsweise dann nötig, wenn Paletten oder Behälter, die ungeordnet innerhalb des Geländes stehen, neue Hindernisse bilden. Eine andere Quelle für Änderungen ist die Auftragslage bei den Stationen: Eine Station, die anfänglich ein sehr hohes Aufkommen an Aufträgen hat, kann aufgrund von Produktionsabläufen nach einer gewissen Zeit an Bedeutung verlieren. Stationen lassen sich deshalb innerhalb des Geländes spontan eröffnen, um schnell reagieren zu können, wenn zum Beispiel ein Lastwagen neue Waren anliefert und schnell ein paar Fahrzeuge zu deren Verteilung benötigt. Ein spezieller Optimierungsalgorithmus maximiert hierbei die Güte dieser Anpassung.

Effizienz einzelner Stationen im Vergleich: Dieses Diagramm zeigt die herkömmliche Methode.Universität Freiburg

Während sich Änderungen der Auftragslage direkt messen lassen, benötigt die Erkennung von Änderungen in der Karte ein spezielles Verfahren, das auf dem Ansatz der HMMs (Hidden Markov Models) basiert. Dieses Verfahren betrachtet die Distanz-Messungen der Laserscanner aller Fahrzeuge über einen längeren Zeitraum. Weichen diese Messungen lokal in starkem Maße von der momentanen Karte ab, berechnet es diese neu und löst überdies die Neuberechnung der Roadmap aus. Neu eingefügte Hindernisse berücksichtigt der Algorithmus indem er dann automatisch eine neue Straßenkarte verlegt, die diese umgeht. Ein wichtiger Vorteil dieses Verfahrens ist, dass, solange keine Änderungen auftreten, die Planung einzelner Fahrzeuge wie im echten Straßen­verkehr vollständig dezentral erfolgen kann.

Effizienz einzelner Stationen im Vergleich: Dieses Diagramm zeigt die neue Methode, bei der eine ausgewogene Verteilung der Effizienz eintritt.Universität Freiburg

Das Problem der Aufgabenverteilung beim Betrieb mehrerer Fahrzeuge gehen die beteiligten Experten mithilfe eines speziellen Verfahrens an, das auf de­zentralen Hash-Tabellen (DHTs: Decentralized Hash Tables) basiert. Diese Technik, die auch Peer-to-Peer-Netze im Internet verwenden, erreicht eine ausgewogene Zuweisung von Fahrzeugen, ohne dabei eine zentrale Steuerung zu benötigen. Ähnlich wie bei Peer-to-Peer-Netzen, die Dateien gleichmäßig über mehrere Teilnehmer global verteilen, weisen sie in unserer Anpassung Fahrzeuge gleichmäßig den Stationen zu. Bei diesem Verfahren adaptiert sich die Verteilung der Fahr­zeuge bezüglich der Momentan-Durchsätze, der Warteschlangen aller Stationen sowie an Veränderungen auf der Karte. Wenn beispielsweise die Verbindung zu einer Station blockiert ist und sich dadurch die durchschnittliche Fahrtzeit der beliefernden Fahrzeuge verlängert, ordnet das Verfahren dieser Station automatisch eine höhere Zahl von Fahrzeugen zu.

… und noch viel weiter

Multi-Agenten-Systeme und Multi-Roboter-Systeme bestehen aus mehreren autonomen Komponenten, die miteinander kooperieren oder konkurrieren. Gerade in Produktion und Logistik bietet es sich an, solche Systeme einzusetzen. Sie bedeuten einen Gewinn an Flexibilität und Zuverlässigkeit. Für mehrere Dutzend solcher Fahrzeuge reichen dabei heutige Technologien aus. Allerdings ist noch viel Forschungsaufwand nötig, um die Skalierbarkeit solcher Systeme zu erhöhen. Wenn hunderte oder sogar tausende solcher Roboter-Systeme gleichzeitig im Einsatz sind, ist es erforderlich, auf allen Ebenen – Funkkommunikation, Koordination, Navigation und Aufgabenverteilung – eine gleichmäßige Lastverteilung zu erreichen und das System robust gegen partielle Ausfälle der Infrastruktur zu machen. Die Techniken dafür befinden sich bereits in der Entwicklung.