Path Planning Algorithms

1. 다익스트라 알고리즘

2. A star algortihm  다익스트라 알고리즘에서 휴리스틱한 cost를 추가한것이다.

3. Weighted A star 알고리즘은 휴리스틱한 cost가 더 큰 알고리즘 , 휴리스틱 cost를 추가하는 이유는 좀더 빠르게 목적지 까지 path를 search 하기 위함임 빠른만큼 optimal path를 보장 할 수 없다. trade off 가 있다.

4. RRT Algorithm 아래의 과정을 목적지를 찾을떄까지 반복을 한다. 하지만 랜덤노드가 목적지에 떨어질 확률은 현저히 적기 떄문에 그 근처에 랜덤노드가 정해져서 패스를 찾게 되어도 종료하게 된다. 일종의 threshold 를 결정해줘야한다.

5. RRT star Algorithm 기존의 RRT와는 다르게 트리내의 노드를 대체하여 cost를 줄일 수 있는 경우 기존 노드를 데체하여 트리를 구성한다. 

c를 살펴보면 1 - 4 - new 의  cost는 7 이지만 1 - 2 - new 는 4 임으로 가까운 것들 중에 최고의 옵션을 선택하는 것을 확인 할 수 있다.

e를 살펴보면 기존에 1 - 4 - 5 는 10 만큼이 드는데 1 -2 - new - 5 는 8 밖에 안 듬으로 패스를 교체한 것을 확인 할  수 있다.

5.1 Dubins path 아래와 같은 방법으로 총 6가지 , RSR, RSL, LSR, lSL, RLR, LRL optimal path가 존재하고 forward 방향으로 만 이동이 가능하다는 단점이 있다.

5.2 Reeds-Sheep path 전진 후진이 둘다 가능하고 총 46 가지의 optimal path가 존재하지만 curvature의 불연속이 존재하여 steering 관점에서 매우 불리하다. 중간중간에 멈춰서 방향을 바꿔줘야 한다.

5.3 Continous curvature Reeds-Sheep path 위의 방법을 보완하기 위해 나온 알고리즘이다. curvature 가 연속적임으로 기어를 바꾸지 않는 이상 차량을 멈춰야 할 필요가 없다.

5.4 Informed RRT start algorithm 이 좀더 좋은것이다. searching space 가 현저히 줄어 드는것을 확인 할 수 있다.