Graph of Convex Sets

• 다른 이름: GCS, graphs of convex sets
• 카테고리: Planning & manipulation › Trajectory optimisation
• 태그: motion-planning, convex-optimization, trajectory-optimization, configuration-space, manipulation

자유 공간의 볼록 영역들을 그래프로 연결하고, 볼록 최적화로 그 영역들을 지나는 매끄럽고 충돌 없는 경로를 찾는 모션 계획 정식화.

정의

볼록 집합 그래프(graph of convex sets, GCS)는 모든 정점이 볼록 집합이고 각 집합 안에서 고르는 점이 연속 결정 변수인 그래프다. 간선은 서로 오갈 수 있는 집합들을 잇고, 간선 비용과 제약은 양 끝 점들의 볼록 함수다. 이런 그래프를 통과하는 가장 저렴한 경로를 찾는 것은 어떤 집합들을 통과할지라는 이산적 선택과, 각 집합의 어디로 갈지라는 연속적 선택을 결합한다. Tobia Marcucci, Russ Tedrake와 동료들은 이 최단 경로 문제를 정식화하고, 일반적으로는 혼합 정수 문제이지만 흔히 타이트하거나 거의 타이트한 강한 볼록 완화를 가진다는 것을 보였다.

모션 계획에서는 먼저 구성 공간의 충돌 없는 부분을 볼록 영역들의 모음으로 덮는데, 예를 들어 시드 점에서 장애물 없는 큰 다면체를 키워 나가는 IRIS 알고리즘을 사용한다. 각 영역은 정점이 되고, 겹치는 영역들은 간선으로 이어지며, 각 영역 안에서 궤적은 매끄러운 곡선, 보통 베지에 곡선으로 표현되는데, 곡선의 제어점이 영역 안에 있으므로 곡선도 영역 안에 머문다. 경로 길이, 소요 시간, 에너지 같은 비용과 속도 및 가속도 한계는 볼록 제약으로 쓴다. 완화 문제를 풀고 이를 반올림하면 샘플링 기반 탐색이나 후처리 없이 매끄럽고 충돌 없는 궤적을 얻는다.

이 접근법은 각 집합 안에서 일반적인 유클리드 기하를 가정한다. 한계가 없는 연속 회전 관절이나 이동 베이스의 방향처럼 구성 공간이 감겨 도는 로봇은 이 가정에 바로 들어맞지 않는다. 확장 방법은 볼록 집합을 다양체 위의 측지 볼록(geodesically convex) 집합으로 대체한다. 이는 임의의 두 점이 집합 안에 머무는 유일한 최단 경로, 즉 측지선으로 이어지는 집합이다. 이렇게 바꾸면 같은 그래프 정식화로 그런 비유클리드 공간에서 계획할 수 있다. GCS는 Drake 툴박스에서 사용할 수 있다.

중요한 이유

샘플링 기반 계획기는 실행 가능한 경로를 찾지만 보통 평활화가 필요하고 경로가 얼마나 좋은지에 대한 척도를 주지 않는다. GCS는 단일 최적화로 매끄럽고 제약을 준수하는 궤적을 만들며, 흔히 결과가 최적에 얼마나 가까운지에 대한 인증서도 함께 주므로, 선반이나 작업대처럼 고정된 셀에서 반복적으로 작업하는 로봇 팔에 가치가 있다.

주요 응용

• 고정된 작업 셀에서 로봇 암의 충돌 없는 궤적 계획
• 연속 관절이나 감겨 도는 구성 공간을 가진 로봇을 위한 계획
• 지형의 볼록 영역 위에서의 발 디딤 및 접촉 계획
• 복잡한 환경을 통과하는 드론의 최소 시간 궤적
• 공유 작업 공간에서의 양팔 및 다중 팔 계획

실제 사례

고정된 선반 칸 집합에서 물건을 집도록 팔을 배치하는 팀은 먼저 오프라인으로 충돌 없는 구성 공간의 볼록 영역을 생성하는데, 각 칸 앞과 안의 구성에 IRIS 시드를 둔다. 이 작업은 시간이 걸리지만 셀이 바뀔 때만 다시 하면 된다. 실행 시간에는 각 집기 요청이 현재 구성에서 한 칸 안의 목표로 가는 GCS 질의가 된다. 솔버는 속도 한계가 지켜지는 매끄러운 궤적을 반환하며, 풀이 시간은 영역 수에 따라 늘어나므로 팀은 영역 집합을 셀에 필요한 것보다 크게 하지 않는다. 목표가 모든 영역 밖에 있으면 질의가 실패하므로, 팀은 커버리지가 빠진 곳에 시드를 추가한다. 짧은 호라이즌의 충돌 검사가 여전히 모델에 없던 물체에 대비한다.

흔한 오해

• GCS는 자유 공간이 볼록이어야 한다 — 자유 공간이 볼록 영역들의 합집합으로 덮이기만 하면 되며, 이는 복잡한 형상을 근사할 수 있다
• GCS는 볼록 최적화로 항상 전역 최적해를 반환한다 — 완화는 흔히 타이트하지만 항상 그렇지는 않으며, 반올림이나 혼합 정수 풀이가 필요할 수 있다
• GCS는 충돌 검사를 완전히 대체한다 — 사용된 영역에 대해서만 충돌 없음을 보장하므로, 영역이 실제 환경을 반영해야 한다

알아야 할 사람

• 로봇 암과 드론을 위한 모션 계획 엔지니어
• 최적화 기반 계획 연구자
• 고정 셀 피킹 및 조립 시스템 통합자
• 계획과 볼록 최적화를 공부하는 로보틱스 학생

관련 기술

• Drake
• IRIS 영역 생성(IRIS Region Generation)
• 베지에 곡선(Bézier Curves)
• 볼록 최적화(Convex Optimization)
• 혼합 정수 볼록 계획법(Mixed-Integer Convex Programming)

관련 용어

• Configuration Space
• Motion Planning
• Trajectory Planning
• Mixed-Integer Programming
• Probabilistic Roadmap
• RRT*

관련 프로젝트

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
• OpenArm: 7DOF humanoid arm for physical AI research in contact-rich environments

동영상

• MIT Robotics - Russ Tedrake - Planning with Graphs of Convex Sets (in the age of foundation models): MIT Robotics