Motion Planning : A*

움직이는 자동차/로봇은 필연적으로 위치를 알아야 할 필요가 있으므로 Localization을 위한 3가지 filter에 대해 알아보았다. 그 다음 단계는 무었일까? 그것은 목표지점으로 빠르고 효과적인 방법으로 찾아가는 루트를 설정하는 일이다. 이것을 motion planning이라고 하며, 중요한 분야이다 보니 다양한 방법들이 제시되어 있다. 가장 간단한 방법은 현재 위치와 목표지점의 위치를 파악하여 목표지점의 방향으로 로봇이 진행하도록 하는 방법을 생각해 볼 수 있다. 도중에 장애물이 있으면 그 장애물을 피하거나 돌아가는 다양한 알고리즘을 도입하여 안정성을 높일 수도 있다. 그러나 장애물이 아니라 도로를 달린다고 하면, 장애물만 고려해서는 안될것이다. 효과적인 주행루트를 계산해 내는 방법이 필요하다. 즉, 네비게이션 시스템과 같은 알고리즘을 구현해야 하는 것이다.

A* method

우리가 출발점으로 부터 목표지점까지 가는 최적의 path라고 말한다면 일단 거리기준으로 최단거리를 의미한다. 물론 속도개념을 도입하여 최단시간을 최적이라고 말할 수 있다. 그러나 그 기준이 무엇이 되었든 최적의 path를 찾는 기법은 기본적으로 사용된다. 이 방법은 사실 개념이 복잡하지 않다. 주행 가능한 지점만을 통과하도록 하고 출발점에서 가까운 지점부터 포인트를 부여하고 전개할때마다 추가로 cost값을 더해서 많은 전개로 인해 큰 포인트가 부여된 path로는 가지 않는 것이다. 즉 돌아가면 출발점으로부터 더 많은 전개과정이 필요하므로 더 큰 포인트가 부여된다. 이러한 point를 g value라고 부른다. 이 방법은 한가지 단점이 있는데, 너무 돌아 가기때문에 더 이상 전개할 필요성이 없는 부분도 계속 고려하는 경우가 발생한다는 점이다. 이러한 단점을 극복하기 위해 제안된 알고리즘이 A* method이다. 이 방법에서는 기존의 g value외에 heuristic value를 추가로 도입한다. 이 heuristic value는 아래와 같은 규칙이 있다.

 h(x,y) <= minimum distance from goal

예를 들어, 목표지점으로 부터 멀어 지면 penalty 개념의 h 값을 높게 부여하되, 그 값이 goal과의 distance보다 높아서는 안된다. 그 이유는 이 값이 그보다 높으면 path를 평가시 penalty가 과도하게 부여되기 때문이다. 즉, 각 지점에서의 평가 점수 f는 아래와 같다.

 f = g + h(x,y)

이 방법을 사용하면 penalty가 높게 부여된 지점은 평가되상에서 제외되기 때문에 필요없는 지점까지 평가하려 하지 않고 최적 path를 찾아 나간다.

A* search algorithm 예

앞서 설명한 g value를 사용한 방법과 A* algorithm을 사용한 결과를 비교해 보기로 하자. 먼저 같은 구조를 가진 2차원 평면에서 ‘1’표기된 지점은 장애물을 나타내고, ‘0’으로 표기된 지점은 주행가능한(navigable)이라고 하자. Start 지점([0,0])에서 Goal([4,5])지점까지 최단 경로를 찾는 두가지 algorithm의 실행 결과를 아래 비교하였다. 왼쪽이 g value search, 오른쪽이 A* 알고리즘의 결과이다. 두 알고리즘 모두 결국 같은 최단 path를 찾아 내기는 하지만 찾는 과정에서 A* 알고리즘은 g value 알고리즘에 비해 계산하여 검토하는 지점이 적다. 왼쪽 행렬에서 ‘0’으로 표기된 지점은 계산하지 않은 영역이고, 오른쪽은 ‘-1’로 표기된 영역이 알고리즘이 최적 path를 찾기 위해 계산에 고려하지 않는 지점을 의미한다. 즉, A* 알고리즘이 보다 효율적으로 탐색한다는 것을 의미한다.

Search grid world

 

 

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중