SLAM auf dem ESP32?

[Holomino]

Ich hab hier ein ESP32-S2 Wrover Devboard (Saola V1.2 mit 2MB PSRAM) herumliegen (konnte beim Shoppen nicht widerstehen). Nominal sollte damit nichts gegen einen abgespeckten Lidarroboter mit kleinem Gridslam sprechen(?):
- Frontend über Websocket
- Aufnahme der Eingangsdaten (Odometrie und Lidarmessungen) über serielle Schnittstelle (für den Anfang aus einem Simulator).

Hat das schon mal jemand hier mit dem ESP32 versucht?

[Moppi]

Ich habe noch gar nichts mit dem ESP32 versucht. Das liegt da dran, dass ESP32 nicht so gut unterstützt (Arduino-IDE) wird, wie ESP8266; ist jedenfalls das, was ich mal gelesen habe. Ob das inzwischen anders ist, weiß ich nicht. Auch nicht, ob LittleFS inzwischen für den ESP32 verfügbar ist.
Von der Leistung müsste der ESP32 doch ausreichen, mit >=140MHz Taktrate und zwei Kernen?

Freundlichen Gruß

[Holomino]

Ob es reicht? Versuch macht kluch!

So, ich habe mittlerweile:
- die passende Unterstützung für meine Arduino IDE(1.8.16) installiert (https://blog.espressif.com/arduino-for-esp32-s2-and-esp32-c3-is-coming-f36d79967eb8). Mittlerweile gibt es das ESP-Package in der Version 2.01
- das erste Beispiel (https://randomnerdtutorials.com/esp32-websocket-server-arduino/) mit Installation der Bibliotheken für den WebSocket-Server angetestet. Das funktioniert auch mit dem neueren ESP32-S2.

Der Plan wäre nun, das Grundgerüst des Projektes zu erstellen. Ich denke mal, mit drei wesentlichen Komponenten komme ich erst einmal hin.
- HWCom: (Serielle Schnittstelle mit telegrammbasiertem Protokoll)
- Slam: Die eigentliche Algorithmusrechnerei
- Drawing: IO und Handling des Websocket-Servers

[Holomino]

Erste Versuche, eine Preview!

35671

Da ich mal annehme, dass ein Simulator auf Windows-Basis weder als exe (wer startet schon fremde Software auf dem eigenen Rechner) noch als Code (wer hat schon ein Visual Studio) breite Akzeptanz findet, habe ich etwas umdisponiert und als Demo einfach eine sim-Datei aus meinem Simulator erzeugt, die sich auf das SPIFFS-Datenlaufwerk des ESP laden lässt.

Um trotzdem die heilige Dreifaltigkeit "Kommunikation (HWCom)", "Algorithmus (Slam)" und "Ausgabe (Drawing)" des Programmes zu erhalten, wird der Inhalt der Sim-Datei physikalisch über die UART geschickt (man kann ja einfach RxD und TxD brücken).

Der Inhalt der Sim-Datei: Ein Roboter mit Odometrie (Radencoder) fährt durch eine simulierte Umgebung und misst dabei mit einem sich drehenden Lidar die Abstände zu Wänden und Gegenständen (Hindernissen). Als Information bekommt der ESP für jede Messung ein Telegramm mit folgendem Aufbau:


typedef struct
{
uint8_t CmdID; //Telegram ID
float X; //subjective Pose X
float Y; //subjective Pose Y
float Orientation; //subjective Pose Angle
float LidarX; //measurement offset X (relative to robot Pose)
float LidarY; //measurement offset Y (relative to robot Pose)
}__attribute__ ((packed)) LidarData_t; //Length 21


35670

X,Y und Orientation geben die Pose (Punkt und Ausrichtung nach Odometrieberechnung) an. LidarX/Y drücken das Ergebnis der Abstandsmessung relativ zur aktuellen Pose aus.
Ein Rundumscan (360°) aus der Bewegung heraus ist im unteren Teil des Bildes dargestellt, wobei real wesentlich mehr Messungen pro Umdrehung von einem Lidar zu erwarten sind. Hier in der Simulationsdatei sind es z.B. 120 Messungen pro Umdrehung, die aus der Bewegung heraus jeweils mit der entsprechenden Pose geliefert werden.

Gleichzeitig zeigt dieser Bildteil, wie der Slam die Daten aufbereitet: Die Messungen werden solange gepuffert, bis ein 360°-Rundumscan vollständig von der seriellen Schnittstelle empfangen wurde. Danach werden alle Messungen auf die Pose der letzten Messung im Scan umgerechnet (die Pfeile in Magenta). So erhalten wir für einen Scan eine einzelne subjektive (von der Odometrie gemessene) Pose mit vielen Messungen.

Der eigentliche Algorithmus hat nun folgenden Ablauf:
1. Er errechnet eine Posendifferenz (PoseChange) aus der subjektiven Pose des aktuellen und des letzten Scans
2. Diese Posendifferenz schlägt er im Rahmen des Testes mit leichten Variationen (Zufallsgenerator) auf die letzte objektive (vom Slam generierte) Pose auf. Entsprechend werden dabei die Messungen des Lidars umgerechnet und auf Korrelation in der Map getestet.
3. Das beste Ergebnis des Testes bestimmt einerseits, wo sich der Roboter befindet (jetzt kann die variierte Posendifferenz auf die objektive Pose aufgeschlagen werden) und darauf basierend, wo die Hindernisse in der Karte einzutragen sind.

Voraussetzungen für das Beispiel:
=======================
- ESP32-/ESP32-S2 Devboard (z.B. https://www.reichelt.de/nodemcu-esp32-wifi-und-bluetooth-modul-debo-jt-esp32-p219897.html) (https://www.reichelt.de/de/de/entwicklungsboard-esp32-s2-wrover-esp32s2saola1r-p311737.html)
- Arduino IDE (1.8.16 ?)
Board-Package für den ESP32 (Erstinstallation: https://blog.espressif.com/arduino-for-esp32-s2-and-esp32-c3-is-coming-f36d79967eb8 , Update über Boardverwalter)
- Bibliotheken AsyncTCP/ESPAsyncWebServer (Anweisunge/Download: https://randomnerdtutorials.com/esp32-websocket-server-arduino/)
- Arduino PlugIn SPIFFS Uploader (für den S2: https://github.com/lorol/arduino-esp32fs-plugin/releases)
- Dieses Projekt (Unter https://c.gmx.net/@319026116394227058/FcgxNt1fSkGUZEDN7AmUzQ die Datei V0.5.zip)
- Ein Patchkabel 2 x feminin, um RxD/TxD einer UART an den Stiftleisten zu brücken


Step by step
============
- Nach Installation der Bibliotheken AsyncTCP/ESPAsyncWebServer die Datei "AsyncWebSocket.h" suchen, mit einem Texteditor öffnen und die Konstante WS_MAX_QUEUED_MESSAGES auf 8 setzen.
- Das Spiffs PlugIn nach Anleitung installieren
- Das Projekt entpacken und mit der Arduino-IDE laden
- Hier muss ggf. für den S2 das ESP-Package im Boardverwalter aktualisiert werden (aktuell Version 2.0.1)
- Wie in so jedem Web-Beispiel üblich, die Konstanten SSID/PWD an den eigenen Router anpassen. (in Common.h DRAWING_WIFI_SSID/ DRAWING_WIFI_PWD)
- Den ESP per USB an den Entwicklungsrechner anschließen, die entsprechenden Einstellungen im Werkzeugmenü vornehmen.
- Entscheidung mit/ ohne PSRAM (Wrover oder Wroom). Wenn mit PSRAM, dann "Werkzeuge->UsePSRAM" aktivieren UND ggf. Kommentarzeichen vor der Konstante SLAM_USE_PSRAM aus Common.h löschen.
- RxD und TxD an den Stiftleisten brücken. Beim ESP32 bietet sich UART2 an, beim ESP32-S2 UART1, In Common.h lässt sich die Sache über die Konstanten HWCOM_UART, HWCOM_RXGPIO und HWCOM_TXGPIO konfigurieren. (HWCOM_RXGPIO/HWCOM_TXGPIO berücksichtigen die Möglichkeit des Portmultiplexing. Man kann sie auskommentieren)
- Das Projekt auf den ESP hochladen (Strg+U).
- Anschließend die Dateien aus dem data-Verzeichnis per "Werkzeuge->ESP Sketch Data Upload" auf den ESP laden


Im seriellen Monitor der Arduino IDE sollten nun nach den üblichen Bootmeldungen des ESP folgende Zeilen erscheinen:


WS_MAX_QUEUED_MESSAGES from AsyncWebSocket.h:8
->gibt den Erfolg der Patchaktion in AsyncWebSocket.h an. Diese Einstellung ist heikel, weil die Nachrichtenschlange damit nur in der Anzahl der Telegramme begrenzt ist. dabei allerdings die Größe der Telegramme nicht berücksichtigt.


SPIFFS: 1378241 total, 1027594 used
Listing directory: /
FILE: Data1.sim SIZE: 361914
...
->auch die Dateien sind angekommen


Connecting to WiFi..
192.168.137.136

-> Die hier angegebene IP einfach mal als URL im Browser eingeben


RANDOM INITIALIZED

-> Oh, es geht schon los. Wenn die Meldung fehlt, steckt das Patchkabel an den falschen Pins.


Simulation end

-> Schon fertig? Nochmal! Also: Reset-Taster am ESP drücken, Browser durch F5 aktualisieren.

Versuche:
=========
Ok, irgendwann hat man sich sicher satt gesehen. Vielleicht zuerst einmal schauen, ob die Sache nicht ein Fake ist? Um zu sehen, welche Daten der Simulator wirklich geliefert hat, kann der SLAM durch das Nullen der Variationsgrößen praktisch außer Gefecht gesetzt werden. Ändere dazu in Common.h folgende defines:

#define SLAM_ANGLEDEVIATION 0
#define SLAM_DISTANCEDEVIATION 0

Wird das Ergebnis besser/schlechter, wenn ich mehr oder weniger Variationen verwende?

#define SLAM_VARIATIONS 50

Kann ich die Karte gröber oder feiner auflösen?

#define SLAM_RASTER 25.0

Kann ich die Kacheln größer oder kleiner machen?

#define SLAM_TILESIZE 16

Kann ich die Sache beschleunigen?
Aus Common.h

#define HWCOM_SIMFILEPRESCALER 6
Sprich: Alle 6ms (nominal 6x 1ms Zykluszeit der HWCom-Task) wird ein Lidartelegramm versendet.
Tatsächlich aber gibt die HTML-Seite in der Debug-Sektion Auskunft.
Der "Scan integration report" gibt an, wie lange die Integration eines Scans dauert (Time) und wie lange der Algorithmus zwischen den Scans Päuschen macht (Idle).

Überraschend für mich: Auf dem ESP32-S2 (LX7, neuere Architektur, aber nur Single-Core) erreiche ich einen Verarbeitungszyklus von ca. 500ms/Scan. Der ältere ESP32(LX6, Dualcore) braucht dafür nur ca. 120ms. Da die Geschwindigkeit mehr als doppelt so hoch ist, bleibt für den S2 nur zu vermuten, dass sich hier der Overhead aller laufenden Tasks auf einem Kern negativ auswirkt oder (hoffentlich) kommende Package-Versionen die Sache noch etwas beschleunigen.

[Moppi]

Reicht denn die Rechenleistung für sinnvolle Nutzung aus?

[Holomino]

Das ist nicht ganz einfach zu beantworten. Ich versuche es mal:
Die simulierte Umgebung hat eine Grundfläche von ca. 3000*2000 Einheiten (ob Inch, cm oder mm ist nicht festgelegt). Die Auflösung der Karte wird durch SLAM_RASTER (hier 25) bestimmt. Ein Feld auf der Karte ist also 25x25 Einheiten groß.

Wäre die simulierte Umgebung z.B. eine reale Wohnung mit der Grundfläche 12x8m, würde sich als Einheit 4mm ergeben. Damit hättest Du eine Feldauflösung von 10x10cm. Wenn Dir diese Auflösung zum Navigieren reicht, kannst Du mit einer Bearbeitungszeit von 500ms/Scan bei 120 Messungen/Scan für den SLAM rechnen.

Pragmatischer Ansatz, wenn Du noch keinen ESP32 zum Testen hast - ich stelle es gerade für Dich um und lasse es laufen:

Bei SLAM_RASTER = 12,5 (bezogen auf obiges Beispiel also 5x5cm für ein Feld auf der Karte) zeigt mir meine Messung Durchlaufzeiten von bis zu 850ms.

Bei SLAM_RASTER = 50 (bezogen auf obiges Beispiel also 20x20cm für ein Feld auf der Karte) zeigt mir meine Messung Durchlaufzeiten von etwa 420ms.

(Man merkt schon: Die Anzahl der Fließkommaoperationen sinkt durch die Änderung der Auflösung nicht. Die ergibt sich aus "Anzahl Variationen * Messungen pro Scan". Was sich proportional zur Auflösung ändert, ist die Anzahl der Ganzzahloperationen (der Bresenham-Line Algorithmus), die gehen aber auch bei 240MHz recht fix.)

Also grob geschätzt: Typische Wohnung = 500ms Zykluszeit für den SLAM - es fehlen noch Pathfinder, Pathfollower und die intellektuelle Aufgabe, die Karte in Bahnen für einen Staubsauger zu unterteilen oder zeitgesteuert Überwaschungsrouten abzufahren. Das wären sinnvolle Anwendungen, bei denen der Aktualisierungszyklus irgendwo im Sekundenbereich liegen muss

Nicht sinnvoll wäre es, eine Katze damit spielen zu lassen.

[Moppi]

Bresenham ist bei mir Ewigkeiten her, habe ich ganz kurz in den 90gern mal was mit gemacht. Nur zur Verwendung mit Grafikkarte. Habe das dann nie wieder benötigt.

500ms scheint mir schon recht viel. Die 1s pro Zyklus, sind auch nur relativ zur Geschwindigkeit zu sehen oder nicht? Wie dem auch sei, habe ich nur eine begrenzte Vorstellung von dem, was da so im Programm passieren muss, weil ich mich noch nie damit beschäftigt habe. Frage ist, ob ein Roboter bei normaler Geschwindigkeit mit der Rechenleistung auskäme. Oder ob das wirklich nur Sinn macht, wenn der dann entsprechend langsam fährt.

Trotzdem, erstmal schöne Sache!

Gruß
Moppi

[Holomino]

500ms scheint mir schon recht viel. Die 1s pro Zyklus, sind auch nur relativ zur Geschwindigkeit zu sehen oder nicht?

Ich hatte in der Simulation die Robotergeschwindigkeit auf 1Einheit/ Beam (ein Beam=eine Abstandsmessung des Lidars) gesetzt. Mit 120 Beams/Scan sind das also 120 Einheiten, die das Teil sich max. pro Scan fortbewegt. Auf obiges Beispiel mit der Wohnung bezogen (4mm/Einheit) wären das bei Fullspeed (der Roboter rennt wirklich geradeaus) knapp 50cm/Scan.

Auch zeigt mir der "Scan integration report" nach Durchlauf der Simulationsdatei 235 ermittelte Scans an. Bei 1s/Scan hätten die beiden Rundläufe durch die Wohnung etwa 4min gedauert.

Sag Du mir, ob das langsam ist?


Nachtrag:
Ich habe mir gerade einmal eine Wegmessung eingebaut...
In Slam.h:


class Slam
{
public:
float Way=0;


...und am Ende der Funktion Slam::IntegrateScan() unter dem Kommentar "// Report to client" die Sache etwas aufgebohrt.


// Report to client
Scans++;
Way+=max.Distance();
unsigned long end = millis();

snprintf(Report, sizeof(Report),"{\"MsgID\":3, \"Text\":\"Nr %d, %d Beams | Pose X:%.1f, Y:%.1f, O:%.2f, Way:%.2f, Weight:%.2f| Time:%d ms, Idle:%d ms, Heap: %d bytes\"}\0", Scans, scanLen, PsObj->X, PsObj->Y, PsObj->Orientation, Way, maxWeight, end-start, start-lastEnd, ESP.getFreeHeap());
lastEnd= end;
PoseUpdated = true;
ReportUpdated = true;

Ergebnis der Sache: Am Ende der Simulation ist der Way-Zähler auf etwa 24000 hochgelaufen. Das entspräche dann etwa 100m Netto-Fahrstrecke.

[Moppi]

Ich kenne das Konzept nicht, auch keinen Ablaufplan. Daher weiß ich nicht, wie schnell was ist, bzw. ob es ausreichend schnell ist. Ausreichend schnell, für Dein Konzept. Das interessierte mich, deswegen fragte ich.

Bei Bewegungsabläufen, bei denen auch Reaktionen auf Ereignisse stattfinden, spielen Latenzen immer eine nicht unerhebliche Rolle, auf Systemen, die eine überschaubar geringe Leistung haben. Für drinnen ist meine Schätzung maximal 50cm pro Sekunde. Steuert die Umgebungsauswertung direkt die Fahrt, bedeutet das, dass in einer halben Sekunde 25cm zurückgelegt sind, in denen womöglich nichts passiert. Wenn die Fahrt aber generell anders gesteuert wird, mit anderen Sensoren, und die Umgebungserfassung nur zur groben Richtungsbestimmung dient (im Grunde so, wie bei Autofahren durch einen Menschen, der nebenbei ein Navi benutzt), spielt da eine Verzögerung im Sekundenbereich keine große Rolle. Zur Not hält so ein Roboter dann an und wartet, bis ein Ergebnis vorliegt, das er zum Weiterfahren benötigt. Wenn die Umgebungserkennung und Kartierung eingesetzt wird, um überhaupt nur einen Grundriss zu erstellen, mit Hindernissen, und ein Reinungsroboter (bspw.) würde dann aber nur aufgrund der fertigen Karte im Speicher fahren (ohne auf Echtzeitscans angewiesen zu sein), ist das auch wieder eine andere Sache.

Du hast so eine Kartierung ja schon ein paar mal gemacht / umgesetzt. Ich dachte, wegen dem Thementitel, dass auch eine Einschätzung am Ende steht, wie man so einen SLAM-Algorythmus auf -- jetzt -- einem ESP sinnvoll einsetzt. Was geht, was nicht, in Bezug auf Steuerungskonzepte (oder auch nur Dein Steuerungskonzept).

Lieben Gruß
Moppi

[Holomino]

Du hast so eine Kartierung ja schon ein paar mal gemacht / umgesetzt. Ich dachte, wegen dem Thementitel, dass auch eine Einschätzung am Ende steht, wie man so einen SLAM-Algorythmus auf -- jetzt -- einem ESP sinnvoll einsetzt. Was geht, was nicht, in Bezug auf Steuerungskonzepte (oder auch nur Dein Steuerungskonzept).


Mal ganz allgemein: SLAM ist auch nur eine Teillösung. Ohne Pathfinder und Pathfollower ist es ein Gimmik (schön anzusehen). Diesbezüglich bin ich auch nicht "am Ende" angelangt. Ich muss es allerdings auch erst noch schreiben. Bislang ist es nur eine Preview.
Nach 25 Jahren C++-Abstinenz und ohne wesentliche Vorkenntnisse über den ESP32, RTOS, Arduino, WebServer oder HTML finde ich allerdings schon, dass es vorangeht (aufgrund des Verbreitungsgrades kann man sich viele Dinge aus dem Netz ziehen).

Bezüglich "Steuerungskonzept": Ich gehe jetzt nicht davon aus, dass die laufende Umrechnung von Radencoderwerten in eine Pose oder das Anschließen oder verdrahten von Motortreibern zum jetzigen Zeitpunkt projektrelevant sind. Dazu verwende ich eben die Simulation.
Den einen Teil der Hardwareschnittstelle (das Lidartelegramm) habe ich bereits vorgestellt.
Der Pathfinder hat keine Schnittstelle zur Hardware (nur zur UI) und der Pathfollower wird auch nur zyklisch eine aus der subjektiven Pose abgeleitete Koordinate ausgeben, die der Roboter über eine primitive Regelung ansteuern kann (maximal kann man während der Fahrt durch weitere Hindernissensoren den Pathfollower unterbrechen und am Pathfinder eine Neuberechnung antriggern).

Kurz: Die beiden Telegramme kann ich über die serielle Schnittstelle lösen, die Gegenstelle (Simulation) ist eh da, dann kann ich mich auf's Wesentliche konzentrieren.




Was geht, was nicht.

Es werden einige komplexere Probleme (closed loop, kidnapped robot) wahrscheinlich nicht gehen. Allerdings weiß ich auch nicht, ob die bei z.B. Staubsaugerrobotern gelöst werden, oder ob diese Geräte nicht gerade deshalb die "Verbindung nach Hause" suchen, damit die Softies beim Hersteller die Sache heilen.

[Holomino]

Weiter geht es mit neuen Features.
Die V0.6 liegt hier (https://c.gmx.net/@319026116394227058/FcgxNt1fSkGUZEDN7AmUzQ):
Wenn auf der verlinkten Seite etwas von fehlender Freigabe steht, einmal über F5 im Browser aktualisieren.

Als Update einfach entpacken, mit Arduino öffnen, PWD und SSID aus Common.h anpassen und das Spiffs-Laufwerk aus dem data-Verzeichnis aktualisieren. Ggf. noch die serielle Schnittstelle anpassen (sonst kommen keine Daten).

Die Eroded-map
==============

35686

Der im Fall A) gezeigte Pfad geht zwar nach den Informationen der bisher erstellten Karte über freie Felder, trotzdem würde der dem Pfad folgende Roboter mit dem Hinderniss kollidieren (er ist selber ein Körper).
Entweder berechnet man bei der Pfadsuche also die Abmessungen des Roboters ein, oder, wie in Fall B) gezeigt, man vergrößert die Hindernisse entsprechend: man zeichnet jeden Hindernispunkt der Lidar-map als Klecks mit dem Radius des Roboters in die Eroded-map.
Das funktioniert nach folgenden Spielregeln:
Aus dem Slam-Zyklus heraus werden die Felder der Lidar-map über Grid->Set(x,y,value) letztendlich in Tile->Set(x,y,value) manipuliert.

Verpassen wir Tile->Set einen Rückgabewert, der angibt, in welche Richtung sich der Belegtwert des Feldes (>0 oder <=0) ändert...


int8_t Tile::Set(int x, int y, int8_t val)
{
int8_t rval =0;
int offset = y*_width+x;
if(Data[offset]<=0 && val > 0)
rval= 5;
if(Data[offset]>0 && val <= 0)
rval= -5;

Data[offset] = val;
IsDirty= true;
IsTested= false;
return rval;
}

... können wir in Grid->Set mithilfe einer vordefinierten Maske in der Eroded-map den nötigen Tintenklecks einfügen.


//from common.h
// 2 fields additional mask:
// XXX
//XXXXX
//XXOXX
//XXXXX
// XXX
int RobotMask[][2]={ {-1, 2},{0, 2},{1, 2},
{-2, 1},{-1, 1},{0, 1},{1, 1},{2, 1},
{-2, 0},{-1, 0},{0, 0},{1, 0},{2, 0},
{-2, -1},{-1, -1},{0, -1},{1, -1},{2, -1},
{-1, -2},{0, -2},{1, -2}
};



void Grid::Set(int x, int y, int8_t val)
{
Tile* tile = GetTile(x,y, true);
if (tile == nullptr)
return;

int8_t e = tile->Set((x-xMin)%SLAM_TILESIZE,(y-yMin)%SLAM_TILESIZE, val);
if (e !=0)
{
int ex, ey;
for (int i=0;i <sizeof(RobotMask)/8;i++)
{
ex= x+RobotMask[i][0];
ey= y+RobotMask[i][1];

tile = GetTile(ex,ey, true);
if (tile != nullptr)
tile->AddToEroded((ex-xMin)%SLAM_TILESIZE,(ey-yMin)%SLAM_TILESIZE, e);
}
}
}



Das Resultat: Dickere Wände, freie Felder sind 0, besetzte Felder haben einen positiven Wert.
Negative Werte werden nicht eingenommen.

Wissenswert vielleicht noch: Die Umstellung der Ansicht Lidar-map/ Eroded-map erfolgt über
#define DRAWING_SHOW_ERODED
(wie immer in Common.h)

Der Pathfinder
==============
In der jetzigen Testimplementierung sucht der Pathfinder den Weg von der aktuellen Roboterposition zum Zielpunkt (0;0). Den Zielpunkt kann man im Frontend durch Klicken auf die Map umsetzen. In der Debug-Sektion gibt der "Pathfinder-Report" weitere Infos.

Zum Algorithmus: Nachdem wir mit der Eroded-map quasi das Speicheraufkommen für die lapidare Aufgabe der Kollisionsvermeidung um Hindernisse herum verdoppelt haben, wurde es Zeit, zumindest beim Pathfinder nach einer der Hardware angemessenen Lösung zu suchen.

35687

Das Ergebnis im Bild: Links der aktuell implementierte Algorithmus, im Vergleich rechts ein A* auf dem PC. Das sieht auf den ersten Blick nicht optimal aus.
Auf den zweiten Blick allerdings zeigt auch der A* keinen perfekten Weg. Knoten sind nun mal auf einem Array Nachbarfelder. Die können nur horizontal, vertikal oder diagonal sein. Entsprechend ermittelt auch der A* nicht die über die blaue Linie angedeutete Abkürzung.

Beim A* bietet es sich an, während der Fahrt über den Pfad (Pathfollower) diese Abkürzungen zu suchen, indem man mithilfe des bereits im Slam verwendeten Bresenham die vor sich liegenden Felder abtastet. Wenn man dadurch ein´weiter entferntes Feld hinter der nöchsten Kurve geradlinig erreichen kann, dann kann man die Kurve also schneiden.

Und ja, ich bin der Meinung, das kann man auch mit dem Ergebnis des ESP-Patfinders. Mit ein bisschen Spielen wird also während der Fahrt nicht viel Anderes bei rumkommen.

Die Handbremse lösen
===================
Wer noch einmal die alte Version 0.5 hervorholt und hier in der loop() in ESP32Slam.ino ein vTaskDelay(100) einfügt, wird bemerken, dass sich die Zykluszeiten des Slam auf dem ESP32-S2 um ca. 40% verbessern.
Ich denke mal, dass auch die loop() eine RTOS-Task mit Priority>0 ist und der leere Rumpf alleine die anderen Tasks gewaltig ausbremst. Anders kann ich es mir nicht erklären.

[Holomino]

35695

Der Simulator ist da
Als Vorbereitung für den Pathfollower oder einfach zum Spielen.
Ein Klick auf die Karte in der HTML-Seite löst beim simulierten Roboter ein primitives Bewegungsmuster (drehen in Richtung/ Vorwärtsfahrt bis zum Zielpunkt) aus. Kollidiert der Roboter dabei mit einem Hindernis, hält er stumpf an.

Sowohl die Bewegung als auch die kontinuierlichen Lidarmessungen werden mit Fehlern versehen, so dass der Slam etwas zu tun hat (sieht man nach kurzer Fahrt recht gut, wenn man den Slam über SLAM_ANGLEDEVIATION/SLAM_DISTANCEDEVIATION deaktiviert).

Die simulierte Karte ist in sim.h als Array mit 32x32 Feldern definiert. Eine 1 als Element definiert ein Hindernis, eine 0 ist frei befahrbar. Entsprechend der angegebenen Feldgröße 400 (SIM_FIELDSIZE) hätte die Karte eine Abmessung von 12800x12880 Einheiten.
Mit der Einheit "mm" und der Rastereinstellung 100 im Slam (SLAM_RASTER) wäre die Simulationsumgebung von 12,8x12,8m also in 10cm-Kästchen gerastert.
Ebenso in sim.h befinden sich die anderen zugehörigen Parameter, so dass man mit unterschiedlichen Sensor- (Reichweite, Messungen/Umdrehung, Genauigkeit) und Fahrsettings (Robotergröße, Odometriegenauigkeit, Geschwindigkeit) spielen kann.


Stabilere Ausgabe
Ich suche Fehler eigentlich immer eher bei mir, es hat also etwas gedauert (nach Betrachtung der Quellen zusammen mit meinem personal Informatiker waren uns beiden die Quellen nicht so recht geheuer), bis ich diesen Link gesucht/gefunden habe:
https://github.com/me-no-dev/ESPAsyncWebServer/issues/900

Bedauerlich: Es gibt etliche begeisterte Netzbeiträge über den AsyncWebserver und mindestens genauso viele Rückfragen bezüglich Instabilität. Die Lösung liegt (versteckt den Dornröschenschlaf fristend) gleich nebenan:
https://github.com/yubox-node-org/ESPAsyncWebServer.
Warum verlinkt da keiner drauf?

Lässt sich jedenfalls, genau wie das Original, als Zip-Lib in Arduino installieren (vorher das Original einfach von der Platte löschen)
Für diese Anwendung ist der Wert 4 in der Konstante WS_MAX_QUEUED_MESSAGES ein guter Kompromiss.

Das neue Board-Package 2.0.2
...funktioniert bei mir nicht. Soweit ich nach kurzer Testinstallation (mal so nebenbei, sollte ja nur 10 min dauern und hat dann doch wieder 2h Stirnrunzeln gekostet, grummel) gesehen habe, läuft UART1 auf dem S2 nicht mehr. Ob's nun am Programm bei mir liegt oder am Package? Keine Ahnung - ich muss es noch testen. Also:
Zur Zeit ist das gültige Board-Package für dieses Projekt noch die Version 2.0.1.



Die V0.7 liegt hier: (https://c.gmx.net/@319026116394227058/FcgxNt1fSkGUZEDN7AmUzQ). Wie gehabt: Wenn "diese Freigabe leider ungültig ist", einmal über F5 aktualisieren, dann klappt das schon.
Der Simulator sendet seine Daten, wie bisher schon zelebriert, weiterhin über die UART. Also auch das Patchkabel zum Brücken von RxD/TxD stecken lassen.

[Holomino]

Der Pathfollower

Ein Linksklick auf die Map lässt den Roboter jetzt optimiert über den Pathfollower den Pfad zum Zielpunkt folgen.
Rechtsklick ist die aus der letzten Version bereits bekannte Fahrt per Luftlinie (da klatscht der Roboter halt vor die nächste Wand).

Netter Nebeneffekt für Indoor: Wenn man auf einen Punkt außerhalb der Umrisse klickt, sucht sich der Roboter iterativ den Pfad und exploriert so nebenbei die gesamte Umgebung:


https://youtu.be/Cew5G0Zmi-E



Die V0.8 liegt hier (https://c.gmx.net/@319026116394227058/FcgxNt1fSkGUZEDN7AmUzQ). Wie gehabt: Wenn "diese Freigabe leider ungültig ist", einmal über F5 aktualisieren, dann klappt das schon.

Um Links-/Rechtsklick nutzen zu können, muss auch wieder das SPIFFS-Verzeichnis aktualisiert werden.

[Holomino]

Alles dynamisch
Die neuen Funktionen lassen sich grob durch die Begriffe Kurzzeit- und Langzeitgedächtnis umreißen.
Das Kurzzeitgedächtnis umfasst Kenntnisse über den aktuellen Zustand (so dass der Pathfinder einen Weg finden kann), das Langzeitgedächtnis muss ausreichende Informationen zur dauerhaften Lokalisierung bieten.

Wer mit der letzten Version etwas gespielt hat, wird sicher bemerkt haben: nach der erstmaligen Exploration (Filmchen) tut sich nicht mehr so viel an der Karte. Es war ja auch alles noch statisch. Was tun, wenn Türen in der gezeichneten Wohnung verschlossen werden oder das typische Kinderchaos auf den Böden wütet?

Insbesondere das Kinderchaos (auch Erwachsene bleiben manchmal ewig jung) wirft das nächste Problem auf: Spielzeug oder hingeworfene Klamotten sind oft so flach, dass das Lidar sie gar nicht erst sieht (wegen der freien Rundumsicht wird das Lidar üblicherweise am höchsten Punkt des Roboters angebracht). Den Rest muss die Nahfelddetektion (Hindernissensoren) erledigen. Deren Daten können aber schlecht zur Lokalisierung verwendet werden. Entweder sehen die Nahfeldsensoren Dinge, die das Lidar schpn längst gesehen hat (redundant) oder sie sehen Hindernisse, die sich nicht mit den Lidardaten vereinbaren lassen (der Sache nicht förderlich).

Lösung: Wir können einen Grundzustand der Umgebung in das Langzeitgedächtnis (Lidarkarte) prägen. Wenn wir die Werte der Nahfeldsensoren zusammen mit den Messergebnissen der letzten paar Lidarscans noch in ein temporäres Kurzzeitgedächtnis schreiben und dies ebenso auf die Eroded-Karte übertragen, wie wir es auch schon mit der Lidarkarte gemacht haben, bietet die Eroded-karte einen aktuellen Zustand für den Pathfinder. Es muss nur reichen, um ein umfahrbares Hindernis zu umfahren oder eine wirkliche Blockade (geschlossene Tür) bis zum Abbruch der Mission zu erkennen.

Showtime
Zur Demonstration all dieser Funktionen habe ich Spielkram eingebaut:
In der HTML-Seite kann man jetzt durch Rechtsklick den Basispunkt (blaues Fähnchen) und durch Linksklick das Ziel (gelbes Fähnchen) festlegen. Der Roboter wird versuchen, zwischen den beiden Punkten zu pendeln. Der Unterschied zwischen Basis und Ziel: Wenn das Ziel nicht erreicht werden konnte, kehrt der Roboter nacxh kurzer Wartezeit zur Basis um. Wenn der Pfad zur Basis abgeschnitten wurde, bleibt der Roboter stumpf an seinem Standort (und verhungert). Praktischer Sinn dahinter: Wenn der Roboter während der Fahrt zu einem nicht erreichbaren Ziel auch noch den Kontakt zum WLAN verliert, kehrt er hoffentlich noch zur Basis zurück.

Unterhalb der Kartendarstellung ist ein Stimuli-Feld zur Eingabe eines bitcodierten Wertes:
Bit 0: Sperrt das Mapping im SLAM (Localization läuft aber weiter).
Bit 1: Schaltet zusätzlich beim simulierten Roboter einen frontal ausgerichteten Nahfeldsensor mit Reichweite 1000 ein.
Bit5..7 schaltet die entsprechend gekennzeichneten Felder der Simulationskarte um, dass sie als Hindernisse wirken, die nur für Nahfeldsensorik und Bumper sichtbar sind.
Bit2..4 schaltet die entsprechend gekennzeichneten Felder der Simulationskarte um, dass sie als Hindernisse wirken, die auch vom Lidar gesehen werden.


35724
Wenn ich also beispielsweise den Wert 43 (binär 00101011) im Stimulifeld eingebe (und mit ENTER abschließe), schalte ich damit im Raum unten rechts die große für das Lidar unsichtbare Blockade ein, schließe gleichzeitig die untere Tür. Außerdem ist dann das Mapping blockiert und der Nahfeldsensor eingeschaltet.

Programmtechnisch befindet sich das Kurzzeitgedächtnis als "ShortTimeList" im Grid-Objekt (Common.cpp/.h). Das Sperren der Lidarkarte beschränkt sich auf die Funktion Slam::IntegrateVariation und der rudimentärste aller Routenplaner versteckt sich in SLAM.cpp/.h


Diese Version (0.9) liegt, wie gewohnt auf https://c.gmx.net/@319026116394227058/FcgxNt1fSkGUZEDN7AmUzQ
Viel Spaß damit

[Holomino]

35734

Layout:
Der gefüllte Kreis mit Richtungszeiger in der HTML-Seite sah eh schon fast wie ein Pacman aus. Dann können wir die Sauerei mithilfe einer einfachen farblichen Konvertierung im TileConverter auch komplett machen.

Wifi reconnect:
Damit der Roboter sich nach Verbindungsverlust wiederverbindet.

Putzen einiger Magic-Numbers im Code:
Eine Aufgabe eher allgemeiner Natur.

Speicherauslastung/-fragmentierung im Scan-Report:
min Heap, max Heap block size, used PSRAM. Das gehört zum Langzeittest dazu (seit der letzten Version kann die Simulation auch mal eigenständig hundert virtuelle Kilometer abspulen).


Alles in allem also eher Konsolidierungsmaßnahmen, konzeptionell nichts Neues. Im Augenblick strecke ich die Fühler etwas in Richtung OpenSlam.org aus: zumindest sehen TinySlam und GridSlam oberflächlich so aus, als würden sie sich irgendwie zwischen Ausgabe, Simulator, Grid und Pathfinder auf den ESP quetschen lassen.

Wie immer:
Die V 0.10 liegt auf https://c.gmx.net/@319026116394227058/FcgxNt1fSkGUZEDN7AmUzQ

[Holomino]

tinySlam

35752

Im Groben sind Aufbau und Struktur des tinySLAM identisch zum Bisherigen. Es wird über die Variation der Pose getestet und anschließend das beste Ergebnis in die Karte eingetragen. Augenscheinliche Unterschiede:

Der Datentyp der Kartenfelder muss erweitert werden auf uint16_t
Belegte und freie Felder unterscheiden sich in der Richtung (bisher wurden freie Felder dekrementiert, jetzt werden sie inkrementiert)
Der Test erfolgt nur noch über den Vergleich der Endpunkte (schneller)
Das Eintragen der Hindernisse erfolgt über einen Fangbereich (hole_width), wobei die Wertigkeit der betroffenen Felder per Tiefpass gesetzt wird.



Weniger augenscheinliche Unterschiede (Macken):
Messungen im spitzen Winkel (nah vor der Wand oder bei der Fahrt um eine Innenecke herum) reißen bisher geschlossene Umrissstrukturen wieder auf. Das kann man aber filtern. Aus Slam.cpp:


//Suppress small angle entries (rays disturbing walls)
if (x<= 3*dxc/4 && oldVal <0x8000)
return;


Wo einerseits hinzugefügt, aber offensichtlich auch abgetragen wird, muss mit einem Langzeitdrift gerechnet werden. D.h. die Karte läuft langsam unter den Absolutkoordinaten des Routenplaners weg.
35753
Dagegen hilft eigentlich nur das Sperren der Lidarkarte.


Deutliche Vorteile gegenüber der bisherigen SLAM-Lösung beginnen sich abzuzeichnen, wenn man in sim.h die Reichweite des Lidars drastisch reduziert (z.B. #define SIM_LIDARRANGE 2500). Auch wenn die langfristige Lokalisierung nach Abschluss der Exploration noch nicht zuverlässig läuft (hier fehlt im Wesentlichen noch die Erweiterung der Variationsbereiche in Richtung der OutOfRange-Messungen), funktioniert die Exploration in der Regel so gut, dass man wirklich einmal über den Bau eines "Poor mans Lidar" nachdenken darf. Zumindest nominal kommt man hier schon recht nah an den realen Messbereich eines VL53L1X - frei nach Lou Ottens also: Wenn's kleiner, einfacher und günstiger ist, könnte es was werden...

Der aktuelle Spielkram befindet sich als V0.10TS.zip unter: https://c.gmx.net/@319026116394227058/FcgxNt1fSkGUZEDN7AmUzQ

Weitere Infos über tinySLAM:
www.OpenSLAM.org
https://www.researchgate.net/profile/Oussama-El-Hamzaoui/publication/228374722_CoreSLAM_a_SLAM_Algorithm_in_less_than_2 00_lines_of_C_code/links/0912f5134a7837f5b8000000/CoreSLAM-a-SLAM-Algorithm-in-less-than-200-lines-of-C-code.pdf