12.15 가시성 그래프와 보로노이 다이어그램

1. 개요

가시성 그래프(visibility graph)와 보로노이 다이어그램(Voronoi diagram)은 환경의 기하학적 정보를 활용한 두 가지 중요한 그래프 표현이다. 가시성 그래프는 환경에서 직선으로 보이는 점들을 연결하여 구축되며, 가장 짧은 경로를 찾는 데 효과적이다. 보로노이 다이어그램은 장애물에서 가장 멀리 떨어진 점들의 집합이며, 안전한 경로를 제공한다. 두 표현 모두 평면 환경의 경로 계획에서 광범위하게 활용되며, 모바일 로봇과 자율 주행 차량의 운동 계획에서 중요한 도구이다.

2. 가시성 그래프

2.1 정의

가시성 그래프는 다음과 같이 정의된다.

노드: 시작점, 목표점, 그리고 모든 다각형 장애물의 꼭짓점
엣지: 두 노드를 연결하는 직선이 장애물 내부를 통과하지 않으면 엣지가 존재
가중치: 두 노드 사이의 유클리드 거리

2.2 핵심 성질

가시성 그래프의 가장 중요한 성질은 다음과 같다.

정리: 다각형 장애물이 있는 평면 환경에서 시작점에서 목표점까지의 최단 경로는 가시성 그래프 위에 존재한다.

이는 최단 경로가 장애물의 꼭짓점을 통과한다는 사실에서 비롯된다. 직선 경로가 장애물에 막히면, 최단 우회 경로는 장애물의 꼭짓점에서 꺾인다.

2.3 알고리즘

2.3.1 단순 알고리즘

construct_visibility_graph(start, goal, obstacles):
    nodes = [start, goal] + all vertices of obstacles
    G = empty graph
    
    for i in range(len(nodes)):
        for j in range(i+1, len(nodes)):
            if line_segment(nodes[i], nodes[j]) is collision-free:
                G.add_edge(nodes[i], nodes[j], distance(nodes[i], nodes[j]))
    
    return G

이 알고리즘의 시간 복잡도는 $O(n^3)$ 이며, 여기서 $n$ 은 노드의 수이다.

2.3.2 회전 평면 스위프

회전 평면 스위프(rotational plane sweep) 알고리즘은 가시성 그래프를 $O(n^2 \log n)$ 시간에 구축한다.

2.3.3 가시성 복잡도

평면의 가시성 복잡도(visibility complex)를 사용하면 더 효율적인 알고리즘이 가능하다.

2.4 가시성 검사

두 점 사이의 가시성 검사는 직선 분이 어떤 장애물과도 교차하지 않는지 확인한다.

def is_visible(p1, p2, obstacles):
    for obstacle in obstacles:
        for edge in obstacle.edges:
            if segments_intersect((p1, p2), edge):
                return False
    return True

2.5 최단 경로 계산

가시성 그래프 위에서 다익스트라 알고리즘을 적용하면 최단 경로가 얻어진다.

def shortest_path_visibility(start, goal, obstacles):
    G = construct_visibility_graph(start, goal, obstacles)
    return dijkstra(G, start, goal)

2.6 가시성 그래프의 장점

최적성: 가장 짧은 유클리드 경로를 보장한다.
단순성: 개념과 구현이 단순하다.
다각형 환경에 효과적: 다각형 장애물이 있는 환경에 적합하다.

2.7 가시성 그래프의 단점

장애물과의 접촉: 경로가 장애물 표면에 접하므로 안전하지 않다.
곡선 장애물: 곡선 장애물에는 직접 적용하기 어렵다.
계산 비용: $n$ 이 클 때 계산 비용이 크다.
2차원 제한: 평면 환경에 적합하며, 3차원으로 확장이 어렵다.

2.8 안전성 개선

가시성 그래프의 안전성을 개선하기 위해 장애물을 일정 거리 확장한 후 가시성 그래프를 구축할 수 있다. 이를 환원 가시성 그래프(reduced visibility graph)라 한다.

3. 보로노이 다이어그램

3.1 정의

보로노이 다이어그램은 평면을 영역으로 분할한다. 각 영역은 가장 가까운 장애물 점에 대응한다.

점들의 집합 $S = \{p_1, p_2, \ldots, p_n\}$ 이 주어지면, 점 $p_i$ 의 보로노이 셀(Voronoi cell)은 다음과 같이 정의된다.

$V(p_i) = \{x \in \mathbb{R}^2 : d(x, p_i) \leq d(x, p_j), \forall j \neq i\}$

즉, $p_i$ 가 가장 가까운 점인 모든 점들의 집합이다.

3.2 보로노이 엣지

보로노이 다이어그램의 엣지는 두 보로노이 셀의 경계이다. 이는 두 가장 가까운 점에서 등거리에 있는 점들의 집합이다.

3.3 보로노이 정점

보로노이 정점은 세 개 이상의 보로노이 엣지가 만나는 점이다. 이는 세 개 이상의 가장 가까운 점에서 등거리에 있다.

