T-PRM: Temporal Probabilistic Roadmap for Path Planning in Dynamic Environments

T-PRM: Temporal Probabilistic Roadmap for Path Planning in Dynamic Environments

Matthias Hu ̈ppi, Luca Bartolomei, Ruben Mascaro and Margarita Chli

 

https://ieeexplore.ieee.org/document/9981739

T-PRM: Temporal Probabilistic Roadmap for Path Planning in Dynamic Environments

 

Abstract

 

샘플링 기반 모션 플래너는 단순하고 계산이 효율적이기 때문에 로보틱스 분야에서 널리 사용된다. 그러나 가장 기본적인 형태에서 이런 알고리즘들은 정적인 환경을 가정하고 동작하며, 동적 (움직이는) 장애물과의 충돌을 피하는 능력이 부족하다. 이는 안전상의 문제점을 야기하며, 실제 환경에서 모바일 로봇의 활용 범위를 제한할 수 있다. 
본 연구는 동적 환경에서 장애물 회피를 수행하는 새로운 샘플링 기반 경로 계획 알고리즘인 Temporal-PRM을 제시한다. 제안된 접근 방식은 기존의 확률적 로드맵 (PRM)에 시간 개념을 확장하여, 본 논문에서 새롭게 소개하는 time-aware variant of the A* 알고리즘을 사용하여 효율적으로 탐색할 수 있는 확장된 그래프 구조를 생성한다. 이 설계는 부드러운 경로 찾기, 다중 쿼리 수행 능력같은 PRM의 특성을 유지하면서도, 계산 비용을 약간 증가시키는 것 만으로도 고도로 동적인 환경에서 충돌 회피를 가능하게 함으로써 PRM의 단점을 해결한다. 

 

Introduction

 

(충돌 없는 모션 플래닝의 필요성)

경로 계획 문제는 역사적으로 최적화 기반 접근법부터 샘플링 기반 접근법에 이르기까지 다양한 관점에서 다루어져 왔다. 전자의 경우, 최적의 경로를 찾기 위해 로봇 플랫폼과 작업 공간의 정확한 모델링을 필요로 한다. 샘플링 기반 접근법은 환경적 제약의 명시적 표현 없이도 로봇의 구성 공간에서 작동할 수 있다. 

이런 Path Planner 중에서 현재까지 가장 영향력이 있는 두 알고리즘은 PRM (Probabilistic Roadmap) 접근법과 RRT (Rapidly-exploring Random Tree) 방법이다. RRT 기반 접근법이 점진적 샘플링과 검색 체계를 사용하는 반면, PRM은 주어진 환경에서 상당한 사전 계산에 의존하여 매우 빠른 Mulriple planning query를 처리할 수 있다. 하지만 사전 처리 단계에서 충돌을 피하기 위한 정보가 필요하다는 점은 일반적으로 PRM 기반 알고리즘을 동적 시나리오에 배치하기 어렵게 만든다. 과거에 이 문제를 해결하기 위한 몇몇 연구들이 있었지만, 지금까지는 단일 쿼리 실행 모드만 지원하거나 쿼리 단계에서 추가적인 샘플링과 충돌 검사를 필요로 하여 경로 검색 과정을 느리게 만드는 방법들에 그쳤다. 

본 논문에서는 정적 및 동적 장애물을 모두 고려하는 새롭고 효율적인 다중 쿼리 경로 계획 접근법을 제시한다. T-PRM이라고 불리는 우리의 방법은 로드맵의 각 노드가 동적 장애물과 충돌하지 않는 시간 간격을 통합하여 표준 PRM 공식을 확장한다. 또한 이런 노드들의 time availability를 고려하고 해결 경로를 따라 time monotonicity 제약을 준수하는 A* 검색 알고리즘의 변형을 소개한다. 이를 통해 움직이는 장애물이 있는 상황에서도 그래프를 추가로 샘플링하거나 재구축할 필요 없이 빠르고 효율적인 쿼리가 가능해진다. 

본 논문의 주요 기여 :
- 정적 및 동적 환경에서 실시간 장애물 회피를 위한 T-RPM
- 시간 차원이 추가된 그래프에서 쿼리를 해결할 수 있는 개선된 A* qusgud
- 시뮬레이션과 실제 실험 모두에서 이루어진 평가

 

 

Related Works

 

