Simulatore di labirinto a linee con instradamento LSRB

Controlli

Modalità sceglie tra l’esecuzione completa in tre atti — esplora, semplifica, poi percorri a velocità — e il salto diretto alla rotta finale. Velocità di esecuzione imposta quanto velocemente il robot guida. Avvia, Pausa e Passo lo eseguono continuamente o una mossa alla volta, Reimposta riproduce lo stesso labirinto e Nuovo labirinto ne genera uno nuovo. Porta il focus sul canvas e usa Space, N, R, M e F per gli stessi controlli dalla tastiera.

La striscia della memoria del percorso sotto il labirinto è la parte da guardare. Si riempie di un simbolo per mossa mentre il robot guida, poi si riscrive durante la fase di semplificazione man mano che scatta ogni sostituzione.

Teoria

Un robot per labirinti a linee è costruito in due strati, e tenerli separati è ciò che lo rende gestibile.

Lo strato inferiore è un normale robot seguilinea. Un array di riflettanza a otto canali legge il nastro, le letture collassano in un unico errore ponderato e un anello PID trasforma quell’errore in due velocità diverse delle ruote. Questo strato non sa nulla dei labirinti.

Lo strato superiore si attiva solo quando il nastro si ramifica. Classifica la giunzione — sinistra, destra, T, incrocio, vicolo cieco o arrivo — sceglie un ramo con la regola della mano sinistra e aggiunge un carattere a una stringa. La barra disegnata sul muso del robot in questo simulatore è quell’array e puoi guardare un lato intero accendersi quando si apre un ramo.

Il problema è che la lettura istantanea è ambigua. Una giunzione a T, un incrocio e il blocco di arrivo riportano ogni canale nero. Il robot deve superare la giunzione e leggere di nuovo prima di sapere cosa abbia appena attraversato.

Algoritmo

L’esplorazione usa la regola della mano sinistra: in ogni cella sceglie l’opzione più a sinistra e torna indietro solo quando un vicolo cieco non lascia alternative. In un labirinto senza anelli arriva sempre all’arrivo ed è abbastanza senza stato da poter verificare a mano.

Ogni mossa aggiunge un simbolo. L, S e R sono svolte; B compare solo dove il robot è tornato indietro da un vicolo cieco. Quindi ogni B nella stringa finale segna un errore, insieme alla svolta prima e alla svolta dopo.

Quella finestra di tre caratteri è sempre sostituibile da una singola svolta, perché le tre mosse sono soltanto angoli che si sommano. Contando la sinistra come −90°, il dritto come 0°, la destra come +90° e l’indietro come 180°, L B L dà 0°, cioè S: guida dritto invece di entrare nel ramo laterale. Le sei regole di sostituzione sono questa aritmetica, tabulata.

Una passata non basta: ripiegare una deviazione può accostare due svolte che ora formano una nuova finestra riducibile, quindi le regole vengono applicate ripetutamente finché non cambia più nulla. Quando il ciclo termina non resta alcun B nella stringa, ed è la prova che il percorso è finito: un eventuale vicolo cieco residuo mostrerebbe ancora uno.

Codice sorgente

// Repeat until a full pass changes nothing: collapsing one detour
// can push two turns together that are themselves reducible.
void simplify(String& route) {
  bool changed = true;
  while (changed) {
    changed = false;
    for (int i = 1; i + 1 < route.length(); i++) {
      if (route[i] != 'B') continue;          // windows centre on a turn-back
      route = route.substring(0, i - 1)
            + fold(route[i - 1], route[i + 1])
            + route.substring(i + 2);
      changed = true;
      break;
    }
  }
}

fold è la tabella di sostituzione ed è breve perché contiene solo aritmetica degli angoli: somma le due svolte ai lati dell’inversione di 180°, riporta il risultato nell’intervallo ±180° e mappa di nuovo il risultato su un simbolo.

Ipotesi e differenze hardware

Il nastro è reso come nero perfetto su bianco perfetto, senza arricciamento, riflessi o ombre, e l’array di riflettanza riporta valori binari ideali a un’altezza fissa. Un array IR reale vede riflessi in scala di grigi che cambiano con la luce ambiente, l’altezza del sensore e l’usura del nastro, quindi ogni esecuzione hardware deve prima calibrare bianco e nero con una scansione, come spiega la sezione sul cablaggio. Il simulatore esegue anche l’anello PID con un periodo perfetto e avanza di una cella pulita per ogni decisione; su un Arduino compaiono come classificazioni errate delle giunzioni il jitter del ciclo, lo slittamento delle ruote e un offset di montaggio di 2 mm. Tratta i guadagni e la stringa LSRB qui presentati come logica da trasferire, non come numeri da copiare.

Schema elettrico

Il robot modellato da questo laboratorio è quello del percorso di costruzione del risolutore di labirinto a linee: un Arduino Nano che legge un array di riflettanza a otto canali sui pin analogici e aziona due motori con riduttore tramite un TB6612FNG.

La regola di cablaggio più importante è la separazione dell’alimentazione. La batteria dei motori raggiunge il pin VM del driver e nient’altro; i 5 V dell’Arduino alimentano solo la logica; ogni massa — scheda, driver, array di sensori, polo negativo della batteria — deve essere collegata insieme, altrimenti i segnali di controllo non hanno riferimento e il fallimento è silenzioso.