Make-Projekt: Pfadplanung für Roboter am Beispiel eines Lego-EV3
Ein Pfadplanungs-Algorithmus berechnet für autonome Roboter Fahrwege zum gewünschten Ziel. Anhand unseres Beispiels können Sie eigene Experimente durchführen.
- Detlef Heinze
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.
- 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.
Immer mehr Wissen. Das digitale Abo für IT und Technik.
Karrierewechsel: Warum sich ein Informatikstudium auch für Quereinsteiger lohnt
Proxmox VE: Was es kann und was man dafür braucht
DNS-Leck: Browser ignorieren Windows-Konfiguration
Fujifilm X100VI im Test: Neuauflage der beliebten Edelkompaktkamera
Günstiges Display samt Einplatinencomputer für Bastelanfänger im Kurztest
Boox Note Air3 C im Test: Hybrid-Tablet mit farbigem E-Paper-Display
Immer mehr Wissen. Das digitale Abo für IT und Technik.
Karrierewechsel: Warum sich ein Informatikstudium auch für Quereinsteiger lohnt
Proxmox VE: Was es kann und was man dafür braucht
DNS-Leck: Browser ignorieren Windows-Konfiguration
Fujifilm X100VI im Test: Neuauflage der beliebten Edelkompaktkamera
Günstiges Display samt Einplatinencomputer für Bastelanfänger im Kurztest