Dubins path 알고리즘

 

오늘은 지난 포스팅에서 다뤘던 A*알고리즘에 이어서 Dubins path 알고리즘에 대해서 알아보겠습니다.

 

---

Dubins path란?

 

Dubins path는 시작지점에서 목적지점으로 가기 위한 방향, 곡선 경로를 생성하는 알고리즘입니다. 

 

앞서 설명드린 Dijkstra, A* 알고리즘은 직선 경로 생성만 가능했으며 뱡향에 대한 개념을 다루고 있지 않았습니다.

 

즉, 벡터가 아닌 스칼라 값을 다루고 있습니다. 

 

여기서 벡터 경로를 생성하기 위한 알고리즘중 하나가 Dubins path 알고리즘입니다.

 

Dubins path는 시작지점과 목적지점의 좌표 및 방향을 입력 받고 로봇의 회전반경을 기반으로 곡전 및 직선 경로를 생성합니다.

 

---

< 입력 값 >

- 시작지점 좌표

- 시작지점에서의 방향

- 목적지점 좌표

- 목적지점에서의 방향

- 로봇의 회전 반경

 

< 출력 값 >

- 곡선 + 직선 경로

---

 

---

알고리즘 특징

 

Dubins path는 오직 세 가지 유형의 움직임, 즉 직진, 우회전, 좌회전으로 이루어진 경로를 생성합니다.

 

해당 알고리즘으로 생성가능한 경로의 종류는 총 6가지가 있습니다. 

---

- RSL : 우회전 + 직진 + 좌회전

- LSR : 좌회전 + 직진 + 우회전

- RSR : 우회전 + 직진 + 우회전

- LSL : 좌회전 + 직진 + 좌회전

- RLR : 우회전 + 좌회전 + 우회전

- LRL : 좌회전 + 우회전 + 좌회전

---

 

아래의 그림이 이해하는데 도움이 되길 바라겠습니다.

---

내용 정리

 

1. 경로 생성 방법

        1) 시작, 목적 지점의 좌표 및 방향을 입력

        2) 차량의 회전 반경 입력

        3) 입력값을 기반으로 6가지의 경로 종류 중 적절한 경로를 선택하여 경로 생성

 

2. 알고리즘의 특징

        1) 위의 알고리즘은 벡터값을 포함

        2) 차량의 전진만 고려 (후진 불가)

        3) 연산량이 적어 빠른 경로 계산이 가능

        4) A* 알고리즘과 결합하여 곡선 주행이 가능한 경로 생성 가능

 

---

 

오늘은 곡선 주행이 가능하며 방향성을 가진 경로 생성알고리즘인 Dubins path 알고리즘에 대해 알아보았습니다.

 

해당 알고리즘은 다양한 분야에서 사용되고 있으며 빠른 연산이 가능하다는 장점을 가지고 있습니다. 

 

다음시간엔 Dubins path를 개선한 reeds shepp path 알고리즘에 대해 알아보겠습니다.