Motion planning - 3. 알고리즘들

모션플래닝과 관련된 여러가지 알고리즘들이 존재한다. 알고리즘들은 아주 간단한 planning 문제를 해결하는 것에서 시작하여 점점 발전하여왔다. 각 알고리즘에 관련된 학습을 하면서 간단한 예제들을 만들어보면 이해를 하는데에 도움이 되지 않을까 싶어 알아보려고 한다.

---

저차원의 문제들은 Configuration space에 grid(격자)를 그려 계산하는 grid based 알고리즘과 $C_{free}^{}$안의 연결성이나 모양을 계산하는 geometric algorithm 방식으로 해결할 수 있다.

 

 

복잡한 제한조건을 가진 고차원 시스템의 정확한 motion planning은 computationally intractable하다. intractable하다는 뜻은 이론적으로 해결될 수 있으나, 실제로 해결하려면 자원(resource)를 너무 요구하는 것을 말한다. resource는 대체로 시간이다.

 

Potential field algorithm은 효율적인 편이다. 그러나 local minima에 빠질 수 있다. local minima는 좁은 시야의 관점에선 최적이라고 생각되지만 전체적인 시각으로 봤을 땐 최적이 아닌 방법에 빠져 헤어나오지 못하는 문제를 말한다. 

 

Sampling based algorithm은 local minima 문제를 피할 수 있고 속도도 아주 빠른 편이다. 그러나 갈 수 있는 경우가 하나도 없는 경우, 즉 no path exist인 상황을 바로 결정할 수 없고 그럴 수 있는 확률을 시간이 감에 따라 찾아낼 수 있다. Sampling based algorithm은 고차원 공간에서 motion planning을 해결하는 가장 최신의 기술이다. 응용 예로는 로봇 매니퓰레이터, 분자 생물학, 디지털 캐릭터의 애니메이션, 보행 로봇에서 사용한다.