지도 표현

1. 지도 표현의 요소

1.1 지도 표현

• 시스템이 환경을 이해하고 장애물을 인식하며 경로를 계획하는 데 필요한 정보의 기반을 제공, 계획의 효율성과 정확성에 영향을 줌

1.2 지도 표현의 요소

• 환경 인식: 지도는 로봇이나 자율 시스템이 주변환경을 인식하고 해석함, 이는 시스템이 장애물을 탐지하고 우회할 수 있도록 함
• 정보의 정확성 및 접근성: 다양한 지도 표현 방식은 경로계획 알고리즘에 필요한 정보의 수준과 유형을 결정, 이는 알고리즘의 선택과 효율성에 영향
• 경로 최적화: 지도 표현은 경로의 최적화 가능성을 결정함, 예를 들어, 격자 기반 지도는 구현이 간단하지만, 고해상도 지도는 더 정밀한 경로 계획이 가능함
• 적응성: 동적 환경에서의 경로계획을 위해서는 지도가 변화하는 환경에 신속하게 적응할수 있어야함. 이는 자율 시스템이 예기치 않은 변화에 효과적으로 대응할수 있게 함.

1.3 지도 표현 분류(예)

2. 격자 기반 지도(Grid-based Maps)

2.1 격자 기반 지도

• 환경은 고정된 크기의 정사각형(또는 직사각형) 셀로 구성된 격자로 표현
• 각 셀은 해당 영역의 특성을 나타내며, 일반적으로 장애물의 존재 유무, 이동 가능 여부, 비용 등의 정보를 포함
  

2.2 구조와 특성

• 셀
  -> 환경을 이루는 기본 단위로, 모든 셀은 격자 내에서 고유한 위치(좌표)를 가짐.
  -> 셀의 크기는 지도의 해상도를 결정하며, 작을수록 더 높은 해상도의 지도를 생성
• 장애물
  -> 셀은 장애물이 있는 공간을 '점유' 상태로, 이동 가능한 공간을 '비점유' 상태로 표시.
  -> 일부 구현에서는 셀에 비점유, 부분적으로 점유, 완전히 점유 등의 상태를 부여하여 환경을 더 세밀하게 모델링 할 수 있음
• 비용
  -> 셀은 이동 비용을 나타낼 수도 있으며, 이는 경로 계획 시 최소 비용 경로를 찾는 데 사용.
  -> 예를 들어) 다른 지형(평지, 언덕, 물 등)을 표현하여 로봇이 에너지 효율적인 경로를 선택 가능

2.3 특징

• 단순성과 일관성 : 격자 기반 지도는 구현이 간단하며, 모든 셀이 동일한 크기와 모양을 가지므로 처리가 용이
• 알고리즘과 호환성 : 많은 표준 경로계획 알고리즘은 격자 기반 지도와 잘 작동하며, 이를 사용하여 효과적으로 경로를 찾을 수 있음
• 확장성: 크기 조정이 용이하며 다양한 환경과 해상도에 적용할 수 있음
• 메모리 사용량 : 고해상도 지도는 많은 수의 셀을 필요로 하며, 이는 메모리 사용량이 증가함
• 해상도와 정밀도의 제한: 셀의 크기가 경로계획의 정밀도를 제안할 수 있으며 너무 큰 셀은 작은 장애물을 놓칠 수 있음
• 이동성 모델링 제한: 격자 기반 지도는 주로 직선 또는 각진 이동 경로를 모델링 하기 쉽지만 연속적인 공간에서의 복잡한 이동을 표현하는데는 제한적일 수 있음

2.4 적용 분야

• 실내 로봇 내비게이션, 자율주행 차량의 단순한 환경 인식, 비디오 게임의 경로 계획, 그리고 재난 구조 작업에서의 탐색과 같이 다양한 분야에서 사용
• 이 방식은 특히 이산적인 공간의 표현에 적합하며, 실시간 처리와 단순한 환경에서의 경로 계획에 용이

2.5 격자 기반 지도 표현:실습

import numpy as np
import matplotlib.pyplot as plt

# 격자 기반 지도의 크기 설정, 여기서는 10 x 10 격자 사용
grid_size = 10

# 0으로 초기화된 10x10 격자를 생성, 0은 비점유 셀을 나타냄
grid_map = np.zeros((grid_size, grid_size))