샘플링 기반 모션 플래닝은 로보틱스에서 가장 많이 연구되는 주제 중 하나이다. 이런 모션 플래너는 일반적으로 문제의 정확한 모델링과 복잡한 constrained cost function의 계산을 필요로 하는 최적화 기반 솔루션보다 더 선호된다. 
수 년간 많은 플래너들이 제안되었지만 이 분야의 가장 중요한 이정표는 PRM과 RRT이다. 두 방법 모두 고차원 계획 문제를 해결할 수 있고 시작 구성에서 목표 구성까지 충돌 없는 경로를 생성할 수 있지만 차이점이 있다. 
RRT는 무작위로 샘플링된 상태들을 연결하여 목표를 향해 성장시키면서 시작 구성의 뿌리를 둔 트리를 반복적으로 구축한다. 반면 PRM은 이 과정을 두 개의 별도 단계로 나눈다. 먼저, 무작위로 샘플링된 구성들을 그래프로 연결하여 로드맵을 생성하고, 이후 시작점에서 목표점까지의 경로를 찾기 위해 이를 쿼리한다. 

(RRT 방법론들)

RRT의 경우와 마찬가지로, PRM 패러다임을 따르는 수많은 방법들도 원래 알고리즘의 특정 결함을 목표로 제안되었다. 특히, PRM은 좁은 간격을 통과하는 경로를 찾거나, 동적 환경에서 안전한 경로를 찾을 때 한계점이 있다. 

 

 

Methodology

 

우리의 목표는 정적 및 동적 장애물과의 충돌을 피하면서 시작 위치에서 주어진 목적지까지 안전한 경로를 생성하는 것이다. 
핵심은 로드맵을 구축하고 쿼리할 때 시간 차원을 고려하도록 원래의 PRM 알고리즘을 확장한 것에 있다. 우리의 T-PRM은 n차원 공간에서 움직이는 홀로노믹 로봇을 위해 개발되었다. 

A. 예비 지식 : 확률적 로드맵 (PRM)

로드맵은 노드 집합 V가 엣지 E로 연결된 무방향 그래프 G=(V,E) 형태의 데이터 구조이다. 그래프 G가 먼저 로봇의 자유 공간에서 구축되며, 엣지는 서로 다른 노드를 연결하는 실현 가능한 경로이다. 
PRM 알고리즘은 초기에 G를 구축하고 그 후 시작과 목표 구성 사이의 가장 짧고 충돌 없는 경로를 찾기 위해 이를 쿼리한다. 학습 단계 동안 노드는 로봇의 자유 구성 공간에서 무작위로 샘플링된다. 새로운 노드 v가 샘플링될 때, v에서 이미 G에 있는 이웃 노드들까지의 지역 경로를 생성할 수 잇다면 그래프 G에 연결된다. 
로컬 플래너는 노드 쌍 사이의 실현 가능한 경로를 찾는 데 사용되며, 검색이 성공적인 때 결과 엣지가 E에 추가된다. 이 단계는 주어진 시간이 소진되거나 최대 샘플 수에 도달할 때까지 계속된다.
쿼리 단계에서는 그래프 G를 사용하여 노드 사이의 경로를 찾는다. PRM이 원래 정적인 상황만 고려하기 때문에 그래프는 한 번만 구축된다. 따라서 동일한 기본 구조를 추가 샘플링 없이 여러 쿼리에 재사용할 수 있다. 

B. Temporal Probabilisctic Roadmaps

PRM은 환경이 정적이라고 가정하기 때문에 이 알고리즘은 동적 장면에서 장애물 회피를 수행하는 데 활용될 수 없다. 본 논문에서는 PRM과 유사하게 학습과 쿼리 단계를 분리된 상태로 유지하면서 그래프 G에 시간 개념을 통합하고 정적 장애물과 동적 장애물을 구분하는 것을 제안한다. 

1) 학습 단계

이동하는 물체를 반영하기 위해 우리는 노드에 TA (Time Availability)라는 개념을 도입한다. 이는 주어진 노드가 free (or available)하고 동적 장애물과 충돌하지 않는 time interval을 인코딩한다. 엣지에는 TA를 할당하지 않는다. 

장애물이 일정한 속도를 가진다고 가정하기 때문에 모든 노드 v에 대한 TAv는 그래프 G가 구축될 때 계산된다. 

 

*내가 이해한 부분*

 

1. TA는 각 노드가 "사용 가능한" 시간 구간들의 집합이다. 

2. 노드가 "사용 가능하다"라는 것은 해당 시점에 동적 장애물과 충돌하지 않는다는 의미이다. 

 

TAv = ∩ (모든 장애물 o에 대한 TAvo)

- TAv : 노드 v의 최종 TA

- TAvo : 장애물 o에 대한 노드 v의 TA

 

C. 다중 쿼리와 재계획

PRM의 원래 공식은 학습 단계에서 구축된 그래프를 재사용할 수 있다. 장애물의 속도를 알고 있다는 가정 때문에, T-PRM은 장애물의 움직임이 이미 로드맵에 통합되어 있으므로 동적 환경에서도 이 특성을 유지한다. 이 가정이 지켜지지 않는 경우, 우리의 알고리즘은 노드의 TA를 재계산하여 고정된 주기로 재계획을 수행하도록 조정될 수 있다.