Motion Planning : Dynamic Programming

앞서 소개한 A* method로도 훌륭하지만, 이번 포스팅은 다양한 문제에 범용적으로 사용 가능한 강화학습(Reinforcement Learning)기법인 Dynamic Programming을 사용하여 최적 path을 찾아내는 방법에 대한 글이다. RL을 구현하는데 가장 많이 사용하는 environment중의 하나가 grid world이므로, 최적 path를 찾는 환경이 이와 비슷하고, DP가 motion planning에 적용 가능하다는 것은 알 수 있다.

Path search의 경우, DP의 reward개념보다는 cost 개념을 도입한다. 즉 cost가 가장 적은 path를 따라가면 어느지점에서든 목표지점으로 가는 가장 짧은 단거리를 알아 낼 수 있다. 그러나 DP는 value function을 Bellman식을 사용한 update를 수행해야 하므로 모든 지점에 대해 value function을 구해야 하는 단점이 있다. 그러나 장점도 있다. 모든 지점에 대해 value function 값이 구해져 있기 때문에, 출발점이 어디든 곧바로 최적 path를 알아 낼 수 있다는 점이다.  반면에, A* method는 로봇/자동차의 시점을 가지고 있다. 즉 로봇의 출발점이 달라지면 path 평가를 다시 해야 한다. 또한 road map에 대한 사전 정보를 가지고 있어야 한다는 특징도 있다.

Dynamic programming에 대한 방법을 이미 소개한 바 있지만, 최적 path를 찾는 문제에 적용할 때는 추가적인 고려사항이 있다. 먼저 reward의 개념이 아니고 cost의 개념이 필요하다. 그러므로 reward의 maximization이 아니라 cost의 minimization 접근방법을 사용한다. 더 복잡한 문제는 주행과 관련하여 cost를 부여할때 고려사항이 또 있다는 점이다. 필자도 처음에는 기계적으로 접근했다가 문제점을 발견하였다.

일반적으로 자동차 주행에 있어서 직직, 좌회전, 우회전에 대해 같은 cost값을 적용하지 않는다. 가장 선호하는 것은 직진이 많은것이 좋고 그다음에는 우회전(일본과 같은 경우는 좌회전) 그리고 좌회전이 가장 선호되지 않는다. 신호를 기다려야 하기 때문이다. 그러므로 3가지 action에 대해 같은 cost를 부여하지 않고 다른 cost를 부여하며, 특히 좌회전의 경우에 높은 cost를 부여하게 된다. 여기서 문제가 발생한다. 자동차의 주행방향에 따라 좌표상 좌회전과 우회전의 방향이 달라지기 때문이다. 물론, 자동차에 탑승한 탑승자의 입장에서는 주행방향에 관계없이 좌회전과 우회전은 모두 같다. 하지만, 자동차에 탑승하지 않은 입장에서 value function을 구해야 하는 DP에서는 문제가 발생한다. 주행방향에 따라 구분하여 개별적으로 value function의 cost를 부여해야 하기 때문이다. 그러므로 주행 방향 (up, down, left, right)에 따라 별도의 value function을 구해야 하며, 최종 구해진 value function을 사용하여 turn을 할때마다 해당 주행 방향에 해당하는 value function을 사용하여 path를 설정하고, 이를 모두 종합하여 하나의 최적 path를 찾아 내는 방법을 사용해야 한다.


사실, 필자도 쉽게 접근했다가 DP를 적용하는 것이 그다지 쉽지 않다는 점을 알았다. 간단하지 않다는 점뿐만 아니라 단점도 존재한다. 주행방향이 앞서 설명한 4가지만 있는게 아니기 때문이다. 그러므로 최종적인 필자의 결론은 자동차에 탑승한 사람의 관점에서 value function을 평가해 줘야 한다는 점이다. A* search 방법이 더 효율적이라는 생각이다.


DP 적용 예

DP를 사용하여 grid map에서 최적의 path를 찾아내는 방법를 구현해 보았다. 먼저 앞서 언급한 바와 같이 자동차/로봇의 heading에 따라 구분하여 각 지점에서의 value function과 최적 이동방향을 계산해 낼 수 있다. 그리고 이 결과를 종합하여 최종 optimal path를 마지막 매트릭스와 같이 구해 낸다. 자동차의 직진방향에 따른 개별적인 최적 action 결과와 최종 합성 결과를 아래 나타내었다. ‘#’는 직진, ‘L’은 좌회전, ‘R’은 우회전을 의미한다. 출발지점은 [4,3]이고, 목표지점은 [2,0]으로 설정하였다. ‘0’으로 표기된 지점만 도로이며, 주행 가능하고, ‘1’로 표기된 지점은 주행할 수 없다. 왼쪽 결과는 좌회전에 대한 cost가 크지 않을때의 결과로 직진후 좌회전하여 목표지점으로 이동한다. 반면 오른쪽 결과는 좌회전에 대한 cost가 큰 경우로 교차로에서 좌회전 하지 않고 한 블럭을 우회전을 통해 돌아서 목표지점으로 가는것을 계산하여 선택하는 것을 볼 수 있다.

left turn policy grid world

Advertisements

답글 남기기

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

WordPress.com 로고

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

Google+ photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중