# 장애물을 나타내기 위해 일부 셀을 1로 설정, 1은 점유 셀을 나타냄
# 예시로, 격자의 가운데에 작은 장애물을 생성
obstacle_positions = [(4,4), (4,5), (5,4), (5,5)] #장애물의 위치를 표시하기 위한 좌표를 정의, 격자의 중심에 작은 장애물을 생성하기 위해 중심 주변의 4개의 셀을 장애물로 설정
for pos in obstacle_positions:
    grid_map[pos] = 1 #장애물 위치에 해당하는 셀을 1로 설정하여 격자 맵에 장애물을 추가

# 격자 기반 지도를 시각화
plt.imshow(grid_map, cmap='Greys', interpolation='none') #cmap 에서 색상 맵을 흑백으로 설정, 0은 흰색으로 1은 흑백으로 그림
plt.title('Grid-based Map Representation')
plt.xticks(range(grid_size))
plt.yticks(range(grid_size))
plt.grid(which = 'both') # 격자 그림
plt.show()

코드를 살펴보면
지도의 크기를 설정한다.

grid_size = 10

지도의 각 셀 상태를 저장: 0은 비점유 셀, 1은 점유 셀

grid_map = np.zeros((grid_size, grid_size))

장애물의 위치를 정의하고 해당 위치의 셀값을 1로 설정

obstacle_positions = [(4,4), (4,5), (5,4), (5,5)]
for pos in obstacle_positions:
    grid_map[pos] = 1 

3. 셀 분해 기반 지도

3.1 셀 분해(Cell Decomposition) 기반 지도

• 로봇 경로계획 및 네비게이션 문제에서 환경을 모델링하기 위해 사용되는 방법 중 하나
• 이 접근법에서는 환경을 여러 개의 작은 셀 또는 영역으로 분해하여, 각 셀이 이동가능한 공간이나 장애물을 표현
• 셀 분해 방식은 환경의 복잡성을 줄이고, 경로 계획 알고리즘이 처리하기 쉬운 형태로 정보를 단순화
  

3.2 셀 분해 기반 지도의 유형

• 근사적(Approximate) 셀 분해
  -> 환경을 대략적으로 표현하는 셀로 분해
  -> 이 방식은 환경의 정확한 모델링보다는 계산의 효율성을 우선
  -> 주로 정사각형 또는 직사각형 셀을 사용하며, 경로 계획을 위한 근사적인 해를 제공
  
• 정확한(Exact) 셀 분해
  -> 환경을 완전히 커버하는, 서로 겹치지 않는 셀로 분해
  -> 각 셀은 이동가능한 공간이나 장애물을 정확히 표현
  -> 복잡한 환경을 모델링 하기 위해 다각형과 같은 기하학적 형태를 사용할 수 있음
  
• 정확한(Exact)셀 분해 : 사다리꼴 분해
  -> 환경 공간을 별개의 블록(convex) 셀 영역으로 분해
  -> 일반적으로 환경을 수직으로 왼쪽에서 오른쪽으로 스캔하며, 장애물의 꼭짓점을 만날 때마다 수직 분해선을 추가
  -> 환경 공간 내에서 만나는 장애물 주변에 일련의 다각형 셀 영역이 생성
  
  -정확한(Exact) 셀 분해 : 부스트로페돈 분해
  -> 환경을 직선적인 경로로 탐색하면서, 경계나 장애물에 도달할 때마다 방향을 전환
  -> 이 과정은 환경 전체를 효과적으로 커버하며, 각 탐색 경로는 장애물에 의해 생성된 비볼록(non-convex)셀로 분해
  -> 분해된 셀들은 환경 내의 자유 공간과 장애물을 표현
  

3.3 인접 그래프 생성

-> 분류된 셀을 기반으로 인접 그래프를 생성
-> 간의 인접 관계를 노드와 엣지로 표현하며, 각 노드는 자유 공간 셀을 대표하고, 엣지는 노드(셀)간의 이동 가능성을 나타냄
-> 그래프 생성 과정에서 중요한 위치(예: 셀의 꼭짓점, 셀 간의 경계)에서 노드를 추출하고, 이동 가능한 셀 간에 엣지를 생성하여 연결성을 표현

