Motion Planning Problem
이 포스트에서는 Motion Planning Problem 이란 무엇이며, 어떤 특징을 갖고 있는지에 대해 다루어 보겠습니다.
Motion planning problem 이란, 어떤 로봇에 대해 정지한 장애물 사이를 통과하는 경로를 계산하는 문제입니다. 간단하게 말해서 여기서 저기까지 어떻게 갈까? 라는 질문을 하는 거죠. 여기서 '어떤 로봇' 은 관절 로봇이 될 수도 있고, 드론이나 무인항공기가 될 수도 있습니다.
위의 그림은 motion planning 의 예시입니다. 좁은 통로를 따라서 길쭉한 막대기를 옮긴다던가 피아노를 이 방에서 저 방으로 옮긴다던가 하는 문제가 바로 motion planning 의 좋은 예시가 되겠습니다.
이 문제를 풀기 위한 알고리즘 혹은 motion planner 가 있다고 할 때, 그 알고리즘의 입력과 출력은 다음과 같습니다.
- Input
- 로봇과 장애물의 geometry
- 로봇의 움직임을 나타내는 동역학 방정식
- 초기/최종 configuration (혹은 상태변수)
- Output
- 초기/최종 configurations 를 연결하는 collision-free configurations 의 연속적인 집합(경로)
장애물을 피하는 경로를 얻어야 하기 때문에, 먼저 장애물이 있는 configuration 과 장애물이 없는 free configuration 을 수학적으로 다음과 같이 표현할 수 있습니다.
For every obstacle $B_i,i=1,\cdots,q \in W$,
$$\begin{align}
CB_i &= \{q\in C: A(q) \cap B_i \neq \emptyset\}\\
C_\textrm{free} &= C\backslash \cup_{i=1}^qCB_i
\end{align}$$
각각 $C$-obstacle space과 free space 라고 부를 수 있겠습니다. Motion planning problem 을 수학적으로 표현하면 어떤 $\tau:[0,1]\rightarrow C_\textrm{free}$ 가 존재해서, $\tau(0) = q_{init},\tau(1) = q_{goal}$ 을 만족하는 $\tau(t)$ 를 찾는 문제가 되겠습니다.이상적으로는 Theoretic algorithm 이 completeness 를 추구하다 보면 실제로 적용하기가 힘들고, 따라서 completeness 를 약화시킨다던지, 몇 가지 단순화를 거쳐 효율이 좋은 Heuristic algorithm 을 사용하게 됩니다. 하지만 효율을 얻는 대신 상황이 달라지면 성능이 일관되지 않다거나 하는 다른 문제가 발생할 수도 있는 것이죠.
보통 문제를 두 가지로 구분해서 풀게 됩니다. Global planning 과 local planning 이 그것인데요, 각각의 특징을 정리하면 다음과 같습니다.
- Global approach
- 오프라인에서 설계한다.
- 전체 지도가 있어야 한다.
- 장애물 회피가 힘들고, 부정확할 수 있다.
- Local approach
- 온라인에서 바로 계산한다.
- 계산이 복잡하지 않다.
- 최적해가 아닐 수 있고, local minima 에 빠질 수 있다.
다음 포스트는 motion planning problem 의 한 가지 예라고 할 수 있는, point robot 에 대한 path planning 기법에 대해 알아보도록 하겠습니다.
댓글
댓글 쓰기