1. 문제 정의 (Problem Statement)

기존의 실내 로봇 경로 계획 알고리즘들은 구성 공간 (C-space) 을 밀집하게 샘플링하여 경로를 찾지만, 환경이 크고 복잡해질수록 계산 비용이 급격히 증가하여 비효율적입니다. 또한, 이러한 계획기들은 다음과 같은 한계를 가집니다.

• 계산 비효율성: 좁은 통로나 시야가 제한된 실내 환경에서 휴리스틱이 제대로 작동하지 않아 탐색 시간이 길어집니다.
• 시맨틱 부재: 인간이 직관적으로 이해할 수 있는 의미 (방, 문, 복도 등) 를 고려하지 않아, 인간의 명령과 통합하기 어렵습니다.
• 확장성 부족: 기존 시맨틱 기반 방법들은 계층적이지 않거나, 대규모 환경에서 재계획 (Replanning) 시 비효율적입니다.

2. 방법론 (Methodology)

S-Path 는 3D 장면 그래프의 계층적 구조를 활용하여 전역 계획 문제를 작은 독립적인 부분 문제 (Subproblems) 로 분해하고 병렬로 해결하는 2 단계 프로세스를 따릅니다.

A. 입력 데이터 및 환경 설정

• 입력: 실내 3D 메트릭 - 시맨틱 장면 그래프 (방, 벽, 문의 위치 및 상태 포함) 와 메트릭 메시 (ESDF 기반).
• 컨투어 생성 (Contour Generation): 장면 그래프의 벽 정보를 기반으로 방과 문의 2.5D 컨투어 (폴리곤) 를 생성합니다. 이는 샘플링 영역을 제한하는 데 사용됩니다.

B. 1 단계: 시맨틱 계획 (Semantic Planning)

• 고수준 경로 탐색: A* 알고리즘을 사용하여 장면 그래프 상에서 시작점 (방) 에서 목표점 (방) 까지의 최단 시맨틱 경로를 찾습니다.
• 경로 분해: 이 고수준 경로는 일련의 "방 $\rightarrow$ 문 $\rightarrow$ 방" 시퀀스로 표현되며, 이를 통해 로봇이 통과해야 하는 관련 영역 (Room and Doorway Contours) 만을 식별합니다.
• 중간 웨이포인트: 각 문의 중심점을 웨이포인트로 설정하여 전체 경로를 여러 개의 부분 경로로 분할합니다.

C. 2 단계: 기하학적 계획 (Geometric Planning)

• 부분 문제 분해: 전체 경로를 "시작점 $\rightarrow$ 첫 번째 문", "문 $\rightarrow$ 문", "마지막 문 $\rightarrow$ 목표점"과 같은 독립적인 부분 문제로 나눕니다.
• 병렬 처리: 각 부분 문제는 해당 영역의 컨투어 (제한된 C-space) 내에서만 샘플링 기반 계획기 (OMPL 라이브러리 기반) 를 사용하여 병렬로 해결됩니다.
• 효율성: 전체 공간을 탐색하는 대신 관련 영역만 탐색하므로 샘플링 밀도가 높아지고 계산 시간이 단축됩니다.

D. 재계획 메커니즘 (Replanning)

• 상황 변화 대응: 문이 닫히거나 장애물이 생기면, 영향을 받은 부분의 시맨틱 그래프 가중치를 무한대로 설정하거나 업데이트합니다.
• 지식 재사용: 이미 해결된 부분 문제 (캐시된 경로) 는 재사용하고, 변경된 부분만 다시 계획합니다. 이는 재계획 지연 시간을 획기적으로 줄여줍니다.

3. 주요 기여 (Key Contributions)

1. 계층적 구조 활용: 실내 3D 장면 그래프의 계층적 구조를 활용하여 계획 영역을 관련 지역으로만 제한함으로써 탐색 공간을 축소했습니다.
2. 병렬 분해 전략: 전역 계획 문제를 독립적인 부분 문제로 분해하여 병렬 처리를 가능하게 하고, 계획 시간을 대폭 단축했습니다.
3. 자원 효율적 재계획: 영향을 받은 부분만 업데이트하고 이전 해결책을 재사용하는 전략을 도입하여 동적 환경에서의 재계획 속도를 높였습니다.
4. 해석 가능한 경로: 방과 문과 같은 시맨틱 개념을 활용한 인간이 이해하기 쉬운 경로 (예: "264 번 방에서 293 번 문을 통과하여 266 번 복도로 이동") 를 생성합니다.

4. 실험 결과 (Results)

실제 환경 (RF1, RF2) 과 합성 환경 (SF1, SF2) 에서 BIT*, PRM*, RRT* 등 기존 샘플링 기반 계획기와 비교 평가되었습니다.

• 계획 시간 단축: S-Path 는 평균 **6 배 (6×)*의 계획 시간 단축 효과를 보였습니다. 특히 PRM과 결합 시 평균 8.7 배, 재계획 시에는 최대 52 배까지 효율성이 향상되었습니다.
• 경로 최적성: 문 중심을 통과하도록 제약이 걸려 있어 경로 길이가 약간 길어질 수 있으나 (평균 +2.5%), 시간 단축에 비해 미미한 수준이며, 복잡한 시나리오에서는 오히려 기존 계획기보다 더 좋은 성능을 보였습니다.
• 병렬 처리 성능: 부분 문제의 수에 비례하여 병렬 실행 속도가 향상되었으며, 합성 환경에서는 더 큰 속도 향상을 보였습니다.
• 재계획 효율성: 장애물 발생 시, 기존에 계산된 경로를 재사용하여 불필요한 계산을 제거하고 신속하게 우회 경로를 생성했습니다.

5. 의의 및 결론 (Significance & Conclusion)

S-Path 는 3D 장면 그래프의 시맨틱 정보를 메트릭 계획기에 효과적으로 통합하여, 대규모 및 복잡한 실내 환경에서 로봇 경로 계획의 효율성과 해석 가능성을 동시에 달성했습니다.

• 실용성: 계산 비용이 적게 들기 때문에 실시간 응용에 적합하며, 인간과의 상호작용 (명령 이해 등) 을 용이하게 합니다.
• 한계 및 향후 과제: 현재는 문 중심 통과를 강제하므로 넓은 문의 경우 경로가 최적화되지 않을 수 있으며, 곡면 구조가 있는 복잡한 건축물에서는 컨투어 생성에 어려움이 있을 수 있습니다. 또한 초기 맵의 정확도를 전제로 하며 불확실성을 고려하지 않습니다.

이 연구는 로봇이 복잡한 실내 환경에서 더 빠르고 지능적으로 이동할 수 있는 새로운 패러다임을 제시하며, 특히 대규모 건물 내 자율 주행 로봇의 실용화에 중요한 기여를 합니다.