3.4 셀 분해 특징

• 복잡한 환경을 단순화하여 경로 계획 용이
• 이산적인 데이터로 변환함으로써 컴퓨터 알고리즘이 처리하기 쉬움
• 고해상도 분해는 계산 비용이 많이 들 수 있음
• 셀의 크기와 형태에 따라 경로의 정밀도가 제한될 수 있음

4. 로드맵 기반 지도 표현

4.1 로드맵 기반 지도 표현

• 환경 내의 주요 자유 공간 위치를 나타내는 노드 모음에서 형성된 연결 그래프
• 노드 : 환경 내의 각 위치
• 에지 : 인접 노드 간에 이동할 수 있음을 표현
  -> 시간이나 거리와 같은 가중치 요인으로써 경로 계획에 활용 가능

4.2 로드맵 기반의 지도표현 특징

• 경로 탐색의 효율성 : 로드맵 기반 지도표현은 경로 탐색에 대해 효율적이다. 이는 주어진 지도에서 출발점과 도착점 사이의 최적 경로를 효율적으로 계산할 수 있음을 의미함. 로드맵은 보통 연결된 노드와 엣지들의 그래프로 표현되어 있어, 그래프 알고리즘을 활용하여 최단 경로를 빠르게 찾을 수 있음
• 유연성과 확장성 : 로드맵 기반 지도표현은 유연성과 확장성이 높다. 새로운 도로나 지리적 특징이 추가되거나 기존의 도로가 변경되어도 상대적으로 쉽게 지도를 업데이트 할 수 있다. 또한, 다양한 환경에서 적용 가능하도록 로드맵을 다양한 규모와 정확도로 구성할 수 있음
• 환경 변화에 대한 대응 : 로드맵은 환경의 변화에 대응할수 있음, 새로운 건물이나 도로가 건설되거나 도로의 상태가 변활 때, 이러한 변화를 지도에 반영하여 최신 정보를 유지할 수 있음
• 초기 구성의 복잡성 : 로드맵 기반 지도표현을 구성하는 초기 단계에서는 상당한 복잡성이 발생한다. 지형의 세부 정보를 수집하고 지도를 생성하는 과정은 시간과 노력이 많이 필요함 또한, 정확한 지형 데이터를 수집하고 처리하는 데에도 비용이 소요될 수 있음

4.3 가시성 그래프(Visibility Graph)

• 환경 내의 점들(주로 장애물의 꼭짓점)을 노드로 하고, 두 노드 간에 직선 경로가 장애물에 의해 차단되지 않을 때 노드 사이에 에지(연결선)을 생성
  -> 즉, 두 점이 서로 '가시적'일 때, 즉 직선 경로가 장애물로 막히지 않으면 이 두점을 연결하는 선분이 그래프에 에지로 추가
  -> 노드(Node) : 환경 내의 중요한 위치를 나타내며, 대체로 장애물의 꼭짓점
  -> 에지(Edge) : 두 노드 간의 가시적 연결을 나타내며 이동 경로를 의미함
  

4.4 가시성 그래프 특징

• 최단 경로 계산 : 장애물을 피하는 최단 경로를 효율적으로 계산 가능
• 환경 모델링의 정확성 : 환경을 정확하게 모델링하며, 장애물 사이의 가시적 연결을 기반으로 경로를 계획
• 경로 계획의 유연성 : 다양한 유형의 환경에서 경로 계획을 위한 기반을 제공
• 계산 복잡도 : 크고 복잡한 환경에서는 가시성 그래프의 생성이 계산적으로 많은 리소스를 요구할 수 있음
• 장애물 근접 문제 : 생성된 경로가 장애물에 매우 근접할 수 있어, 실제 로봇이나 에이전트의 크기 및 안전 마진을 고려한 추가 처리가 필요할 수 있음

4.5 보로노이 다이어그램

• 주어진 공간의 각 점에 대해 가장 가까운 '사이트'(일반적으로는 장애물의 꼭짓점)를 찾아 이를 기반으로 각 사이트를 중심으로 하는 셀(다각형 영역)을 형성
• 이러한 각 셀의 경계는 해당 사이트와 다른 사이트 사이의 동등한 거리에 위치
  

4.5.1 보로노이 다이어그램의 특징

