Qual algoritmo devo implementar para programar um robô de limpeza de sala?

Para esta pergunta, suponha que as seguintes coisas sejam desconhecidas:

• O tamanho e a forma da sala
• A localização do robô
• A presença de quaisquer obstáculos

Suponha também que as seguintes coisas sejam constantes:

• O tamanho e a forma da sala
• O número, forma e localização de todos (se houver) obstáculos

E suponha que o robô tenha as seguintes propriedades:

• Só pode avançar em incrementos de unidades absolutas e girar em graus. Além disso, a operação que se move retornará true se for bem-sucedida ou false se não tiver se movido devido a uma obstrução
• Uma fonte de energia razoavelmente ilimitada (digamos que seja um robô movido a energia solar colocado em uma estação espacial que enfrenta o sol o tempo todo, sem teto)
• Todo movimento e rotação é realizado com precisão absoluta todas as vezes (não se preocupe com dados não confiáveis)

Por fim, considere as seguintes propriedades do ambiente do robô:

• Por estar em uma estação espacial sem teto, a sala fica a uma distância segura, mas frustrantemente próxima, da passagem de cometas, de modo que a poeira (e o gelo) estão constantemente cobrindo o ambiente.

Foi-me perguntada uma versão muito mais simples desta pergunta (a sala é um retângulo e não há obstáculos, como você a moveria, garantindo que você poderia passar por todas as partes pelo menos uma vez) e depois que comecei a pensar em como você abordaria isso se não pudesse garante a forma ou a presença de obstáculos. Comecei a analisar isso com o algoritmo de Dijkstra , mas fico fascinado ao saber como os outros abordam isso (ou se há uma resposta bem aceita para isso? (Como o Roomba faz isso?)

Até onde eu sei, esse problema não foi "resolvido".

Formalmente, esse é um problema de cobertura online. Cobertura, porque precisamos cobrir cada ponto no chão, e on-line, porque não temos acesso off-line ao mapa. Se você estiver interessado nos resultados mais recentes, sugiro que você pesquise " algoritmos de cobertura on-line robóticos ", talvez no google scholar (existem muitos e ótimos resultados). Além do (re) post muito colorido do @ embedded.kyle, adicionarei alguns detalhes (também tentarei encontrar rapidamente alguns resultados simples):

• Dijkstra's vai te dar um caminho, mas não necessariamente uma cobertura. Por exemplo, como você especifica para o Dijkstra que deve visitar cada ponto do gráfico, em vez de visitar um ponto o mais rápido possível? Você pode executar os caminhos mais curtos de todos os pares, mas quais são os pontos? Você não tem um mapa.

• Algoritmos on-line como esse são freqüentemente chamados de "bug", porque tendem a parecer um bug vagando por uma área, esbarrando em algo e depois vagando um pouco.

• Sem obstáculos, e uma sala retangular, e supondo que você comece no limite um caminho de boustrophedon (caminho do boi) é ideal.

Engraçado que os agricultores fazem isso sempre, certo? http://en.wikipedia.org/wiki/Boustrophedon . Isso pode ser estendido para salas com obstáculos, encontrando uma área aproximadamente retangular que está livre de obstáculos. Howie Choset trabalhou um pouco nisso .

• $\pi*d^2$$d$ é a distância até o ponto mais próximo). limite , certo?). Isso é útil: agora você tem a garantia de encontrar o limite mais próximo e pode rastreá-lo.
• Esta é uma área enorme e fascinante. Sinto muito, não posso fornecer um resumo melhor!

O maior problema é que você não tem um mapa. Sem um mapa, você está limitado a ações simples, como seguir o perímetro e mover-se ao longo de um caminho (como a espiral mencionada). Portanto, existem alguns robôs que realmente constroem o mapa durante a limpeza, decompõem a área mapeada em formas e cobrem cada forma para garantir a cobertura. Veja: http://mintcleaner.com/

O Roomba começa em espiral até atingir algo e depois faz uma varredura de perímetro. Então ele apenas salta. O Roomba é o padrão de fato nos aspiradores robóticos para uso doméstico, acho que você poderia chamá-lo de "solução aceita". Mas por experiência pessoal (possuo dois), definitivamente há espaço para melhorias.

De Como as coisas funcionam :

De uma entrevista com Nancy Dussault Smith, vice-presidente de comunicações de marketing da iRobot:

Quando ele começa, você notará um padrão em espiral, que se estenderá por uma área cada vez maior até atingir um objeto. Quando encontra um objeto, segue-o ao longo da borda do objeto por um período de tempo e, em seguida, inicia uma travessia rápida, tentando descobrir a maior distância possível sem atingir outro objeto, o que ajuda a descobrir qual o tamanho do espaço, mas se ele demorar muito tempo sem bater em uma parede, começará a espiralar novamente, porque mostra que está em um amplo espaço aberto e está constantemente calculando e calculando isso.

