💻 computer science

POMDP-based Object Search with Growing State Space and Hybrid Action Domain

이 논문은 복잡한 실내 환경에서 이동 로봇의 객체 탐색 문제를 해결하기 위해, 성장하는 상태 공간과 하이브리드 행동 도메인을 가진 POMDP 프레임워크를 구축하고, 신경 프로세스 필터링과 k-센터 클러스터링을 활용한 새로운 온라인 솔버 GNPF-kCT 를 제안하여 기존 방법론보다 효율적이고 신뢰성 높은 탐색 성능을 입증했습니다.

원저자: Yongbo Chen, Hesheng Wang, Shoudong Huang, Hanna Kurniawati

게시일 2026-04-17

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yongbo Chen, Hesheng Wang, Shoudong Huang, Hanna Kurniawati

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

1. 문제 상황: 로봇의 '눈가림'과 '망설임'

상상해 보세요. 로봇이 방에 들어갔는데, 책상 위에는 컵, 노트북, 책 등 온갖 물건들이 쌓여 있습니다. 로봇은 찾고 싶은 '스낵 박스'가 어디 있는지 정확히 모릅니다.

문제: 로봇의 카메라 시야는 좁고, 다른 물건들이 가리고 있어서 (가려짐), 물건을 한 번에 다 볼 수 없습니다.
기존 방식의 한계: 기존의 로봇들은 "여기 있을 거야"라고 추측만 하거나, 너무 단순하게 움직여서 시간을 낭비하거나 실패했습니다.

2. 해결책: "스마트한 탐정"이 되다 (POMDP)

이 연구는 로봇을 단순한 기계가 아니라, **"불완전한 정보를 가지고 추리하는 스마트한 탐정"**으로 만들었습니다. 이를 수학적으로는 **POMDP(부분 관측 마르코프 결정 과정)**라고 부릅니다.

비유: 로봇은 "아마도 여기 있을 거야"라는 **믿음 (Belief)**을 가지고 시작합니다.
- "책상 왼쪽에 있을 확률이 30%, 오른쪽에 있을 확률이 70%"라고 생각하죠.
- 로봇이 움직여서 새로운 것을 보면, 이 믿음을 업데이트합니다. "아, 왼쪽은 비어있네? 그럼 오른쪽일 확률이 90% 로 올라갔어!"

3. 핵심 기술 3 가지: 로봇의 '초능력'

이 탐정 로봇이 어떻게 그렇게 똑똑해졌는지, 세 가지 핵심 비법을 소개합니다.

① "불필요한 행동은 걸러내는 필터" (Neural Process)

로봇이 할 수 있는 행동은 무궁무진합니다. (예: "왼쪽으로 1cm 이동", "머리를 0.5 도 회전"... 등) 모든 행동을 다 시도하면 시간이 너무 걸립니다.

비유: 마치 스마트한 비서가 로봇에게 "이건 안 될 거야, 저쪽만 봐"라고 조언하는 것과 같습니다.
기술: 인공지능 (신경 과정) 이 미리 학습해서, "이런 자세에서는 물건을 볼 확률이 거의 없어"라고 쓸데없는 행동을 미리 걸러냅니다. 그래서 로봇은 의미 있는 행동만 집중해서 시도합니다.

② "행동을 뭉쳐서 효율화하기" (k-center Clustering)

걸러낸 행동들도 여전히 너무 많습니다.

비유: "왼쪽으로 1cm, 1.1cm, 1.2cm..."를 하나씩 시도하는 대신, **"왼쪽 영역 전체"**를 하나의 덩어리로 묶어서 한 번에 탐색하는 것입니다.
기술: 비슷한 행동들을 **하위 구 (Hypersphere)**로 묶어서, 로봇이 "이쪽 영역을 자세히 찾아보자"라고 결정하게 합니다. 이렇게 하면 탐색 속도가 훨씬 빨라집니다.

③ "기억을 재활용하는 지혜" (Belief Tree Reuse)

로봇이 한 번 탐색한 경로를 매번 처음부터 다시 계산하면 비효율적입니다.