• 공간 분해 : 2차원 문제 공간을 여러 개의 다각형 영역으로 분해, 각 영역은 특정 환경 위치를 중심으로 구성
• 에지 생성 : 각 보로노이 셀의 에지는 환경 내 위치들 사이의 동등한 거리 관계를 기반으로 형성, 이는 에지가 직접적으로 연결된 것이 아니라 환경 내 다른 위치들과 동일한 거리에 있음을 의미
• 경로 계획 : 생성된 보로노이 다이어그램은 경로 계획을 위한 그래프로 사용, 로봇이 보로노이 에지를 따라 장애물과 안전한 거리를 유지하며 이동할 수 있음
• 안전한 경로 : 보로노이 에지는 장애물로부터 일정한 거리를 유지하기 때문에, 로봇이나 UAV가 장애물에 가까이 접근하지 않고도 안전한 경로를 이동할 수 있음
• 최적화된 커버리지 : 보로노이 다이어그램은 공간을 균등하게 커버할 수 있음
• 계산 복잡성 : 크고 복잡한 환경에서 보로노이 다이어그램을 계산하는 것은 많은 연산이 필요
• 동적 환경 처리의 한계 : 변화하는 환경에서는 보로노이 다이어그램을 실시간으로 갱신할 필요가 있으며, 이는 추가적인 계산 비용을 발생

4.6 확률적 로드맵(Probabilistic Roadmap, PRM)

• 주로 고차원 공간에서의 경로 계획 문제에 사용되는 기법
• 복잡한 환경 내에서 무작위 샘플링을 통해 노드를 생성하고, 이 노드들 간의 연결 가능성을 평가하여 경로를 계획
  
• PRM의 주요 단계
  -> 샘플링 : 환경에서의 임의의 점(노드)을 샘플링, 샘플링은 일반적으로 균일 분포 또는 다른 휴리스틱 방법을 사용
  -> 노드 연결 : 샘플링된 노드들 간의 연결 가능성을 평가, 두 노드 사이의 직선 경로가 장애물 없이 이동 가능한지 확인하여, 가능한 경우 두 노드를 연결하는 에지를 생성
  -> 로드맵 생성 : 장애물 충돌 등으로 인하여 제외되는 노드 및 간선 등을 제외하고 로드맵을 완성

4.6.1 확률적 로드맵의 특징

• 빠른 경로 탐색 : 그래프가 한 번 구성되면, 다양한 시작점과 목표점에 대해 빠르게 경로를 탐색할 수 있음
• 유연성과 확장성 : 샘플링 및 연결 전략을 조정함으로써 다양한 환경과 요구 사항에 맞게 PRM을 적용 가능
• 초기 그래프 구성 비용 : 크고 복잡한 환경에서는 충분한 노드를 샘플링하고 연결하는데 상당한 계산 비용이 들 수 있음
• 동적 환경 적용의 어려움 : 환경이 변할 경우, 그래프를 새로 구성하거나 업데이트해야 하는데, 이는 실시간 응용에서는 어려움을 줄 수 있음

4.7 가시성 그래프: 실습

import matplotlib.pyplot as plt
from shapely.geometry import LineString, Point, Polygon # Python의 Shapely 라이브러리에 포함된 모듈로 평면 기하학(2D geometry)을 조작하고 분석할 수 있는 기능
from itertools import combinations

def is_visible(p1, p2, obstacles):
    """
    두 점 p1,p2 가 주어진 장애물에 의해 가려지지 않고, 장애물 내부를 통과하지 않는지 확인
    """
    line = LineString([p1, p2])  # 선분 생성, 두 점 p1, p2를 연결하는 LineString 객체를 생성
    for obs in obstacles:        #장애물과의 교차 확인: 입력으로 받은 모든 장애물 obstacles에 대해 반복문을 수행
        if line.crosses(obs) or obs.contains(line): # 1) line.crosses(obs): line이 obs라는 장애물과 교차하는지 확인, 장애물을 교차한다는 것은 선분이 장애물의 경계선을 건너는 것을 의미
            return False                            # 2) obs.contains(line) : 선분 line이 장애물 obs 내부에 완전히 포함되는지 확인, 이 경우에도 두 점사이의 경로가 장애물에 의해 차단
    return True

