Quadtree

• 
• Quad tree는 계층적 데이터 구조 중 하나
• 이 구조는 2차원 공간을 표현하고 관리하는 데 효율적이며, 특히 이미지 처리, 공간 인덱싱, 그리고 로봇의 환경 인식 및 맵핑에서 중요한 역할
• Quad tree는 공간을 재귀적으로 네 개의 동일한 사분면으로 분할하여 구성
• 각 노드는 공간의 한 부분을 대표하며, 그 공간이 더 이상 분할할 필요가 없거나 일정 기준에 도달할 때까지 네 개의 자식 노드(사분면)로 나뉩니다.

Quad Tree의 기본 구조

Quad tree의 각 노드는 최대 네 개의 자식을 가질 수 있습니다:

• 북서(NW, North-West)
• 북동(NE, North-East)
• 남서(SW, South-West)
• 남동(SE, South-East)

Quad Tree의 사용

1. 공간 분할(Spatial Partitioning):

• 로봇이 탐색하는 환경을 더 작고 관리하기 쉬운 부분으로 분할하여,
• 로봇이 효율적으로 경로를 계획하고 장애물을 회피할 수 있도록

2. 경로 계획(Path Planning):

• 로봇의 현재 위치와 목적지 사이의 최적 경로를 찾는 데 사용될 수 있음
• Quad tree는 공간을 분할함으로써 로봇이 탐색해야 할 영역을 줄이고, 계산 복잡성을 감소

3. 장애물 탐지(Obstacle Detection) 및 환경 매핑(Environment Mapping)

• 로봇이 주변 환경을 인식하고, 장애물의 위치를 정확히 파악하여 맵에 표시하는 데 유용
• 각 사분면은 장애물의 존재 유무에 따라 구분될 수 있으며, 이 정보는 로봇이 안전하게 탐색하도록 돕습니다.

Quad Tree의 수학적 표현

• Quad tree의 구현에는 수학적 수식이 직접적으로 적용되는 경우가 적지만, 기본적으로는 2차원 공간을 재귀적으로 분할하는 알고리즘을 기반으로 합니다.
• 공간을 분할하는 기준은 특정 영역의 크기, 포함된 데이터의 양, 또는 미리 정의된 깊이 등
• 예를 들어, 공간 (S)를 분할하는 기준이 되는 함수를 (f(S))라고 할 때, (f(S))가 특정 임계값보다 크면 (S)를 네 개의 사분면으로 분할합니다. 이 과정은 재귀적으로 반복됩니다.

결론

• Quad tree는 로봇 내비게이션에서 공간을 효율적으로 표현하고 처리하는 데 매우 유용한 데이터 구조
• 이를 통해 로봇은 복잡한 환경에서도 효과적으로 탐색하고, 장애물을 회피하며, 목적지까지의 최적 경로를 계획할 수 있습니다.

---

Quad tree와 path planning

• Quad tree 구조는 로봇 경로 계획(Robot Path Planning)에 있어서 환경을 효율적으로 나누고 관리하는 방법으로 자주 사용됩니다.
• 로봇 경로 계획에서는 로봇이 출발지에서 목적지까지 장애물을 피해 최적 또는 효율적인 경로를 찾는 것이 목표
• Quad tree는 이러한 과정을 지원하기 위해 2차원 공간을 재귀적으로 네 개의 사분면으로 분할하여 관리하는 데이터 구조
• 이를 통해 대규모 환경에서도 빠르게 특정 영역을 조회하고, 경로 계획을 수립할 수 있습니다.
• 다음은 Quad tree를 이용한 로봇 경로 계획의 구체적인 로직입니다.

1. 환경 분할

• 초기 단계:
  • 전체 환경을 대표하는 Quad tree의 루트 노드를 생성합니다.
  • 이 노드는 전체 맵을 나타냅니다.
• 분할 과정:
  • 환경 내에 장애물이 포함된 영역이나 경로 계획에 중요한 특징을 가진 영역을 기준으로 현재 노드를 네 개의 사분면으로 분할합니다.
  • 각 사분면은 자식 노드로 표현되며, 이 과정은 지정된 분할 기준(예: 최소 영역 크기, 장애물 밀도)을 만족할 때까지 재귀적으로 수행됩니다.

