PlannerFlows
Reference
PlannerFlows
Introduction
이 논문도 이전 Neural RRT* 와 비슷하게 sampling based motion planning의 전통적인 방식과 Neural Network를 결합하여 알고리즘의 효율을 개선 시키는 내용이다. sampling based 방식은 다양한 분야에서 활용되어져 왔다. 빠르게 공간을 탐색할 수 있지만 이전에는 무작위로 공간을 탐색하여 planning을 해왔기 때문에 최적 경로까지 도달하기 오랜 시간이 걸릴 뿐 아니라 샘플링 효율도 떨어진다. 이에 따라 효율적인 샘플링을 위해 생성모델을 이용한 샘플링 가이드를 제안한다. 해당 논문에서는 구성공간, 출발점과 도착점을 조건으로 하는 conditional normalizing flow 모델을 이용해 샘플링 가이드를 생성한다.
Normalizing Flow
생성모델에는 GAN, VAE, Flow-based 등 다양한 방식의 모델들이 존재한다. Normalizing Flow (NF)는 Flow-based model 중 하나의 방식이다.
NF 는 기본 분포 z (ex. gaussian or uniform distribution)를 여러 가역 함수들의 연속으로 변형하여 복잡한 데이터 분포 x 를 모델링 하는 방식이다. 또한, 가역함수들을 사용하기 때문에 복잡한 데이터 분포 x에서 기본 분포 z로 역방향으로도 연산 쉽게 가능하다는 특징을 가지고 있다. 이에 따라 학습시에 복잡한 데이터 분포 x에서 기본 분포 z로 가는 가역함수들을 학습한 이후 기본 분포 z에서 복잡한 데이터 분포 x를 샘플링하게 된다. 해당 논문에서는 RealNVP 에서 사용한 방식을 사용하여 NF를 구성하였다.
Conditional Normalizing Flow
Conditional Normalizing Flow (cNF)는 기존 Normalizing Flow에 추가적인 조건 정보 c 를 입력하여, 조건에 따른 데이터분포 x를 학습하게 되는 방식이다. 따라서 조건 c에 따라 서로 다른 데이터 분포를 모델링하게 된다. 따라서 동일한 기본 분포 z라고 해도 조건에 따라 서로 다른 x를 모델링할 수 있게 된다. 해당 논문에서 지도 (m), 출발점 (s), 도착점 (g)를 조건으로 사용하는 cNF를 이용했다.
왜 Normalizing Flow를 사용한 걸까?
해당 논문에서는 기존 GAN 혹은 CVAE 같은 생성모델을 사용했을때 mode collapse가 발생할 수 있다는 문제를 지적한다. 그에 반해 NF는 데이터 분포의 likelihood를 명시적으로 학습하기 때문에 상대적으로 mode callapse 강하다. 또한 가역변환을 사용하기 때문에 샘플링시 다른 모델들의 비해 계산 비용이 낮고 빠른 추론이 가능하다.
Method & Re-Implementation
논문에서 제안할때는 map에 대한 정보가 point cloud 형태로 되어있어 해당 형태에 맞는 Encoder를 사용하였다고 한다. 하지만 내가 직접 구현할때는 이미지 정보를 사용하여 재구현 하였기 때문에 실제 구현과는 살짝 다를 수 있다. Dataset은 Neural-RRT*에서 만든 dataset을 활용하였다.
Condition Encoder
Condition Encoder는 크게 3가지 input을 가진다.
- Start point (x, y)
- Goal point (x, y)
- 3-channel Map
- 0ch : Map Image (0: obstacles, 1: free space)
- 1ch : 각 좌표에 start (1), goal (-1) 로 표시
- 2ch : SDF (signed-distance field)
3-channel Map을 ResNet을 이용해 인코딩된 벡터와 start, goal 좌표 정보를 concatenate 하여 최종 조건 벡터 c로 사용하게 된다.
Conditional Normalizing Flow 학습
참고: Dinh et al., “Density Estimation using Real NVP,” ICLR, 2017
dataset 생성시 만들었던 A* 알고리즘으로 만든 최적 경로 좌표들을 사용한다.
최적 경로 좌표를 복잡한 데이터의 분포로 보고 학습 데이터 사용한다. 조건 벡터 는 각 Affine Coupling Block에 함께 입력되어 단순히 전체 데이터의 평균적인 분포를 학습하는 것이 아니라, 현재 주어진 지도와 start-goal에 맞는 경로 분포를 학습하게 된다.
사용한 Affine Coupling Block은 Noramlizing Flow 모델중 하나인 RealNVP에서 제시한 Affine Coupling Block을 사용하였다. 헤당 블록의 특징은 입력 좌표를 invertible하게 변환할 수 있고, likelihood 계산에 필요한 log-determinant를 효율적으로 계산할 수 있다는 장점이 있다고 한다.
학습 과정에서는 A* 경로 샘플(복잡한 분포)를 forward 방향으로 통과시켜 latent variable 𝑧 (기본 분포)로 변환하게 된다. 그리고 이 latent variable이 표준정규분포가 되도록 negative log-likelihood를 최소화하도록 학습되게 된다.
이렇게 조건에 따라 경로분포가 알맞게 생성되도록하는 가역함수들(Affine Coupling Blocks)을 학습하게 된다.
Conditional Normalizing Flow 추론
실제 경로 가이드 분포를 샘플링할때는 표준정규분포에서 샘플들을 먼저 뽑고 이 샘플들과 앞에서 인코딩한 조건 벡터를 함께 사용하여 NF 모델을 inverse 방향으로 통과시킨다. 최종 경과로 정규분포의 단순한 샘플들이 현재 환경에 맞는 경로 가이드 분포로 변환된다.
샘플들은 최적 경로가 존재할 가능성이 높은 영역을 중심으로 생성됨을 볼 수 있다. 이렇게 생성된 샘플 분포를 이후 RRT*의 확장 과정에서 사용하여, 불필요한 탐색을 줄이고 효율적인 경로탐색을 가이드해주게 된다.
Result
ResNet 종류와 uniform RRT* Success Rate, Path Cost, Nodes Expanded 수치 비교
2D에서의 Uniform RRT*과 PlannerFlows 비교 시각화 (first solution, max iteration: 3000)
- 1st row: 둘다 성공한 case 이다.
- 하지만 PlannerFlows의 샘플링 가이드 영역이 최적 경로를 따라 샘플링되어 더 좋은 cost를 보여준다.
- 2nd row: PlannerFlows만 성공한 case이다.
- RRT*는 도착점과는 다른 방향으로 tree를 만들어가다가 실패하였다. 반면에 PlannerFlows는 샘플링 가이드 영역이 목표점까지 생성됨에 따라 성공한 것을 확인 할 수 있다.