def create_visibility_graph(vertices, obstacles):
    """
    주어진 꼭짓점과 장애물을 기반으로 가시성 그래프를 생성
    """
    edges = []   # 에지 리스트 초기화
    for p1, p2 in combinations(vertices, 2):  # 모든 꼭짓점 쌍에 대한 반복, combinations(vertices, 2)는 주어진 vertices 리스트에서 모두 가능한 두 점의 조합을 생성, 이는 각 꼭짓점 쌍 (p1,p2) 에 대해 반복문을 수행
        if is_visible(p1, p2, obstacles):   # 가시성 확인 : 각 꼭짓점 쌍에 대해 is_visible 함수를 호출, 이 함수는 두 점 p1, p2 사이에 직선 경로가 장애물에 의해 차단되지 않는지를 결정
            edges.append([p1,p2])   # 에지 추가 : 만약 is_visible 함수가 True를 반환하면, (p1 ,p2)쌍은 서로 볼 수 있다는 의미이므로, 이 쌍을 edges 리스트에 추가
    return edges

def plot_graph(vertices, edges, obstacles):  
    """
    가시성 그래프의 장애물을 시각화함.
    """
    plt.figure()    # 그래프 창 초기화: plt.figure()를 호출하면 새로운 그래프 창을 생성,
    ax = plt.gca()  # plt.gca() 를 사용하여 현재 활성화된 축(Axis)를 호출

    #장애물 플롯
    for obs in obstacles:   # 장애물 시각화 : obstacles 리스트에 있는 각 장애물 obs에 대해 반복
        x, y = obs.exterior.xy  #obs.exterior.xy를 호출하여 장애물의 외곽선을 구성하는 x좌표와 y좌표를 획득
        ax.fill(x, y, alpha = 0.5, fc = 'r', ec = 'black') # ax.fill 메서드를 사용하여 이 좌표들로 정의된 장애물의 영역을 채우서 그림
        # 여기서 alpha는 채우기 색상의 투명도, fc는 채우기 색상을, ec는 외곽선 색상을 지정
    # 가시성 그래프 플롯
    for edge in edges: # 가시성 그래프 시각화 : 생성된 에지(연결선) 리스트 edges를 반복하여 각 에지에 대해 두 점 p1과 p2 사이에 선을 도시
        p1, p2 = edge   
        plt.plot([p1.x, p2.x], [p1.y, p2.y], 'go-', markersize = 5) #plt.plot 함수를 사용하여 이 선들을 그래프에 추가
        # 여기서 점들은 녹색 원으로 표시('-go'), 마커 크기는 5로 설정

    plt.axis('equal') # 축 비율 설정 : plt.axis('equal')은 x축과 y축의 스케일을 동일하게 만들어 그림의 비율을 1:1로 설정
    plt.show()  # 그래프 표새 : 마지막으로 plt.show()를 호출하여 준비된 그래프 점을 사용자에게 표시

#장애물 정의
obstacles = [Polygon([(2,2), (2,3), (3,5), (4,4), (4,2)]),
             Polygon([(6,8), (8,8), (8,6)]),
             Polygon([(10,2), (10,4), (12,5), (12,3)])]

#모든 꼭짓점 정의
vertices = [Point(x,y) for obs in obstacles for x,y in obs.exterior.coords[:-1]] 
"""
obs.exterior.coords : Polygon 객체 obs의 외곽선을 나태는 좌표를 가져옴, coords는 해당 외곽선을 구성하는 (x,y)쌍의 시퀀스
for x,y in obs.exterior.coords[:-1] : 이 내부 루프는 각 Polygon 의 외곽선 좌표를 반복하고 각 좌표 쌍 (x,y)를 추출
"""

# 가시성 그래프 생성
edges = create_visibility_graph(vertices, obstacles)

# 그래프 시각화
plot_graph(vertices, edges, obstacles)

5. 포텐셜 필드 지도 표현

5.1 포텐셜 필드(Potential Field)

• 인력(Attractive Field)
  -> 목표 지점에서 로봇에게 작용하는 인력을 생성
  -> 일반적으로 로봇과 목표 지점 간의 거리에 비례하여 증가, 목표에 가까울수록 인력이 감소하여, 목표 지점에 도달할 때 최소값에 이른다.
