[Path Planning]Probablistic Roadmap method(PRM)

PRM

---

PRM (확률적 로드맵 방법)

---

확률적 로드맵 방법은 장애물이 존재하는 임의의 Map 상에서 경로계획하는 방법이다.

 

하지만 많고 많은 경로계획 방법중에는 Artificial Potential Field나 잘 알려진 A*알고리즘 등이 존재한다!

출처 : https://github.com/Yaaximus/artificial-potential-field

경로계획에 조금이라도 관심이 있다면 Potential Field가 유려한 곡선경로 및 장애물 회피 성능을 보장하고, A* 알고리즘은 같은 환경에서 일정한 최적경로를 도출한다는 사실을 알고 있을 것이다.

 

하지만 위의 두 알고리즘은 치명적인 단점이 존재한다.

 

A* : 탐색시간이 길다.

APF(Artificial Potential Field) : Local minimum에 빠진다면 아무리 시간이 흘러도 경로가 도출되지 않는다.

 

이를 확률적 경로탐색법 중 하나인 PRM으로 해결해보고자 한다

 

.

C-space

우선 C-Space(Configuration Space)를 정의한다. 이는 하나의 물체가 움직일 수 있는 영역을 의미한다.

 

이제 장애물이 센서에 의해 탐지 되었을때 다음과 같은 정보를 얻게 된다.

 

 

이제 샘플링을 진행해보겠다. 랜덤하게 C-space내 샘플링을 진행하면 다음과 같다.

 

우선 장애물과 충돌한 Sample들은 제외하고 다시 샘플링이 진행된다.

 

그리고 샘플들 주변 거리내의 샘플들을 local path로 연결해준다.

 

충돌했던 샘플점이 삭제되고 Local path가 연결되었다. ( 너무 많아질거같아서 적당히 연결된 상태 )

 

이때, 장애물과 충돌하는 local path또한 연결되지 않는다.

 

결국 local path들로 정의된 그래프 관계를 이용해 출발점과 도착점까지의 경로를 도출해낼 수 있다.

 

---

간단한 개념은 위와 같았고, 세부개념을 알아보자.

 

Uniform Sampling

샘플링을 진행할때 Uniformly하게 샘플링을 하는 것이다. 사실 다른 Sampling 기법이 들어가도 무관하다고 한다.

 

Resampling

Failure Rate

실패율을 정의해보자.

 

하나의 샘플링점에 대해서 주변 노드의 개수를(link)로 정의하고, failed link를 중간에 장애물이 있어 연결되지 못한 개수로 정의한다.

 

Normalized weight

 

 

모든 샘플링점의 실패율의 합으로 현재 실패율을 나누어 wight를 정규화 해준다.

 

Resampling probability

다시 샘플링할때의 확률을 Normalized weight로 정의한다.

 

아직 개념이 확실하게 잡히지 않아서 잡히면 다시 보완해서 포스팅 할 예정입니다.