Cell Decomposition

Cell Decomposition

• 셀 분할은 로봇 경로계획에서 자유공간을 여러개의 cell로 나누고, 이러한 셀들을 연결한 그래프를 통해서 collision-free한 경로를 찾는 기법이다.
• 목적
  • 1. 복잡한 환경을 단순 영역(셀)들의 연결로 바꿔서,
  • 2. 셀 간의 인접성 그래프를 만든뒤에
  • 3. 그래프 탐색으로 경로 계획
  • ==> 이러한 과정을 거치면, 연속적인 공간이 아니라 이산 그래프 상에서 최단 경로를 효율적으로 구할수있다.

 

• 셀 분할 방법의 분류
  • 1. 정확 셀 분할( exact cell decomposition ) ==> 장애물 경계를 기준으로 셀을 나누기에, 자유공간을 정확히 분할하여,  후처리나 보간 없이도 "비충돌 영역"임을 보장
    • 1-1. 수직 셀 분할( vertical cell decomposition )
      • 장애물 꼭짓점에서 위와 아래로 선을 쏴서 사각형 셀을 생성한다.
    • 1-2. 사다리꼴 셀 분할( trapezoidal decomposition )
      • 장애물 각 꼭짓점에서 수직 이등분선을 그어서 사다리꼴 셀을 생성한다.
    • 1-3. 삼각 분할 ( triangulation )
      • 자유공간 전체를 삼각형으로 분할 
  • 2. 근사 셀 분할 ( approximate cell decomposition ) ==> 환경을 "균일" "비균일" 격자 셀로 나누어서 충돌 여부만 검사해 자유/충돌 셀로 구분
    • 2-1. 균일 격자 분할
    • 2-2. 쿼드트리 분할 
    • 2-3. 바이너리 공간 분할

---