Simulateur de couverture pour robots aspirateurs

Commandes

Strategy bascule entre les trois. La pièce est reconstruite et l’essai redémarre immédiatement, car un chiffre de couverture n’a de sens que face à la pièce où il a été mesuré.

Tirez n’importe quel meuble avec le pointeur, ou appuyez sur 1–4 pour en sélectionner un et le déplacer avec les flèches du clavier. L’essai redémarre pendant que vous tirez. Placez une table au milieu du sol et regardez la distance du balayage planifié grimper pendant que sa couverture chute.

New room disperse à nouveau les meubles. Run speed arbitre entre fluidité et patience — la stratégie aléatoire a besoin de plusieurs milliers de mouvements pour finir, donc lancez-la en rapide.

Théorie

Un planificateur de trajectoire répond à comment y aller. Un planificateur de couverture répond à comment tout toucher, et les deux n’ont presque rien en commun.

Le seul étalon honnête est la distance dont un robot parfait aurait besoin. Avec un sol d’aire A et une brosse de largeur w, balayer chaque case une fois sans jamais repasser prend :

d_optimal = A / w

Tout ce que le labo rapporte est un multiple de ce nombre. Une stratégie à 1,2× passe 20 % de sa vie sur du sol déjà fait ; une à 8× y passe sept huitièmes.

Les rebonds aléatoires ont une forme fermée, et elle n’est pas encourageante. Un robot sans carte couvre du sol nouveau en proportion de ce qui reste non couvert, donc la surface non couverte décroît exponentiellement :

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

C’est la courbe en pointillés sur le tracé. Lisez-en trois points : 63 % du sol après une distance optimale, 90 % après 2,3, et 99 % après 4,6. Le dernier dixième de la pièce coûte le double des trois premiers quarts — le problème du collectionneur de coupons, avec une brosse.

La couverture systématique est linéaire, donc elle finit à 1× plus le surcoût de l’espacement des rangées et des virages. Dans ce labo, ce surcoût est d’environ 35 %.

Les essais mesurés atterrissent près de la théorie, et quand ils la manquent, c’est dans le sens attendu : une vraie marche aléatoire revisite le sol proche plutôt que de se téléporter, donc elle fait légèrement moins bien que ce que suggère la courbe d’échantillonnage indépendant.

Algorithme

Rebonds aléatoires. Avancez tout droit. Sur un contact, choisissez un nouveau cap au hasard et vérifiez qu’il est libre. C’est tout, et il faut un bit de détection et aucune mémoire.

Spirale, puis relocalisation. Tournez d’un angle inversement proportionnel à la distance parcourue depuis le centre, ce qui trace une spirale croissante. Sur un contact, foncez en ligne droite sur une distance fixe et recommencez une nouvelle spirale. Excellent sur sol dégagé — une spirale n’a presque aucun recouvrement — et sans recours dans une pièce encombrée, où chaque spirale est interrompue après quelques tours.

Serpentin planifié. Trois étapes, et la seconde est celle que l’on oublie :

1. Gonflez. Agrandissez chaque obstacle du rayon du robot plus une marge de sécurité. Ce qui reste est la zone où le centre du robot peut aller.
2. Découpez. Parcourez la carte gonflée en rangées espacées d’une largeur de brosse. Chaque rangée devient un ou plusieurs segments libres.
3. Reliez. Visitez les segments en ordre de serpentin, et routez entre segments consécutifs par un plus court chemin dans l’espace libre, pour que le robot contourne le canapé en roulant plutôt que de le heurter.

L’étape 3 est d’où vient le surcoût en distance, et c’est pourquoi une pièce encombrée punit un planificateur plus qu’une pièce vide.

Code source

La stratégie aléatoire est celle à avoir en premier sur un vrai robot, car elle fonctionne avec la détection que vous avez déjà :

// Random-bounce coverage. Two bump switches, no map, no encoders.
const uint8_t BUMP_L = 2, BUMP_R = 3;
const uint16_t CRUISE = 170;      // PWM
unsigned long turnUntil = 0;
int turnDir = 1;

void loop() {
  bool left  = digitalRead(BUMP_L) == LOW;   // switches are active-low with pull-ups
  bool right = digitalRead(BUMP_R) == LOW;

  if (millis() < turnUntil) {                 // still executing a bounce
    drive(turnDir * CRUISE, -turnDir * CRUISE);
    return;
  }

  if (left || right) {
    // Back off first — turning while wedged against a chair leg does nothing.
    reverseFor(320);
    // A random turn between 90 and 270 degrees. The randomness is what stops the
    // robot tracing the same closed loop around the room forever.
    turnDir = right ? -1 : 1;
    turnUntil = millis() + random(420, 1250);
    return;
  }

  drive(CRUISE, CRUISE);
}

L’angle de rebond doit être aléatoire. Une réflexion fixe transforme la pièce en billard, et une bille de billard sur une table rectangulaire trace un parcours fermé qui manque la majeure partie de la surface pour toujours.

Le balayage planifié exige le passage gonfler-découper-relier ci-dessus plus une odométrie assez bonne pour tenir une rangée droite, ce qui est une autre classe de robot. Prototypez-le ici, où la position est exacte par construction, avant de décider si votre matériel peut le porter.

Hypothèses et différences avec le matériel

Le labo donne au robot une odométrie parfaite, une carte parfaitement connue, des virages sur place instantanés et une brosse qui couvre un cercle net. Une vraie machine n’a rien de tout cela.

Le patinage des roues et la dérive du gyroscope écartent les rangées en une dizaine de rangées environ, c’est pourquoi les robots commerciaux se relocalisent par rapport aux murs, aux détails du plafond ou à une balise. Les virages prennent un temps auquel ce labo ne facture aucune distance. Et la brosse ne couvre pas un cercle — elle couvre un rectangle derrière le robot, donc reculer sur du sol déjà fait ne nettoie rien.

L’écart entre les stratégies survit à tout cela. Si un planificateur bat les rebonds aléatoires d’un facteur 3× ici, il les bat peut-être d’un facteur 2× sur du matériel réel ; l’ordre ne change pas.

Schéma de câblage

La détection se sépare nettement en trois tâches, et seule la première est exigée.

Contact. Deux microrupteurs sur un pare-chocs avant à ressort, câblés à niveau bas actif vers des broches compatibles interruption avec les résistances de rappel internes activées. C’est la détection qui rend les rebonds aléatoires possibles et c’est la dernière à tomber en panne.

Vide. Capteurs de réflectance vers le bas aux coins avant, lus à chaque passage de la boucle. Un parcours de couverture visite partout, y compris le haut des escaliers — le calcul de la distance parcourue par le robot au-delà du bord avant de pouvoir s’arrêter est détaillé ici.

Position. Codeurs en quadrature sur les deux roues, et un gyroscope si vous voulez des rangées qui restent parallèles. Seule la stratégie planifiée en a besoin, et en avoir besoin est toute la raison d’être des deux autres.

Pour les stratégies de couverture comme montage, voir le robot de couverture de pièce ; pour la couche réactive sous toutes ces stratégies, le simulateur d’évitement d’obstacles couvre les seuils d’arrêt et le balayage.