도로면 크랙실링 공법은 예방적 차원에서 도로면에 발생된 크랙을 초기에 효과적으로 보수할 수 있는 공법으로 국내외에 서는 1990년대 초반부터 기존 도로면 크랙실링 작업의 생산성, 안전성 및 품질의 균일성 확보를 목적으로 크랙실링 자동화 장비의 개발을 위한 지속적인 연구개발 노력을 수행해 왔다. 도로면 크랙실링 자동화 장비를 개발함에 있어 특히 경로계획은 주어진 작업 영역 내에서 개발 장비로 하여금 실링될 크랙 네트워크를 시간 효과적으로 횡단할 수 있도록 하는 운항 정보를 제공하게 되므로 이는 개발 장비의 성능을 결정 짖는 매우 중요한 연구주제라 할 수 있다. 본 연구의 목적은 작업 영역 내 경로계획 데이터의 효과적인 모델링을 통해 크랙실링 자동화 장비의 최적 경로계획 알고리즘을 개발하는 것으로써, 경로 집합전체를 완전 탐색하는 2단계 트리 알고리즘과 크랙의 순열만을 탐색하는 1단계 트리 알고리즘을 개발하였으며, 알고리즘의 성능 측정 및 분석을 통해 최적 경로계획 알고리즘의 적용 범위와 그에 따른 성능 향상 정도를 평가하였다. 이 연구의 결과는 도로면 크랙실링 자동화 장비의 생산성 향상에 크게 기여할 수 있을 것으로 기대된다.
도로면 크랙실링 공법은 예방적 차원에서 도로면에 발생된 크랙을 초기에 효과적으로 보수할 수 있는 공법으로 국내외에 서는 1990년대 초반부터 기존 도로면 크랙실링 작업의 생산성, 안전성 및 품질의 균일성 확보를 목적으로 크랙실링 자동화 장비의 개발을 위한 지속적인 연구개발 노력을 수행해 왔다. 도로면 크랙실링 자동화 장비를 개발함에 있어 특히 경로계획은 주어진 작업 영역 내에서 개발 장비로 하여금 실링될 크랙 네트워크를 시간 효과적으로 횡단할 수 있도록 하는 운항 정보를 제공하게 되므로 이는 개발 장비의 성능을 결정 짖는 매우 중요한 연구주제라 할 수 있다. 본 연구의 목적은 작업 영역 내 경로계획 데이터의 효과적인 모델링을 통해 크랙실링 자동화 장비의 최적 경로계획 알고리즘을 개발하는 것으로써, 경로 집합전체를 완전 탐색하는 2단계 트리 알고리즘과 크랙의 순열만을 탐색하는 1단계 트리 알고리즘을 개발하였으며, 알고리즘의 성능 측정 및 분석을 통해 최적 경로계획 알고리즘의 적용 범위와 그에 따른 성능 향상 정도를 평가하였다. 이 연구의 결과는 도로면 크랙실링 자동화 장비의 생산성 향상에 크게 기여할 수 있을 것으로 기대된다.
During the last two decades, several tele-operated and machine-vision-assisted systems have been developed in construction and maintenance area such as pavement crack sealing, sewer pipe rehabilitation, and excavation. In developing such tele-operated and machine-vision-assisted systems, trajectory ...
During the last two decades, several tele-operated and machine-vision-assisted systems have been developed in construction and maintenance area such as pavement crack sealing, sewer pipe rehabilitation, and excavation. In developing such tele-operated and machine-vision-assisted systems, trajectory plans are very important tasks for optimal motions of robots whether their environments are structured or unstructured. This paper presents an optimal trajectory planning algorithm used for a machine-vision-assisted automatic pavement crack sealing system. In this paper, the performance of the proposed optimal trajectory planning algorithm is compared with the greedy trajectory plans which are used in previously developed pavement crack sealing systems. The comparison is based on computational cost versus overall gains in crack sealing efficiency. Finally, it is concluded that the proposed algorithm plays an important role in productivity improvement of the automatic pavement crack sealing system developed.
During the last two decades, several tele-operated and machine-vision-assisted systems have been developed in construction and maintenance area such as pavement crack sealing, sewer pipe rehabilitation, and excavation. In developing such tele-operated and machine-vision-assisted systems, trajectory plans are very important tasks for optimal motions of robots whether their environments are structured or unstructured. This paper presents an optimal trajectory planning algorithm used for a machine-vision-assisted automatic pavement crack sealing system. In this paper, the performance of the proposed optimal trajectory planning algorithm is compared with the greedy trajectory plans which are used in previously developed pavement crack sealing systems. The comparison is based on computational cost versus overall gains in crack sealing efficiency. Finally, it is concluded that the proposed algorithm plays an important role in productivity improvement of the automatic pavement crack sealing system developed.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
실제 크랙의 수 n이 7일 때 연산시간은 3초를 초과하며, n이 8일 때는 72초를 초과한다. 본 연구에서는 2단계 트리 알고리즘의 이러한 문제점을 보완하기 위해 경로 순열에 대한 1단계 트리만을 이용하고 크랙의 진입점(front and rear)은 가까운 거리를 선택하는 1단계 트리 알고리즘을 개발하였다. 1단계 트리 알고리즘은 2번째 트리의 생성과 해체를 생략하기 때문에 전체 연산량에 있어 2단계 트리 알고리즘에 비해 1/2n로 감소시킬 수 있다.
본 연구의 목적은 효과적인 경로계획 데이터 모델링을 통해 크랙실링 자동화 장비의 최적 경로계획 알고리즘을 개발하는 것이며, 개발된 알고리즘의 성능 측정 및 분석을 통해 최적 알고리즘의 적용 범위와 기존 알고리즘 대비 성능 향상 정도를 평가하는 것이다. 이 연구의 결과는 크랙실링 자동화 장비의 생산성을 한층 증진시킬 수 있을 것으로 기대된다.
앞서 언급한 바와 같이 크랙의 수 n에 따라 1차 트리 및 2차 트리 경로계획 알고리즘은 한계 적용범위가 있기 때문에 본 연구에서는 크랙실링 자동화 장비의 경로계획 알고리즘 적용에 있어 크랙의 수 n에 따라 적절한 경로계획 알고리즘이 실행될 수 있도록 하였다. 즉, 크랙의 수 n이 1이상 6이하인 경우 2차 트리 알고리즘이 실행되고, n이 7이상 8이하인 경우 1차 트리 알고리즘이 실행되며, n이 9이상인 경우 그리디 경로계획 알고리즘이 실행되도록 설정하였다.
제안 방법
1) 비전 알고리즘의 개념과 프로세스를 설명하고 비전 알고리즘 내에서 경로계획 알고리즘의 역할과 중요성을 분석한다.
1) 크랙실링 자동화 장비의 머신비전 알고리즘 가운데 경로계획 알고리즘의 역할을 분석하고, 경로계획 알고리즘의 개념과 성능 차에 따른 생산성의 변화를 분석하였다.
2) 선행 개발된 경로계획 알고리즘의 성능과 문제점을 분석한다.
2단계 트리 알고리즘의 실제 데이터 구조 구현모델은 그림 9와 같이 역방향 포인터를 가진 트리 구조이고, 말단 노드 하단에 별도의 포인터 큐를 생성하여 경로 데이터를 하나씩 로드할 수 있도록 설계되었다. 이는 상향으로 경로 데이터를 로드하는 방법이 하향 순회 방식보다 속도가 빠르고 구현이 간단하기 때문이다.
4) 경로 순서에 관한 1단계 트리 구조 모델링을 통해 경로 순열을 생성하였고, 다시 진입순서를 결정하기 위한 2단계 트리구조를 모델링하여 크랙의 수 n에 대한 모든 이동거리를 산출하는 2단계 트리 경로계획 알고리즘을 개발하였다. 또한 2단계 트리 알고리즘의 시간 비용을 줄이기 위해 1단계 트리로 경로순열을 생성하고 크랙의 진입순서는 가까운 위치를 선택하는 1단계 트리 경로계획 알고리즘을 개발하였다.
4) 기존 그리디 알고리즘과 제안된 알고리즘을 프로그래밍 언어로 각각 구현하여 성능 및 장단점을 분석하고 크랙실링 자동화 장비에서의 효과적인 적용방법을 제시한다.
5) 기존 그리디 알고리즘과 본 연구에서 개발된 1단계 트리 알고리즘, 2단계 트리 알고리즘 등 각각의 알고리즘을 소프트웨어로 구현하였다. 본 연구에서 270장의 경로 데이터를 이용하여 각 알고리즘의 소요시간과 정확성을 테스트한 결과, 그리디 알고리즘이 가장 빠르지만 정확성(평균 18.
경로계획 알고리즘은 크랙실링 자동화 장비에서 자동으로 인식된 크랙 경로 정보를 이용하여 크랙 실링 자동화 장비의 말단장치가 가장 짧은 이동경로를 찾아내어 신속하게 실링을 수행할 수 있도록 하는 알고리즘으로써, 본 연구에서는 1단계 트리 알고리즘과 2단계 트리 알고리즘을 개발하여 기존 그리디 알고리즘과의 성능을 비교 분석하였으며, 본 연구를 통해 얻은 결론은 다음과 같다.
4) 경로 순서에 관한 1단계 트리 구조 모델링을 통해 경로 순열을 생성하였고, 다시 진입순서를 결정하기 위한 2단계 트리구조를 모델링하여 크랙의 수 n에 대한 모든 이동거리를 산출하는 2단계 트리 경로계획 알고리즘을 개발하였다. 또한 2단계 트리 알고리즘의 시간 비용을 줄이기 위해 1단계 트리로 경로순열을 생성하고 크랙의 진입순서는 가까운 위치를 선택하는 1단계 트리 경로계획 알고리즘을 개발하였다.
본 연구에서 개발된 2단계 트리 및 1단계 트리 알고리즘은 그림 13의 크랙 인식 및 네트워크 모델링 소프트웨어에 통합되어 구현되었으며, 해당 소프트웨어는 Microsoft Visual C++ 6.0기반으로 구현되었다. 본 소프트웨어에는 영상 획득, 크랙 인식, 크랙 네트워크 모델링, 경로계획, 모션 컨트롤 제어 등 크랙실링 자동화 장비에 필요한 모든 기능이 통합 구현되어 있다.
0)을 기준으로 n개의 경로를 지나가는 모든 경우의 수를 데이터 구조(data structure)로 모델링하고 연산을 통해 크랙 간 이동 거리(idle distance)가 가장 짧은 경로를 선택하는 방법이다. 본 연구에서는 모든 경로의 경우의 수를 모델링하기 위한 방법으로는 2단계의 트리 구조를 사용한다. 원점을 기준으로 모든 경로를 한 번씩 지나가는 순서의 집합을 경로집합(표 1 참조)이라고 한다면, 1단계 트리는 크랙의 양 끝점(front[rear])을 고려하지 않고 경로집합 내의 각 경로의 순서에 대한 경우의 수를 결정한다.
그림 2는 연결 리스트로 저장된 맵핑 데이터의 구조이다. 이 논문에서는 배열과 연결리스트가 혼합된 구조를 사용하였다. 각 경로의 처음점(front[])과 끝점(rear[])은 배열 포인터(array pointer)에 의해 참조되고, 내부의 경로데이터는 스트링(string) 형태의 연결리스트 구조로 연결되어 있다.
대상 데이터
경로계획 알고리즘의 성능 측정에 사용된 데이터는 총 270장의 512×512 화소 원시 영상이고 크랙의 수가 1개인 영상부터 9개인 영상까지 각각 30장의 이미지가 성능측정에 사용되었다.
본 연구의 범위는 크랙 실링 자동화 장비의 제어를 위한 머신비전 알고리즘 가운데 기존 경로계획 알고리즘의 문제점을 분석하고 새로운 경로계획 알고리즘을 제안하여 성능을 비교·검토하는 것으로서, 연구의 방법은 다음과 같다.
이론/모형
앞서 언급한 바와 같이 TSP는 모든 경로를 검색하여 그 경로를 검색한 뒤 최적의 경로를 찾는 방법 외에는 개발된 알고리즘이 없다. 방문지의 수 n의 값이 클 경우 TSP의 시간비용이 매우 크기 때문에 흔히 Dijkstra(1959), Kruskal(1956), Prim(1957), Sollin(1962)과 같은 그리디 알고리즘(greedy algorithm)을 사용한다. 그리디 알고리즘이란 여행 경로를 완성하기 위하여 방문하지 않은 정점 중 최소 비용의 가중치를 갖는 것을 다음번 간선으로 선택하는 방법을 말하는데, 그리디 알고리즘은 상당히 좋은(good) 해결책을 찾을 수 있지만 반드시 최적(optimal)의 경로를 찾을 수 있는 것은 아니며, 특히 n이 커질수록 최적 경로를 찾을 수 있는 확률은 점점 더 낮아지게 된다.
이 두 가지 항목은 비전 알고리즘의 전체적인 프로세싱 타임과 직접적인 관계를 갖고 있다. 본 연구에서 연산시간 측정은 MFC(Microsoft Foundation Class)의 Clock() 함수를 이용하였다. Clock() 함수는 millisecond(1/1000 sec)단위로 측정된다.
이 알고리즘은 대량의 계산을 피하기 위해 볼쯔만 확률 분포 (Boltzmann probability distribution)를 사용하며 온도 감소함수인 알파(α) 팩터로 0.88을 사용하였다.
성능/효과
24%의 오차)이 가장 낮았으며, 2단계 트리 알고리즘은 가장 느리지만 항상 최적의 경로를 탐색할 수 있었다. 1단계 트리 알고리즘은 2단계 트리 알고리즘보다는 빠르고, 오차는 평균 4.03%로 2단계 트리 알고리즘에 거의 근접하는 것으로 나타났다.
2) 기존 그리디 경로계획 알고리즘을 분석한 결과, 매우 빠르고 효과적인 알고리즘이지만, 크랙의 수 n이 증가할수록 정확성이 저하되는 것으로 분석되었다.
3) 최적 경로계획 알고리즘의 이론적 고찰을 통해 크랙실링 자동화 장비의 경로계획 알고리즘은 경로순서에 관한 1단계 트리와 진입 순서에 관한 2단계 트리로 분할하여 모델링할 수 있음을 고찰하였다.
6) 크랙의 수 n에 따라 적절한 경로계획 알고리즘이 실행될 수 있도록 크랙의 수 n이 1이상 6이하인 경우 2차 트리 알고리즘이 실행되고, n이 7이상 8이하인 경우 1차 트리 알고리즘이 실행되며, n이 9이상인 경우 그리디 경로계획 알고리즘이 실행되도록 설정한 결과, 크랙실링 자동화 장비의 경로계획 적용 모델은 최대 0.3초 이내에 수행될 수 있으며, 이동거리의 적용결과는 최적 값에 평균 5.7% 오차가 있었다.
즉, 크랙의 수 n이 1이상 6이하인 경우 2차 트리 알고리즘이 실행되고, n이 7이상 8이하인 경우 1차 트리 알고리즘이 실행되며, n이 9이상인 경우 그리디 경로계획 알고리즘이 실행되도록 설정하였다. 그 결과 그림 15와 같이 경로계획 적용모델은 최대 0.3초 이내에 수행될 수 있으며, 이동거리의 적용결과는 최적 값에 비해 평균 5.7% 오차를 보였다.
현재까지 크랙실링 자동화 장비의 경로계획은 Kim 과 Haas(1998)의 그리디 경로계획 알고리즘(greedy path planning algorithm)이 대표적인 경로계획 알고리즘이었다. 그리디 알고리즘은 구현이 간단할 뿐만 아니라 빠르게 동작하고, 매우 효과적인 결과(efficient path)를 도출하지만 알고리즘의 특성상 항상 최적의 결과(shortest path)를 보장하는 알고리즘은 될 수 없으며, 도로면 영상에 촬영된 크랙의 수가 증가할수록 최적 결과 값과의 오차(idle distance)가 점점 더 크게 나타나는 문제점이 있었다.
61초가 걸려 1초를 초과하였다. 그림14의 ②에서 알 수 있듯이 항상 최적결과를 보장하는 2차 트리 경로계획 알고리즘에 비해 그리디 알고리즘은 평균 18.24% 더 먼 경로를 찾았으며, n이 증가할수록 오차가 증가하는 것으로 확인되었다. 이에 비해 1차 트리 경로계획 알고리즘은 2차 트리 경로계획 알고리즘에 비해 평균 4.
기존 그리디 알고리즘과 본 연구에서 개발된 2단계 트리 알고리즘 및 1단계 트리 알고리즘을 구현하여 각 알고리즘의 연산시간과 이동거리를 측정한 결과(표 7), 그리디 알고리즘은 크랙의 수 n의 9까지 증가하더라도 연산시간이 최대 2ms이하였으나, 1차 트리 경로계획 알고리즘은 n이 9일 때 평균 3.55초가 걸려 1초를 초과하는 결과가 나타났고, 2차 트리 경로계획 알고리즘은 n이 7일 때 평균 3.61초가 걸려 1초를 초과하였다. 그림14의 ②에서 알 수 있듯이 항상 최적결과를 보장하는 2차 트리 경로계획 알고리즘에 비해 그리디 알고리즘은 평균 18.
5) 기존 그리디 알고리즘과 본 연구에서 개발된 1단계 트리 알고리즘, 2단계 트리 알고리즘 등 각각의 알고리즘을 소프트웨어로 구현하였다. 본 연구에서 270장의 경로 데이터를 이용하여 각 알고리즘의 소요시간과 정확성을 테스트한 결과, 그리디 알고리즘이 가장 빠르지만 정확성(평균 18.24%의 오차)이 가장 낮았으며, 2단계 트리 알고리즘은 가장 느리지만 항상 최적의 경로를 탐색할 수 있었다. 1단계 트리 알고리즘은 2단계 트리 알고리즘보다는 빠르고, 오차는 평균 4.
24% 더 먼 경로를 찾았으며, n이 증가할수록 오차가 증가하는 것으로 확인되었다. 이에 비해 1차 트리 경로계획 알고리즘은 2차 트리 경로계획 알고리즘에 비해 평균 4.03% 더 먼 경로를 찾았으며, 그리디 경로계획 알고리즘과 마찬가지로 n이 증가할수록 오차도 증가하였다.
후속연구
본 연구에서 개발된 1단계 트리 및 2단계 트리 경로계획 알고리즘은 크랙실링 자동화 장비의 생산성 향상에 기여할 수 있을 것으로 기대되며, 향후 유전자 알고리즘(genetic algorithm), 2-Opt 알고리즘과 같은 최적화 알고리즘(optimization algorithm)의 적용을 통해 시간 비용(time cost)의 성능을 개선할 수 있을 것으로 기대된다.
본 연구의 목적은 효과적인 경로계획 데이터 모델링을 통해 크랙실링 자동화 장비의 최적 경로계획 알고리즘을 개발하는 것이며, 개발된 알고리즘의 성능 측정 및 분석을 통해 최적 알고리즘의 적용 범위와 기존 알고리즘 대비 성능 향상 정도를 평가하는 것이다. 이 연구의 결과는 크랙실링 자동화 장비의 생산성을 한층 증진시킬 수 있을 것으로 기대된다.
질의응답
핵심어
질문
논문에서 추출한 답변
도로면 크랙실링 공법은 무엇인가?
도로면 크랙실링 공법은 예방적 차원에서 도로면에 발생된 크랙을 초기에 효과적으로 보수할 수 있는 공법으로 국내외에 서는 1990년대 초반부터 기존 도로면 크랙실링 작업의 생산성, 안전성 및 품질의 균일성 확보를 목적으로 크랙실링 자동화 장비의 개발을 위한 지속적인 연구개발 노력을 수행해 왔다. 도로면 크랙실링 자동화 장비를 개발함에 있어 특히 경로계획은 주어진 작업 영역 내에서 개발 장비로 하여금 실링될 크랙 네트워크를 시간 효과적으로 횡단할 수 있도록 하는 운항 정보를 제공하게 되므로 이는 개발 장비의 성능을 결정 짖는 매우 중요한 연구주제라 할 수 있다.
크랙실링 자동화 장비의 경로계획은 그리디 경로계획 알고르즘이 대표적인데 어떤 문제점을 가지고 있는가?
크랙실링 자동화 장비의 경로계획은 컴퓨터 공학의 그래프 이론(graph theory) 측면에서“모든 경로를 탐색해 보기 전까지는 최적의 결과를 알 수 없는”문제에 속한다. 이러한 문제는 크랙의 수가 적으면 해결이 가능하지만 크랙의 수가 증가할수록 경로의 수도 기하급수적으로 증가하기 때문에 막대한 시간 비용이드는 문제로 분류된다. 그러나 실제 크랙실링 장비를 이용하여 현장 실험을 수행한 결과, 도로면 영상에 존재하는 크랙은 최대 8~9개 정도이며, 대부분의 경우 1~4개 정도의 크랙이 발견된다.
크랙실링 자동화 장비의 머신비전 시스템은 어떻게 구성되고 있는가?
현재까지 개발된 크랙실링 자동화 장비의 머신비전 시스템(machine vision system)은 크랙 탐지 및 모델링 모듈과 경로계획 모듈로 구성되어 있는데, 이 가운데 크랙 탐지 및 모델링 모듈은 크랙 네트워크의 골격(spine)을 정확하게 탐지하고 모델링하기 위한 모듈로서 크랙실링 자동화 장비의 정확성과 품질을 좌우하는 중요한 모듈이다. 크랙 탐지 및 모델링 모듈은 지속적으로 인식률 개선을 위한 연구개발을 통해 균열 완전자동 인식률이 95.
Feng, X., Mathurin, R., and Velinsky S. A. (2005), "Practical, Interactive, and Object-Oriented Machine Vision for Highway Crack Sealing", Journal of Transportation Engineering, Vol. 131, No. 6, pp.451-459, June, 2005.
Glover, F., and Punnen, A. P.(1997), "The traveling salesman problem : New solvable cases and linkages with the development of approximation algorithms", J. Oper. Res. Soc., 48, pp. 502-510.
Horowitz, E., Sahni, S., and Anderson-Freed, S.(1993), "Fundamentals of Data Structures in C", W. H.Freeman and Company, 1993.
Kim, Y. S.., Hass, C. T.(1998)," Path Planning for Machine Vision Assisted, Teleoperated Pavement Crack Sealer", Journal of Transportation Engineering, Vol.124, No. 2, Mar/Apr, 1998.
Kirschke, K. R. and Velinsky, S. A. (1992)," Histogram- Based Approach for Automated Pavement-Crack Sensing",Journal of Transportation Engineering, Vol. 118, Issue 5, pp. 700-710, September/October 1992
Mathurin R., Velinsky S. A(2000), "Simulated Annealing for the Optimal Trajectory Planning of an Automated Crack Sealing Machine", Proceedings ASME design technical conference, 2000
Prim, R. C.(1957), "Shortest Connection Networks and Some Generalizations", Bell Syst. Tech. J. 36, pp 1389-1401
※ AI-Helper는 부적절한 답변을 할 수 있습니다.