Multi-Resolution POMDP Planning for Multi-Object Search in 3D

Autores: Kaiyu Zheng, Yoonchang Sung, George Konidaris, Stefanie Tellex · IROS 2021

Licenças

Acesso aberto
Artigo: CC BY 4.0

Tudo o que segue se baseia no artigo completo sob a licença CC BY 4.0; sua figura é mostrada com crédito aos autores.

Em resumo

Busca 3D de múltiplos objetos como POMDP, resolvida online por planejamento em paralelo em várias resoluções do octree; supera linhas de base planas em grandes espaços simulados e roda em um Kinova MOVO.

Por que importa

Leva a busca de objetos com POMDP de mapas 2D para regiões de busca 3D, mantendo o planejamento online dentro de um tempo fixo por passo. A crença em octree não precisa ser construída por completo, e a oclusão é tratada por meio de um rótulo de voxel UNKNOWN, sem modelos geométricos dos objetos que atrapalham.

Problema

Robôs domésticos precisam encontrar vários objetos em prateleiras, sob mesas e em armários com uma visão de câmera limitada, em forma de tronco de pirâmide, e com oclusão. A busca de objetos baseada em POMDP é fundamentada, mas trabalhos anteriores reduziam o espaço de busca ou a mobilidade do robô a 2D, porque a crença exata sobre grandes espaços de estados 3D é intratável e grandes espaços de observações dão aos planejadores um fator de ramificação alto.

Solução proposta

Os autores definem o 3D-MOS, um POMDP orientado a objetos com poses de câmera 6D, ações MOVE, LOOK e FIND, e observações formadas por voxels rotulados dentro do tronco de visão, fatoradas por objeto. Um modelo de observação por voxel e uma crença em octree dão atualizações exatas de crença em O(|V| log |G|) e amostragem em qualquer resolução em O(log |G|); POMDPs abstratos em resoluções mais grossas são resolvidos cada um pelo POUCT em paralelo, e a ação de maior valor é executada (MR-POUCT).

Principais ideias

Fatorar o estado e a observação por objeto faz o espaço de crenças crescer de forma linear, e não exponencial, com o número de objetos.
Modelar o rótulo de cada voxel separadamente, com voxels ocluídos ou fora da vista tratados como não informativos, reduz o espaço de observações para o planejamento e limita as atualizações de crença aos voxels visíveis.
Armazenar as crenças em um octree, em que cada nó guarda a soma dos valores de seus filhos, dá crenças exatas em todas as resoluções e amostragem em tempo logarítmico.
Planejar em várias resoluções em paralelo e executar a melhor ação permite lidar com tamanhos e distâncias de objetos desconhecidos aos quais uma única resolução não se ajustaria.
Crenças de partículas (POMCP) sofrem privação de partículas com grandes espaços de observações e degeneram em comportamento aleatório neste domínio.

Principais resultados

Em simulação com 12 configurações (lado do espaço de busca m ∈ {4, 8, 16, 32}, n ∈ {2, 4, 6} objetos, 40 ensaios cada), o MR-POUCT superou a busca exaustiva (Exhaustive) em recompensa acumulada descontada em todos os casos de teste com m = 16 e m = 32.
A busca exaustiva foi melhor nos espaços pequenos (m = 4 e 8), onde uma vista cobre até 17,2 % e 8,8 % da grade; com m = 32 uma vista cobre no máximo 2,6 %.
Cada método teve no máximo 3,0 s de planejamento por passo e de 120 s a 480 s no total, dependendo de m; o POMCP teve desempenho ruim por causa da privação de partículas.
Com ruído de sensoriamento na instância (16, 2, 10), o MR-POUCT foi consistentemente o melhor em todas as configurações testadas, e β quase não teve efeito enquanto β < 1. O texto fala em 5 configurações de α, mas lista seis valores (10, 100, 500, 10³, 10⁴, 10⁵).
Em um Kinova MOVO, o robô encontrou 3 de 6 objetos colocados em diferentes alturas em duas regiões de aproximadamente 10 m² × 2 m em cerca de 15 minutos, abaixando o torso quando necessário para ver um alvo.
Usar k = 10 ou k = 40 amostras de Monte Carlo para o modelo de observação abstrato deu desempenho de busca semelhante; foi usado k = 10.

Limitações

Supor que os objetos são independentes economiza computação, mas pode descartar dependências úteis entre objetos; a busca de objetos correlacionados fica em aberto (segundo os autores).
O modelo de observação não raciocina sobre a geometria dos objetos, e supõe-se que cada objeto caiba em um único voxel na resolução de planejamento (segundo os autores).
Foi usada uma política de rollout aleatória uniforme; os autores sugerem um rollout heurístico para problemas mais realistas, à custa da otimalidade.
No robô real, objetos não cobertos por nenhum ponto de vista do mapa topológico não foram encontrados; os autores propõem um mapa mais denso ou destinos MOVE amostrados.
Supõe-se que objetos e obstáculos são estáticos e que o estado do robô é observável, e em espaços de busca pequenos a simples busca exaustiva foi melhor.

Impacto na área

Ganhou o IROS 2021 Best RoboCup Paper Award e tem 33 citações. O artigo traz o link de uma página do projeto com vídeo das observações volumétricas e das atualizações de crença no octree; não informa a liberação de código.

Resumo

Robôs que operam em residências precisam encontrar objetos em prateleiras, sob mesas e em armários. Nesses ambientes, é crucial buscar de forma eficiente em escala 3D, lidando ao mesmo tempo com um campo de visão limitado e com a complexidade de buscar vários objetos. Abordagens fundamentadas para a busca de objetos frequentemente usam o processo de decisão de Markov parcialmente observável (POMDP) como arcabouço subjacente para calcular estratégias de busca, mas restringem o espaço de busca a 2D. Neste artigo, apresentamos uma formulação POMDP para a busca de múltiplos objetos em uma região 3D com um campo de visão em forma de tronco de pirâmide (frustum). Para resolver esse POMDP de forma eficiente, propomos um algoritmo de planejamento multirresolução baseado em busca em árvore de Monte Carlo online. Nessa abordagem, projetamos uma nova representação de crença baseada em octree para capturar a incerteza sobre os objetos-alvo em diferentes níveis de resolução e, em seguida, derivamos POMDPs abstratos em resoluções mais baixas, com espaços de estados e de observações drasticamente menores. A avaliação em um domínio 3D simulado mostra que nossa abordagem encontra objetos de forma mais eficiente e com mais sucesso do que um conjunto de linhas de base sem hierarquia de resolução em instâncias maiores, sob o mesmo requisito computacional. Demonstramos nossa abordagem em um robô móvel que encontra objetos colocados em diferentes alturas em duas regiões de 10m² × 2m movendo sua base e acionando seu torso.

Open Source Robotics