[로봇내비게이션 강의정리] Voronoi

강의 전체 내용 개요

Voronoi 개념

맵에 점이 여러개 찍혀있을 때, 그 점에 가장 가까운 영역들은 그 점의 영역이라고 보는 방법이다.

 

이 때, General Voronoi Diagram은 다음을 말한다.

 

F13은 장애물 1과3 사이의 보로노이 경계선을 의미하고 S13은 그 경계선을 직선으로 무한히 이은 선을 말한다.

이 때, F들의 모든 집합을 GVD라고 한다.

 

 

Voronoi를 어떻게 path planning에 활용할 것인가

장애물을 한 점으로 근사했을 때, 위 그림에서 점을 장애물이라고 보자. 이 때, 점 주변의 영역은 장애물 주변의 영역이 되는것이고, 다시말해 영역과 영역사이 경계선은 장애물들로 부터 가장 먼 경로가 된다.

 

따라서 이 경계선을 따라서 로봇을 움직이면 로봇은 가장 안전한 path planning을 할 수 있게 된다.

 

이 때, 위에 그림에서 파란 점으로 찍어놓은 부분들을 node, 이 점들을 이은 선은 edge로 취급하여 A*알고리즘 적용이 가능하다. 

위의 그림에서는 선과 선이 만나는 부분만 점이 찍혀있지만 경우에 따라서는 선이 만나지는 않지만 꺾인 부분에도 가상의 노드를 추가하여 path planning에 활용할 수 있을 것으로 보인다.

 

적용하면 아래 그림과 같이 나타날 것이다.

예시1

예시2

 

voronoi 구현법

보로노이 맵이 그려져 있을 때, 로봇이 놓여있다면 로봇을 근처에 있는 경계선에 근사하여 QinitNode를 설정, 목표점도 마찬가지로 경계선에 근사하여 QgoalNode로 설정하여 path planning을 시작할 수 있다.

voronoi 경계선 구현법

brushfire알고리즘을 이용하여 아래 사진과 같이 구현이 가능하다.

여기서 경계선을 구하는 방법은?

(검은 숫자 값 - 빨간 숫자 값) 의 부호가 바뀌는 지점을 경계선으로 설정하면 된다.

 

voronoi 장애물 인식, 구현법

맵 grid를 하나하나 탐색하며 장애물이 어디있는지를 탐색한다. 이 때, 탐색방향은 왼쪽에서 오른쪽직선으로 훑고, 오른쪽 끝가지 훑었으면 아래칸으로 내려와서 왼쪽부터 다시 시작하는 방식이다.

 

그렇게 최초로 장애물을 만나면 빨간색 처리한다.

빨간색 : 장애물 && boundary

 

빨간 노드 주변에 1~8방향 확인하며 장애물이 있는지를 확인한다. 장애물이 있으면 노란색 처리한다.

노란색 : 장애물. && 아직 boundary인지는 확인 안한 상태

위와 같은 방법으로 boundary를 체크해 나간다. 이 때 주의할 점은 boundary와 장애물의 내부영역을 구분해서 잘 찾아나가야 한다는 점이다.

 

장애물을 노란색 처리하고 노란색의 주변 노드를 살펴보아야 노란색이 장애물의 내부인지 장애물의 boundary인지 확인 할 수 있다. 이 점에 주의해서 코딩한다.

boundary를 탐색하다가 최초의 boundary노드를 만나면 장애물 boundary처리가 완성된다.

이 후 새로운 장애물 탐색을 위해 원래 탐색방향대로(왼->오른쪽) 탐색해 나간다.