비유: 미로 찾기를 할 때, 이미 "여기서는 길이 막혔다"라고 확인한 길을 다시 탐색하지 않고, 그 기억을 바탕으로 새로운 길을 찾는 것과 같습니다.
기술: 로봇이 새로운 물건을 발견해서 상태가 변해도, 이전 탐색 기록 (나무 구조) 을 버리지 않고 수정해서 다시 사용합니다. 덕분에 복잡한 상황에서도 빠르게 다음 단계를 계획할 수 있습니다.

4. 특별한 전략: "가상의 목표물" (Guessed Target)

로봇이 물건을 아직 못 봤을 때, "아직 안 보인다는 건 어딘가에 있을 거야"라고 생각하며 가상의 목표물을 상상으로 설정합니다.

비유: "열쇠가 어디 있을지 모르니, 일단 '아마도 책상 위일 거야'라고 가정하고 그 주변을 집중적으로 훑어보자"는 전략입니다.
이 가상의 목표물을 통해 로봇은 적극적으로 움직여 가려진 물건을 치우거나 (Obstacle Removal), 시야를 넓히는 행동을 취하게 됩니다.

5. 실험 결과: 실제 로봇이 증명하다

연구자들은 이 방법을 Fetch와 Stretch라는 실제 로봇에게 적용했습니다.

결과: 기존의 방법들 (무작위 탐색, 다른 AI 모델 등) 보다 훨씬 더 빠르고 정확하게 숨겨진 물건을 찾아냈습니다.
특히, 물건이 빽빽하게 쌓여 있고 가려진 복잡한 상황에서도 다른 방법들은 실패하거나 시간이 오래 걸렸지만, 이 방법은 성공했습니다.

6. 요약: 왜 이 연구가 중요한가요?

이 논문은 로봇이 **"눈이 가려진 어지러운 환경"**에서도 스스로 판단하고, 물건을 치우며, 목표를 찾아내는 실제적인 능력을 갖게 했다는 점에서 중요합니다.

기존: "보이는 것만 보고 움직인다."
이 연구: "보이지 않는 것도 추론하고, 가려진 것을 치우며, 가장 효율적인 길을 찾아낸다."

마치 현명한 집사가 주인이 잃어버린 물건을 찾아주기 위해 방을 정리하고, 책상 위를 뒤지고, 서랍을 열어보는 것처럼, 로봇도 이제 스스로 지혜롭게 행동할 수 있게 된 것입니다.

1. 문제 정의 (Problem Definition)

이 논문은 복잡한 실내 환경 (선반, 테이블, 침대 등 다양한 가구와 물체가 혼재된 공간) 에서 모바일 로봇이 목표 물체를 효율적으로 찾고 제거하는 문제를 다룹니다. 이러한 작업은 다음과 같은 주요 도전 과제들로 인해 어렵습니다.

불완전한 관측 (Partial Observability): 로봇의 시야 (FOV) 제한, 국소화 오차, 그리고 다른 물체에 의한 가림 (Occlusion) 으로 인해 목표 물체를 항상 볼 수 없습니다.
증가하는 상태 공간 (Growing State Space): 로봇이 환경을 탐색하는 과정에서 새로운 물체들이 계속 발견되며, 이는 상태 공간이 실시간으로 확장됨을 의미합니다. 기존 POMDP 솔버는 새로운 상태가 발견될 때마다 신뢰 트리 (Belief Tree) 를 처음부터 다시 구축해야 하므로 계산 비용이 매우 큽니다.
하이브리드 행동 공간 (Hybrid Action Domain): 로봇의 행동은 연속적인 값 (기저 이동, 카메라 틸트/팬, 리프트 높이) 과 이산적인 값 (물체 선언, 장애물 제거) 이 혼합되어 있어, 기존 이산 공간 전용 솔버나 연속 공간 전용 솔버 모두 적용하기 어렵습니다.
불확실성: 물체의 위치, 크기, 이동 가능성 (Move-ability) 이 불확실하며, 로봇은 이를 직접 상호작용 (장애물 제거 등) 을 통해 확인해야 합니다.