2. 경로 탐색 알고리즘과의 통합

• 노드 평가:
  • 각 Quad tree 노드는 로봇이 통과할 수 있는 공간인지, 장애물이 있는 공간인지 등의 정보를 포함할 수 있습니다.
  • 이 정보는 A* 같은 경로 탐색 알고리즘에서 특정 노드를 거쳐가는 경로의 가능성과 비용을 평가하는 데 사용됩니다.
• 경로 탐색:
  • 경로 탐색 알고리즘은 Quad tree의 구조를 이용하여 시작 노드에서 목표 노드까지의 경로를 찾습니다.
  • 이 과정에서 불필요한 영역의 탐색을 최소화하고, 효율적으로 목적지까지의 경로를 계산할 수 있습니다.

3. 동적 환경 대응

• 환경 업데이트:
  • 로봇이 이동하는 환경이 동적으로 변할 수 있습니다
  • 이러한 변경 사항이 감지되면, 관련된 Quad tree의 노드를 업데이트하고 필요한 경우 재분할하여 경로를 다시 계산합니다.
• 경로 재계산:
  • 환경의 변화로 인해 기존의 경로가 더 이상 최적이거나 실행 가능하지 않게 될 경우, 변경된 Quad tree를 기반으로 새로운 경로를 계산

4. 최적화와 휴리스틱

• 휴리스틱 함수:
  • 경로 탐색의 효율성을 높이기 위해 휴리스틱 함수를 사용하여 각 노드의 가치를 추정할 수 있습니다.
  • 이 함수는 목적지까지의 예상 거리, 장애물을 피하는 비용 등을 고려할 수 있습니다.
• 최적화 기법:
  • 다양한 최적화 기법을 적용하여 Quad tree 구조의 생성과 경로 탐색 과정을 더 빠르고 효율적으로 만들 수 있습니다.
  • 예를 들어, 불필요한 노드의 생성을 방지하거나, 경로 탐색 과정에서 우선 순위를 설정하여 중요한 영역을 먼저 탐색하도록 할 수 있습니다.
• Quad tree 구조를 사용하는 로봇 경로 계획은 이러한 로직을 기반으로 하여 복잡하고 다양한 환경에서 로봇이 효율적으로 목적지까지 이동할 수 있도록 도와줍니다.

---

quad tree graph grenetation VS grid map graph grenetation

• Quad tree 구조를 사용한 로봇 경로 계획과 일반적인 그리드 맵(grid map)을 사용한 경로 계획을 비교했을 때, 각각의 접근 방식은 고유한 장단점을 가지고 있습니다. 이러한 차이는 데이터 구조의 효율성, 처리 속도, 메모리 사용량 등 여러 측면에서 나타납니다.

Quad Tree의 장점

1. 메모리 효율성:

• Quad tree는 공간을 재귀적으로 분할하여 관리하기 때문에, 비어 있는 공간이 많은 환경에서 메모리 사용량을 크게 줄일 수 있습니다.

2. 동적 환경 대응력:

• 환경에 변화가 생겼을 때, 해당 영역만을 대상으로 빠르게 트리 구조를 업데이트하고 재분할할 수 있어, 동적 환경에서의 경로 재계산이 효율적

3. 적응적 공간 분해능:

• Quad tree는 지역적 특성에 따라 공간을 다르게 분할할 수 있어, 장애물이 밀집되어 있는 영역을 더 세밀하게 나누어 처리할 수 있습니다.
• 이는 경로 계획의 정밀도와 효율성을 높일 수 있습니다.

Quad Tree의 단점

2. 탐색 시간: 일부 경우에서 Quad tree의 탐색 속도가 그리드 맵에 비해 느릴 수 있습니다. 특히, 공간을 매우 세밀하게 분할한 경우, 경로 탐색 알고리즘의 탐색 깊이가 깊어져 탐색 시간이 증가할 수 있습니다.
3. 비균일 탐색 성능: 공간의 분할이 비균일하게 이루어질 경우, 경로 탐색의 성능이 예측하기 어렵고, 일관성이 떨어질 수 있습니다. 이는 특히, 장애물 분포가 균일하지 않은 환경에서 문제가 될 수 있습니다.

Grid Map의 장점

