Lidar pour robots : du balayage à la carte

Introduction

Un capteur de distance dit à quelle distance est une chose, le long d’une ligne. Une carte dit la forme d’une pièce. Tout ce qui est intéressant en navigation vit dans l’écart entre les deux, et cet écart est l’objet de cette page.

Les deux bouts sont déjà couverts ici : la télémétrie ponctuelle d’un côté, et le SLAM et A* sur grille d’occupation de l’autre. Mais ceux-là supposent qu’une grille existe déjà. Rien ne dit d’où elle vient, et la réponse — projeter un balayage en cellules par lancer de rayons — est à la fois simple et pleine de pièges.

Un lidar 2D est un capteur ToF sur un plateau tournant

C’est la chose la plus utile à savoir, parce que cela signifie que vous comprenez déjà la moitié télémétrie.

Dans un lidar 2D amateur se tient un module optique de télémétrie par temps de vol, exactement du genre d’une carte VL53, pointé sur le côté et mis en rotation. Un encodeur angulaire rapporte où il regardait à chaque mesure. L’alimentation et les données franchissent la frontière tournante par une bague collectrice ou un couplage optique ou inductif.

Donc un « balayage » n’est pas une photographie. C’est une liste de paires (angle, distance), recueillies une à une, sur un tour. Chaque limitation ci-dessous découle de cette phrase.

Cela dit aussi pourquoi les capteurs ultrasons ne sont pas montés en lidars tournants. Un faisceau ultrasonore fait des dizaines de degrés de large, donc le tourner ne gagne presque rien — vous étaleriez un faisceau déjà large à travers la pièce. Un faisceau optique étroit est ce qui rend la résolution angulaire significative en premier lieu. Balayer un unique capteur ToF sur un servo, comme dans le tutoriel du balayage ultrasonore, est vraiment un lidar lent et basse résolution.

Le budget d’échantillons est fixe, donc résolution et fraîcheur s’échangent

Voici la partie qui surprend, et elle vaut d’être comprise avant tout achat.

Le module de télémétrie a un seul nombre de débit : combien de mesures par seconde il peut prendre. Sur un RPLIDAR A1 c’est environ 8 000 échantillons par seconde, et cela ne change pas quand vous changez la vitesse de rotation. La vitesse de rotation est à vous, typiquement 1–10 Hz.

Donc les points obtenus par tour sont simplement le budget divisé par la vitesse de rotation :

points per revolution = samples per second ÷ spin rate
angular step          = 360° ÷ points per revolution

Vous ne pouvez pas avoir des balayages frais et une fine résolution angulaire à la fois. Tourner à 10 Hz divise la latence par deux et divise presque la résolution angulaire par deux. Ce seul compromis décide plus du comportement d’un robot que le chiffre de portée en titre, et c’est la première chose à régler délibérément plutôt qu’à laisser au défaut du pilote.

Robot rapide dans un couloir ouvert : tournez vite, il faut la fraîcheur et les murs sont grands. Robot lent cartographiant une pièce encombrée : tournez lentement, il faut le détail et vous pouvez payer la latence.

Les faisceaux divergent, donc les obstacles lointains passent entre eux

Un pas angulaire est un angle, pas une distance. Deux faisceaux adjacents s’écartent en voyageant :

gap between beams ≈ range × angular step (in radians)

À 0,45° cela fait 7,9 mm d’écart à un mètre, et 31 mm à quatre mètres. Rien n’échantillonne l’espace entre.

Prenez un pied de chaise de 20 mm. En tournant à 10 Hz, l’écart des faisceaux dépasse 20 mm vers 2,5 m — au-delà, le pied peut se tenir entièrement entre deux faisceaux et ne rien renvoyer. À 5,5 Hz vous allez jusqu’à environ 4,6 m avant la même chose.

Cela explique un comportement qui ressemble sinon à un capteur cassé : les obstacles minces apparaissent à mesure que le robot approche, surgissant dans la carte à un ou deux mètres. Le lidar ne tombait pas en panne. Le pied n’était jamais échantillonné.