É semelhante aos sensores de sujeira embaixo, quando um desses sensores é acionado, ele muda seu comportamento para cobrir essa área. Em seguida, ele sai em busca de outra área suja em um caminho reto. Da maneira como esses diferentes padrões se acumulam, sabemos que essa é a maneira mais eficaz de cobrir uma sala.

Os padrões que escolhemos e como o algoritmo foi originalmente desenvolvido foram baseados em algoritmos baseados em comportamento nascidos no MIT que estudam animais e como eles procuram por comida nas áreas. Quando você olha como as formigas e as abelhas saem e pesquisam áreas, esse tipo de cobertura e a compreensão de tudo isso provém dessa pesquisa. Não é exato, obviamente, não estou dizendo que somos abelhas, mas é esse entendimento de como pesquisar uma área da natureza que é a base por trás de como nossa tecnologia adaptativa é desenvolvida.

Algumas fotos de longa exposição do Roombas com LEDs ilustram como funciona na prática:

Neato usa uma abordagem organizada. Usando SLAM e pára-choques, ele mapeia a sala 'atual', primeiro o perímetro, e depois aplica algum algoritmo para a limpeza da maneira mais eficiente possível. Eu nunca possuía um Roomba, mas, considerando o que li sobre seu algoritmo, nunca mudaria de um neato.

O Localizador de alcance a laser no neato é frequentemente canabilizado para robótica, pois é um sensor econômico para algoritmos SLAM.

Se eu recebesse sua tarefa, primeiro encontraria uma implementação SLAM adequada , com base no hardware que tinha.

Então eu usaria um algoritmo de planejamento CNC ISLAND Motion . Minha experiência é que eles tendem a ser muito eficientes em cobrir uma área arbitrária com a menor quantidade de movimento.

A primeira coisa que você precisa estabelecer é o objetivo do robô - não muito claro em sua pergunta. Há duas tarefas principais que seu robô deve realizar: descobrir a forma da área que pode ser limpa e depois limpá-la.

Mas a quantidade de sujeira é constante? A sujeira é adicionada constantemente? O seu objetivo é minimizar o tempo médio que a sujeira permanece no chão ou o tempo médio? O objetivo é manter o chão igualmente limpo? Ou é só limpar uma vez, o mais rápido possível? Existem padrões no acúmulo de sujeira que você pode medir e usar para sua vantagem na realização de seu objetivo?

A resposta a essas perguntas ajudará a orientar qual algoritmo você escolher. No caso do robô do Roomba, pode ser inútil aprender o layout exato da sala porque móveis (como cadeiras em torno de uma mesa), pessoas e outros obstáculos se movem com muita frequência. No entanto, no seu caso, talvez seja melhor explorar o espaço para criar um mapa completo (alguma combinação de um padrão de cortador de grama com arestas) e use esse mapa para calcular o caminho mais curto pelo espaço (o termo é "cobertura", e existem várias maneiras de fazê-lo, por exemplo , algoritmo de spanning tree ).

Mais uma coisa com a qual você precisa se preocupar é como discretizar o espaço em que está. Como você pode se mover em qualquer direção - mesmo com valores de graus inteiros e unidades inteiras de distância - suas posições X e Y podem ter fracionário valores. Você precisará decidir como representar obstáculos nesse mapa sem que ele cresça para um número infinito de pontos de dados.

Não tenho certeza se você ainda precisa, mas para aqueles que passaram pelo google para esse segmento, criei uma versão simples do algoritmo.

Basicamente, ele tenta construir o mapa da área enquanto limpa, e usa o mapa para encontrar o nó não ventilado mais próximo (parte da sala). Quando não consegue encontrar nada, isso significa que a sala está limpa (ou as partes não limpas são inacessíveis pelo robô).

Pode ser mais lento que outro algoritmo, mas pode garantir cobertura, independentemente da posição inicial, direção e obstáculos.

https://github.com/dungba88/cleaner_robot

ATUALIZAÇÃO: Fiz uma demonstração aqui e a comparei com um DFS de retorno. Portanto, mesmo que meu algoritmo seja O (N ^ 2), ele é muito mais otimizado em termos de número de movimentos e turnos.

http://jenova.dungba.org/cleaner/showdown

Olhando para o problema mais simples que lhe foi perguntado - uma sala retangular, sem obstáculos e limpe cada parte pelo menos uma vez.

A solução é encontrar um canto da sala, e encontrar um canto não será um grande problema. Uma vez que isso foi alcançado, basta seguir um caminho em espiral para o centro da sala.