피아노를 옮겨보자! 도전, Motion Planning!

여기 두 로봇 청년이 있습니다. 이들은 어느 날 아름다운 소녀로부터 부탁을 받지요.

모솔이었던 두 로봇 청년은 '이게 웬 우리 집마당에 유전 터지는 소리냐!'라며 부탁을 덥석 받아들이지요. 그런데 웬걸...ㅠ 소녀의 집은 피아노가 진입하기도 힘든 쓰레기장이 아니겠습니까...! 이 피아노를 어떻게 하면 옮길 수 있을까요...? 오늘의 주제는 "piano mover's problem"으로 유명한 motion planning 입니다.

이야기의 시작은 역시나 joint space의 문제에서부터 시작합니다 (관련 블로그: 로봇이 움직이는 공간 Joint Space). 일단 피아노 문제는 잠시 접어두고, 우선 로봇의 장애물 회피 문제부터 이야기해보죠. 왜냐하면 피아노를 옮기는 데에는 장애물 회피가 핵심이니까요.

Terry Taewoong Um, a RRT demonstration, 2009

 동영상과 같이 로봇 팔이 장애물에 갇혀있습니다. 일단 팔을 빼려면 장애물의 위치를 알아야하죠. 로봇의 카메라는 이런 정보를 알려줍니다.

"장애물은 (0,0,10)부터...(30,30,10)까지 있고, 또.. (0,0,30)부터 (30,30,30)까지...." (task space)

근데 문제는 이게 아닙니다. 사실 로봇이 알고싶었던 정보는

"그래서 내 팔의 관절이 7개가 있는데, 그럼 (0º, 0º, 30º, 70º, 0º, 45º, 0º)에는 장애물이 있다는거야 없다는거야?" (joint space)

라는거죠. 결국 로봇을 움직이기위해서는 3차원 task space 상의 환경정보를 7차원⁽¹⁾의 joint space 공간으로 변환할 필요가 있는 것입니다. 하지만 모든 장애물 정보를 미리 7차원 공간으로 변환해두는 것은 그렇게 만만한 일이 아닌지라, 이대신 그때그때 "이거 충돌해? 안해?"라는 로봇의 질문에 대해 "Yes / No"로 대답해주는 collision checker⁽²⁾를 주로 이용한답니다.

collision checker는 준비되었고, 이제 두 로봇이 한 팔씩을 사용해서 피아노를 옮긴다고 해볼까요?  내 팔 7, 내 바퀴 2,  너 팔 7, 너 바퀴 2, 피아노 3(orientation) 자유도 등 우리는 총 21자유도에 매순간 입력을 넣어줘야하겠네요. 거기에 구속조건까지 있고...ㅠㅠ 이거 어떻게 계산한다죠...?ㅠㅠㅠ (절 to the 망....ㅠㅠ)

RRT in 2D space, http://msl.cs.uiuc.edu/rrt/

정답은...... 이거 계산 안해요! 아니 못해요!ㅋㅋㅋ 이걸 어떻게 계산한답니까ㅎㅎㅎ 이렇게 해석적인 정답(analytic solution)을 얻기 힘들 때 로봇공학자들이 기대는 언덕이 있죠. 바로 확률통계입니다. 이제 컴퓨터 계산능력 믿고 무식하게 나갈 겁니다.⁽³⁾ 21자유도의 공간의 시작점과 끝점으로부터 random tree를 뻗어나가며 두 손이 맞닿길 기대하는거죠. 이것이 바로 대표적 motion planning 알고리듬인 RRT(Rapidly-exploring Random Trees)의 핵심 아이디어입니다.

"(0,0,20,27,30,80,100,90,25,20,....,30,80,100) 이거 장애물 부딪혀? 아니야? 그럼 OK, 트리 확장해~ 다음...."

이런 질문을 무수히 던지며 장애물에 안부딪히는 점들을 하나씩 확장해나가는 거죠. 결국 두 tree는 만나게되고 두 손 맞잡은 길은 하나의 path가 됩니다. 아까 위에 로봇팔 동영상에서 로봇이 이상하게 막 떨었었죠? 그 이유는 바로 로봇이 random tree에 의한 지그재그 길을 따라갔기 때문이랍니다. (이 문제는 smoothing 의 후처리 과정을 통해 해결 가능합니다.) 중요한 건 이거죠.

"해냈어! 해냈다고!! 난 미녀한테 이용당한게 아니었어!!! 자아실현한거라고!!!" 

RRT demonstrations ,B.K.Kim, C.S.Suh, T.T.Um and F.C.Park, 2010

저는 석사시절에 Tangent Space RRT라는 방법을 개발했었는데요, 구속조건들이 있을 때 무식하게 질문을 던지지말고, 어떻게하면 효율적으로 질문들을 던질 수 있을까에 대한 해답을 제시했었지요.⁽⁴⁾ (문맥과 상관없는 제 자랑입니다ㅋㅋㅋ). 위 동영상은 저와 저 졸업 후 후배들이 함께 만든 동영상입니다. 결국 저는 피아노를 옮겼드랬죠ㅋㅋㅋ 이젠 미녀의 부탁~ 걱정없어요~ :D


(1) 사실 완벽한 힘 제어(동역학 기반 제어)를 위해서는 7차원의 관절위치값 뿐만 아니라 관절속도값, 관절가속도값 등 총 21차원의 joint space에서 해석이 필요합니다.

(2) 예전에 두 원이 떨어져있는지, 접하는지, 교차하는지 문제 풀었던 기억나시죠? 이렇듯 collision checker는 로봇의 링크들을 실린더, 다면체 등으로 근사하여 도형간의 상대거리를 계산한답니다. 결국 이것도 수학, 수학, 수학...>.<

(3) 확률통계가 무식한 분야라는 것은 절대아닙니다. 제가 요즘 machine learning 쪽으로 끙끙거리며 연구하고있거든요. 확률통계야말로 로봇의 uncertainty(불확실성)을 해결하기 위한 최후의 보루입니다. RRT에서도 topology에 대한 고려와 sampling의 completeness에 대해 매우 엄밀하게 다루어지고 있죠. 확률통계 짜앙~

(4) 이와 관련된 저의 논문은 http://scholar.google.co.kr/scholar?hl=ko&q=terry+taewoong+um&btnG=&lr= 에서도 찾으실 수 있습니다. 두 편의 인용수가 각각 7회, 3회라능~ 신기신기~ㅋ

* 제 글은 RSS로도 구독하실 수 있습니다. http://t-robotics.blogspot.kr/feeds/posts/default