2. 탐색 속도: 동일한 크기의 셀로 구성된 그리드 맵에서는 경로 탐색 알고리즘의 계산 속도가 일반적으로 빠르며, 특히 단순한 환경에서 효율적

Grid Map의 단점

1. 메모리 사용량: 특히 대규모 환경에서, 그리드 맵은 빈 공간도 동일하게 저장해야 하므로, Quad tree에 비해 메모리 사용량이 많을 수 있음
2. 정밀도와 메모리 사용량의 트레이드오프: 그리드의 크기를 줄여 공간의 정밀도를 높이면, 메모리 사용량이 기하급수적으로 증가합니다.
3. 동적 환경 대응: 환경의 변화를 반영하기 위해서는 전체 맵을 업데이트하거나 재구성해야 하며, 이는 비효율적일 수 있습니다.

---

Quad tree에서 보통 주행 가능한 graph generation은 어떤 방식으로 진행돼?

• Quad tree 구조에서 주행 가능한 그래프(Traversable Graph)를 생성하는 과정은 일반적으로,
• 환경의 공간적 특성을 분석하여 주행 가능한 영역과 장애물을 구분하고, 이 정보를 기반으로 주행 경로를 계획할 수 있는 그래프를 구성하는 방식으로 진행됩니다.
• Quad tree의 장점은 공간을 효율적으로 분할하여 관리할 수 있다는 점입니다.

Quad Tree를 이용한 그래프 생성 방식

1. 환경 분할 및 표현:

• Quad tree를 사용하여 환경을 네 개의 사분면으로 재귀적으로 분할합니다.
• 이때, 각 사분면(노드)은 장애물이 있는 영역인지, 주행 가능한 영역인지를 나타냅니다.
• 분할의 기준은 특정 임계값(예: 사분면 내 장애물의 비율, 최소 사분면 크기 등)에 따라 결정될 수 있습니다.

2. 노드 분류:

• 각 Quad tree 노드를 주행 가능한 영역, 장애물 영역, 혼합 영역 등으로 분류합니다.
• 이 과정에서 주행 가능한 영역만을 추출하여 그래프의 노드로 사용할 수 있음

3. 연결성 분석:

• 주행 가능한 노드들 사이의 연결성을 분석하여, 이들을 연결하는 에지를 생성
• 연결성 분석은 노드들 사이의 거리, 장애물의 존재 유무, 주행 가능 영역의 연속성 등을 고려하여 진행됩니다.

4. 그래프 최적화:

• 생성된 그래프에서 불필요한 노드나 에지를 제거하고, 경로 계획의 효율성을 높이기 위해 그래프를 최적화합니다.
• 이 과정에서 주행 경로의 길이, 안전성, 주행 비용 등을 고려할 수 있습니다.

Quad Tree와 Voronoi 그래프의 통합 사용

• Quad tree 구조에서도 Voronoi 그래프를 통한 경로 계획 방식을 적용할 수 있습니다.
• 이 경우, Quad tree는 주로 환경을 효율적으로 분할하고 관리하는 데 사용되며, Voronoi 그래프는 이러한 환경 내에서 주행 가능한 경로를 찾는 데 활용됩니다.
• Voronoi 기반 경로 생성:
  • 환경 내의 장애물을 기준으로 Voronoi 다이어그램을 생성하고, 이를 통해 로봇이 장애물로부터 안전한 거리를 유지하며 이동할 수 있는 경로를 계획합니다.
• Quad tree와의 통합:
  • Quad tree로 표현된 환경 정보를 사용하여 Voronoi 다이어그램을 생성할 때, 장애물의 위치와 주행 가능한 영역을 더 정확하게 식별할 수 있습니다.
  • 이를 통해 더 효율적이고 안전한 경로 계획이 가능해집니다.
• Quad tree 구조를 이용한 그래프 생성 방식은 환경의 복잡성에 따라 다양하게 조정될 수 있으며, 경로 계획의 목적과 조건에 따라 다른 경로 계획 알고리즘과 결합하여 사용될 수 있습니다.
• Quad tree의 재귀적인 특성과 공간 분할 능력을 활용하면, 대규모 또는 복잡한 환경에서도 효율적으로 주행 가능한 경로를 찾아낼 수 있는 강력한 도구가 됩니다.