[로봇내비게이션 강의정리] V-graph(Visibility)

Roadmap-based method

선들의 연결로 path를 완성하는 알고리즘

Visibility graph, Voronoi Diagram

 

Visibility Graph란?

 

"보이는" 꼭지점(노드)들을 연결하는 graph를 말한다.

 

v-graph를 만드는법 : 안보이는 점은 잇지 말고 보이는 점만 잇는다.(간단)

v-graph 예시

v-graph를 만드는 의사코드는 다음과 같다.

v-graph 의사코드

QInit, QGoal에서 Q(q)가 의미하는 바 : configuration을 의미하는 약어이다.

2줄에 segment는 노드와 노드를 연결하는 선을 의미. edge또한 선을 의미한다.

u,v는 각각 노드를 의미한다.

 

==> 위 의사코드를 간단히 정리하자면

1. 만약 선분이 장애물의 한 변을 이루는 선분이면 ok, 선분이 장애물과 안 부딫히면 ok

2. ok하면 graph에 포함시켜

 

 

V-graph 장단점

v-graph의 단점은 장애물과 부딫힐 가능성이 꽤 높다는 것이다. 왜냐면 애초에 알고리즘 특성상 로봇의 부피를 0인 점으로 보기 때문이다. 따라서 이 문제를 해결하기 위해 장애물을 기존의 크기보다 더 크다고 가정하고 맵에 장애물을 형성한다.

파란색 : 장애물의 크기를 늘린부분

장점으로는 장애물 근처의 직선경로만 생성하기 때문에 굉장히 효율적인 경로가 나온다는 것이다.

그러나 v-graph는 장애물의 크기를 늘려준다 하더라도 근본적으로 꽤 치명적인 단점이 있는 알고리즘 이기 때문에 이를 보완하기 위해 voronoi graph가 제안된다.