PV-OSIMr: A Lowest Order Complexity Algorithm for Computing the Delassus Matrix

저자: Ajay Suresha Sathya, Wilm Decré, Jan Swevers · IEEE Robotics and Automation Letters (RA-L) 2024

라이선스

• 오픈 액세스
• 논문: CC BY-SA 4.0

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

요약

PV-OSIM의 계산 순서를 재배열하여 전파되는 구속 조건이 6차원을 넘지 않도록 함으로써 O(n + m²)의 Delassus 행렬 계산을 달성하며, 저자들은 이것이 점근적으로 최적임을 보인다.

중요한 이유

발과 다지 손을 가진 휴머노이드처럼 접촉이 많은 로봇은 시뮬레이션과 제어를 위해 이 행렬을 높은 빈도로 필요로 하므로, 연산이 적을수록 솔버가 빨라진다. m × m 행렬을 구성하고 n개의 관절을 모두 방문하는 것은 피할 수 없으므로, 저자들은 O(n + m²)가 최적 차수라고 주장한다. 알고리즘은 CasADi 코드 생성으로 구현되었고, 논문에 따르면 Pinocchio 라이브러리에도 C++로 구현되었다.

문제

Delassus 행렬, 즉 역 작업 공간 관성 행렬은 구속력과 구속 가속도를 연결하며, 구속 및 접촉 동역학 시뮬레이션과 작업 공간 제어에 필요하고, MPC와 RL에서 가장 비용이 큰 단계인 경우가 많다. 이를 단순하게 계산하면 O(n³ + m²n)의 비용이 든다. 가장 잘 알려진 알고리즘인 EFPA는 O(n + md + m²)에 도달하며, 저자들의 이전 PV-OSIM은 O(n + m²d)로, 많은 구속 조건을 많은 관절을 거쳐 전파해야 할 때 확장성이 떨어진다.

제안 방법

PV-OSIMr은 PV-OSIM의 후방 스윕을 수정하여, 구속 조건 수에 따라 커지는 구속 공간 행렬을 전파하는 대신 연속한 분기 링크(집합 N) 사이에서 고정 크기 6×6 확장 힘 전파자와 공간 역관성을 전파한다. N에 대한 제한된 전방 스윕이 역관성을 계산하고, 제한된 후방 스윕이 각 엔드이펙터의 구속 공간 전파자를 계산하며, Delassus 행렬의 각 블록은 상수 시간에 조립된다. 이로써 O(n + m²) 복잡도가 얻어진다.

핵심 통찰

• 한 링크가 6차원보다 많은 구속 차원을 지지할 때는, 구속 공간 항을 직접 전파하는 것보다 6D 공간 물리량을 전파하고 나중에 구속 공간 항을 복원하는 편이 더 저렴하다.
• 비용이 큰 물리량은 구속된 링크들의 가장 가까운 공통 조상에서만 계산하면 되므로, 추가 스윕은 축소된 링크 집합에 대해서만 수행된다.
• 점근적 복잡도가 낮다고 해서 작은 로봇에서 연산 횟수가 적다는 보장은 없다. EFPA는 3회 스윕 구조와 링크별 좌표계 변환 때문에 시험한 거의 모든 메커니즘에서 PV-OSIM 및 PV-OSIMr보다 비용이 컸다.
• LTL-OSIM은 복잡도가 더 높음에도 단일 Shadow 핸드에서 EFPA를 앞섰는데, 손의 분기 구조가 만들어 내는 희소성을 활용하기 때문이다.

주요 결과

