Planification et cartographie : du remplissage au SLAM
Vous savez planifier un itinéraire dans une grille connue, replanifier face à de nouveaux obstacles et expliquer comment un robot construit la carte sur laquelle il planifie.
La navigation réactive fait circuler un robot dans une pièce sans jamais savoir où il est. Cela s’épuise vite : un robot purement réactif ne peut pas recevoir l’ordre va à la cuisine, et il bouclera joyeusement dans une pièce en fer à cheval. La planification est la réponse, et elle exige ce que la commande réactive n’a jamais — une carte.
Ce parcours commence là où la carte est gratuite. Dans un labyrinthe, le remplissage inonde les distances depuis l’objectif et le robot descend simplement la pente, en replanifiant dès qu’il découvre un mur supposé ouvert. Puis le monde se complique : A* planifie sur une grille d’occupation où les cases ont des coûts, où les obstacles doivent être gonflés, et où l’heuristique décide si votre planificateur est rapide ou seulement correct.
Le dernier nœud est l’honnête. Chaque planificateur ci-dessus suppose que vous avez une carte, et un vrai robot doit en construire une tout en roulant sur des roues qui lui mentent. Le SLAM est ce qui arrive quand cartographie et localisation refusent d’être séparées, et la fermeture de boucle est ce qui empêche la carte de se déformer pendant que l’odométrie dérive. Une IMU gagne sa place ici pour la même raison : elle mesure la rotation directement, ce que des roues qui glissent ne peuvent tout simplement pas.
Avant de commencer
Il faut être à l’aise avec les tableaux à deux dimensions et la pensée algorithmique de base — files, et l’idée de visiter des cases dans un ordre. Le parcours de commande des moteurs vaut la peine d’être fait d’abord, car chaque planificateur ici suppose que le robot peut exécuter un mouvement commandé et indiquer à peu près de combien il est allé.
Ce que vous saurez faire
- Inonder une grille de distances depuis un objectif et en descendre le gradient.
- Faire tourner A* avec une heuristique dont vous pouvez montrer qu’elle ne surestime jamais, et expliquer pourquoi cette propriété rend le résultat le plus court.
- Convertir des mesures de distance en grille d’occupation par lancer de rayons, en mettant à jour les cellules libres et occupées séparément.
- Dire pourquoi l’odométrie seule ne peut pas produire une carte utilisable sur une longue mission, et ce que le SLAM ajoute.
Où l’on se heurte
Une heuristique qui surestime. A* ne garantit le plus court chemin que quand l’heuristique n’annonce jamais une distance supérieure au vrai coût restant. Utiliser la distance euclidienne sur une grille 4-connexe, ou gonfler une heuristique pour accélérer la recherche, renvoie silencieusement des trajectoires qui ne sont pas les plus courtes.
Planifier pour un robot ponctuel. La trajectoire est calculée dans la grille, mais le robot a une largeur. Un itinéraire qui frôle un coin est géométriquement valide et physiquement une collision. Gonflez les obstacles du rayon du robot avant de planifier, et le problème disparaît.
Traiter l’inconnu comme libre. Une case que rien n’a observée n’est pas vide — elle est non mesurée. Planifier à travers comme en espace libre et le robot fonce avec assurance dans ce qui n’a jamais été vu. L’inconnu est un troisième état, et il doit rester un troisième état.
Des déplacements diagonaux coûtant un. Sur une grille 8-connexe, un pas diagonal couvre √2 cases, pas une. Le facturer un produit des trajectoires qui préfèrent les escaliers et des distances simplement fausses.
Supposer que le robot est où dit l’odométrie. Chaque planificateur ici travaille sur une pose. L’odométrie à roues dérive sans limite, donc un plan parfait est exécuté depuis une position de plus en plus fictive. Cet écart est toute la motivation du dernier nœud de ce parcours.
Ce qu’il vous faut
| Quoi | Pourquoi ce parcours en a besoin | Notes |
|---|---|---|
| Aisance avec tableaux 2D et files | Chaque algorithme ici est une boucle sur une grille | Pas de maths avancées ; une file et une boucle imbriquée forment toute la boîte à outils |
| Un robot qui exécute des mouvements commandés | Un plan ne vaut rien si le robot ne peut pas le rouler | Le parcours de commande des moteurs vous y amène |
| Un gyroscope ou une IMU | Les roues ne peuvent pas mesurer une rotation traversée en glissant | MPU-6050 ; les nœuds de cartographie dépendent du cap |
| Un capteur de distance, idéalement à balayage | Les cases ne deviennent connues qu’en étant mesurées | Un sonar balayé par servomoteur suffit à construire une grille grossière |
| De quoi visualiser une grille | Diagnostiquer un planificateur en regardant un robot est presque impossible | Affichez de l’ASCII sur le port série, ou utilisez les laboratoires de ce parcours |
Les deux laboratoires tournent entièrement dans le navigateur, donc vous pouvez accomplir les nœuds de remplissage et de couverture sans aucun matériel.
Pourquoi le parcours suit cet ordre
Le labyrinthe vient en premier parce que la carte y est gratuite. Dans un labyrinthe de micromouse, le monde est une grille par construction — les cases ont une taille connue, les murs sont sur les frontières de cases, et la position du robot est toujours un indice de case. Cela supprime d’un coup tout problème de perception et ne laisse que la planification, objet de votre venue ici. Le remplissage dans une grille connue est l’introduction la plus propre possible à « calcule un champ de distance, puis descends la pente ».
A vient deuxième parce qu’il retire les commodités du labyrinthe une à une.* Les cases ont désormais des coûts plutôt que de simples murs. La grille est plus grande, donc l’étendre en entier est du gaspillage et une heuristique devient rentable. Le robot a une largeur, donc les obstacles doivent être gonflés. Et les cases peuvent être inconnues, idée vraiment nouvelle dont le labyrinthe n’avait jamais besoin.
Les grilles d’occupation viennent troisièmes parce que c’est là que la carte cesse de vous être donnée. Le lancer de rayons convertit une mesure de distance en preuve sur de nombreuses cases à la fois — tout le long du rayon est plus probablement libre, le point d’arrivée plus probablement occupé — et mettre à jour ces deux séparément est toute la technique.
L’IMU se trouve ici délibérément. Elle arrive au nœud exact où l’erreur de cap commence à s’écrire dans la carte, car un gyroscope mesure la rotation directement et des roues qui glissent ne le peuvent tout simplement pas.
Le SLAM vient en dernier car c’est l’aveu que les nœuds précédents supposaient quelque chose de faux. Chaque planificateur ci-dessus travaille sur une pose, et chaque pose ci-dessus venait d’une odométrie qui dérive sans limite. Le SLAM est ce qui arrive quand on cesse de prétendre que cartographie et localisation peuvent être résolues séparément.
La couverture clôt le parcours car c’est le problème qui a le plus évidemment besoin d’une carte et qui le plus évidemment ne peut pas se faire en réactif. « Ai-je été partout ? » est une question à laquelle seule la mémoire peut répondre.
Étapes : comment savoir qu’une étape est acquise
| Étape | Le test | Ce à quoi ressemble la réussite |
|---|---|---|
| Remplissage | Affichez le champ de distance pour un petit labyrinthe | L’objectif est à 0, les valeurs croissent vers l’extérieur, et les murs créent les détours attendus |
| Replanification | Révélez un mur que le robot supposait ouvert | Le champ se met à jour et le prochain mouvement du robot change — sans réexplorer |
| Exactitude d’A* | Faites-le tourner sur une grille dont vous connaissez la réponse à la main | Même longueur que le plus court chemin calculé à la main, à chaque fois |
| Admissibilité | Gonflez délibérément votre heuristique d’un facteur 2 | La recherche accélère et la trajectoire s’allonge — vous avez vu le compromis |
| Coût diagonal | Planifiez en espace ouvert sur une grille 8-connexe | La trajectoire est une diagonale droite, pas un escalier ; les diagonales coûtent √2 |
| Gonflement d’obstacles | Planifiez devant un coin avec gonflement coupé, puis actif | Coupé, la trajectoire frôle le coin ; actif, elle dégage du rayon du robot |
| Grille d’occupation | Balayez un capteur devant une porte et affichez la grille | L’espace libre apparaît le long des rayons, les cellules occupées aux extrémités, l’inconnu derrière les murs |
| Gestion de l’inconnu | Demandez à votre planificateur de router en espace non cartographié | Il refuse, ou il s’engage délibérément — les deux conviennent, deviner non |
| Dérive | Roulez une boucle fermée et comparez le début et la fin de la carte | La carte ne se referme pas — cet écart est exactement ce pourquoi la fermeture de boucle existe |
| Couverture | Faites tourner un balayage planifié et une marche aléatoire à durée égale | Le balayage planifié couvre bien plus, et vous pouvez énoncer les deux pourcentages |
Où ce parcours s’arrête
Ce parcours planifie dans un monde statique, bidimensionnel, de taille connue. Chacun de ces mots est une limitation à nommer.
Statique. Rien ici ne gère une personne traversant le plan. Les obstacles dynamiques exigent un planificateur local tournant sous le planificateur global, en replanifiant bien plus vite qu’A* sur une grille entière ne le peut.
Bidimensionnel. Une grille de cellules libres et occupées est un plan d’étage. Elle ne peut pas représenter une table sous laquelle on peut passer mais à travers laquelle on ne peut pas passer, et c’est pourquoi les robots sérieux utilisent des représentations 3D ou des cartes de coûts en couches.
Basé sur grille. Les planificateurs par échantillonnage comme RRT et RRT* traitent les espaces de grande dimension — l’espace articulaire d’un bras robot, par exemple — où une grille est sans espoir. Ils échangent la garantie du plus court chemin contre la capacité de fonctionner.
Le parcours ne couvre pas non plus les filtres particulaires ou la localisation de Monte-Carlo, manière dont un robot se retrouve dans une carte donnée plutôt que dans une carte qu’il construit. C’est le problème le plus simple et de loin le plus fréquent, et il vaut la peine de savoir qu’il existe avant d’attraper le SLAM complet.
Parcours d'apprentissage
Le parcours
Suivez les nœuds dans l'ordre — chacun débloque le suivant une fois terminé. Votre progression est enregistrée sur cet appareil.
0 / 9 terminés
Questions courantes
Questions fréquentes
Quelle est la différence entre le remplissage et A* pour la planification robotique ?
Le remplissage calcule la distance de l'objectif à chaque case de la grille, pour que le robot descende ensuite la pente depuis l'endroit où il se trouve. A* cherche d'un départ unique vers un objectif unique et n'étend que les cases qu'une heuristique juge prometteuses. Le remplissage est le bon choix dans un labyrinthe de micromouse, car le robot y découvre constamment de nouveaux murs et doit replanifier depuis une nouvelle position toutes les quelques cases — avoir déjà calculé la distance de chaque case rend cela gratuit. A* est le bon choix sur une grande grille où l'on planifie une fois depuis un départ connu et où étendre toute la carte serait du gaspillage.
Pourquoi ma trajectoire A* racle-t-elle les coins des obstacles ?
Parce que vous avez planifié pour un point et que le robot a une largeur. La trajectoire est géométriquement valide dans la grille et physiquement une collision, car le planificateur n'a jamais su que le robot occupe plus d'une case. La correction standard consiste à gonfler chaque obstacle du rayon du robot avant de planifier — étendre les cases occupées vers l'extérieur — pour que toute trajectoire trouvée soit automatiquement dégagée pour le vrai robot. C'est bien plus simple et fiable que de tenter de vérifier le dégagement pendant la recherche.
Qu'est-ce qui rend une heuristique A* admissible, et pourquoi est-ce important ?
Une heuristique admissible ne surestime jamais le vrai coût restant jusqu'à l'objectif. Cette seule propriété garantit qu'A* renvoie le plus court chemin — surestimez quelque part et la recherche peut retenir un itinéraire qu'elle aurait dû rejeter. Les façons courantes de la briser sont d'utiliser la distance euclidienne sur une grille 4-connexe, où le vrai coût est Manhattan et toujours au moins aussi grand, et de gonfler délibérément l'heuristique pour accélérer la recherche. La seconde est une vraie technique, mais elle abandonne la garantie du plus court chemin, et vous devez savoir que vous l'abandonnez.
Faut-il le SLAM pour un robot amateur ?
Seulement quand le robot doit savoir où il est sur une longue mission dans un espace dont on ne lui a pas donné la carte. Si vous pouvez fournir une carte, la localisation seule est bien plus simple. Si l'espace est assez petit pour que la dérive odométrique reste tolérable — un labyrinthe, une pièce, quelques minutes de roulage — inutile non plus. Le SLAM mérite sa complexité quand les deux conditions échouent à la fois, et c'est un vrai seuil plutôt qu'un insigne : beaucoup de robots vraiment capables n'en ont jamais besoin.
Pourquoi ma carte en grille d'occupation se déforme-t-elle pendant que le robot roule ?
Parce que la dérive odométrique s'écrit dans la carte. Chaque balayage est placé à la pose que le robot croyait avoir, donc une estimation de cap lentement tournée inscrit un couloir droit comme une courbe dans la carte. Rien de la cartographie n'est faux — elle enregistre fidèlement une pose fictive. C'est précisément ce que corrige la fermeture de boucle : reconnaître que le robot est revenu à un endroit déjà visité, et corriger toute la trajectoire pour que les deux observations concordent.
Pourquoi ne pas traiter les cellules inconnues comme de l'espace libre ?
Parce qu'une case que rien n'a observée est non mesurée, pas vide, et la différence décide si le robot fonce dans des choses jamais vues. Traitez l'inconnu comme libre et le planificateur routera joyeusement par une région qu'aucun capteur n'a jamais couverte — qui est d'habitude exactement là où se trouvent les meubles, car espace occulté et espace occupé sont fortement corrélés. Gardez l'inconnu comme un troisième état distinct à côté de libre et occupé, et décidez délibérément si un planificateur donné peut y router.