Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets

저자: Thomas Cohn, Mark Petersen, Max Simchowitz, Russ Tedrake · RSS 2023

라이선스

오픈 액세스
논문: CC BY 4.0

아래 내용은 모두 논문의 라이선스(CC BY 4.0)에 따라 논문 전문을 바탕으로 하며, 그림에는 저자를 표기했습니다.

요약

되감기는(wrap-around) 관절 공간(모바일 베이스, 연속 관절)을 평탄한 다양체로 다루어, GCS 최단 경로 계획기가 여전히 전역 최적이고 충돌 없는 경로를 내도록 한다.

중요한 이유

모바일 매니퓰레이터와 회전 제한이 없는 베이스 관절을 가진 로봇 팔도 이제 궤적의 모든 점이 충돌 없음을 보증하고, 정확히 풀릴 경우 인증된 자유 공간 내에서 최적인 계획기를 사용할 수 있다. 논문은 또한 양의 곡률(예: SO(3) 볼 조인트나 자유 부유 물체)이 볼록성을 깨뜨림을 증명하여, 이 접근법이 갈 수 없는 지점을 표시한다.

문제

Marcucci 등의 GCS 계획기는 자유 구성 공간을 볼록 집합들로 분해하여 충돌 없는 전역 최적 경로를 찾지만, 유클리드 구성 공간에서만 가능하다. 360° 완전히 회전할 수 있는 모바일 베이스나 연속 회전 관절은 한 바퀴 돌아 제자리로 오므로 그 구성 공간은 유클리드가 아니다. 인위적인 관절 한계를 추가하거나 각도를 무한한 실수로 취급하면, 최적해가 실행 불가능해지거나 답에 대한 사전 지식과 많은 중복 집합이 필요해진다.

제안 방법

저자들은 구성 공간을 리만 다양체로 모델링하고 Graph of Geodesically-Convex Sets(GGCS)를 정의하며, 이것이 일반 GCS의 보장을 유지함을 증명한다. 1-DoF 관절과 SE(2) 베이스로 구성된 모든 로봇을 포함하는 평탄한(곡률 0) 다양체의 경우, 각 집합을 국소 등거리 차트를 통해 유클리드 공간으로 대응시키고, 문제는 아핀 전이 제약을 가진 표준 혼합 정수 볼록 GCS 문제로 환원된다. 영역은 IRIS로 확장하고 관절별로 볼록성 반지름으로 제한하며, 연속성 제약을 가진 구간별 Bézier 궤적도 그대로 적용된다.

핵심 통찰

SE(2), 모든 1차원 다양체, 그리고 평탄한 다양체들의 곱은 평탄하므로, 단일 DoF 관절과 모바일 베이스로 이루어진 로봇은 이 방법에 맞는다; 3-DoF 볼 조인트는 그렇지 않다
각 IRIS 영역을 관절별로 볼록성 반지름으로 제한하면, 그 영역을 다양체로 다시 대응시켰을 때 측지적으로 볼록하게 유지됨이 보장된다
전역적으로 정렬된 좌표를 가진 평탄한 공간에서는 전이 사상이 아핀이므로, 끝점 일치 제약과 미분 연속성 제약이 볼록하게 유지된다
양의 곡률을 가진 점이 하나만 있어도 리만 거리 함수는 그 점의 모든 근방에서 비볼록이 된다(정리 5)

주요 결과

토러스 위의 점 로봇: 0.79 s 만에 되감기는 최적 경로; 연속 관절을 가진 5관절 평면 팔: 5.36 s와 4.63 s에 계획하며, 그중 하나는 가운데 관절을 360° 넘게 회전시킨다
평면 팔: relax-and-round 경로 길이 7.749와 8.448, 분기 한정(branch-and-bound) 최적값 7.274와 8.008
연속 베이스 관절을 가진 KUKA iiwa(시뮬레이션): 18개 볼록 영역을 사용한 머그잔 분류 동작 14개, 동작당 평균 25.75 s(범위 4.63–50.30 s)
PR2(시뮬레이션, 15차원 구성 공간), 선반 도달 작업 7개: GGCS 경로는 모든 경우에 충돌이 없었다. 예: 1M→4M 길이 3.875, PRM은 14.554; Drake-Trajopt와 PRM+Trajopt는 때때로 더 짧은 경로를 냈지만 약간 충돌했다
PR2 온라인 계획 시간은 GGCS-Planner가 25.51–66.15 s, PRM은 0.49–0.54 s, Drake-Trajopt는 2.26–15.23 s, PRM+Trajopt는 11.61–40.10 s였다
PR2 오프라인 준비: IRIS 영역 하나에 평균 30.20 s(8.56–75.42 s), 모든 영역을 병렬로 156.63 s; 100,000개 샘플의 PRM 구축에 124.39 s

한계

저자들은 이 방법이 비선형 동역학이나 닫힌 기구학 연쇄 같은 비볼록 비용 및 제약을 다룰 수 없고, 볼 조인트도 다룰 수 없다고 밝힌다
SO(3) 같은 양의 곡률 공간은 그곳에서 거리 함수가 비볼록임이 증명되므로 제외된다
최적성은 영역들이 덮는 '인증된' 자유 공간 내에서만 성립한다; 성능은 영역 선택에 크게 좌우되며, PR2의 경우 일부 중간 영역은 수작업으로 추가되었다
PR2의 온라인 계획 시간(25.51–66.15 s)은 비교한 모든 베이스라인보다 길었다
모든 로봇 결과는 시뮬레이션이다; 저자들은 암묵적 기구학 제약을 가진 양팔 계획과 접촉을 통한 계획을 향후 과제로 꼽는다

분야에 미친 영향

RSS 2023 Best Paper Award 최종 후보이며, 인용 수는 44회이다. 저자들은 모든 궤적의 인터랙티브 녹화를 결과 웹사이트에 공개한다.

초록

고차원 시스템에 대해 최적이면서 충돌 없는 궤적을 계산하는 것은 어려운 문제이다. 샘플링 기반 계획기는 차원 수 때문에 어려움을 겪고, 궤적 최적화기는 최적화 지형에 내재한 비볼록성 때문에 지역 최솟값에 갇힐 수 있다. 혼합 정수 계획법을 사용해 이러한 비볼록성을 포괄하고 전역 최적 궤적을 찾는 방법은 최근 큰 가능성을 보여 왔는데, 이는 부분적으로 실행 시간을 크게 줄이는 타이트한 볼록 완화와 효율적인 근사 전략 덕분이다. 이러한 접근법은 이전에는 유클리드 구성 공간에 한정되어 모바일 베이스나 연속 회전 관절에는 사용할 수 없었다. 본 논문에서는 구성 공간을 리만 다양체로 모델링하여 이러한 경우를 다루며, 곡률이 0인 경우를 혼합 정수 볼록 최적화 문제로 환원하는 절차를 기술한다. PR2 양팔 모바일 매니퓰레이터에 대한 효율적이고 충돌 없는 궤적 생성을 포함하여 다양한 로봇 플랫폼에서 결과를 시연한다.

링크

arXiv 2305.06341: https://arxiv.org/abs/2305.06341
DOI 10.1177/02783649241302419: https://doi.org/10.1177/02783649241302419
PDF: https://arxiv.org/pdf/2305.06341v1
프로젝트 페이지: https://ggcs-anonymous-submission.github.io/