L'algorithme d'évitement : détecter, balayer, tourner

Une fois qu’un robot peut lire une distance propre et balayer vers la direction libre, il reste une pièce : la logique qui décide quoi faire. C’est le cerveau d’un robot qui évite les obstacles — une courte boucle qui roule vers l’avant, remarque quand quelque chose est trop proche, regarde autour, et tourne vers l’espace. C’est plus simple qu’il n’y paraît, et le réussir consiste surtout à ne pas se coincer.

Réactif, pas planifié

Ce robot n’a pas de carte. Il réagit à ce qui est devant lui maintenant : détecter, décider, agir, répéter. C’est de la navigation réactive, et c’est la bonne première approche — bon marché, robuste, et assez pour errer dans une pièce encombrée sans rien heurter. Ce n’est pas la même chose que la planification de trajectoire, où un robot utilise une carte pour choisir un itinéraire à l’avance (c’est le territoire de A* sur grille d’occupation). L’évitement réactif est le fondement ; la planification vient après.

Le seuil d’arrêt

Tout tient à un nombre : à quelle proximité est trop près ? Choisissez une distance à laquelle le robot s’arrête et reconsidère. Trop petite et il racle les obstacles avant de réagir ; trop grande et il s’arrête à tout et avance nerveusement. La bonne valeur dépend de la vitesse — un robot plus rapide doit réagir plus tôt, parce qu’il couvre plus de terrain avant de pouvoir s’arrêter. Pour un petit robot à allure douce, 15–25 cm est un début sensé.

La machine à états

Un capteur de distance évite l’essentiel des obstacles ; un pare-chocs attrape ceux qu’il ne peut pas voir, et chaque robot qui tourne sans surveillance veut les deux.

La façon la plus propre d’exprimer le comportement est une machine à états finis : quelques états nommés avec des règles claires pour passer de l’un à l’autre. Elle remplace un enchevêtrement de if imbriqués par quelque chose de lisible et débogable. (Pour le motif général, voir les machines à états finis pour le comportement des robots.)

enum State { DRIVE, SCAN, TURN, REVERSE };
State state = DRIVE;
const int STOP_CM = 20;

void loop() {
  switch (state) {
    case DRIVE:
      driveForward();
      if (medianCm() < STOP_CM) { stopMotors(); state = SCAN; }
      break;

    case SCAN: {
      int a = bestAngle();            // servo sweep from the scan tutorial
      long open = distanceAt(a);
      if (open < STOP_CM)      state = REVERSE;   // nowhere to go
      else { turnToward(a); state = TURN; }
      break;
    }

    case TURN:
      if (turnComplete()) state = DRIVE;          // opening cleared, resume
      break;

    case REVERSE:
      backUp(400);                                // ms
      state = SCAN;                               // then look again
      break;
  }
}

Choisir le sens du virage

Le balayage a déjà fait le dur : il renvoie le relèvement le plus dégagé. Tournez par là. L’appel turnToward(angle) projette « dégagé à gauche » en pivot à gauche et « dégagé à droite » en pivot à droite, en utilisant la traction différentielle — une roue avant, l’autre arrière, pour pivoter à peu près sur place.

Éviter l’oscillation et les impasses

Deux modes de panne piègent les robots naïfs, et les deux ont des correctifs simples :

• L’hésitation entre gauche et droite dans un coin où les deux semblent pareils. Ajoutez une durée minimale de virage pour que le robot s’engage dans un virage au lieu de redécider à chaque boucle.
• Le coincement dans une impasse où chaque direction est bloquée. C’est à cela que sert l’état REVERSE : reculez, puis rebalayez. Un petit compteur de blocage — reculez plus fort si vous avez balayé plusieurs fois sans progrès — casse les pires pièges.

Réglage : vitesse contre distance de réaction

Deux boutons décident si le robot semble doux ou paniqué : vitesse de roulement et seuil d’arrêt. Montez la vitesse et vous devez monter le seuil pour garder la distance d’arrêt sûre — par v·t pour la latence et v²/2a pour le freinage, et c’est pourquoi doubler la vitesse fait plus que doubler le seuil. La façon la plus rapide de trouver une bonne paire est de les changer là où une erreur ne coûte rien — le simulateur d’évitement d’obstacles — et ensuite seulement de transférer les valeurs au matériel.

Hystérésis : deux seuils, pas un

La machine à états ci-dessus utilise un seul STOP_CM, et c’est la première chose à corriger. Un robot qui plane près d’un seuil bascule entre DRIVE et SCAN plusieurs fois par seconde, parce que de minuscules changements de mesure font basculer la comparaison. Il saccade au lieu de s’engager.

const int STOP_CM   = 20;   // stop when closer than this
const int RESUME_CM = 30;   // do not drive again until clearer than this

L’écart entre eux est l’hystérésis, et elle force le comportement à s’engager. Le même motif corrige presque toute oscillation pilotée par seuil dans le code robotique, pas juste celle-ci — un détecteur de bord, une alerte batterie basse, une approche d’accostage.

