Make-Projekt: Pfadplanung für Roboter am Beispiel eines Lego-EV3

Inhaltsverzeichnis

Im Jahr 2004 landeten die zwei NASA-Marsrover Spirit und Opportunity auf dem Mars. Die Signalübertragung zum Mars dauert bis zu 24 Minuten – in eine Richtung. Eine Fernsteuerung durch Menschen ist daher nicht möglich. Die beiden Roboter nutzten daher das Ergebnis einer Pfadplanung und fuhren dann autonom ihre Wege zu ihren Missionszielen. Dieses Prinzip setzen NASA und ESA auch bei den nachfolgenden Marsmissionen ein.

Spirit und Opportunity verwendeten ab 2006 einen Algorithmus aus der sogenannten D*-Familie. Aus dieser Familie von Algorithmen setzen wir hier für unseren PathRunner genannten EV3-Roboter den Algorithmus D*-Lite ein (gelesen D-Star-Lite). Er ist in Python implementiert und mit einer grafischen Oberfläche für den menschlichen Operator versehen. Das Programm läuft auf dem Raspberry Pi und heißt Interactive D*Lite.

Kurzinfo

• Interaktive Pfadplanung verstehen und anwenden
• Raspberry Pi steuert Lego-EV3-Roboter über Bluetooth
• Programmierung mit Python und Lego EV3 Mindstorms
• Bedienen des Pfadplanungssimulators

Checkliste

• Zeitaufwand: 4 Stunden
• Kosten: 60 Euro (ohne Lego-Baukasten)
• Programmieren: Python unter Linux oder Windows

Material

• Raspberry Pi ab Modell 3B+ oder höher (ohne Kamera)
• MicroSD-Speicherkarte mit installiertem Raspbian Buster oder Raspberry Pi OS Buster (beide Python 3.7.3)
• Lego-EV3-Baukasten 31313

Pfadplanung

Pfadplanungsalgorithmen gehören mit zu den ältesten Algorithmen der künstlichen Intelligenz. Die meisten kennen sie von der Navigation im Auto oder vom Routenplaner auf Google Maps. Schon 1959 hat der niederländische Mathematiker Edgar W. Dijkstra einen Algorithmus zur Pfadplanung beschrieben, mit dem sich der kürzeste Weg zwischen zwei Punkten vorab berechnen lässt. Im Prinzip hat man dabei Orte (Knoten) durch die man fahren kann, die durch Kanten (Straßen) miteinander verbunden sind. Den Kanten ordnet man Kosten zu (Länge der Straße). Das Geflecht aus den per Kanten miteinander verbundenen Kanten nennt man auch Graph.

Das war die Leseprobe unseres heise-Plus-Artikels "Make-Projekt: Pfadplanung für Roboter am Beispiel eines Lego-EV3". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.