Journal of Institute of Control, Robotics and Systems (2014) 20(2):138-142 http://dx.doi.org/10.5302/j.icros.2014.13.9006 ISSN:1976-5622 eissn:2233-4335 무인 주행 차량의 하이브리드 경로 생성을 위한 B-spline 곡선의 조정점 선정 알고리즘 A UGV Hybrid Path Generation Method by using B-spline Curve s Control Point Selection Algorithm 이 희 무, 김 민 호, 이 민 철 * (Hee-Mu Lee 1, Min-Ho Kim 2, and Min-Cheol Lee 2,* ) 1 Interdisciplinary Program in Robotics, Pusan National University 2 Mechanical Engineering, Pusan National University Abstract: This research presents an A* based algorithm which can be applied to Unmanned Ground Vehicle self-navigation in order to make the driving path smoother. Based on the grid map, A* algorithm generated the path by using straight lines. However, in this situation, the knee points, which are the connection points when vehicle changed orientation, are created. These points make Unmanned Ground Vehicle continuous navigation unsuitable. Therefore, in this paper, B-spline curve function is applied to transform the path transfer into curve type. And because the location of the control point has influenced the B-spline curve, the optimal control selection algorithm is proposed. Also, the optimal path tracking speed can be calculated through the curvature radius of the B-spline curve. Finally, based on this algorithm, a path created program is applied to the path results of the A* algorithm and this B-spline curve algorithm. After that, the final path results are compared through the simulation. Keywords: B-spline, UGV, optimal path generation, optimal path tracking Copyright ICROS 2014 I. 서론 무인주행은 환경 정보와 위치 정보를 기반으로 현재 위 치로부터 목적지까지 경로를 생성하고 제어하는 기술 체계 를 의미한다. 주행 기술은 이미 로봇청소기, 군용로봇, 무인 주행 자동차, 농업용 무인트랙터 등 개인용 서비스 로봇으 로부터 전문서비스 로봇까지 다양한 응용제품의 형태로 구 현되고 있다. 즉, 무인주행은 로봇의 이동 기능을 구현하는 것으로 제품 형태로 혹은 획기적인 기술 시연을 통해 보편 화되고 있다[1]. 그중 무인주행차량의 개발에 대한 관심은 날로 높아지고 있다. 미국에서는 DARPA Grand Challenge와 같은 무인주행 차량대회도 개최 되었고 구글(Google)에서는 이미 무인주행 차량으로 주행실험을 성공적으로 수행하였다[2,3]. 국내에서 도 현대자동차에서 무인주행자동차 대회를 개최 하였고 2013년에는 산업통상자원부가 주관하는 무인주행자동차 경 주대회가 개최되었다. 이렇듯 국내외적으로 무인주행차량에 대한 연구가 활발하게 진행됨에 따라 주위 환경인식, 경로 * Corresponding Author Manuscript received November 20, 2013 / revised December 20, 2013 / accepted December 31, 2013 이희무: 부산대학교 로봇관련협동과정(slm1023@nate.com) 김민호, 이민철: 부산대학교 기계공학부 (xho1995@gmail.com/mclee@pusan.ac.kr) 본 연구는 지식경제부 및 정보통신산업진흥원 융복합형 로봇 전문 인력양성 특수 환경 Navigation/Localization 로봇기술연구 센터 지원사업의 연구결과로 수행되었음(H1502-13-1001). 생성 및 주행방법 등 무인 차량 기술 발전을 촉진 시키고 있다. 주행은 위치인식과 환경지도로부터 이동경로와 방향을 결정하고 제어하는 기술이다. 그리고 기본적으로 무인주행 이 가능한 차량을 구현하기 위해서는 차량이 주행 할 수 있는 경로가 있어야 한다. 따라서 무인주행의 기준이 되는 경로를 계획하는 방법에 대한 연구가 필수적이다. 현재 다 양한 경로 계획 방법에 대한 연구가 이루어지고 있는데, 그 중 대표적인 알고리즘인 A*는 목표지점까지 최단거리의 경 로를 생성해 준다. 하지만 그리드 맵 기반으로 이루어져 있 기 때문에 직선의 조합으로만 이루어진 경로가 생성되는 단점이 있다[4]. 이러한 경우 일정 각도의 변곡점이 발생하 게 되므로 실제 조향장치가 있는 차량이 경로를 연속적으 로 주행을 하기에는 부적합한 부분이 있다. 그리고 A*는 최단거리의 경로 생성 알고리즘이기 때문에 주행속도는 경 로 생성 시 반영되지 않는 단점이 있다. 무인주행차량이 연 속적인 주행을 하기 위해서는 경로의 코너 부분이 부드러 운 곡선 형태로 이루어져야 한다. 또한 주행 시간 단축을 위해 생성된 경로의 속도 계획이 필요하다. 이를 위해 본 논문에서는 A*의 단점들을 보완하기위해 B-spline 곡선 방정식을 이용하여 A*알고리즘으로 생성된 경로를 곡선형태로 변환 하였다. 또한 B-spline 곡선은 조정 점의 위치가 경로에 많은 영향을 주기 때문에 조정점 선정 알고리즘을 이용하여 최적의 경로를 생성하였다. 그리고 B-spline 곡선의 곡률반경을 이용하여 생성된 경로의 속도 계획 및 경로 추종을 위한 핸들 조향 각을 제시 하였다. 마
A UGV Hybrid Path Generation Method by using B-spline Curve s Control Point Selection Algorithm 139 지막으로 본 논문에서는 A*알고리즘과 제안한 알고리즘의 비교를 위하여 시뮬레이션 프로그램을 작성하여, 시뮬레이 션을 수행하고 그 결과를 검토하였다. II. B-spline 곡선 경로 생성 알고리즘 1. B-spline 곡선 개요 A*알고리즘의 경로를 변환하기 위해 먼저 B-spline 곡선 에 대해 설명 하겠다. B-spline 곡선은 생성하고자 하는 곡 선을 포함하는 다각형의 조정점(Control Point)과 조정점의 영향을 혼합하는 블렌딩 함수(blending function)라는 함수로 이루어져 있다. 블렌딩 함수는 다음과 같은 성질을 갖도록 선택되어야 한다. 첫째, 블렌딩 함수는 조정점의 개수와 관 련된 n을 포함하지 않아야 하고, 결과적으로 블렌딩 함수의 차수, 즉 곡선의 차수는 조정점의 개수와는 무관하여야 한 다. 둘째로, 각각의 블렌딩 함수들은 매개변수의 전체 범위 중 서로 다른 일정범위에서만 0이 아닌 값을 갖도록 하여, 일정 범위의 곡선 부위에서는 그 범위에서 0이 아닌 블렌 딩 함수와 짝이 되는 한정된 개수의 조정점들만 형상에 영 향을 주어야 한다. 위의 조건을 만족시키는 블렌딩 함수를 Cox [5]와 de Boor [6]는 식 (1), (2)와 같은 점화식 의 형태의 블렌딩 함수를 제안 하였다. 여기서 는 매듭 값(knot value)으로, 이는 매개변수의 범위 를 여러 개의 간격으로 나누었을 때 각각의 블렌딩 함수가 0이 되지 않는 범위의 경계가 되는 매개변수 값이다. 앞의 블렌딩 함수와 조정점을 결합한 B-spline 곡선 방정 식은 식 (3)으로 정의한다. (1) (2) (3) 여기서 는 조정점 벡터이고, 는 블렌딩 함수이 다[7,8]. 2. 조정점 선정 알고리즘 이번 절에서는 B-spine 곡선을 이용하여 A*알고리즘으로 생성된 경로를 조정점 선정 알고리즘을 사용하여 경로를 곡선으로 변환하는 방법에 대해 알아보겠다. A*알고리즘은 주어진 지도에 경로를 생성하기 위해 지 도를 격자형태로 나누고 현재지점에서 인근 한 8방향을 검 색하여 그 중에 거리비용이 가장 작은 노드를 선택하여 경 로를 생성하는 알고리즘이다. A*알고리즘은 직선으로만 이 루어진 경로가 생성이 된다는 특징이 있다. 그림 1의 검정 선은 A*알고리즘으로 생성된 경로를 나 타낸다. A*알고리즘은 경로가 직선으로만 생성됨을 볼 수 있는데, 코너 부분이 직선으로 꺾여 있어 조향 장치를 가진 무인지상차량에는 적합하지 않음을 확인 할 수 있다. 그림 1의 붉은 선은 A*의 변곡점이 발생하는 지점을 조 그림 1. A*알고리즘과 B-spline 곡선 경로. Fig. 1. A* algorithm path and B-spline curve path. 정점으로 선정하여 생성한 3차 곡선 경로이다. B-spline 곡 선의 차수를 3차로 한 이유는 차수가 높아지면 계산 시간 이 증가하므로 차수는 낮을수록 좋은데, 실제 차량의 모델 링 식이 2차 미분 방정식의 형태로 이루어져 있기 때문에 2차 미분에 대해 연속성이 보장되어야 한다. 따라서 2차 미 분에 연속이며, 가장 낮은 차수인 3차로 선정하였다. B-spline 곡선은 조정점의 개수에 따라 곡선의 경로에 많 은 영향을 준다. 조정점의 개수가 적으면 적을수록 계산 시 간이 빨라지지만 너무 적게 선정하면 실제 경로와 너무 벗 어나게 되고 장애물과 충돌하는 경로가 나올 수도 있다. 그림 1은 A*알고리즘으로 생성된 경로의 코너 노드를 조정점으로 선정한 결과이다. 생성된 결과를 보면 장애물과 겹치는 경로가 생성이 된 것을 알 수 있다. 그리고 불필요 한 조정점으로 인해 최단 거리의 경로가 생성이 되지 않았 다. 이런 문제들을 해결하기 위해 최적의 조정점을 선정하 는 방법이 필요하다. 이에 본 논문에서는 다음과 같은 조정 점 선정 방법을 제안한다. 조정점 선정 방법 1) A*알고리즘으로 생성된 경로의 시작노드를 첫 번째 조정점으로 선정 2) 처음 조정점으로 선정된 노드에서 경로상의 바로 다 음노드로 직선을 생성 3) 직선경로에 장애물이 없으면 그 다음 노드로 직선 생성 4) 위의 작업을 반복하여 직선경로와 장애물이 겹치는 그림 2. 조정점 선정방법. Fig. 2. Control point selection algorithm.
140 이 희 무, 김 민 호, 이 민 철 그림 3. 조정점 선정 알고리즘을 사용한 B-spline 곡선경로. Fig. 3. B-spline path by control point selection algorithm. 노드를 찾으면 바로 직전 노드를 조정점으로 선정 5) 조정점으로 선정된 노드로부터 3,4번 작업을 반복 수행 6) 목표노드까지 직선상에 장애물이 없으면 목표노드를 마지막 조정점으로 선정 그림 4. B-spline 곡선의 곡률반경. Fig. 4. Radius of B-spline curvature. 표 1. 타이어의 마찰력. Table 1. Friction of the tires. Road Peak Friction Dry 0.8-0.9 Wet 0.5-0.7 Hard Packed Snow 0.2 그림 2는 조정점 선정 방법을 나타내었다. 그리고 조정 점 선정 방법으로 생성된 경로 결과가 그림 3이다. III. B-spline 곡선 경로 추종 앞 장에서 생성된 경로를 최단시간 주행을 하기 위해서 최적의 속도를 결정하여 주어야 한다. 이를 위해, 본 논문 에서는 생성된 경로의 곡률반경을 이용하여 차량이 경로를 주행 시 구간 별로 최대 주행 가능 속도를 구하였다. 이를 사용하여 경로 추종 속도 계획을 하였다. 그리고 자율주행 차량의 경로 추종에 필요한 핸들 조향 각을 구하였다. 1. B-spline 곡선의 곡률반경 곡률반경이란 곡면이나 곡선의 각 점에 있어서의 만곡의 정도를 표시하는 값으로, 곡률반경이 클수록 만곡은 완만하 다. 평면에서는 곡률반경이 무한대이며, 원의 곡률반경은 그 반지름과 같고 만곡의 정도도 일정하다. B-spline 곡선은 값을 변화시키면 그에 따른 벡터 가 생성이 된다. 여기서 는 B-spline 곡선을 n등분한 값으 로 0 ~ n 까지 변화한다. 이 성질을 이용하면 필요한 점을 구할 수 있다. 정확한 곡률반경을 구하기 위해서는 곡선을 미분을 하여야 하지만 계산식이 복잡해지므로 근사 곡률반 경을 구하였다. 근사 곡률반경은 벡터의 간격을 줄이 면 줄일수록 미분한 결과와의 오차는 줄어든다. 이에 본 논 문에서는 오차율이 0.01% 미만이 되도록 벡터의 간격 을 조정 하였다. B-spline곡선으로 생성된 경로는 벡터의 점들을 이용 하면 호의 길이와 두 접선이 이루는 각을 알 수 있다. 그림 4와 같이 호의 길이를, 두 접선이 이루는 각을 라 하면 곡률반경 은 로 정의 된다. 2. 최대 주행 가능 속도 계획 곡선 경로의 주행속도는 곡률반경을 이용하여 구할 수 있다. 자율주행차량이 주행 시 공기의 흐름에 의한 저항력 의 영향이 없다고 가정한다면, 차량이 커브를 통과할 수 있 그림 5. 선회 구심력(횡 항력). Fig. 5. Cornering force. 는 최고속도는 곡률반경과 타이어와 노면과의 마찰계수 2 가지 요인으로 결정된다. 차가 허용 최대 속도로 코너링하 고 있다고 보면 차에 가해지는 원심력과 차와 노면사이에 작용하는 타이어와 노면사이에 작용하는 마찰력의 최대 값 은 반대방향으로 완전히 균형을 이룬다. 따라서 양쪽을 같 다고 방정식을 만들면 다음과 같다. (4) (5) lim (6) 여기서 은 곡률반경, 은 차 의 질량, 는 중력가속도, 은 타이어 마찰계수, 는 원심력, lim 은 코너에서의 최대 속도이다. 구동바퀴와 노면사이에 작용하는 마찰계수는 표 1과 같다[9,10]. 3. 경로추종 조향 각 이번 절에서는 무인지상차량의 경로 추종에 필요한 조향
무인 주행 차량의 하이브리드 경로 생성을 위한 B-spline 곡선의 조정점 선정 알고리즘 141 그림 6. 조향 각. Fig. 6. Steering angle. 각을 구하는 방법에 대해 설명한다. 조향 각을 구할 때에도 B-spline 곡선 방정식의 벡터 를 사용한다. 먼저 벡터에 따른 곡선상의 점들을 구하 고 두 점들을 잇는 직선의 끼인각을 구한다. 구한 각들의 를 구하면 각점들에서의 조향 각을 알 수 있다. B-spline 곡선 특성상 세 점의 좌표는 쉽게 구할 수 있기 때문에 끼인각은 간단한 삼각함수 식으로 구할 수 있다. 그 림 6의 그림과 같이,, 를 세 점의 좌표라 하면 다음식과 같이 구할 수 있다. 그림 7. 시뮬레이션 결과 1. Fig. 7. The simulation results 1. tan (7) tan (8), (9) (10) 단 위의 식은 무인주행차량의 최초 진행방향이 경로와 일치 한다고 가정하면 식 (10)과 같이 무인주행차량이 이동 시 각 지점의 조향 각을 값을 증가 시키면 구할 수 있다. 의 값은 최초 값이 0이며 무인주행차량이 이동 시 각 점에서의 조향 각은 이전 조향 각의 누적으로 나타낼 수 있다. IV. 주행시간 평가 시뮬레이션 본 논문에서 제안한 알고리즘을 바탕으로 경로를 생성하 고 생성된 경로를 추종한 결과를 보이도록 한다. 시뮬레이 션 프로그램은 MathWork사의 Matlab을 사용하여 작성하였 다. 시뮬레이션 평가를 하기위해 선행 연구로서 A*알고리 즘으로 생성된 경로를 추종하는 알고리즘을 수행 하였다. 선행연구에서 나온 결과와 본 논문에서 제안한 알고리즘을 비교 평가 하였다. 1. 시뮬레이션 조건 시뮬레이션을 통한 평가를 하기 위해서 몇 가지 조건들 을 정하였다. 지도는 가로 32칸, 세로 24칸으로 정하였고 격자의 간격은 각 1m로 하였다. 국내 도로의 구조 시설기 준에 관한 규칙에 따르면 제한속도를 가지는 국내도로의 회전 반경은 15m 이상이 되어야 한다. 최소 회전반경 15m 에서 최대 회전 속도는 10m/s이지만 권장속도는 6m/s이다. 그림 8. 시뮬레이션 결과 2. Fig. 8. The simulation results 2. 최소 회전반경을 많이 가지는 90 코너에서의 감속 속도는 6m/s로 둔다. 45 코너는 평균 회전 반경 25m를 기준으로 10m/s를 감속 정도로 둔다. 그리고 차량의 최대 속도는 30m/s (100km/h)를 기준으로 하며, 일반적인 차량의 제로백 은 10초정도 이므로 가속도는 3 로 둔다. 이는 국내 도로에서 가장 일반적인 예를 기준으로 잡았다. 위의 경우 실제 차량 기준으로 시뮬레이션을 하기위해 지도의 크기를 고려하여 모든 수치를 비례적으로 낮추어 차량의 최대 속 도는 0.6m/s로 정하였다. A*의 경우 코너를 만났을 때의 코 너링 속도는 0.2m/s로 B-spline은 본 논문에서 제시한 근사 곡률방경을 이용하여 계산한 속도를 사용하여 시뮬레이션 을 수행 하였다. 장애물은 격자의 중앙부분이 장애물의 끝 점으로 간주하였다. 경로가 장애물로 표시한 점과 겹치지만 않는다면 장애물과 충돌하지 않는 것이라고 간주 하였다. 2. 시뮬레이션 결과 시뮬레이션 결과는 다음과 같다. 그림 7은 출발지점과 목표지점 사이의 거리가 짧은 경로에 있어서 기존 A*알고 리즘과 본 논문에서 제시한 알고리즘의 결과 경로를 비교 해서 보여준다. 그림 7에서 검은색 선으로 된 경로가 A*의 경로이고 붉은색 선으로 된 경로가 조정점 선정 알고리즘 을 이용하여 생성된 B-spline 곡선 경로이다. 붉은색 점은 장애물이고 시작점은 start, 목표점은 Target로 표시 하였다. 그림 7을 보면 장애물과 겹치지 않으면서 A*의 경로보 다 부드러운 경로가 생성이 되는 것을 볼 수 있다. 그림 8의 경우 출발지점과 목표지점사이의 거리가 먼 경
142 Hee-Mu Lee, Min-Ho Kim, and Min-Cheol Lee 표 2. A*와 B-spline 경로의 시뮬레이션 결과비교. Table 2. Comparison of the results of A* and B-spline. 총 거리(m) 총 주행시간 (s) Fig. 6 A* B-spline 21.7 20.2 68 38.7 Fig. 7 A* B-spline 36.5 34.5 95.4 62.5 로를 나타내었다. 위의 경우와 마찬가지로 기존의 A*보다 부드러운 경로가 생성이 되었다. [9] C. B. Noh, M. H. Kim, and M. C. Lee, Path planning for the shortest driving time considering UGV driving characteristic and driving time and its driving algorithm, Journal of Korea Robotics Society, vol. 8, no. 1, pp. 43-50, 2013. [10] K. S. Lee, Tire-road friction estimation for vehicle active safety systems applications, Transactions of the Korean Society of Automotive Engineers, vol. 20, no. 6, pp. 31-37, 1998. 다음은 생성된 경로의 총거리와 총 주행시간을 비교해 보았다. 표 2의 결과를 보면 주행 거리와 시간이 단축이 된 것을 확인할 수 있었다. 본 연구에서 제안한 알고리즘이 기 존의 A*알고리즘으로 생성된 경로보다 뛰어남을 시뮬레이 션 결과에서 밝힐 수 있었다. V. 결론 본 논문에서는 A*알고리즘으로 생성된 경로를 조정점 선정 알고리즘을 이용하여 B-spline 곡선 경로로 변환을 하 였다. 그리고 생성된 경로의 최대 주행 가능 속도 계획 및 핸들 조향 각을 구하였다. 이를 평가하기 위하여 시뮬레이 션 프로그램을 제작한 후, 결과를 나타내었다. 시뮬레이션 결과에서 보듯이 A*의 경로를 주행하였을 경우 코너에서 내지 의 큰 조향각의 변동으로 인해 감속이 많이 발생하여 주행시간이 늘어남을 볼 수 있다. B-spline의 경우 이희무 2011년 부경대학교 제어계측공학과 졸 업. 2012년~현재 부산대학교 대학원 로봇관련협동과정 석사과정. 관심분야 는 자율로봇 경로 생성, 로보틱스, 센 서융합. 김민호 2005년 부산대학교 기계공학부 졸업. 2007년 부산대학교 대학원 기계시스템 설계전공 공학석사. 2010년~현재 부산 부드러운 곡선 경로가 생성이 되어 조향각의 변화가 적어 대학교 기계공학부 박사과정. 관심분 야는 로봇시스템 설계, 자율로봇 경로 주행시간이 줄어듦을 확인할 수 있었다. 생성. REFERENCES [1] W. P. Yu, S. L. Choi, J. Y. Lee, and S. H. Park, Robot navigation technology and standardization trends, Electronics and Telecommunications Trends, vol. 26, no. [2] 6, pp. 108-119, 2011. P. E. Hart, N. J. Nilsson, and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE transactions of Systems Science and Cybernetics, vol. ssc-4, no. 2, pp. 100-107, 1968. [3] Wikipedia, DARPA Grand Challenge, http://en.wikipedia. [4] org/wiki/darpa_grand_challenge, 2013. Wikipedia, Google driverless car, http://en.wikipedia.org/ wiki/google_car, 2013. [5] M. G. Cox, The numerical evaluation of B-spline, Journal of Approximation Theory, vol. 6, pp. 95-108, 1972. [6] C. de Boor, On calculation with B-spline, Journal of Approximation Theory, vol. 6, pp. 76-78, 1997. [7] K. W. Lee, Principles of CAD/CAM/CAE Systems, [8] Addson Wesley, 1999. M. H. Kim and M. C. Lee, A path generation method for path tracking algorithms that use the augmented reality, International Conference on Control, Automation and Systems, pp. 1487-1490, 2010. 이민철 1983년 부산대학교 기계공학과 졸업. 1988년 쯔쿠바대학교 이공학 연구과 대학원 석사. 1991년 쯔쿠바대학교 물 리공학 연구과 공학박사. 2000년 8 월~2001년 8월 노스캐롤라이나주립대학 교(NCSU) 방문교수. 2009년 8월~2010 년 8월 퍼듀대학교 방문교수 1991년~현재 부산대학교 기계 공학부 교수. 관심분야는 시스템 규명, 로봇제어, 의료로봇, 지능형 서비스로봇, 메카트로닉스.