2. 제안된 방법론 (Methodology: GNPF-kCT)

저자들은 위 문제를 해결하기 위해 GNPF-kCT (Growing Neural Process filtered k-center clustering Tree) 라는 새로운 온라인 POMDP 솔버를 제안했습니다. 이 프레임워크는 4 단계 (계획, 실행, 관측, 필터링) 를 반복하며 다음과 같은 핵심 기술들을 통합합니다.

가. POMDP 공식화 (POMDP Formulation)

상태 공간 (S): 로봇의 구성 (기저 위치, 리프트 높이, 카메라 각도) 과 모든 관측된 물체의 상태 (위치, 크기, 이동 가능성, 가림 상태) 를 포함합니다. 새로운 물체가 발견되면 상태 벡터에 추가되어 상태 공간이 성장합니다.
행동 공간 (A): 연속 행동 ( $A_c$ : 로봇 위치/자세 변경) 과 이산 행동 ( $A_d$ : 물체 선언, 제거) 의 곱집합으로 정의됩니다.
관측 공간 (O): 로봇 카메라의 시야 내에서 관측된 물체의 8 개 격자 (Grid) 의 로그-오즈 (Log-odds) 값 업데이트를 포함합니다.
추측된 목표 물체 (Guessed Target Object): 실제 관측되지 않은 목표 물체의 위치를 탐색하기 위해 가상의 목표 물체와 그리드 월드 모델을 도입하여 탐색 효율성을 높였습니다.

나. 신경 과정 필터링 (Neural Process Filtering)

목적: 고차원 연속 행동 공간에서 비효율적인 기본 행동 (Primitive Actions) 을 사전에 필터링하여 탐색 공간을 축소합니다.
기술: Neural Process (NP) 네트워크를 사용하여 특정 로봇 구성과 환경 상태 하에서 목표 물체의 격자 업데이트 확률 (Score) 을 예측합니다.
작동 원리: NP 네트워크는 평균 ( $\mu$ ) 과 분산 ( $\sigma$ ) 을 출력하며, $\mu > \beta^* \sigma$ 조건을 만족하는 행동들만 유효한 행동 집합으로 선정합니다. 이는 불필요한 행동을 제거하여 MCTS 의 효율성을 극대화합니다.

다. k-센터 클러스터링 트리 (k-center Clustering Tree)

목적: 필터링된 연속 행동 공간을 효율적으로 이산화하고 정제합니다.
기술: 유효한 행동들을 k-center clustering을 통해 고차원 초구 (Hypersphere) 단위로 그룹화합니다.
동적 정제 (Refinement): MCTS 탐색 과정에서 특정 행동 노드가 충분히 방문되면, 해당 초구를 더 작은 클러스터로 분할하여 행동 공간을 점진적으로 정밀화합니다. 이는 Lipschitz 연속성을 가정하여 최적 행동을 찾을 확률을 보장합니다.

라. 신뢰 트리 재사용 (Belief Tree Reuse)

문제 해결: 새로운 물체가 발견되어 상태 공간이 확장될 때, 기존에 구축된 신뢰 트리를 폐기하고 새로 구축하는 대신, 기존 트리를 재사용합니다.
기술: 상태 히스토리 ( $H_s$ ), 행동 - 관측 히스토리 ( $H$ ), 보상 히스토리 ( $H_r$ ) 를 저장해 두었다가, 새로운 관측이 들어오면 해당 히스토리를 업데이트하고 트리의 일부를 잘라내어 (Cutting) 새로운 상태에 맞게 확장합니다. 이는 계산 비용을 크게 절감합니다.

마. 수정된 UCB 전략 (Modified UCB)

MCTS 의 행동 선택 전략으로, 기존 UCB1 에 신뢰 거리 (Belief Distance, BD) 항과 초구 반경 (Hypersphere Range) 항을 추가하여, 상태 공간의 성장과 행동 공간의 불확실성을 고려한 탐색을 유도합니다.

3. 주요 기여 (Key Contributions)

