Simulador de labirinto de linha com simplificação LSRB

Controles

Modo escolhe entre a execução completa em três fases — explorar, simplificar e depois percorrer rapidamente — e a ir direto para a rota final. Velocidade de execução define a rapidez com que o robô dirige. Iniciar, Pausar e Passo executam continuamente ou um movimento por vez; Reiniciar repete o mesmo labirinto e Novo labirinto gera um novo. Mantenha o canvas em foco e use Espaço, N, R, M e F para acessar os mesmos controles pelo teclado.

A faixa de memória da rota abaixo do labirinto é a parte que vale observar. Ela é preenchida com um símbolo por movimento enquanto o robô dirige e depois se reescreve durante a fase de simplificação, a cada substituição.

Teoria

Um robô de labirinto de linha é construído em duas camadas, e mantê-las separadas é o que torna o problema tratável.

A camada inferior é um robô seguidor de linha comum. Uma matriz de refletância de oito canais lê a fita, as leituras são combinadas em um único erro ponderado e um controlador PID transforma esse erro em duas velocidades de roda diferentes. Esta camada nada sabe sobre labirintos.

A camada superior só acorda quando a fita se ramifica. Ela classifica o cruzamento — esquerda, direita, T, cruzamento completo, beco sem saída ou chegada — escolhe um ramo pela regra da mão esquerda e acrescenta um caractere a uma sequência. A barra desenhada na frente do robô neste simulador é essa matriz, e você pode ver um lado inteiro acender quando um ramo se abre.

O problema é que a leitura instantânea é ambígua. Um cruzamento em T, um cruzamento completo e o bloco de chegada relatam todos os canais pretos. O robô precisa avançar além do cruzamento e ler novamente antes de saber o que acabou de atravessar.

Algoritmo

A exploração usa a regra da mão esquerda: em cada célula, escolha a opção disponível mais à esquerda e só vire quando um beco sem saída não deixar outra opção. Em um labirinto sem ciclos, isso sempre alcança a chegada, e não exige manter estado, o que permite verificar o resultado manualmente.

Cada movimento acrescenta um símbolo. L, S e R registram movimentos para a esquerda, em frente e para a direita; B registra o retorno de 180° necessário depois de entrar em um beco sem saída. Portanto, cada B marca um retorno que precisa ser eliminado, junto com o movimento anterior e o movimento posterior.

Essa janela de três caracteres sempre pode ser substituída por uma única curva, porque os três movimentos são apenas ângulos que se somam. Contando esquerda como −90°, em frente como 0°, direita como +90° e retorno como 180°, L B L soma 0°, que é S — siga em frente em vez de entrar no desvio. As seis regras de substituição são essa aritmética, tabulada.

Uma passagem não basta: simplificar um desvio pode juntar duas curvas que agora formam uma nova janela redutível, portanto as regras são aplicadas repetidamente até nada mudar. Quando o ciclo termina, não resta nenhum B na sequência, o que prova que ela terminou — qualquer beco sem saída restante ainda mostraria um.

Código-fonte

// 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 é a tabela de substituições, e ela é curta porque contém apenas aritmética de ângulos: some as duas curvas dos dois lados da reversão de 180°, reduza o resultado ao intervalo de ±180° e mapeie-o de volta para um símbolo.

Premissas e diferenças do hardware

A fita é renderizada como preto perfeito sobre branco perfeito, sem enrolamento, reflexo ou sombra, e a matriz de refletância relata valores binários ideais a uma altura fixa. Uma matriz IR real vê reflexões em tons de cinza que mudam com a luz ambiente, a altura dos sensores e o desgaste da fita, portanto toda execução no hardware precisa calibrar branco e preto primeiro, como observam as notas de fiação. O simulador também executa o controlador PID com período perfeito e avança uma célula limpa por decisão; em um Arduino, a variação do intervalo de execução do controlador, a derrapagem das rodas e um deslocamento de montagem de 2 mm aparecem como classificações erradas de cruzamentos. Considere os ganhos e a sequência LSRB aqui como a lógica a transferir, não como números para copiar.

Diagrama do circuito

O robô que este laboratório modela é o do caminho de construção do solucionador de labirinto de linha: um Arduino Nano lendo uma matriz de refletância de oito canais em seus pinos analógicos e acionando dois motorredutores por meio de um TB6612FNG.

A regra de fiação mais importante é a divisão de alimentação. A bateria do motor deve alcançar o pino VM do driver e nada mais; os 5 V do Arduino alimentam apenas a lógica; e todos os terras — placa, driver, matriz de sensores e negativo da bateria — precisam estar conectados, ou os sinais de controle não terão referência e a falha será silenciosa.