Deux conséquences à intégrer à la conception :

• Ne croyez pas un seul balayage pour les obstacles minces. Accumuler plusieurs balayages dans une grille, comme ci-dessous, est ce qui trouve vraiment les pieds de table — chaque balayage échantillonne des angles légèrement différents.
• Les pieds de chaises et de tables sont la panne classique du robot domestique, parce qu’ils sont minces, ils sont exactement à hauteur du lidar, et le robot ne les apprend que tard.

Un balayage n’est pas un instantané

Les points d’un tour n’ont pas été mesurés au même instant. À 5,5 Hz le balayage prend 182 ms, et le robot n’attend pas poliment.

• En roulant à 0,5 m/s, le robot parcourt 91 mm pendant un tour.
• En tournant à 1 rad/s, le balayage est étalé sur 10,4°.

Traiter cette liste de points comme un instantané rigide pris en une pose courbe le monde. Les murs droits sortent courbes ou dédoublés, et l’appariement de balayages combat des corrections qui sont vraiment votre propre mouvement.

C’est pourquoi sensor_msgs/LaserScan porte scan_time et time_increment à côté des distances : ils laissent un consommateur calculer quand chaque faisceau a été pris. Corriger cela — transformer chaque point par la pose que le robot tenait à l’horodatage de ce faisceau — s’appelle le redressement ou compensation de mouvement, et les bons frontaux SLAM le font pour vous.

Ce que cela signifie en pratique : si vos cartes sont propres à l’arrêt et floues en roulant, suspectez le redressement et les horodatages bien avant le capteur. Et ralentissez en cartographiant. Moitié de la vitesse est moitié de la distorsion, gratuitement.

Une tranche horizontale est tout ce que vous avez

Un lidar 2D mesure un plan. Ce qui se tient au-dessus ou au-dessous de ce plan n’existe pas.

Les trois classiques :

• Surplombs. Un plateau de table à 700 mm est invisible à un lidar à 150 mm. Le robot s’engage dessous avec assurance et s’y coince.
• Obstacles bas. Un seuil de porte, un câble, une chaussette. Tous sous le plan.
• Décrochements. Un escalier qui descend est de l’espace vide dans chaque direction que le lidar peut voir. Il se lit comme un sol magnifiquement dégagé.

Aucun traitement de balayage ne corrige cela, parce que l’information n’a jamais été saisie. Les vrais robots gardent un pare-chocs, des capteurs de vide et souvent un télémètre vers le bas ou incliné vers l’avant à côté du lidar — non parce que le lidar est mauvais, mais parce qu’un plan est un plan. Quand vous lisez qu’un robot aspirateur « a un lidar et quand même des pare-chocs », voilà pourquoi.

Du balayage à la grille : le lancer de rayons

Maintenant la moitié cartographie. Une grille d’occupation divise le monde en cellules carrées et stocke, pour chacune, l’intensité de votre croyance qu’elle est occupée.

L’idée qui la fait marcher : une mesure de distance parle de chaque cellule le long du rayon, pas juste de la cellule au bout. Si un faisceau a voyagé 3 m avant de heurter quelque chose, alors tout l’espace traversé devait être vide — sinon il se serait arrêté plus tôt.

Chaque faisceau produit donc trois verdicts :

1. Cellules traversées par le rayon → indice de vide. Parcourez la ligne du capteur à l’impact et poussez chaque cellule vers vide.
2. La cellule où la mesure a atterri → indice d’occupé. Poussez-la vers plein.
3. Cellules au-delà de l’impact → rien. Le faisceau s’est arrêté. Vous n’avez rien appris de ce qui est derrière ce mur, donc vous devez laisser ces cellules tranquilles.

Parcourir la ligne est juste de la rastérisation de ligne — l’algorithme de Bresenham, le même qui trace une ligne sur un écran.

