Visibility Graph

Visibility Graph

• 가시성 그래프는 경로 계획,컴퓨터 그래픽스, 컴퓨터 비전 등에서 장애물 회피와 최단 경로 탐색에 널리 사용되는 그래프 기반 기법이다.
  • 특히. 2D 환경에서 폴리곤 형태의 장애물이 있을때, 로봇이 start에서 goal까지의 shortest path를 찾는데 자주 쓰인다.
• 정의
  • 환경 내의 장애물들의 꼭짓점(vertices)들과 로봇의 start,goal을 node로하고,
    각 node쌍이 서로를 직선으로 바라볼 수 있을때에만 edge를 연결하여 만든 그래프이다.
    • 즉, "장애물의 꼭짓점끼리, 그리고 start / goal 과 장애물 꼭짓점 간에, 장애물을 뚫지 않고 연결할 수 있으면 연결하는 그래프"이다.
• 장점
  
  • 최단 경로를 보장하며, 직관적이다.
• 단점
  • 장애물이 많거나, 꼭짓점이 많으면 그래프의 edge수가 급격히 증가함.
  • 실제 로봇에 적용하면, 장애물에 너무 붙어서 안전하지 않을수있음.

 

• 알고리즘 절차
  • 1. Node를 정의
    • 모든 장애물의 꼭짓점 , start , goal를 노드로 정의한다.
  • 2. Edge 연결
    • 각 노드 쌍에 대해서, 그을 수 있는 직선이 다른 장애물을 관통하지 않으면 edge를 추가한다.
      • 선분이 장애물 내부( or 경계 )와 교차하지 않아야 한다.
  • 3. 가중치
    • 일반적으로 유클리드 거리를 edge의 가중치로 사용
  • 4. 경로 탐색
    • 그래프가 완성되면, 다익스트라 or A*를 가지고 start에서 goal까지의 경로를 탐색.