《여러가지 로보트를 개발하고 받아들이는데서 나서는 과학기술적문제도 풀어야 하겠습니다.》 (
무인운반차는 유연생산체계에서 자동창고에 대한 요구를 충족시킬수 있는 지능형이동로보트로서 생산의 자동화를 실현하는데서 가장 중요한 구성부분들중의 하나로 되고있다. 무인운반차에 의한 자동운송체계를 실현하자면 많은 기술적문제들이 제기되는데 대표적으로 무인운반차의 합리적인 자리길구축과 위치확정, 통신과 기계체계설계 등을 들수 있다. 특히 초기위치에서 목표위치로 가는 최량경로를 선택하는것은 생산비용과 능률을 제고하는데서 중요한 몫을 차지한다.
이로부터 우리는 자동운송체계구축에서 절실한 문제로 나서는 최량경로계획을 그라프탐색의 한가지방법인 A*알고리듬에 의하여 실현하는 한가지방법에 대하여 보기로 한다.
A*알고리듬은 그라프리론을 적용하여 지도를 구축하고 최량경로를 탐색하는 방법들중의 하나이다.
A*알고리듬에 의한 최량경로계획을 실현하자면 다음의 3가지 문제점들을 해결하여야 한다.
① 자동운송체계에 대한 위상모형화.
② A*알고리듬에 의한 경로생성.
③ 무인운반차들사이의 경로충돌회피방략.
우선 자동운송체계에 대한 위상모형화는 위치정보가 실지의 주위환경정보를 그대로 반영한 전자지도이면서도 콤팍트적인 구조여야 한다. 위상모형화방법을 리용하여 설계된 모형은 방향성련결망으로서 마디점들과 두개이상의 마디점들을 련결하는 변두리들의 모임으로 나타낸다. 매 변두리는 한개의 무게를 가지는데 여기서 무게는 보통 정수로서 거리, 비용, 항행시간 혹은 항행비용 등을 나타낸다.
또한 A*알고리듬은 가능한 모든 풀이를 다 탐색하지 않는것으로 하여 탐색효률이 높다.
이 알고리듬에서 리용되는 평가함수는 다음과 같다.
f(n)=g(n)+h(n)
여기서 f(n)은 마디점n에 대하여 출발점S로부터 목표점F까지의 추정거리를 나타내고 g(n)은 실거리를 나타내며 h(n)은 마디점n으로부터 목표점 F까지의 평가함수로서 두 마디점사이의 유클리드거리에 기초하고있다.
A*알고리듬의 실행절차는 다음과 같다.
걸음1:Q가 부분경로렬이라고 한다.
걸음2: Q가 빈모임이 아닐 때
걸음2.1:첫번째 경로 P가 목표마디점에 도달하였으면 성공으로 하고 알고리듬을 끝내며
걸음2.2:렬에서 P를 제거한다.
걸음2.3:모든 가능한 로정에서 P를 확장하고 렬에 새로운 경로를 추가한다.
걸음2.4: 두개 값 즉 현재까지의 P의 값과 남아있는 거리h의 합에 의하여 렬을 구분시킨다.
걸음2.5: 가장 멀리 도달하는 매 마디에 해당한 가장 짧은 나머지 경로에 의하여 렬을 갈라낸다.
걸음3: 성공이면 가장 짧은 경로로 귀환하고 오유이면 귀환하지 않는다.
임의의 마디점n에 대하여 g(n)의 값은 유한이며 f(n)값은 값함수 h(n)에 의존한다. h(n)의 값이 마디점n와 목표점 F사이의 선형거리와 같기때문에 목표방향을 따라 탐색이 진행된다.
A*알고리듬에 의한 최량경로계획을 실현하자면 또한 무인운반차들사이의 경로충돌회피방략을 잘 세워야 한다.
보통 무인운반차의 운동과정에는 보통 3가지 형태의 경로충돌 즉 마디점충돌과 추적충돌, 정면충돌이 발생한다. 마디점충돌은 2개의 운반차가 동시에 한마디점에 도착하여 서로 다른 방향으로 움직이는 경우에 발생하는 충돌이고 추적충돌은 2개의 운반차가 같은 방향으로 움직일 때 뒤에서 따라오는 운반차가 앞의 운반차를 따라잡아 일어나는 충돌이다. 정면충돌은 매개 경로는 한개의 운반차만을 통과시킬수 있다는데로부터 2개의 운반차가 서로 반대방향으로 이동하다가 발생하는 충돌이다. 첫번째와 두번째형태의 충돌에 대하여 스케쥴링체계는 기다림전략에 따라 처음으로 통과하는 무인운반차에 보다 높은 우선권을 준다. 3번째형태의 충돌은 지도를 한방향통로로 구축하는 방법으로 충돌을 회피할수 있다. 다음의 식으로 표시된 운반차들사이의 기하학적거리정보는 마디점충돌회피에 리용할수 있다.sqr()는 두제곱뿌리를 나타낸다.
D=sqr((x1-x2)(x1-x2)+(y1-y2)(y1-y2))
운반차들사이의 거리가 주어진 한계값보다 작다면 알고리듬은 운반차들의 다음번 통과마디점들이 같다는것을 검출할수 있다.
같은 통과마디점을 가지는 경우에는 마디점충돌이 일어나고 그렇지 않은 경우에는 충돌마디점이 발생하지 않는다. 우의 충돌검출방법은 추적충돌인 경우에도 리용할수 있다.
기다림전략은 모든 충돌회피에 리용될수 있는데 시간제한이 없고 여러대의 운반차들이 동시에 한개 통로를 지나갈수 있다는데로부터 2개 마디점들사이의 거리가 안전운동거리보다 클것을 요구한다.
이상의 방법으로 무인운반차에 의한 자동운송체계에서 나서는 경로계획을 실현한 결과 증분그라프방법이나 일반탐색알고리듬과 같은 전통적인 방법에 비하여 최량인 경로가 탐색되고 무인운반차들사이의 충돌이 없이 안전한 운행을 보장할수 있었다.
