Simulador de caminhos de cobertura para robôs aspiradores

Controles

Estratégia alterna entre as três. A sala é reconstruída e a execução reinicia imediatamente, porque um resultado de cobertura só faz sentido quando comparado à sala em que foi medido.

Arraste qualquer móvel com o ponteiro ou pressione 1–4 para selecionar um e movê-lo com as setas. A execução reinicia enquanto você arrasta. Coloque uma mesa no meio do piso e veja a distância da varredura planejada aumentar enquanto sua cobertura diminui.

Nova sala espalha os móveis novamente. Velocidade de execução troca suavidade por paciência — a estratégia aleatória precisa de vários milhares de movimentos para terminar, então comece na velocidade rápida.

Teoria

Um planejador de caminho responde como eu chego lá. Um planejador de cobertura responde como eu toco em tudo isso, e os dois quase não têm nada em comum.

A única régua honesta é a distância que um robô perfeito precisaria percorrer. Com um piso de área A e uma escova de largura w, varrer cada quadrado uma vez e nunca repetir leva:

d_optimal = A / w

Tudo o que o laboratório relata é um múltiplo desse número. Uma estratégia em 1,2× gasta 20% do tempo de operação passando por piso que já fez; uma em 8× gasta sete oitavos dele.

A cobertura aleatória tem uma expressão fechada, e ela não é animadora. Um robô sem mapa cobre piso novo na proporção do que ainda está descoberto, portanto a área não coberta decai exponencialmente:

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

Essa é a curva tracejada no gráfico. Leia três pontos: 63% do piso após uma distância ideal, 90% após 2,3 e 99% após 4,6. O último décimo da sala custa o dobro dos três primeiros quartos — o problema do coletor de cupons, usando uma escova.

A cobertura sistemática é linear, portanto termina em 1× mais a sobrecarga que o espaçamento das faixas e as curvas causam. Neste laboratório, essa sobrecarga é de cerca de 35%.

As execuções medidas ficam próximas da teoria e, quando se afastam, se afastam na direção esperada: um passeio aleatório real revisita o piso próximo em vez de se teletransportar, portanto fica um pouco pior do que a curva de amostragem independente sugere.

Algoritmo

Cobertura aleatória. Siga em frente. Quando uma microchave de contato for acionada, escolha um novo rumo ao acaso e verifique se o caminho está livre. É tudo isso, e precisa de um bit de medição e nenhuma memória.

Espiral e depois reposicionamento. Vire por um ângulo inversamente proporcional à distância percorrida desde o centro, o que traça uma espiral em expansão. Quando uma microchave de contato for acionada, avance em linha reta por uma distância fixa e comece uma nova espiral. Excelente em piso aberto — uma espiral quase não tem sobreposição — e completamente inútil em uma sala cheia de móveis, onde cada espiral é interrompida após poucas voltas.

Varredura serpenteante planejada. Três etapas, e a segunda é aquela que as pessoas costumam pular:

1. Inflar. Aumente cada obstáculo pelo raio do robô mais uma margem de segurança. O que sobra é a região onde o centro do robô pode passar.
2. Recortar. Percorra o mapa inflado em faixas separadas por uma largura de escova. Cada faixa se torna um ou mais trechos livres.
3. Unir. Visite os trechos em ordem serpenteante e faça a rota entre trechos consecutivos com o caminho mais curto pelo espaço livre, para que o robô dirija ao redor do sofá, não para dentro dele.

A etapa 3 é onde vem a sobrecarga de distância, e é por isso que uma sala cheia de móveis penaliza mais um planejador do que uma sala vazia.

Código-fonte

A estratégia aleatória é a que vale ter primeiro em um robô real, porque funciona com a medição que você já tem:

// 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);
}

O ângulo de desvio precisa ser aleatório. Uma reflexão fixa transforma a sala em uma mesa de bilhar, e uma bola de bilhar em uma mesa retangular percorre um caminho fechado que perde a maior parte da superfície para sempre.

A varredura planejada precisa das etapas inflar–recortar–unir apresentadas acima e de odometria suficientemente boa para manter uma faixa reta, o que exige uma categoria diferente de robô. Prototipe-a aqui, onde a posição é exata por construção, antes de decidir se seu hardware consegue executá-la.

Premissas e diferenças do hardware

O laboratório dá ao robô odometria perfeita, um mapa perfeitamente conhecido, giros instantâneos no lugar e uma escova que cobre um círculo limpo. Uma máquina real não tem nenhum desses recursos.

Derrapagem das rodas e deriva do giroscópio separam as faixas depois de cerca de dez delas, e é por isso que robôs comerciais se relocalizam usando paredes, referências do teto ou um farol. Os giros levam tempo que este laboratório não cobra em distância. E a escova não cobre um círculo — cobre um retângulo atrás do robô; portanto, dar ré sobre piso já coberto não limpa nada.

A diferença entre as estratégias sobrevive a tudo isso. Se um planejador superar a cobertura aleatória em 3× aqui, talvez a supere em 2× no hardware real; a ordem não muda.

Diagrama do circuito

O sensoriamento se divide claramente em três funções, e somente a primeira é obrigatória.

Contato. Duas microchaves de contato em um para-choque frontal com mola, conectadas em ativo baixo a pinos capazes de gerar interrupção, com os pull-ups internos ativados. Esse é o sensoriamento que torna possível a cobertura aleatória e é a última coisa a falhar.

Queda. Sensores de refletância voltados para baixo nos cantos da frente, lidos a cada passagem pelo controlador. Uma execução de cobertura visita todos os lugares, inclusive o topo das escadas — a aritmética de quanto o robô percorre depois da borda antes de poder parar é resolvida aqui.

Posição. Encoders em quadratura nas duas rodas e um giroscópio se você quiser faixas que permaneçam paralelas. Somente a estratégia planejada precisa disso, e essa necessidade é a principal razão pela qual as outras duas existem.

Para realizar as estratégias de cobertura em um projeto, veja o robô de cobertura de sala; para a camada reativa subjacente a todas elas, o simulador de desvio de obstáculos cobre limiares de parada e varredura.