Planejamento de cobertura: varra um piso inteiro

Um problema diferente de chegar a algum lugar

A* encontra uma rota até um objetivo. Um planejador de cobertura precisa tocar em cada célula alcançável, o que muda completamente o objetivo: não há um destino para se aproximar, nenhuma heurística para guiar você, e o sucesso não é binário.

A métrica que substitui esse sucesso binário é a distância percorrida por metro quadrado varrido. Com área de piso A e uma escova de largura w, um robô perfeito varre cada célula uma única vez e nunca repete:

d_optimal = A / w

Um cômodo de 20 m² com uma escova de 250 mm exige 80 m. Todos os números abaixo são múltiplos desse valor, porque o ideal é a única referência que continua válida quando o cômodo muda.

A lei que governa a varredura sem mapa

Um robô que não sabe onde já passou cobre nova área do piso na proporção do quanto ainda está sem cobertura. Isso corresponde a uma equação diferencial cuja solução é:

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

Considere três pontos dessa curva e o comportamento de todo o problema fica evidente:

Os últimos 9% custam mais do que os primeiros 90%. Esse é o problema do coletor de cupons com uma escova acoplada, e é o único fato que explica todos os robôs aspiradores que você já observou.

O que realmente acontece

A teoria pressupõe que cada metro de percurso caia em uma região do piso escolhida independentemente. Um robô real se desloca em linhas retas, portanto metros consecutivos são correlacionados — ele continua revarrendo a área sobre a qual já está. Em medições realizadas em cinco cômodos no simulador de cobertura:

Três pontos dessa tabela valem mais do que o restante desta página.

Na primeira metade do piso, nada importa. As três estratégias apresentam diferenças de até 20% entre si em 50%. Um robô sem sensores e sem memória é realmente tão bom quanto um planejador na primeira metade do trabalho — exatamente por isso que a abordagem barata é viável comercialmente e por isso que observar superficialmente nunca revela a diferença.

O deslocamento aleatório é pior do que a própria teoria previa. São 6,76× contra os 4,61× previstos em 99%, porque um rebote em linha reta continua revisitando o piso que acabou de percorrer. Trate 1 − e^(−d) como um limite otimista, não como uma estimativa.

O planejador nunca conclui a varredura. Ele para em 90,4% e permanece ali, e isso não é um defeito.

Por que o planejador deixa um décimo do piso

Um planejador de cobertura precisa manter o corpo do robô afastado de cada parede e de cada perna de mesa. Por isso, aumenta as dimensões de cada obstáculo pelo raio do robô mais uma margem e planeja dentro do espaço restante. Tudo o que fica fora é piso ao qual o robô nunca poderá chegar.

Na execução medida, 130 das 133 células perdidas pelo planejador estavam a no máximo duas células de uma parede ou de um móvel. Apenas três estavam em piso aberto. As perdas não ficam espalhadas — formam um anel ao redor de cada obstáculo no cômodo.

Isso explica dois recursos presentes em todas as máquinas comerciais:

• A escova lateral que avança além do chassi. A escova é mais larga que a parte que entra em contato, portanto alcança áreas do piso às quais as rodas nunca chegam.
• A passagem junto às paredes. É um comportamento executado em uma etapa separada, porque a varredura sistemática não consegue realizá-lo.

O deslocamento aleatório acaba alcancando essas bordas por sorte — sua única vantagem.

Escolhendo as faixas

Para uma varredura sistemática, o único parâmetro real é o espaçamento entre as faixas.

Espaçar as faixas com distância exatamente igual a uma largura de escova deixa uma área não limpa entre elas para qualquer erro de orientação — e nada depois encontrará essa faixa, porque o plano considera o piso concluído. Com 10–20% de sobreposição, as faixas se fecham, ao custo de exatamente essa porcentagem em distância.

Essa sobreposição, somada à distância percorrida para contornar os móveis, explica o valor de 1,35× do planejador. Não é desperdício; é o preço de um plano que funciona em um robô real.

Mais duas escolhas importam mais do que parecem:

• Percorra as faixas ao longo do eixo longo do cômodo. Cada curva custa tempo e não cobre uma nova área do piso, portanto reduzir à metade o número de faixas reduz à metade o custo das curvas.
• Planeje o deslocamento entre trechos; não atravesse um trecho para o outro. Quando um móvel divide uma faixa em dois trechos, o robô precisa contorná-lo. Planejar esse deslocamento como o caminho mais curto pelo espaço livre é a diferença entre um plano e um desejo.

Os sensores que cada estratégia exige

Esta é a verdadeira razão para as três existirem.

O deslocamento aleatório precisa de um bit. “Bati em alguma coisa?” Dois interruptores de contato e um gerador de números aleatórios formam o robô inteiro. Sem encoders, mapa, localização nem nada que possa derivar.

A espiral precisa conhecer a distância percorrida desde o centro da espiral atual, que é uma odometria aproximada — suficiente para aumentar um raio, insuficiente para fechar um laço.

Uma varredura planejada precisa saber onde está. Faixas retas, ângulos de giro conhecidos e um deslocamento lateral de uma largura de escova dependem da odometria, e a odometria deriva. Após dez faixas, elas já não estão paralelas. É por isso que máquinas comerciais com planejamento também carregam um giroscópio, uma câmera no teto ou um farol — o planejador é barato, mas a localização que ele pressupõe não é.

Portanto, a estratégia é escolhida pelo orçamento de sensores, não pela elegância do algoritmo. Construa primeiro a versão aleatória: ela funciona, tem vinte linhas e fornece uma linha de base que o planejador precisa superar.

O que isso custa em minutos

Considere o cômodo de 20 m², uma escova de 250 mm e um robô que se desloca a 0,25 m/s:

Uma bateria representa um orçamento de distância. Uma autonomia de uma hora a 0,25 m/s equivale a 900 m, o que cobre confortavelmente um cômodo, mas não três, com estratégia aleatória — e isso, mais do que qualquer ideia algorítmica, impulsionou o mercado de robôs com mapeamento.

Quando dá errado

Execute as três no mesmo cômodo no simulador de cobertura — arraste os móveis enquanto ele funciona e os números mudam junto. Depois construa o robô de cobertura de cômodo, que começa com a estratégia que não precisa de nada e adiciona sensores apenas onde a medição mostra que vale a pena.