Une règle utile pour la taille de l’écart : faites-le plus grand que votre bruit de mesure plus la distance parcourue par le robot en une boucle. Pour un robot à 0,3 m/s avec un cycle de capteur de 60 ms, cela fait 18 mm de trajet plus quelques centimètres de dispersion ultrasonore — donc un écart de 10 cm est généreux et un écart de 3 cm cliquettera encore.

S’engager dans un virage

La seconde oscillation est au niveau décision : le robot tourne à gauche, le balayage semble désormais différent, il tourne à droite, et il hésite sur place. Deux mécanismes le corrigent :

unsigned long turnStartedAt = 0;
const unsigned long MIN_TURN_MS = 250;    // commit for at least this long

case TURN:
  if (millis() - turnStartedAt < MIN_TURN_MS) break;   // no re-deciding yet
  if (medianCm() > RESUME_CM) { stopTurn(); state = DRIVE; }
  break;

Une durée minimale de virage empêche le robot de réévaluer avant que le virage ait changé quoi que ce soit, et c’est contre le seuil de reprise plutôt que le seuil d’arrêt qu’il vérifie.

Détecter qu’on est coincé

REVERSE gère une impasse devant. Il ne gère pas le cas plus dur : un robot qui bouge techniquement, balaye et tourne, et n’arrive nulle part — un coin concave, ou une chaise autour de laquelle il tourne.

uint8_t scanCount = 0;
unsigned long lastProgressAt = 0;

// Called whenever the robot successfully drives forward for a while.
void notedProgress() { scanCount = 0; lastProgressAt = millis(); }

void escalate() {
  scanCount++;
  if (scanCount >= 3) {
    backUp(800);                    // back further
    pivot(random(120, 240));        // and turn a large, RANDOM amount
    scanCount = 0;
  } else if (millis() - lastProgressAt > 15000) {
    backUp(1200);
    pivot(180);                     // full about-turn
    lastProgressAt = millis();
  }
}

Deux points de conception valent d’être nommés ici.

L’escalade. La première réponse à un obstacle est un petit virage ; la troisième réponse à la même situation en est une grande. Une réponse fixe répétée est ce qui tient un robot dans un coin.

Le hasard. Un robot déterministe dans un piège symétrique fait le même choix à chaque fois et boucle indéfiniment. Une composante aléatoire dans le virage d’échappement casse la symétrie, et c’est la raison pour laquelle les premiers aspirateurs robots utilisaient le rebond aléatoire plutôt qu’une règle astucieuse — c’est vraiment robuste contre les pièges imprévus.

Lire les pare-chocs dans chaque état

La machine à états telle qu’écrite ne vérifie que la distance, et chaque capteur télémétrique a des surfaces qu’il ne peut pas voir. Un robot sans détection de contact pousse un rideau jusqu’à caler les moteurs.

Le contact doit être traité au-dessus de la machine à états, pas dans un état :

void loop() {
  updateBumpers();                       // debounced, from the bump-switch tutorial

  // Contact overrides whatever the robot thought it was doing.
  if (bumpLeft || bumpRight) {
    stopMotors();
    backUp(300);
    pivot(bumpLeft ? +60 : -60);         // turn AWAY from the side that hit
    state = SCAN;
    return;
  }

  switch (state) { /* ... as before ... */ }
}

Notez le signe : tournez loin de l’interrupteur qui a part. C’est exactement pourquoi deux interrupteurs valent leur place contre un — un interrupteur central unique dit que vous avez heurté quelque chose, et laisse le sens du virage au hasard.

Vitesse et seuil, en tableau

Le seuil d’arrêt n’est pas une constante ; c’est une fonction de la vitesse, parce que la distance de freinage croît avec le carré de la vitesse. Pour un robot avec 80 ms de latence de détection-décision, freinant à 1,0 m/s², un rayon de 90 mm et une marge de 50 mm :

Doubler la vitesse de 0,3 à 0,6 m/s ne double pas le seuil — mais il le fait croître de 76 %, et à 0,9 m/s le robot doit réagir à plus d’un demi-mètre. C’est pourquoi un robot qui évite fiablement au pas commence à heurter en accélérant, et pourquoi le correctif est un seuil dépendant de la vitesse plutôt qu’une grande valeur fixe qui rend le robot timide partout.

int stopThresholdCm(float speedMps) {
  const float latency = speedMps * 0.08f;             // 80 ms
  const float braking = (speedMps * speedMps) / 2.0f; // a = 1.0 m/s^2
  return (int)((latency + braking + 0.09f + 0.05f) * 100.0f);
}

Afficher l’état est l’outil de débogage

La ligne la plus utile à ajouter :

if (state != lastReportedState) {
  Serial.print(millis()); Serial.print(F(" -> "));
  Serial.println(STATE_NAMES[state]);
  lastReportedState = state;
}

Afficher sur changement plutôt qu’à chaque boucle garde la sortie lisible, et cela transforme un robot qui « se comporte parfois bizarrement » en relevé lisible. Presque chaque bogue de ce comportement est visible comme une séquence d’états insensée — un TURN qui ne finit jamais, un SCAN qui part quarante fois par seconde, un REVERSE qui réentre aussitôt.

Si vous ne pouvez pas répondre « que fait le robot maintenant » depuis une seule variable, la machine à états ne fait pas son travail.

Dépannage