Une mesure à portée max exige son traitement propre. Beaucoup de pilotes rapportent le maximum, ou l’infini, quand rien n’est revenu. Ce n’est pas « il y a un mur à 12 m » — c’est « rien n’a été trouvé ». Marquez le rayon libre et ne marquez aucune cellule occupée au bout.

Log-odds : pourquoi on additionne au lieu de multiplier

Vous pourriez stocker une probabilité par cellule et multiplier les mises à jour de Bayes ensemble. En pratique tout le monde stocke des log-odds à la place :

l = ln( p / (1 - p) )          p = 1 / (1 + e^(-l) )

Deux raisons. Multiplier beaucoup de petites probabilités déborde par le bas ; additionner des logarithmes non. Et cela fait de la mise à jour une seule addition, assez bon marché pour chaque cellule de chaque faisceau de chaque balayage.

Avec p = 0,5 (aucune idée) correspondant à l = 0, choisissez une valeur pour un impact et une pour un manque — disons p_occ = 0,7 (l = +0,847) et p_free = 0,4 (l = −0,405) — et la mise à jour est :

l_cell += l_occ     # this beam hit this cell
l_cell -= 0.405     # this beam passed through this cell

Une cellule partant de l = 0 après trois impacts :

L’évidence s’accumule, et le désaccord la retire. Voilà tout l’algorithme.

Bornez les totaux. Cela compte plus qu’il n’y paraît. Vingt impacts consécutifs sans borne mettent une cellule à l = 16,9, soit p = 0,999999. Maintenant quelqu’un déplace la chaise. Défaire cette certitude prend 42 observations de vide. La chaise laisse un fantôme permanent, et votre planificateur continue de braquer autour de rien.

Borner l à quelque chose comme ±3,5 corrige cela : une croyance forte reste forte, mais une poignée de balayages contradictoires peut la renverser. Si vos cartes accumulent des fantômes d’objets partis, c’est presque toujours pourquoi.

Inconnu est un troisième état, pas un synonyme de libre

C’est l’erreur qui produit des plans assurés et dangereux.

Une grille fraîchement initialisée est entièrement inconnue. Si votre planificateur traite l’inconnu comme franchissable, il routera joyeusement droit à travers les parties du monde jamais regardées — et, inexplorées, elles sont exactement là où vivent les surprises. S’il traite l’inconnu comme bloqué, le robot refuse de bouger au départ, parce que tout est inconnu.

Les deux sont faux ; gardez les trois états distincts et décidez délibérément :

• Occupé — n’y planifiez pas à travers.
• Libre — planifiez à travers.
• Inconnu — n’y planifiez à travers qu’à un coût, ou seulement en explorant délibérément.

L’exploration par frontières, qui est comment un robot choisit où regarder ensuite, est bâtie entièrement sur la frontière libre/inconnu. Confondre les deux et vous avez jeté cela.

Choisir la taille des cellules

La réponse usuelle est 5 cm pour les robots d’intérieur, et il y a une raison de ne pas aller plus fin juste parce qu’on peut.

Une cellule plus petite que votre espacement de faisceaux à portée typique invente une précision que vous n’avez pas — à 4 m les faisceaux sont espacés de 31 mm, donc des cellules de 1 cm laissent des trous permanents entre rayons qui ne se remplissent jamais. Des cellules bien plus grandes que la marge de dégagement de votre robot, pendant ce temps, font paraître les portes infranchissables, parce qu’une seule cellule occupée peut avaler le passage.

Règle pratique : taille de cellule un peu plus petite que le passage le plus étroit à franchir, et pas plus petite que votre espacement de faisceaux là où vous opérez vraiment. Puis gonflez les obstacles du rayon du robot au moment de planifier plutôt que de rétrécir les cellules pour compenser.

Quand ça tourne mal

Cette dernière ligne est la réserve honnête de toute la page. Le lidar bat le sonar en résolution, débit et portée, puis perd complètement contre lui sur une porte vitrée, que le son réfléchit et pas la lumière. C’est l’argument le plus clair pour ne pas choisir un capteur et déclarer le problème résolu.