• 복잡도: PV-OSIMr O(n + m²), 이에 비해 PV-OSIM O(n + m²d), EFPA O(n + md + m²), KJR O(n + m²d), LTL-OSIM O(nd² + m²d + md²), 단순 계산 O(n³ + m²n).
• 발마다 3D 점 접촉 4개(발당 12D)로 서 있는 Atlas: PV-OSIM은 PV-OSIMr보다 19.9% 더 많은 연산이 필요했다. 발마다 6D 용접 구속 하나를 두면 두 알고리즘은 동일했다.
• Shadow 핸드를 단 Atlas(손가락 끝마다 3D 구속, 손당 15D): IV-D절은 차선의 효율을 보인 알고리즘인 PV-OSIM보다 최대 약 34% 적은 연산을 보고하는 반면, 결론에서는 Atlas 예제에서 최대 24% 개선이라고 서술한다.
• 각 분기 끝에 6D 용접 구속을 둔 분기형 시험 메커니즘에서 PV-OSIMr은 분기가 하나일 때 PV-OSIM과 같았고, 분기가 둘 이상일 때부터 더 완만하게 증가했다. 한쪽에 분기가 열 개인 긴 메커니즘에서는 결국 EFPA가 PV-OSIM을 앞섰다.
• 한 경우에는 PV-OSIM이 약 1.5% 적은 연산을 필요로 했다. 양손과 양발에 6D 용접 구속을 둔 Atlas로, 구속 조건이 부유 베이스에 이르기 전에 관절 세 개만 통과하는 경우이다.
• 모든 벤치마크는 CasADi 구현에서 얻은 연산 횟수이며, 실제 경과 시간 측정이 아니다.

한계

• 6차원보다 많은 구속 차원이 소수(세 개 이하)의 단일 DoF 관절만 통과할 때는 PV-OSIM의 rank-1 갱신이 PV-OSIMr의 rank-6 계산 두 번보다 유리하므로 PV-OSIM이 더 저렴할 수 있다.
• 구속 조건이 부유 베이스에서만 만나거나 메커니즘이 단일 체인일 때는 PV-OSIMr이 PV-OSIM보다 나은 점이 없다.
• 결과는 측정된 실행 시간이 아니라 연산 횟수로 보고된다.
• 알고리즘은 운동학적 트리에 대해 제시되며, C++ Pinocchio 버전은 논문 채택 이후에야 공개될 예정이었다.

분야에 미친 영향

이 논문은 RA-L 2025 Best Paper Award를 수상했으며 인용 수는 4회이다. 저자들은 CasADi 구현을 GitHub에 소스 코드로 공개했으며, C++ 버전이 Pinocchio 라이브러리에 구현되어 채택 시 공개될 예정이라고 밝힌다.

초록

우리는 운동학적 트리에 대한 Delassus 행렬(역 작업 공간 관성 행렬이라고도 함)을 계산하는 효율적인 알고리즘 PV-OSIMr을 제시하며, 그 계산 복잡도는 문헌에 알려진 것 중 가장 낮은 차수이다. PV-OSIMr은 힘 전파자와 운동 전파자의 합성 가능성을 이용해 Popov-Vereshchagin(PV) 솔버의 계산을 최적화하여 유도된다. 그 계산 복잡도는 O(n + m²)로, 원래 PV-OSIM 알고리즘의 O(n + m²d) 및 확장 힘 전파자 알고리즘(EFPA)의 O(n+md+m²)과 비교된다. 여기서 n은 관절 수, m은 구속 조건 수, d는 운동학적 트리의 깊이이다. Delassus 행렬 계산은 m × m 크기의 행렬을 구성해야 하고 n개의 관절을 모두 최소 한 번은 고려해야 하므로, PV-OSIMr의 점근적 계산 복잡도는 최적이다. 또한 우리는 알고리즘을 벤치마크하여 실제로 PV-OSIM과 EFPA보다 효율적인 경우가 많음을 확인한다.

링크

• arXiv 2310.03676: https://arxiv.org/abs/2310.03676
• DOI 10.1109/LRA.2024.3469829: https://doi.org/10.1109/LRA.2024.3469829
• PDF: https://arxiv.org/pdf/2310.03676v1
• 코드: https://github.com/AjSat/spatial_V2