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.

Lesezeit: 19 Min.
In Pocket speichern
vorlesen Druckansicht Kommentare lesen 1 Beitrag
Von
  • Detlef Heinze
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

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.

  • Zugriff auf alle Inhalte von heise+
  • exklusive Tests, Ratgeber & Hintergründe: unabhängig, kritisch fundiert
  • c't, iX, MIT Technology Review, Mac & i, Make, c't Fotografie direkt im Browser lesen
  • einmal anmelden – auf allen Geräten lesen - monatlich kündbar
  • erster Monat gratis, danach monatlich ab 9,95 €
  • Wöchentlicher Newsletter mit persönlichen Leseempfehlungen des Chefredakteurs
GRATIS-Monat beginnen Jetzt GRATIS-Monat beginnen Mehr Informationen zu heise+