Artificial Potential Field

  Unmanned Aerial Vehicle(UAVs)나 무인자동차, 그리고 무인 이동로봇의 개발이 두드러지게 나타나면서, Collision avoidance 기술은 무인 이동체의 필수적인 기술이 되었습니다. 본 포스팅에서는 Collision Avoidance에서 가장 널리 사용되고 있는 알고리즘 중의 하나인 Artificial Potential Field에 대해 알아보도록 하겠습니다.

 

Introduction

  Artificial Potential Field는 citation이 7,000번 이상 될 정도로 굉장히 interest한 알고리즘 중의 하나입니다. 비록 여러가지 Limitation이 존재하지만, Potential Field 알고리즘은 simple하기 때문에 구현하기가 쉽고, real-time으로 로봇을 operation 할 수 있기 때문에 많은 사람들이 사용하는 알고리즘입니다.

 

Concept

  다음 그림은 Potential Field의 Concept을 보여주고 있습니다. Concept은 간단합니다. 도달해야할 Goal(목표지점)은 red arrow로 나타낸 것처럼 attractive force 즉, 인력을 발생시키고, 멀어져야 할 Obstacle은 blue arrow로 나타낸 것처럼 repulsive force 즉, 척력을 발생시킵니다. 로봇은 attractive force와 repulsive force의 합 벡터 방향인 green arrow 방향으로 이동하도록 경로를 생성합니다. 

 

 

Algorithm

  Attractive force와 repulsive force에 대해서 수식과 함께 자세히 알아보도록 하겠습니다.

 

1. Attractive Force

  다음은 attractive force를 수식으로 나타낸 것입니다. 수식에서 사용된 notation은 아래에 적어놨습니다. Attractive force는 크기 성분(Fa,mag)과 방향성분(괄호안의 수식)으로 나눌 수 있습니다. X축 방향은 코사인으로, Y축 방향은 사인으로 나타낼 수 있기 때문에, x축 방향과 y축 방향은 red arrow로 표시한 것을 참고하여 수식의 괄호안에 있는 분수식으로 각각 표현할 수 있습니다.. Attractive force의 크기는 사용자가 임의로 정해줄 수 있습니다.

 

2. Repulsive Force

  다음은 repulsive force를 수식으로 나타낸 것입니다. 수식에서 사용된 notation은 아래에 적어놨습니다. Repulsive force도 크기 성분(괄호밖의 수식)과 방향성분(괄호안의 수식)으로 나눌 수 있습니다. 로봇은 장애물과 멀리 떨어져 있으면 천천히 피해도 되지만, 가까이 있으면 빨리 회피해야 합니다. 따라서 Repulsive force의 크기는 사용자가 임의로 정해줄 수 있지만, do로 repulsive force gain을 나눠서 obstacle과의 거리가 멀면 Repulsive Force의 크기를 작아지게 만들고, obstacle과의 거리가 가까우면 Repulsive Force의 크기가 커지도록 설계했습니다. 마지막으로 로봇은 obstacle이 위치한 방향과 반대방향으로 움직여야 하기 때문에 –를 붙여야 합니다.

 

 

3. Artificial Potential Field

  로봇은 위에서 계산한 Attractive Force와 Repulsive Force의 벡터합의 방향과 크기로 이동합니다. 결국, Attractive Force로 인해 target에 접근하면서도 Repulsive Force로 인해 장애물과의 충돌을 회피할 수 있습니다.

 

 

Limitations

 Artificial Potential Field 알고리즘은 simple하여 적용하기 쉽지만 다음과 같은 inherent limitation이 있습니다.

 

1. Local minima (로컬미니멈)

 - 여러개의 obstacle이 있거나 reversed C-shape(거꾸로된 C 모양)의 obstacle이 있을 경우, repulsive force 들어 서로 상쇄되어 local minima에 빠질 수 있습니다.

 

2. No passage between closely spaced obstacles (가까이 위치한 장애물을 지나갈 수 없음)

 - 장애물의 Repulsive force의 합이 Attractive force 보다 크면, 좁은 공간을 지나갈 수 없습니다.

 

3. Oscillations in the presence of obstacles (여러개의 obstacle이 있을때 오실레이션 발생)

 - 여러개의 장애물이 존재하는 환경에서 각각의 장애물의 의해 Repulsive force의 합이 변하기 때문에 오실레이션(진동)이 발생합니다. 이것은 로봇이 불안정하게 움직이도록 하는 경로를 생성합니다.

 

4. Oscillations in narrow passages (좁은 공간에서 오실레이션 발생)

 - 좁은 통로를 통과할 경우, 양쪽의 좁은 벽에서 동시에 Repulsive force가 발생해서 stable하게 이동할 수 있습니다. 그러나, 좁은 공간에서 distabance 또는 한쪽으로 튀어나온 벽이 있을 경우, 연속적으로 반대쪽 벽으로 밀어내려는 힘 때문에 양쪽 벽을 왔다갔다 하면서 결국 충돌할 수 있습니다.

 

Conclusion

  Artificial Potential Field 알고리즘은 가장 interest한 Obstacle avoidance 알고리즘 중의 하나로 알고리즘의 Simplicity 덕분에 많은 연구자들이 사용하고 있습니다. 비록 inherent limitations 가 존재하지만, 이러한 문제들을 해결하려는 연구들이 진행되고 있기 때문에 최근에 발표된 여러가지 논문들을 참고해서 본인의 연구에 적용해 보시길 바랍니다.

 

Reference

[1] Khatib, Oussama. "Real-time obstacle avoidance for manipulators and mobile robots." Autonomous robot vehicles. Springer, New York, NY, 1986. 396-404.

[2] Koren, Y., & Borenstein, J. (1991, April). Potential field methods and their inherent limitations for mobile robot navigation. In ICRA (Vol. 2, pp. 1398-1404).