현실적인 POMDP 공식화: 3D 환경에서 증가하는 상태 공간과 하이브리드 (연속 + 이산) 행동 공간을 고려한 완전한 POMDP 모델 제시.
효율적인 탐색 전략: 추측된 목표 물체 (Guessed Target Object) 와 그리드 월드 모델을 도입하여 정보 부족 상황에서 탐색 효율성을 향상.
혁신적인 솔버 (GNPF-kCT):
- 신경 과정 (NP) 을 활용한 행동 필터링으로 고차원 연속 공간 탐색 효율화.
- k-center 클러스터링을 통한 동적 행동 공간 정제.
- 신뢰 트리 재사용 기법으로 상태 공간 성장 시 계산 비용 절감.
실증적 검증: Fetch 및 Stretch 로봇을 이용한 Gazebo 시뮬레이션과 실제 사무실 환경 테스트를 통해 타 방법론 대비 우수한 성능 입증.

4. 실험 결과 (Results)

비교 대상: 기존 POMDP 솔버 (POMCP, POMCPOW, VOMCPOW), 제안 방법의 변형 (NPF-kCT, GPOMCP), 그리고 최신 비-POMDP 기반 방법 (SGoLAM, SayPlan, MoMa-LLM 등 LLM 기반) 과 비교.
성능:
- 성공률: 복잡한 시나리오 (Covered1, Complex1) 에서 95~100% 의 성공률을 기록하며, 기존 방법들 (특히 LLM 기반 방법) 보다 월등히 높았습니다.
- 단계 수 (Steps): 목표 물체 발견까지 필요한 행동 단계 수를 크게 단축했습니다.
- 누적 보상 (Cumulative Reward): 할인된 누적 보수가 모든 시나리오에서 가장 높았습니다.
- LLM 기반 방법과의 비교: LLM 기반 방법들은 단순한 탐색에서는 좋았으나, 장애물 제거와 같은 물리적 상호작용이 필요한 복잡한 시나리오에서는 성능이 급격히 저하되었습니다. 이는 LLM 이 물리적 제약과 불확실성을 정밀하게 모델링하지 못하기 때문입니다.
실제 로봇 테스트: Fetch 및 Stretch 로봇을 사용한 실제 실험에서 제안된 프레임워크가 실제 환경에서도 적용 가능함을 확인했습니다. (단, 물리적 행동 실패로 인해 성공률이 시뮬레이션보다 약간 낮았습니다.)

5. 의의 및 결론 (Significance)

이 논문은 모바일 로봇의 물리적 상호작용이 필요한 복잡한 객체 탐색 (Mechanical Search) 문제를 해결하는 데 중요한 진전을 이루었습니다.

불확실성 하의 최적 의사결정: POMDP 프레임워크를 통해 불완전한 정보와 물리적 제약 하에서도 최적의 탐색 전략을 수립할 수 있음을 증명했습니다.
계산 효율성: 증가하는 상태 공간과 하이브리드 행동 공간이라는 기존 POMDP 의 치명적인 한계를, 신경 과정 필터링과 신뢰 트리 재사용 기법으로 극복하여 실시간 적용 가능성을 높였습니다.
실용성: 사전에 정의된 3D 맵과 목표 물체 사진만 있으면 추가적인 기하학적 모델 없이도 작동할 수 있어, 실제 로봇 시스템에 적용하기 용이합니다.
향후 방향: LLM 과 같은 고급 추론 기술과 결합하거나, Vision-Language-Action (VLA) 모델을 통해 기본 행동 (Primitive Action) 의 성공률을 높이는 방향으로의 발전 가능성을 제시했습니다.

요약하자면, 이 연구는 복잡한 실내 환경에서 로봇이 장애물을 제거하며 목표 물체를 찾는 문제를 해결하기 위해, 신경망 기반 필터링, 동적 행동 공간 정제, 효율적 트리 재사용을 결합한 강력한 POMDP 솔버를 제안하고, 이를 통해 기존 방법론들보다 훨씬 빠르고 정확하게 작업을 수행함을 입증했습니다.