1. 문제 정의 (Problem)

이 논문은 이족 보행 로봇의 발걸음 계획 (Footstep Planning) 문제를 다룹니다. 발걸음 계획은 로봇이 환경과 접촉 (Contact) 을 만들고 끊는 순서를 결정하는 문제로, 다음과 같은 주요 난제가 존재합니다.

• 조합적 복잡성 (Combinatorial Complexity): 접촉 상태의 순서를 결정하는 것은 지수적인 복잡도를 가지는 이산 (Discrete) 문제입니다.
• 연속성 vs 이산성의 딜레마:
  • 기존 A 알고리즘*은 도달 가능 영역 (Reachability) 을 이산화하여 사용하는데, 이는 해의 탐색 범위를 제한하고 조합적 복잡성을 악화시킵니다.
  • 혼합 정수 계획법 (MIP) 은 연속적인 형식을 지원하지만, 회전 (Rotation) 이 포함될 경우 계산 비용이 급증하여 실시간 적용이 어렵습니다.
• 비선형 제약: 로봇의 기구학적 제약 (Reachability constraints) 은 비선형이며, 이를 조합 문제와 동시에 처리하는 것이 어렵습니다.

2. 방법론 (Methodology)

저자들은 CASSR (Continuous A-Star Search through Reachability) 라는 새로운 프레임워크를 제안합니다. 이는 A* 검색을 "접촉 위치의 순서"가 아닌 **"접촉 표면 (Contact Surfaces) 의 순서"**로 재정의합니다.

핵심 구성 요소

1. 연속 도달 가능성 전파 (Recursive Reachability Propagation):

   • A* 탐색 그래프의 각 노드는 특정 접촉 표면 (Convex Contact Surface) 에 해당합니다.
   • 현재 노드에서 다음 단계로 도달 가능한 위치는 **볼록 다면체 (Convex Polytope)**로 표현됩니다.
   • 이 도달 가능 영역은 **민코프스키 합 (Minkowski Sum)**을 사용하여 재귀적으로 확장됩니다.
   • 각 확장 단계에서 도달 가능 다면체와 환경의 접촉 표면들을 교차 (Intersection) 시켜 새로운 자식 노드를 생성합니다.

2. 2 단계 계획 프로세스:

   • 단계 1 (A 검색):* CASSR 알고리즘을 사용하여 로봇이 목표에 도달하기 위해 밟아야 할 접촉 표면의 시퀀스와 각 발의 요 (Yaw) 방향을 결정합니다.
   • 단계 2 (QP 해결): 결정된 표면 시퀀스와 방향을 바탕으로, **2 차 계획 (Quadratic Program, QP)**을 풀어 구체적인 **접촉 위치 (Contact Locations)**를 계산합니다. 이 QP 는 항상 실행 가능 (Feasible) 하도록 보장됩니다.

3. 새로운 휴리스틱 (Heuristic):

   • 목표까지의 비용 추정 (Cost-to-go) 으로 **EPA (Expanding Polytope Algorithm)**를 사용합니다.
   • EPA 는 다면체 (Polytope) 와 목표점 (또는 다른 다면체) 사이의 최소 거리를 효율적으로 계산하여, 회전 거리를 근사화하고 더 정확한 휴리스틱을 제공합니다.

4. 안전성 비용 (Safety Cost):

   • 접촉 표면의 가장자리에서 최소 거리를 최대화하는 새로운 안전 비용을 도입하여, 로봇이 표면 가장자리에 발을 딛는 것을 방지하고 안정성을 높입니다.

3. 주요 기여 (Key Contributions)

1. 실시간 장기 계획용 연속 도달 가능성 표현을 가진 최초의 A 솔버:*
   • 기존 이산화된 A*의 한계를 극복하고, 긴 시간 범위 (Long Horizon) 에서도 실시간으로 계획이 가능한 연속적인 형식을 도입했습니다.
2. EPA 기반의 새로운 Cost-to-Go 휴리스틱:
   • 회전 각도를 포함한 다면체 간 거리를 효율적으로 계산하여, 회전 문제를 다루는 데 있어 기존 휴리스틱보다 우수한 성능을 보입니다.
3. 강건한 안전성 비용:
   • 접촉 표면의 경계로부터의 최소 거리를 최대화하는 비용을 도입하여 계획된 발걸음의 물리적 안정성을 보장합니다.

4. 실험 결과 (Results)

Talos 로봇을 대상으로 6 가지 시나리오 (계단, 국소 최소값 탈출, 좁은 통로 등) 에서 실험을 수행했습니다.

• 성능 비교:
  • 기존 이산 A 대비:* CASSR 은 최대 100 배 이상 빠른 속도를 보였습니다. 특히 회전이 허용되거나 환경이 복잡해지면 (예: 국소 최소값 시나리오) 성능 차이가 극대화되었습니다.
  • MIP 솔버 대비: CASSR 은 최적의 조건에서도 MIP 보다 최소 6 배, 최대 20 배 이상 빠르며, 30 단계 계획 시에는 훨씬 더 우월한 성능을 보였습니다.
• 계산 시간:
  • 복잡한 시나리오에서도 125ms 미만의 시간 내에 최대 30 단계의 발걸음 시퀀스를 계획할 수 있었습니다.
• 노드 확장 효율:
  • CASSR 은 이산 A*보다 훨씬 적은 수의 노드를 확장하여 해를 찾았습니다 (최대 2000 배 적은 노드). 이는 연속적인 제약 표현이 조합적 복잡성을 효과적으로 줄였음을 의미합니다.
• 최적성:
  • EPA 휴리스틱이 허용 가능 (Admissible) 하지는 않지만, 실험 결과 CASSR 은 항상 **최소 단계 수 (Ground Truth)**를 가진 최적 해를 찾았습니다.

5. 의의 및 결론 (Significance)

• 실시간 제어 파이프라인 통합: CASSR 은 복잡한 이족 보행 로봇의 장기 계획 (Long-horizon planning) 을 실시간 제어 루프에 통합할 수 있는 가능성을 입증했습니다.
• 효율성과 정확성의 균형: MIP 의 전역 최적성 보장과 A의 결정론적 효율성을 결합하면서도, MIP 의 계산 비용 과부하를 피하고 이산 A의 해 탐색 한계를 극복했습니다.
• 미래 전망: 이 프레임워크는 충돌 회피와 동역학을 고려한 더 복잡한 비선형 제약 조건과 머신러닝을 결합하여 확장될 수 있는 기반을 제공합니다.

요약하자면, CASSR 은 이족 보행 로봇의 발걸음 계획 분야에서 연속적인 도달 가능성 모델을 A* 알고리즘에 성공적으로 적용하여, 실시간성, 계산 효율성, 그리고 해의 품질을 모두 획기적으로 개선한 획기적인 연구입니다.