HSVC ( hierarchical state validity checking )

motion planning?

• 로봇이 주어진 환경에서 목표지점까지 장애물을 피하면서 이동할 경로를 찾는 과정이다.
• 기본적인 과정
  • 1. 환경분석
  • 2. 경로 탐색
  • 3. 경로 최적화

 

상태의 유효성? ( validity of a state )

• 로봇이 특정한 상태에서 이동할 수 있는지 or 목표 상태에 도달할 수 있는지 여부를 판단하는 개념이다.
  • 즉, 주어진 상태가 유효한지 아닌지를 평가하는 기준을 말한다.
• 상태가 유효하기 위한 조건
  • 1. 충돌이 없어야한다.
  • 2. 경로 제한을 준수 하였는가
  • 3. 물리적으로 제약이 없는지. ( 이동 범위 , 조작 범위 , 로봇의 크기 등 )
  • 4. 상태가 목표 상태로의 유효한 이동을 허용하는지.
• 즉, "내가 현재의 state에서 다른 state로의 전이가 가능한지"이다.
  • (  전이할때 장애물 같은 제약이 있다면, 당연히 전이 불가능이다. )

 

 

사족 보행 로봇의 실제 형상을 bounding volume으로 점진적으로 근사하는 과정

HSVC ( hierarchical state validity checking )

• motion planning 알고리즘에서 사용되는 방법이다.
  • 특히 고차원 공간 or 로봇의 planning 문제에서 상태의 유효성을 계층적으로 검사하는 방식이다.
  • 즉, 전체 state_space를 한번에 정밀하게 검사하는 대신에, 여러 해상도의 '계층'으로 나누어서 점진적으로 유효성을 확인하는 방식이다.
• 계층적 구조로 나누는 방법
  • HSVC는 state_space( 상태 공간 )을 "거친coarse"부터 "세밀한fine"단계까지 여러 계층으로 나눈다.
    가장 상위 단계에서는 단순화된 모델을 사용해서 충돌이나 제약 위반 여부를 빠르게 판단한다.
• 바운딩 볼륨 및 근사
  • 예를 들어서, 로봇의 복잡한 형상을 단순한 바운딩 박스나 구체로 근사해서 상위 계층에서 검사하는 것이 가능하다.
    해당 단계에서 "유효(안전 , 충돌없음)"으로 판단되면, 보다 세부적인 기하학적인 정보가 반영된 하위 단계에서 다시 한 번 더 정밀하게 확인한다.
• 동작 방식 ( 단계적 검사 coarse-to-fine )
  • 1.  최상위(거친) 단계 
    • 전체 상태를 단순화한 모델로 표현하여, 대략적인 충돌여부나 제약 위반을 신속하게 확인한다.
      • 만약에 이 단계에서 "유효하지 않음"이 판정되면, 상세한 검사를 하지않고 해당 상태를 배제한다.
  • 2. 하위(세밀한) 단계
    • 최상위 단계에서 유효하다고 판단한 상태에 대해서, 점점 더 세밀한 모델을 적용해서 다시 검사함.
      • 만약, 이 단계에서도 하나라도 위반하면, 유효하지 않음으로 간주.
  • 재귀적/반복적 처리
    • 각 계층의 검사 결과는 다음 단계의 검사에 영향을 준다. 그리고 여러 단계에 걸쳐서 상태의 유효성이 최종적으로 결정됨.
• 장점
  • 계산 효율성
    • 전체 상태 공간에 대해서 정밀한 검사를 하면 계산 비용이 매우 높아지지만, HSVC는 거친 단계에서 많은 비유효 상태를 조기에 배제함으로써 전체 계싼의 부담을 크게 줄여준다.
  • 고차원 문제 해결
• 고려사항 
  • 정확도와 근사의 균형
    
    • 상위계층의 근사가 너무 단순하다면, 실제로는 유효하지 않은 상태가 "유효"판정이 될 위험이 존재하다.
      그러니 각 계층간의 근사 수준과 전이 방식에 대해서 세심히 설계해야함