일반기술

서브 골 설정에 의한 아날로그 셀룰라 비선형 회로망 기반최적 경로계획 방법

○ 기술발명의 목적: 아날로그 회로에 의한 병렬처리 방식으로 최적의 경로를 구하는 방법○ 기술 요약 및 특징: 본 발명은 ATM 통신의 패킷 경로나 로봇의 작업경로 및 기타 많은 응용 예에서 필요한 최적 경로계획을 아날로그 셀룰라 비선형 회로망에 의해 구현하는 방법에 관한 것으로 부 목표점들을 순차적으로 찾아서 시작점과 목표점간의 거리에 관계없이 정확하게 최적 경로를 찾는 방법에 관한 것이다. 최적 경로계획이 필요한 대부분의 문제에서는 실 시간적 고속 계산이 요구되기 때문에 아날로그 병렬처리 회로를 이용할 수 있다면 좋은 해결책이 될 수 있다. 이를 위해 동적계획법의 최적화 알고리즘을 아날로그 회로로 구현할 수도 있으나 많은 셀을 포함하는 실제적 문제에는 적용이 어렵기 때문에 실용성이 결여되었다는 결함이 있었다. 본 발명에서는 서브 골 알고리즘을 이용하여 시작 위치와 목표 위치간의 거리에 관계없이 아날로그 회로의 의해 최적 경로를 구할 수 있는 방법이다. 본 발명을 이용하면, 시작 위치가 목표 위치로부터 먼 거리에 있는 경우, 시작 위치로부터 가까운 위치에서 서브 골을 찾아내고 다시 이 위치 점을 시작 위치로 간주하여 점차 목표 위치까지의 최적 경로를 반복적으로 찾아내는 방법이다. 본 발명을 하드웨어로 구현할 경우의 동작을 확인하기 위해 아날로그 회로 구현시의 제약조건을 고려하여 컴퓨터 시뮬레이션을 실시한 결과 대단히 양호한 결과를 얻었다.○ 색인어: 알고리금, 동적계획법, 최적경로, 회로망본 발명에 따르면, 아날로그 셀룰라 비선형 회로망의 구조에 서브 골 알고리즘의 작용에 의해 최적 경로를 구할 수 있다. 다음은 상기의 아날로그 셀룰라 비선형 회로망의 구조와 서브 골 알고리즘의 작용에 관한 내용이다.(가) 최적 경로계획을 위한 셀룰라 비선형 회로망 구조격자모양으로 배치된 비용공간을 가정하여 각 노드에 연산기능을 갖는 연산 유닛을 배치하고 노드들을 경유할 때 필요한 비용을 링크 상에 d로 표시하였다고 가정하자. 또한 노드 C(i,j)의 인접 위치 C(k,l)로부터 목표 위치 점에 이르는 최소 비용을 Dklkl 라고 할 때, 노드 C(i,j)로부터 목표 위치 G에 이르는데 소요되는 최소 비용 Dij ij는 인접한 위치 C(k,l)에 이르는 데 소요되는 비용 dij,kl ij,kl 과 그 위치로부터 목표 위치 점에 이르는 최소 비용 Dkl kl을 합한 값 중 최소 값을 취함으로서 계산된다. (나) 서브 골 설정에 의한 아날로그 회로망 기반 동적계획법동적계획법을 회로로 구현하기 위해서는 목표 위치에 큰 전류나 전압을 인가하고 이 값으로부터 노드간의 비용값이 감해진 후 나머지 값들이 전파 되어야 한다. 이를 위해서 각 노드에 연산을 수행할 수 있는 연산 유닛을 설치하여 연산할 수 있는데 우리는 이것을 연산 셀이라고 하고 셀들이 상호 연결되어 동적계획법을 계산하는 회로를 셀룰라 비선형 회로라고 부른다. 이 CNC에서의 셀은 Chua등이 제안한 셀룰라 신경회로망의 셀과 같은 개념이며 각 셀의 단순한 연산에 의해 전체적으로는 매우 복잡하고 중요한 연산결과를 얻어낼 수 있다는 특징이 있다. 그러나, CNN에서의 각 셀은 입력과 템플릿간의 선형 연산결과를 비선형 함수계산을 거쳐 디지털로 출력하는데 비하여 제안한 CNC에서는 입력의 비선형 연산을 거쳐 출력 함수의 선형 부분을 이용하여 아날로그 출력 값을 얻는다는 점이 기존의 CNN과는 크게 다른 점이다.