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

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

라이선스

• 오픈 액세스
• 논문: CC BY 4.0

아래 내용은 모두 논문의 라이선스(CC BY 4.0)에 따라 논문 전문을 바탕으로 하며, 그림에는 저자를 표기했습니다.

요약

3D 다중 물체 탐색을 POMDP로 정식화하고 여러 옥트리 해상도에서 병렬로 계획하여 온라인으로 푼다. 큰 시뮬레이션 공간에서 계층이 없는 기준선을 앞서며 Kinova MOVO에서 실행된다.

중요한 이유

POMDP 물체 탐색을 2D 지도에서 3D 탐색 영역으로 확장하면서도 온라인 계획을 단계당 고정된 시간 안에 유지한다. 옥트리 신념은 전체를 구축할 필요가 없으며, 가림은 잡다한 물체의 기하 모델 없이 UNKNOWN 복셀 레이블로 처리된다.

문제

가정용 로봇은 제한된 절두체 모양의 카메라 시야와 가림이 있는 상황에서 선반 위, 테이블 아래, 찬장 안의 여러 물체를 찾아야 한다. POMDP 기반 물체 탐색은 원칙적이지만, 이전 연구는 탐색 공간이나 로봇의 이동성을 2D로 축소했다. 큰 3D 상태 공간에 대한 정확한 신념은 계산상 다루기 어렵고, 큰 관측 공간은 계획기에 높은 분기 계수를 주기 때문이다.

제안 방법

저자들은 6D 카메라 자세, MOVE, LOOK, FIND 행동, 그리고 시야 절두체 안의 레이블이 붙은 복셀로 이루어진 관측을 물체별로 분해한 객체 지향 POMDP인 3D-MOS를 정의한다. 복셀별 관측 모델과 옥트리 신념은 O(|V| log |G|)의 정확한 신념 갱신과 O(log |G|)의 임의 해상도 샘플링을 제공한다. 더 거친 해상도의 추상 POMDP들은 각각 POUCT로 병렬로 풀리며, 가장 높은 가치의 행동이 실행된다(MR-POUCT).

핵심 통찰

• 상태와 관측을 물체별로 분해하면 신념 공간이 물체 수에 대해 지수적이 아니라 선형적으로 증가한다.
• 각 복셀의 레이블을 개별적으로 모델링하고 가려지거나 시야 밖에 있는 복셀은 정보가 없는 것으로 두면, 계획을 위한 관측 공간이 줄어들고 신념 갱신이 시야 안의 복셀로 한정된다.
• 각 노드가 자식 노드 값의 합을 저장하는 옥트리에 신념을 저장하면 모든 해상도에서 정확한 신념과 로그 시간 샘플링을 얻는다.
• 여러 해상도에서 병렬로 계획하고 가장 좋은 행동을 실행하면, 단일 해상도로는 맞출 수 없는 알려지지 않은 물체 크기와 거리에 대처할 수 있다.
• 입자 신념(POMCP)은 큰 관측 공간에서 입자 고갈을 겪으며 이 도메인에서는 무작위 행동 수준으로 성능이 떨어진다.

주요 결과

• 12개 설정(탐색 공간 한 변 m ∈ {4, 8, 16, 32}, 물체 수 n ∈ {2, 4, 6}, 각 40회 시행)의 시뮬레이션에서, MR-POUCT는 m = 16과 m = 32의 모든 테스트 사례에서 할인 누적 보상 기준으로 Exhaustive 탐색을 능가했다.
• Exhaustive 탐색은 한 번의 시야가 격자의 최대 17.2%와 8.8%를 덮는 작은 공간(m = 4와 8)에서 더 좋은 결과를 냈다. m = 32에서는 한 번의 시야가 최대 2.6%를 덮는다.
• 모든 방법은 m에 따라 단계당 최대 3.0 s의 계획 시간과 총 120 s에서 480 s의 시간을 가졌다. POMCP는 입자 고갈 때문에 성능이 낮았다.
• (16, 2, 10) 인스턴스의 센싱 잡음 조건에서 MR-POUCT는 시도한 모든 설정에서 일관되게 가장 좋았으며, β < 1인 동안 β는 거의 영향을 주지 않았다. 본문은 α의 설정이 5개라고 하지만 값은 6개(10, 100, 500, 10³, 10⁴, 10⁵)를 나열한다.
• Kinova MOVO에서 로봇은 대략 10 m² × 2 m인 두 영역에 서로 다른 높이로 놓인 물체 6개 중 3개를 약 15분 만에 찾았으며, 목표를 보기 위해 필요할 때 몸통을 낮췄다.
• 추상 관측 모델에 k = 10 또는 k = 40개의 몬테카를로 샘플을 사용한 경우 탐색 성능이 비슷했으며, k = 10이 사용되었다.