3.4 일반화된 보로노이 다이어그램

일반화된 보로노이 다이어그램(Generalized Voronoi Diagram, GVD)은 점이 아닌 일반 객체(직선, 다각형 등)에 대해 정의된다. 로봇 운동 계획에서는 GVD가 일반적으로 사용된다.

3.5 알고리즘

3.5.1 Fortune 알고리즘

Fortune 알고리즘은 보로노이 다이어그램을 $O(n \log n)$ 시간에 구축한다. 평면 스위프 기법을 사용한다.

3.5.2 점진적 알고리즘

점진적 알고리즘은 점을 하나씩 추가하면서 보로노이 다이어그램을 갱신한다.

3.5.3 분할 정복

분할 정복 알고리즘도 $O(n \log n)$ 시간에 동작한다.

3.6 보로노이 그래프

운동 계획을 위해 보로노이 다이어그램을 그래프로 변환한다.

노드: 보로노이 정점
엣지: 보로노이 엣지

이 그래프 위에서 경로를 찾는다.

3.7 보로노이 경로 계획

보로노이 그래프 기반 경로 계획은 다음과 같이 동작한다.

환경의 보로노이 다이어그램을 구축한다.
시작점과 목표점을 가장 가까운 보로노이 엣지에 투영한다.
보로노이 그래프에서 경로를 찾는다.
시작점과 목표점에서 보로노이 그래프까지의 경로를 추가한다.

3.8 보로노이 그래프의 장점

안전성: 경로가 장애물에서 멀리 떨어져 있다.
자연스러운 회랑: 자유 공간의 자연스러운 회랑을 따라간다.
실시간 갱신: 동적 환경에서 갱신이 가능하다.

3.9 보로노이 그래프의 단점

비최적성: 가장 짧은 경로를 보장하지 않는다.
곡선 경로: 직선이 아닌 곡선 경로가 생성될 수 있다.
3차원 어려움: 3차원으로의 확장이 복잡하다.

4. 두 방법의 비교

측면	가시성 그래프	보로노이 다이어그램
최적성	최단 경로	안전한 경로
안전성	장애물 접촉	장애물에서 멀리
차원	2차원	주로 2차원
계산 복잡도	$O(n^2)$	$O(n\log n)$
적합한 경우	다각형 장애물, 최단 경로 필요	안전 우선, 동적 환경

5. 가시성 그래프의 구현

5.1 다각형 장애물

다각형 장애물의 표현은 일반적으로 꼭짓점의 리스트이다.

class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices
    
    @property
    def edges(self):
        n = len(self.vertices)
        return [(self.vertices[i], self.vertices[(i+1) % n]) for i in range(n)]

5.2 가시성 검사

def segments_intersect(seg1, seg2):
    # 두 선분이 교차하는지 검사
    p1, p2 = seg1
    p3, p4 = seg2
    # 외적을 사용한 교차 검사
    ...

5.3 가시성 그래프 구축

def build_visibility_graph(start, goal, obstacles):
    nodes = [start, goal]
    for poly in obstacles:
        nodes.extend(poly.vertices)
    
    n = len(nodes)
    edges = []
    for i in range(n):
        for j in range(i+1, n):
            if is_visible(nodes[i], nodes[j], obstacles):
                dist = euclidean_distance(nodes[i], nodes[j])
                edges.append((i, j, dist))
    
    return nodes, edges

6. 보로노이 다이어그램의 구현

6.1 Scipy를 이용한 구축

Scipy의 Voronoi 클래스를 사용하면 보로노이 다이어그램을 쉽게 구축할 수 있다.

from scipy.spatial import Voronoi
import numpy as np

points = np.array([[0, 0], [1, 0], [0.5, 1]])
vor = Voronoi(points)

print(vor.vertices)  # 보로노이 정점
print(vor.regions)   # 보로노이 영역
print(vor.ridge_vertices)  # 보로노이 엣지

6.2 일반화된 보로노이 다이어그램

다각형 장애물에 대한 일반화된 보로노이 다이어그램은 더 복잡하다. CGAL(Computational Geometry Algorithms Library)이나 다른 컴퓨터 기하학 라이브러리가 사용된다.

7. 응용

7.1 로봇 경로 계획

가시성 그래프와 보로노이 다이어그램은 모바일 로봇의 경로 계획에서 광범위하게 사용된다.

7.2 자율 주행

자율 주행 차량의 경로 계획에서 보로노이 다이어그램이 안전한 경로 생성에 활용된다.

7.3 게임 AI

게임의 NPC가 환경을 인식하고 이동할 때 가시성 그래프와 보로노이 다이어그램이 사용된다.

7.4 컴퓨터 그래픽스

컴퓨터 그래픽스에서 다각형 분할, 메쉬 생성 등에 보로노이 다이어그램이 활용된다.

7.5 지리 정보 시스템

GIS에서 가장 가까운 시설 찾기, 영역 분할 등에 보로노이 다이어그램이 사용된다.

