Planification de couverture : balayer tout un sol

Un problème différent d’arriver

A* trouve un itinéraire vers un but. Un planificateur de couverture doit toucher chaque case atteignable, ce qui change complètement l’objectif : aucun but dont se rapprocher, aucune heuristique pour guider, et un succès non binaire.

La mesure qui le remplace est la distance par mètre carré balayé. Avec une surface A et un outil de largeur w, un robot parfait balaye chaque case une fois et ne répète jamais :

d_optimal = A / w

Une pièce de 20 m² avec une brosse de 250 mm exige 80 m. Chaque nombre ci-dessous est un multiple de cela, car un multiple est la seule comparaison qui survit à un changement de pièce.

La loi qui régit le balayage sans carte

Un robot sans idée d’où il est passé couvre du sol neuf en proportion du sol encore non couvert. C’est une équation différentielle à une seule réponse :

covered(d) ≈ 1 − e^(−d / d_optimal)

Lisez-en trois points et la forme du problème apparaît :

Les 9 derniers pour cent coûtent plus que les 90 premiers. C’est le problème du collectionneur de coupons avec une brosse attachée, et c’est le seul fait qui explique chaque aspirateur robot jamais observé.

Ce qui se passe vraiment

La théorie suppose que chaque mètre tombe sur du sol choisi indépendamment. Un vrai robot roule en lignes droites, donc les mètres consécutifs sont corrélés — il rebalaye sans cesse la zone où il se trouve déjà. Mesuré sur cinq pièces dans le simulateur de couverture :

Trois points de ce tableau valent plus que le reste de cette page.

Pour la première moitié du sol, rien ne compte. Les trois stratégies tiennent en 20 % à 50 %. Un robot sans détection ni mémoire est vraiment aussi bon qu’un planificateur pour la première moitié du travail — exactement pourquoi l’approche bon marché est commercialement viable et pourquoi l’observation occasionnelle ne révèle jamais la différence.

L’aléatoire fait pire que sa propre théorie. 6,76× contre 4,61× prédits à 99 %, car un rebond en ligne droite revisite sans cesse le sol tout juste fait. Traitez 1 − e^(−d) comme la borne optimiste, pas l’estimation.

Le planificateur ne finit jamais. Il s’arrête à 90,4 % et y reste, et ce n’est pas un bogue.

Pourquoi le planificateur laisse un dixième du sol

Un planificateur de couverture doit garder le corps du robot à l’écart de chaque mur et pied de table, il gonfle donc chaque obstacle du rayon du robot plus une marge et planifie dans ce qui reste. Tout ce qui tombe dehors est du sol où le robot ne peut jamais rouler.

Dans l’essai mesuré, 130 des 133 cases manquées par le planificateur étaient à deux cases d’un mur ou d’un meuble. Trois seulement en plein sol. Les manques ne sont pas dispersés — c’est un anneau autour de chaque obstacle de la pièce.

Ce qui explique deux traits de toute machine commerciale :

• La brosse latérale qui dépasse le châssis. La brosse est plus large que ce qui entre en collision, elle atteint donc du sol jamais accessible aux roues.
• Le passage de suivi de mur. C’est un comportement séparé, exécuté séparément, car le balayage systématique ne peut structurellement pas le faire.

Le rebond aléatoire atteint ces bords à terme, par chance, seule chose où il excelle.

Choisir les rangées

Pour un balayage systématique, le seul vrai paramètre est l’espacement des rangées.

Espacez les rangées d’exactement une largeur de brosse et la moindre erreur de cap laisse une bande non nettoyée entre elles — que rien ne retrouvera plus tard, car le plan croit ce sol fait. Recouvrez de 10–20 % et les bandes se ferment, pour exactement ce pourcentage en distance.

Ce recouvrement, plus la distance de transit autour des meubles, est l’origine du 1,35× du planificateur. Ce n’est pas du gaspillage ; c’est le prix d’un plan qui survit au contact d’un vrai robot.

Deux autres choix qui comptent plus qu’il n’y paraît :

• Rangez les rangées selon l’axe long de la pièce. Chaque virage coûte du temps et ne couvre aucun sol neuf, donc diviser le nombre de rangées par deux divise le coût des virages.
• Reliez les tronçons par itinéraire, ne roulez pas entre eux. Quand un meuble coupe une rangée en deux tronçons, le robot doit contourner. Planifier ce transit comme plus court chemin en espace libre sépare un plan d’un vœu.

La détection qu’exige chaque stratégie

C’est la vraie raison d’être des trois.

Le rebond aléatoire exige un bit. Ai-je touché quelque chose. Deux contacts de collision et un générateur aléatoire forment tout le robot. Ni encodeurs, ni carte, ni localisation, et rien qui dérive.

La spirale exige de savoir quelle distance parcourue depuis le centre de la spirale courante, soit une odométrie grossière — assez bonne pour agrandir un rayon, pas pour boucler une boucle.

Un balayage planifié exige de savoir où l’on est. Rangées droites, angles de virage connus, et pas latéral d’une largeur de brosse sont tous des affirmations odométriques, et l’odométrie dérive. Dix rangées plus loin, les rangées ne sont plus parallèles. D’où un gyroscope, une caméra de plafond ou une balise sur toute machine commerciale qui planifie — le planificateur est bon marché et la localisation supposée ne l’est pas.

La stratégie se choisit donc au budget de détection, pas à l’élégance de l’algorithme. Construisez d’abord l’aléatoire : elle marche, elle fait vingt lignes, et elle donne une référence que le planificateur devra battre.

Ce que cela coûte en minutes

Prenez cette pièce de 20 m², une brosse de 250 mm et un robot à 0,25 m/s :

Une batterie est un budget de distance. Une heure d’autonomie à 0,25 m/s fait 900 m, ce qui couvre largement une pièce en aléatoire et ne couvre pas trois — et c’est, plutôt que toute intuition algorithmique, ce qui a poussé le marché vers les robots cartographes.

Quand ça tourne mal

Testez les trois sur la même pièce dans le simulateur de couverture — déplacez les meubles pendant l’exécution et les nombres bougent avec. Puis construisez le robot de couverture de pièce, qui part de la stratégie sans besoin et n’ajoute de la détection que là où la mesure dit que cela paie.