한계

• 물체들이 독립이라고 가정하면 계산은 절약되지만 물체 간의 유용한 의존성을 버릴 수 있다. 상관된 물체의 탐색은 미해결 과제로 남아 있다(저자들이 밝힘).
• 관측 모델은 물체의 기하를 추론하지 않으며, 각 물체는 계획 해상도에서 하나의 복셀에 들어간다고 가정한다(저자들이 밝힘).
• 균일 무작위 롤아웃 정책이 사용되었다. 저자들은 더 현실적인 문제에 대해 최적성을 희생하는 대신 휴리스틱 롤아웃을 제안한다.
• 실제 로봇에서는 위상 지도의 어떤 시점에서도 보이지 않는 물체를 놓쳤다. 저자들은 더 조밀한 지도나 샘플링된 MOVE 목적지를 제안한다.
• 물체와 장애물은 정적이고 로봇 상태는 관측 가능하다고 가정하며, 작은 탐색 공간에서는 단순한 전수 탐색이 더 좋은 결과를 냈다.

분야에 미친 영향

IROS 2021 Best RoboCup Paper Award를 수상했으며 인용 수는 33회이다. 논문은 체적 관측과 옥트리 신념 갱신을 보여주는 영상이 있는 프로젝트 페이지를 링크하며, 코드 공개는 명시하지 않는다.

초록

가정에서 작동하는 로봇은 선반 위, 테이블 아래, 찬장 안에 있는 물체를 찾아야 한다. 이러한 환경에서는 제한된 시야와 여러 물체 탐색의 복잡성에 대처하면서 3D 규모로 효율적으로 탐색하는 것이 매우 중요하다. 물체 탐색에 대한 원칙적 접근법은 탐색 전략을 계산하기 위한 기본 틀로 부분 관측 마르코프 결정 과정(POMDP)을 흔히 사용하지만, 탐색 공간을 2D로 제한한다. 본 논문에서는 절두체 모양의 시야를 가진 3D 영역에서의 다중 물체 탐색을 위한 POMDP 정식화를 제시한다. 이 POMDP를 효율적으로 풀기 위해, 온라인 몬테카를로 트리 탐색에 기반한 다중 해상도 계획 알고리즘을 제안한다. 이 접근법에서는 서로 다른 해상도 수준에서 목표 물체의 불확실성을 포착하는 새로운 옥트리 기반 신념 표현을 설계하고, 이어서 상태 공간과 관측 공간이 극적으로 작은 저해상도의 추상 POMDP를 유도한다. 시뮬레이션된 3D 도메인에서의 평가는, 동일한 계산 요구 조건에서 더 큰 인스턴스에 대해 우리의 접근법이 해상도 계층이 없는 일련의 기준선에 비해 더 효율적이고 성공적으로 물체를 찾는다는 것을 보여준다. 우리는 이동 로봇이 베이스를 이동하고 몸통을 구동하여 두 개의 10m² × 2m 영역에서 서로 다른 높이에 놓인 물체를 찾는 것으로 우리의 접근법을 시연한다.

링크

• 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
• 프로젝트 페이지: https://zkytony.github.io/3D-MOS/