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

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

Licencias

• Acceso abierto
• Artículo: CC BY 4.0

Todo lo que sigue se basa en el artículo completo bajo su licencia CC BY 4.0; su figura se muestra con crédito a los autores.

En resumen

Búsqueda 3D de múltiples objetos como POMDP, resuelta en línea planificando en paralelo a varias resoluciones del octree; supera a las líneas base planas en espacios simulados grandes y funciona en un Kinova MOVO.

Por qué importa

Lleva la búsqueda de objetos con POMDP de mapas 2D a regiones de búsqueda 3D, manteniendo la planificación en línea dentro de un tiempo fijo por paso. La creencia en octree no tiene que construirse por completo, y la oclusión se gestiona mediante una etiqueta de vóxel UNKNOWN, sin modelos geométricos de los objetos que estorban.

Problema

Los robots domésticos deben encontrar varios objetos en estanterías, bajo mesas y en armarios con una vista de cámara limitada, en forma de tronco de pirámide, y con oclusión. La búsqueda de objetos basada en POMDP es fundamentada, pero los trabajos anteriores reducían el espacio de búsqueda o la movilidad del robot a 2D, porque la creencia exacta sobre grandes espacios de estados 3D es intratable y los espacios de observaciones grandes dan a los planificadores un factor de ramificación alto.

Solución propuesta

Los autores definen 3D-MOS, un POMDP orientado a objetos con poses de cámara 6D, acciones MOVE, LOOK y FIND, y observaciones formadas por vóxeles etiquetados dentro del tronco de visión, factorizadas por objeto. Un modelo de observación por vóxel y una creencia en octree dan actualizaciones exactas de la creencia en O(|V| log |G|) y muestreo a cualquier resolución en O(log |G|); los POMDP abstractos a resoluciones más gruesas se resuelven cada uno con POUCT en paralelo y se ejecuta la acción de mayor valor (MR-POUCT).

Ideas clave

• Factorizar el estado y la observación por objeto hace que el espacio de creencias crezca de forma lineal, y no exponencial, con el número de objetos.
• Modelar la etiqueta de cada vóxel por separado, con los vóxeles ocluidos o fuera de la vista como no informativos, reduce el espacio de observaciones para la planificación y limita las actualizaciones de la creencia a los vóxeles visibles.
• Almacenar las creencias en un octree, donde cada nodo guarda la suma de los valores de sus hijos, da creencias exactas a cada resolución y un muestreo en tiempo logarítmico.
• Planificar a varias resoluciones en paralelo y ejecutar la mejor acción permite afrontar tamaños y distancias de objetos desconocidos a los que no se ajustaría una sola resolución.
• Las creencias de partículas (POMCP) sufren privación de partículas con espacios de observaciones grandes y degeneran en un comportamiento aleatorio en este dominio.

Resultados principales

• En simulación con 12 configuraciones (lado del espacio de búsqueda m ∈ {4, 8, 16, 32}, n ∈ {2, 4, 6} objetos, 40 ensayos cada una), MR-POUCT superó a la búsqueda exhaustiva (Exhaustive) en recompensa acumulada descontada en todos los casos de prueba con m = 16 y m = 32.
• La búsqueda exhaustiva fue mejor en los espacios pequeños (m = 4 y 8), donde una vista cubre hasta el 17,2 % y el 8,8 % de la cuadrícula; con m = 32 una vista cubre como máximo el 2,6 %.
• Cada método tuvo como máximo 3,0 s de planificación por paso y de 120 s a 480 s en total según m; POMCP rindió mal debido a la privación de partículas.
• Con ruido de sensado en la instancia (16, 2, 10), MR-POUCT fue sistemáticamente el mejor en todas las configuraciones probadas, y β casi no tuvo efecto mientras β < 1. El texto habla de 5 configuraciones de α, pero enumera seis valores (10, 100, 500, 10³, 10⁴, 10⁵).
• En un Kinova MOVO, el robot encontró 3 de 6 objetos colocados a distintas alturas en dos regiones de aproximadamente 10 m² × 2 m en unos 15 minutos, bajando el torso cuando era necesario para ver un objetivo.
• Usar k = 10 o k = 40 muestras de Monte Carlo para el modelo de observación abstracto dio un rendimiento de búsqueda similar; se usó k = 10.

Limitaciones

• Suponer que los objetos son independientes ahorra cálculo, pero puede descartar una dependencia útil entre objetos; la búsqueda de objetos correlacionados queda abierta (según los autores).
• El modelo de observación no razona sobre la geometría de los objetos, y se supone que cada objeto cabe en un solo vóxel a la resolución de planificación (según los autores).
• Se usó una política de rollout aleatoria uniforme; los autores sugieren un rollout heurístico para problemas más realistas, a costa de la optimalidad.
• En el robot real, se pasaron por alto los objetos no cubiertos por ningún punto de vista del mapa topológico; los autores proponen un mapa más denso o destinos MOVE muestreados.
• Se supone que los objetos y los obstáculos son estáticos y que el estado del robot es observable, y en espacios de búsqueda pequeños la simple búsqueda exhaustiva fue mejor.

Impacto en el campo

Ganó el IROS 2021 Best RoboCup Paper Award y tiene 33 citas. El artículo enlaza una página del proyecto con un vídeo de las observaciones volumétricas y de las actualizaciones de la creencia en octree; no indica la publicación de código.

Resumen

Los robots que operan en hogares deben encontrar objetos en estanterías, bajo mesas y en armarios. En tales entornos, es crucial buscar de forma eficiente a escala 3D, afrontando a la vez un campo de visión limitado y la complejidad de buscar varios objetos. Los enfoques fundamentados para la búsqueda de objetos suelen usar el proceso de decisión de Markov parcialmente observable (POMDP) como marco subyacente para calcular estrategias de búsqueda, pero restringen el espacio de búsqueda a 2D. En este artículo presentamos una formulación POMDP para la búsqueda de múltiples objetos en una región 3D con un campo de visión en forma de tronco de pirámide (frustum). Para resolver este POMDP de forma eficiente, proponemos un algoritmo de planificación multirresolución basado en la búsqueda en árbol de Monte Carlo en línea. En este enfoque, diseñamos una nueva representación de la creencia basada en octree para capturar la incertidumbre sobre los objetos objetivo a distintos niveles de resolución, y después derivamos POMDP abstractos a resoluciones más bajas con espacios de estados y de observaciones drásticamente más pequeños. La evaluación en un dominio 3D simulado muestra que nuestro enfoque encuentra objetos de forma más eficiente y con más éxito que un conjunto de líneas base sin jerarquía de resolución en instancias más grandes, con el mismo requisito computacional. Demostramos nuestro enfoque en un robot móvil que encuentra objetos colocados a distintas alturas en dos regiones de 10m² × 2m moviendo su base y accionando su torso.

Enlaces

• arXiv 2005.02878: https://arxiv.org/abs/2005.02878
• DOI 10.1109/IROS51168.2021.9636737: https://doi.org/10.1109/IROS51168.2021.9636737
• PDF: https://arxiv.org/pdf/2005.02878v4
• Página del proyecto: https://zkytony.github.io/3D-MOS/