Entwicklung und Implementierung eines Routenfindungs-Algorithmus für die Roboter.


Zusammenfassung

Zur Navigation unserer Roboter auf dem Spielfeld soll ein Routing-Algorithmus entwickelt werden, mit dem jeder Roboter autonom die optimale Route zu einem Zielpunkt auf dem Spielfeld berechnen kann. Dabei sollen Hindernisse auf dem Spielfeld und nach Möglichkeit die aktuellen Positionen der anderen Roboter auf dem Feld mit Bezug auf die bekannten Außenmaße des Roboters berücksichtigt werden. Weiterhin sollte der Algorithmus die Einschränkungen des Antriebssystems (Bewegungs-Freiheitsgrade, max. Beschleunigung, etc.) berücksichtigen und möglichst einfach auf andere Antriebssysteme (z.B. Omnidrive) erweiterbar sein.

Features/Ideen:

  • A*-Algorithmus auf einem kartesischen Raster auf dem Spielfeld mit ca. 30mm Auflösung, je 8 Ausrichtungen, 8 Bewegungsrichtungen pro Feld
  • Dynamische Berechnung von Kantengewichten basierend auf Richtungsänderungen und Antriebssystem
  • Vorabberechnung gesperrter Positionen/Ausrichtungen basierend auf Hindernissen und Roboterform
  • Online-Berechnung zusätzlich gesperrter Positionen/Ausrichtungen basierend auf Positionen anderer Roboter
  • Automatische Optimierung (Postprocessing) der Route durch Kurven und Geraden in beliebigen Winkeln
  • Ausführung auf einem separaten Microcontroller mit externem Speicher, Anbindung per CAN-Bus

Tätigkeitsfelder und Technologien

  • Entwicklung von Routing- und Geometrieverarbeitungs-Algorithmen
  • Ggf. Implementierung und Validierung von Algorithmus-Prototypen in Python o.ä.
  • Softwareentwicklung in C++ für Microcontroller
  • Integration in bestehende Robotersoftware mit modm.io und XPCC

Referenzen und Links