• 척력(Repulsive force)
  -> 장애물로부터 로봇에게 작용하는 반발력을 생성
  -> 로봇이 장애물에 가까울 수록 증가, 장애물로부터 안전한 거리를 유지하도록 유도.
  -> 반발력은 일반적으로 장애물로부터 거리에 반비례하여 증가하며, 일정 거리 이상 떨어져 있을 때는 영향을 미치지 않음
  

5.1 포텐셜 필드 지도 표현 특징

• 구현이 간단하고 직관적이며, 동적 환경에서 실시간으로 경로를 계획하고 조정하는데 효과적
• 또한, 로컬 센서 데이터를 기반으로 한 반응형 네비게이션을 지원하여 자율적인 로봇의 의사 결정에 유용
• 로컬 미니마(Local Minima) 문제에 취약할 수 있음
  -> 로봇이 로컬 최소값에 갇혀 목표 지점으로 이동하지 못하는 상황이 발생할 수 있음
• 또한 매우 복잡한 환경에서는 장애물 주변에서의 진동(Oscillation)이나 과도한 경로 계획 문제가 발생할 수 있음

5.2 포텐셜 필드 지도 : 실습

import numpy as np
import matplotlib.pyplot as plt

#환경 설정
goal = np.array([8, 8])  # 로봇이 이동하고자 하는 목표 지점의 좌표를 나타내는 numpy 배열
obstacles = [np.array([3,3]), np.array([5,5])] # 장애물 위치를 나타내는 numpy 배열 리스트
start = np.array([1,1]) #로봇의 시작 위치를 나타내는 numpy 배열

# 매개변수 설정
attractive_scale = 1.0 # 목표 지점에 대한 인력의 크기를 제어하는 스케일 매개변수
repulsive_scale = 5.0  # 장애물로부터의 반발력의 크기를 제어하는 스케일 매개변수
repulsive_threshold = 10.0 # 반발력이 적용되는 최대 거리, 이 거리 이내에 있는 장애물은 로봇에 대한 반발력을 발생

# 그리드 설정
x = np.linspace(0, 10, 100) # x와 y는 그리드의 x 및 y 좌표를 나타내는 numpy 배열
y = np.linspace(0, 10, 100)
X, Y = np.meshgrid(x,y) # X와 Y는 그리드의 x 및 y 좌표를 포함하는 2차원 배열

def calculate_potential_field(x, y):
    #  로봇이 목표 지점으로 이동하려는 인력 필드를 계산. 목표 지점까지의 거리에 따라 인력이 증가
    attractive_potential = 0.5 * attractive_scale * np.sqrt((x - goal[0])**2 + (y - goal[1])**2)

    # 장애물로부터의 반발력 필드를 계산, 장애물과의 거리가 repulsive_threshold보다 작을 때, 반발력이 적용
    repulsive_potential = 0
    for obs in obstacles:
        dist_to_obs = np.sqrt((x - obs[0])**2 + (y - obs[1])**2 )
        if dist_to_obs <= repulsive_threshold:
            repulsive_potential += 0.5 * repulsive_scale * (1 - dist_to_obs / repulsive_threshold)
    
    #총 포텐셜 계산
    total_potential = attractive_potential + repulsive_potential
    return total_potential, attractive_potential, repulsive_potential

# calculate_potential_field 함수를 그리드의 각 점에 적용하여 포텐셜 필드를 계산
PF, AP, RP = np.vectorize(calculate_potential_field)(X,Y)

# 결과 시각화
plt.figure(figsize=(8,6))
contour = plt.contourf(X, Y, PF, levels = 50, cmap = 'viridis') # 계산된 포텐셜 필드를 등고선 그래프로 시각화
plt.colorbar(contour)
plt.plot(goal[0], goal[1], 'r*', markersize = 15, label = 'Goal') #  목표 지점을 빨간 별로 표시
plt.plot(start[0], start[1], 'bs', markersize = 10, label = 'Start') # 시작 위치를 파란 사각형으로 표시
for obs in obstacles:
    plt.plot(obs[0], obs[1], 'ko', markersize = 10, label = 'Obstalces') # 장애물 위치를 검은색 원으로 표시
plt.legend()
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Artificial Potential Field')
plt.show()