8. 로봇공학에서의 응용

8.1 모바일 로봇의 안전 경로

청소 로봇이나 배달 로봇이 장애물에서 안전하게 이동할 때 보로노이 그래프가 사용된다. 가장 짧은 경로보다 안전성이 우선된다.

8.2 자율 주행의 차선 변경

자율 주행 차량이 차선을 변경할 때 보로노이 다이어그램을 활용하여 다른 차량과 충분한 거리를 유지하는 경로를 생성한다.

8.3 인도주의 로봇

재난 환경에서 활동하는 인도주의 로봇이 안전한 경로를 찾을 때 보로노이 그래프가 효과적이다.

8.4 다각형 환경 탐색

다각형 장애물이 있는 환경에서 가시성 그래프가 효과적이다. 매핑된 환경에서의 경로 계획에 사용된다.

9. 가시성 그래프의 응용 예시

9.1 사무실 환경

벽으로 분할된 사무실 환경에서 한 방에서 다른 방으로 이동할 때 가시성 그래프가 효과적이다. 각 방의 출입구 근처의 꼭짓점이 그래프의 노드가 된다.

9.2 미로

다각형으로 표현된 미로의 입구에서 출구까지 가장 짧은 경로를 가시성 그래프로 찾을 수 있다.

9.3 게임의 추적

게임에서 캐릭터가 다른 캐릭터를 볼 수 있는지 결정할 때 가시성 검사가 사용된다.

10. 보로노이 다이어그램의 응용 예시

10.1 안전한 회랑 따라가기

로봇이 두 장애물 사이의 가장 안전한 경로를 찾을 때 보로노이 엣지를 따라간다.

10.2 동적 환경의 갱신

동적 환경에서 보로노이 다이어그램이 갱신되면서 로봇의 경로가 조정된다.

10.3 영역 분할

여러 로봇이 영역을 나누어 작업할 때 보로노이 다이어그램으로 자연스럽게 분할할 수 있다.

10.4 가장 가까운 장애물 찾기

로봇이 가장 가까운 장애물의 거리와 방향을 알고 싶을 때 보로노이 셀을 활용한다.

11. 알고리즘의 결합

11.1 하이브리드 접근법

가시성 그래프와 보로노이 다이어그램을 결합한 하이브리드 접근법이 있다. 일반적으로 보로노이 그래프를 사용하다가 좁은 통로에서 가시성 그래프로 전환한다.

11.2 가중치 보로노이

가중치 보로노이 다이어그램(weighted Voronoi diagram)은 각 점에 가중치를 부여하여 가장 가까운 점의 정의를 변경한다.

11.3 표면 보로노이

3차원 표면 위의 보로노이 다이어그램이 있다. 측지선 거리를 사용한다.

12. 라이브러리 지원

12.1 Scipy

from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt
import numpy as np

points = np.random.rand(20, 2)
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.show()

12.2 CGAL

CGAL은 다양한 컴퓨터 기하학 알고리즘을 제공하는 C++ 라이브러리이다. 보로노이 다이어그램, 가시성 그래프 등을 지원한다.

12.3 Boost.Polygon

Boost.Polygon은 다각형 처리를 위한 C++ 라이브러리이며, 보로노이 다이어그램을 지원한다.

12.4 shapely

shapely는 Python의 컴퓨터 기하학 라이브러리이다.

13. 학습의 가치

가시성 그래프와 보로노이 다이어그램을 이해하는 것은 다음과 같은 이점을 제공한다.

환경의 기하학적 표현 방법을 익힌다.
안전한 경로와 최적 경로의 균형을 이해한다.
모바일 로봇의 경로 계획 방법을 학습한다.
컴퓨터 기하학의 기본 도구를 익힌다.

14. 학습 권장사항

14.1 직접 구현

작은 환경에서 가시성 그래프와 보로노이 다이어그램을 직접 구축해 본다.

14.2 시각화

알고리즘의 결과를 시각화하면 이해가 깊어진다. matplotlib이나 다른 시각화 도구를 활용한다.

14.3 응용 학습

실제 로봇 응용에 적용해 본다.

15. 본 절의 의의

본 절은 가시성 그래프와 보로노이 다이어그램을 다루었다. 이 두 표현은 환경의 기하학적 정보를 활용한 경로 계획의 핵심 도구이며, 모바일 로봇과 자율 주행에서 중요하다. 두 방법의 비교와 결합은 안전성과 최적성의 균형을 이해하는 데 도움이 된다.

16. 참고 문헌

de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational Geometry: Algorithms and Applications (3rd ed.). Springer.
Latombe, J. C. (1991). Robot Motion Planning. Kluwer Academic Publishers.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.
Aurenhammer, F. (1991). “Voronoi diagrams—a survey of a fundamental geometric data structure.” ACM Computing Surveys, 23(3), 345–405.
Fortune, S. (1987). “A sweepline algorithm for Voronoi diagrams.” Algorithmica, 2(1-4), 153–174.

version: 1.0