[첨단 헬로티]

분자 로봇 시스템의 실현에는 DNA나 RNA 등의 생체고분자나 인공고분자 등의 제어 대상에서 로봇으로서의 다양한 기능(센싱, 컴퓨테이션, 액추에이션)을 실현하는 것이 필요하다. 조건은 엄격하고 식별 불가능(익명)하며 고도의 계산 능력을 갖지 않는, 아보가드로 수 오더의 제어 대상이 집합적으로 시스템을 구성한다. 인공적으로 정확한 제어를 실현하는 것은 쉽지 않기 때문에 목적하는 기능의 실현뿐만 아니라, 제어 대상의 집합이 자동적으로 기능을 실현하는 자율성, 예기치 않은 동작이나 외란에 대한 견고성을 보장하는 것이 기대되고 있다.

분산 시스템이란 서로 작용하는 다수의 계산 주체군이 창출하는 계이다. 각 계산 주체는 시스템 전체의 상황을 파악할 수 없고, 국소적인 정보를 기초로 비동기적, 병렬적으로 계산을 한다. 이러한 국소성, 비동기성, 병렬성 하에 계산 주체군이 어떤 합의를 형성할 수 있는지, 합의 형성의 방법, 효율성, 한계, 고장 내성이나 자율적응성에 대해 많은 연구가 이루어지고 있다. 필자는 이론계산기 과학의 입장에서 저기능의 익명 계산 주체군이 구성하는 분산 시스템의 연구에 종사하고 있다.

이 글에서는 분자 로봇 시스템을 분산 시스템으로 간주한 경우, 자기조직화를 실현하는데 중요한 성질과 합의 형성의 방법을 소개한다.

자율 분산 시스템을 위한 중요한 개념의 하나가 자기안정성이다. 자기안정성을 지닌 분산 시스템은 임의의 시스템 상황에서 목적의 시스템 상황으로 자동적으로 도달하는 것을 보장한다. 계산기 네트워크를 대상으로 한 기존의 분산 시스템 연구에서는 자기안정성은 견고성의 이론 보장을 부여하는 강력한 방법의 하나였다. 2000년경부터 분산 시스템 연구의 대상은 센서 네트워크, 모바일 로봇 시스템, 생물 시스템, 화학 반응 시스템으로 확대되고 있다.

이러한 새로운 분산 시스템의 공통점은 계산 주체의 익명성과 저기능성이다. 저렴한 센서, 로봇, 또한 생물 개체, 고분자에는 계산기 네트워크에서 전제로 하는 개별 식별자, 고도의 계산 능력이나 통신 기능은 기대할 수 없으며, 시스템 전체의 초기화나 재설정을 하는 것은 쉽지 않다. 자기안정성은 이와 같은 계산 주체군의 자기조직화 원리로서도 중요한 역할을 할 것으로 기대할 수 있다.

저기능의 익명 계산 주체군을 가정한 분산 시스템 모델은 다수 제안되고 있으며, 대표적인 것으로서는 화학반응계의 일종인 개체군 프로토콜 모델, 국소적인 결합을 구성하는 입자군에 의한 네트워크 구성 모델 아메바에 유래하는 프로그래머블한 입자군 모델, 공간 중을 자율적으로 이동하는 로봇군에 의한 모바일 로봇군 모델, 다수의 모듈이 집합적으로 하나의 로봇을 구성하는 모듈 로봇 시스템 모델 등을 들 수 있다. 이들의 계산 모델에서는 계산 주체군의 국소적인 결합이나 기하적인 배치 제어, 즉 형상의 형성이 가장 중요한 문제로 생각되고 있다.

형상이 익명 분산 시스템에서 중요한 이유는 익명의 계산 주체군의 합의는 계산 주체군의 형상으로서 표출되기 때문이다. 예를 들면, 익명의 계산 주체군을 1점에 모으는 집합 문제는 가장 단순한 합의 형성 문제이다. 단일 형상은 정적인 시스템 상황을 나타내는데, 계산 주체군에 지정한 형상 열을 형성시킴으로써 분산 시스템의 동적인 기능을 의논할 수 있다. 이러한 동적인 형상 형성은 형상 열 형성 문제, 로코모션 문제, 탐색 문제 등 여러 가지 정식화가 제안되고 있다.

이 글에서는 저기능의 익명 계산 주체군이 구성하는 분산 시스템의 자기조직화, 특히 국소성이나 비동기성의 영향, 분산 협조의 방법, 이론적인 한계를 소개한다. 이하에서는 2차원 공간을 이동하는 모바일 로봇군의 형상 형성 능력이 초기 배치의 대칭성에 의해 결정되는 것을 소개하고, 2차원 정사각 격자 영역 중을 이동하는 모듈 로봇 시스템의 이동 기능 획득이나 탐색에 대한 대칭성과 방향 정보의 영향을 소개한다.

모바일 로봇군에 의한 형상 형성

공간을 자율적으로 이동하는 계산 주체의 기본적인 기능은 다른 계산 주체의 위치나 상태를 취득하는 관측, 자신의 거동을 결정하는 계산, 계산 결과에 따라 실시하는 이동이다. 여기서는 이러한 기본적인 기능만을 갖는 익명 계산 주체군을 가정한 모바일 로봇군 모델과 자기조직화에 관한 결과를 소개한다.

1. 패턴 형성 문제

모바일 로봇군 모델에서는 각 계산 주체를 자율적으로 이동하는 체적을 갖지 않는 점으로 생각, 로봇이라고 부른다. 로봇군은 익명으로 명시적 통신 수단은 없고, 공통의 대역 좌표계를 갖지 않는다. 여기서 익명성은 개개의 로봇이 식별 불가능할 뿐만 아니라, 모든 로봇이 동일한 계산 방법(분산 알고리즘)으로 자신의 거동을 결정하는 것을 의미한다.

로봇의 동작 단위는 관측, 계산, 이동으로 구성되는 사이클로, 사이클의 동기 정도에 따라 완전 동기, 반동기, 비동기 등 3종류의 모델이 존재한다. 완전 동기 모델에서는 모든 로봇이 동기해 사이클을 실행, 비동기 모델에서는 사이클의 동기에 일체의 가정을 두지 않는다. 반동기 모델은 양자의 중간적인 모델이다. 로봇이 현재의 사이클에서 얻은 관측 결과만을 기초로 이동처를 계산하는 경우 로봇은 무기억이라고 하고, 이전 사이클의 관측이나 계산 결과를 이용할 수 있는 경우 유기억이라고 한다. 무기억인 로봇군에 대해서는 자기안정성의 보장이 용이하다. 모바일 로봇군을 특징짓는 주요한 요소는 이 비동기성과 무기억성이다.

모바일 로봇군이 지정된 목적 패턴을 형성하는 문제를 패턴 형성 문제라고 부른다(그림 1). 자기조직화의 관점에서 중요한 과제는 주어진 초기 배치에서 형성 가능한 목적 패턴의 특징짓기이다.

예를 들면, 정사각형의 정점에 대응하는 위치에 놓인 4대의 로봇을 생각한다(그림 2 (a)). 각 로봇은 자신의 국소 좌표계를 이용해 관측을 하는데, 국소 좌표계까지가 대칭인 경우(그림 2 (b)) 모든 로봇이 동일한 관측 결과를 얻기 위해 각 로봇이 국소적으로 계산한 이동처는 정사각형을 형성하며(그림 2 (c)), 예를 들면 이 4대의 로봇을 일렬로 정렬할 수 없다. 이 예에서는 모든 로봇이 동기해 관측, 계산, 이동을 하는 것을 예상하고 있는데, 반동기 모델, 비동기 모델에서도 이러한 전체 동기 실행이 일어나기 때문에 이들 모델에서도 정사각형 배치에서 정렬은 보장할 수 없다.

형성 불가능한 패턴의 원인은 로봇군의 초기 배치의 대칭성이다. 로봇군이 해소할 수 없는 대칭성을 점집합의 대칭도를 이용해 설명한다. 2차원 공간 중의 점집합 대칭도를 그 회전대칭성으로 한다. 그림 2 (a)의 점집합은 이 4점을 정점으로 하는 정사각형의 중심에 대해 π/2, π, 3π/2, 2π로 회전해도 외관은 변하지 않는다. 이 4개의 회전 대칭 조작은 자릿수 4의 순회군을 구성한다. 2차원 공간 중의 점집합이 갖는 회전 대칭성은 순회군만이므로 순회군의 자릿수 4를 대칭도로 한다. 단, 점집합의 최소 포함 원의 중심에 점이 있는 경우, 점집합의 대칭도는 1, 즉 비대칭으로 한다. 이것은 회전 중심 상의 로봇이 그 점을 떠남에 따라 배치 대칭성을 해소할 수 있기 때문이다. 2차원 공간 중의 로봇군에 대해 이하의 결과가 알려져 있다.

정리 1  2차원 공간 중의 로봇군이 초기 배치 P에서 목적 패턴 F를 형성하기 위한 필요충분조건은 비동기성, 무기억성에 의하지 않고, 초기 배치 P의 대칭도가 목적 패턴 F의 대칭도를 결론짓는 것이다. 단, F가 다중도 2의 1점인 경우를 제외한다.

정리 1은 결정성의 분산 알고리즘만을 가정하고 있는데, 난수를 이용하는 분산 알고리즘을 허용하면, 비동기의 무기억 로봇군이 초기 배치의 대칭성을 확률 1로 해소할 수 있고, 임의의 목적 패턴을 형성할 수 있는 것을 나타내고 있다. 즉, 2차원 공간 중에서는 비동기, 무기억, 랜덤 등의 매우 저기능의 로봇군에서 자기 안정된 형상 형성을 실현할 수 있다.

필자가 소속된 연구팀에서는 회전군을 이용해 정리 1의 결과를 3차원 공간 중의 로봇군으로 확장했다. 3차원 공간 중의 회전 대칭성을 이루는 무리는 순회군, 이면체군, 정사면체군, 정팔면체군, 정이십면체군 등 5종류의 회전군이며, 각각 정다각뿔, 정다각기둥, 정사면체, 정팔면체, 정이십면체에 대한 회전 대칭 조작의 집합이다. 그림 3에 나타냈듯이 이러한 회전 대칭 조작은 회전축의 집합으로서도 인식할 수 있다. 동일 평면상의 점집합에 작용하는 순회군, 이면체군을 2차원적인 회전군이라고 부르고, 작용하지 않는 정사면체군, 정팔면체군, 정이십 면체군을 3차원적인 회전군이라고 부르기로 한다.

회전군을 하나 선택해 그 회전군이 갖는 회전축 상 이외에 초기점을 두고, 무리의 각 요소를 작용시키면 무리의 자릿수와 동일한 크기의 궤도를 얻을 수 있다. 2차원 공간의 경우와 마찬가지로 이러한 초기 배치에서 대칭성이 낮은 목적 패턴을 형성할 수는 없다.

5종류의 회전군에는 부분군의 구조가 있으며, 자릿수만으로는 대칭도를 의논할 수 없다. 3차원 공간 중의 점집합 P의 회전군 ϒ(P)를 P에 작용하는 회전군 G에서, G를 진짜 부분군으로 하는 회전군의 어느 것도 P에 작용하지 않는 것으로 한다. ϒ(P)는 유일하게 정해지고, P에 대해 ϒ(P)의 축 배치도 정해진다. 점집합 P의 대칭도 ϱ(P)를, ϒ(P)의 축 중 P의 요소를 포함하지 않는 축이 구성하는 모든 회전군의 집합으로 한다. 3차원 공간 중의 로봇군에 대해 이하의 정리가 성립된다.

정리 2  3차원 공간 중의 완전 동기 로봇군이 초기 배치 P에서 목적 패턴 F를 형성할 수 있는 필요충분조건은 무기억성에 의하지 않고, ϱ(P)⊆ϱ(F)이다.

정리 2는 흥미 깊은 결과를 포함하고 있다. 정육면체의 정점 집합의 회전군은 정팔면체군인데, 대칭도는 정팔면체군을 포함하지 않는다. 실제로 정육면체의 8개의 정점에 놓인 로봇의 3차원적인 대칭성을 해소하는 결정성 분산 알고리즘이 존재한다. 마찬가지로 정사면체, 정팔면체, 정십이면체의 정점 집합에 로봇이 놓은 상황에 대해서도 3차원적인 대칭성을 해소하는 결정성 분산 알고리즘이 존재한다. 그러나 정이십면체의 정점 집합에 대해서는 부분군인 정사면체군의 대칭성을 해소할 수 없다. 이것으로부터 3차원 공간 중의 로봇군을 동일 평면에 착지시키는 평면 형성 문제를 해결하기 위한 필요충분조건도 얻을 수 있다.

마지막으로 형성 가능한 목적 패턴에 대한 패턴 형성 알고리즘의 개요를 나타낸다. 2차원 공간, 3차원 공간 모두 과정은 공통으로, 처음에 초기 배치 P의 최소 포함 구(2차원 공간에서는 최소 포함 원)과 목적 패턴 F의 최소 포함 구가 동일한 크기가 되도록 F를 확대 축소하고, ϒ(P)의 축을 기초로 F의 회전을 결정해 작성할 목적 패턴의 배치를 정한다. 다음으로 초기 배치 P를 ϒ(P)에 의해 궤도에 분해하고 각 궤도를 목적 패턴 F의 ϒ(F)에 의한 궤도에 대응시키는, 일종의 완전 매칭을 계산한다. 로봇군은 ϒ(P)에 의한 P의 궤도 공간 요소 간의 완전 순서에 합의할 수 있기 때문에 각 로봇은 이 매칭을 국소적으로 계산할 수 있다. 각 로봇이 이동처를 계산한 후에는 궤도마다 차례로 이동함으로써 매칭을 변경하지 않고 목적 패턴을 형성할 수 있다.

2. 패턴 형성 문제와 그 발전

익명 분산 시스템에서는 대칭성의 해소는 본질적으로 어려우며, 모바일 로봇군 모델뿐만 아니라 계산기 네트워크를 가정한 분산 시스템 모델, 즉 그래프에 대한 대칭도도 정의되어 있다. 필자가 소속된 연구팀에서는 헤테로지니어스한 로봇군의 팀 분할 문제를 제안했다. 이 문제는 채색된 로봇군이 색깔별로 지정된 대수씩 모여서 팀을 형성하는 문제이다. 대칭도의 정의를 채색된 점집합으로 확장함으로써 비동기의 무기억 로봇군이 자기 안정으로 형성할 수 있는 팀의 특징을 부여할 수 있다.

Das 등은 지정된 패턴 열을 차례로 형성하는 패턴 열 형성 문제를 제안, 각 패턴의 대칭도를 이용해 반동기의 무기억 로봇군이 형성 가능한 패턴 열의 특징을 부여했다. 패턴 열 형성 과정은 무기억 로봇군이 기하 배치에 의해 구성하는 카운터로 간주할 수 있다. 또한 로봇 간의 거리에 정보를 포함시킴으로써 무기억 로봇군의 공유 메모리를 구성할 수 있다. Di Luna 등은 정수대의 비동기 무기억 로봇이 1대의 비동기 유기억 로봇을 에뮬레이트하는 방법을 제안했다.

이와 같이 여러 로봇이 협조해 기하적인 배치에 여러 가지 정보를 포함시켜 동기해 그 정보를 갱신함으로써 비동기성, 무기억성을 극복하고, 분자 로봇 시스템의 여러 가지 기능 소자를 구성할 수 있는 가능성을 보였다.

모듈 로봇 시스템에 의한 탐색

분자 로봇 시스템에서 분산 시스템의 요소를 빼내는 방법은 주목하는 스케일, 제약, 기능에 의존한다. 분자 로봇 시스템의 구성 요소를 가정하면 계산 주체군이 충돌이나 결합 등의 상호작용과 신축, 직선 이동, 회전 등의 단순한 이동에 의해 서서히 형상을 변화시키는 모델이 중요하다고 생각된다.

여기서는 2차원 정사각 격자 영역 중의 익명의 모듈군이 집합적으로 구성하는 모듈 로봇 시스템 모델을 소개한다. 이 모델은 모듈이 다른 모듈을 기점으로 슬라이드와 회전(그림 4)을 함으로써 로봇 시스템 전체의 변형이나 이동을 실현한다.

1. 로코모션

모듈 로봇 시스템 모델은 2차원 정사각 격자 영역 중에 놓인 익명의 모듈 집합을 가정한다. 각 모듈은 상태를 갖지 않고 모듈 간에 명시적인 통신 수단이 없으며, 동서남북에 합의하고 있지 않다. 각 셀에는 기껏해야 1개의 모듈을 배치할 수 있으며, 모듈은 근방의 셀에 다른 모듈이 존재하는지의 여부를 관측할 수 있다. 셀의 동서남북 셀을 인접하는 셀이라고 부르며, 모듈군의 연결성을 셀의 인접 관계로 정의한다(그림 4 (a)). 모든 모듈은 각 시각에 동기해 관측, 계산, 이동을 한다. 모듈이 슬라이드를 하는 경우, 이동경로의 한쪽 측을 따라 동시에는 이동하지 않는 모듈이 존재해야 한다. 회전을 하는 경우, 회전 중심의 모듈은 동시에 이동해서는 안 된다. 또한 다른 모듈의 이동경로는 중복되서는 안 된다. 일정 시각에 이동하지 않는 모듈을 그 시각의 백본이라고 부른다. 각 모듈은 자율적으로 이동을 하는데, 각 시각의 모듈군 배치는 연결이며, 백본도 연결이어야 한다.

모듈 로봇 시스템의 형상 형성은 변형 가능성 문제로서 정식화되어 있으며, Dumitrescu 등은 모듈을 일직선으로 늘어놓은 배치를 경유함으로써 형상의 변형을 할 수 있는 것을 나타냈다. 여기서는 모듈 로봇 시스템의 형상을 연속해 변경함으로써 얻어지는 동적인 기능에 주목한다.

그림 5에 회전, 슬라이드에 의한 모듈 로봇 시스템의 형상 변화를 나타냈다. 일련의 움직임에 따라 모듈 로봇 시스템은 1셀만큼 동쪽으로 진행할 수 있다. 이 과정은 쉽게 분산 알고리즘으로서 기술할 수 있고, 또한 그림 5의 움직임을 반복함으로써 모듈 로봇 시스템은 동쪽으로 계속 이동할 수 있다.

자기조직화의 관점에서 중요한 과제는 이러한 이동 능력의 획득, 즉 임의의 초기 배치에서 이동을 시작하는 것이다. 예를 들면, 4개의 모듈이 일직선으로 늘어선 초기 배치를 생각한다(그림 6). 이 초기 배치에서 일어날 수 있는 이동은 양 끝의 2개 모듈의 회전뿐이다. 모듈은 동서남북을 모르기 때문에 이 회전은 동시에 일어난다. 회전 방향에 따라 그림 6의 2종류의 상태로 천이하는데, 어떤 상황에서도 다음에 일어날 수 있는 이동은 조금 전에 회전한 2개 모듈의 슬라이드나 회전뿐이며, 결과는 그림 6의 상태 중 어느 하나가 되고 로봇 시스템은 중심을 고정해 계속 회전한다.

또한, 그림 7 (a)에 나타낸 배치는 대칭성으로 백본을 유지할 수 없고, 어떤 모듈도 이동할 수 없다. 따라서 4개의 모듈은 자율적으로 이동 능력을 획득할 수 없다. 마찬가지로 5개의 모듈에도 교착 상태가 존재하고(그림 7 (b)), 6개의 모듈에도 대칭성으로 진행 방향이 정해지지 않는 초기 배치가 존재한다. 그러나 7개의 모듈에는 대칭의 초기 배치나 교착 상태가 없고, 로봇 시스템은 어떤 위치에서도 이동을 시작할 수 있다. 

모듈 로봇 시스템의 직선 이동에 대해서는 Dumitrescu 등이 모듈이 이동 방향을 합의하고 있는 경우에 대해, 최대 속도와 최대 속도로 이동하는 방법을 나타내고 있다.

2. 탐색 문제

모듈 로봇 시스템은 모듈의 배치가 로봇 시스템의 상태를 나타내며, 모듈의 수가 늘어날수록 로봇 시스템이 취할 수 있는 상태 수도 증가, 보다 복잡한 형상 열을 형성할 수 있다. 필자가 속한 연구팀은 이 점에 주목해, 유한 영역 중의 탐색에 필요충분한 모듈 수를 나타냈다.

탐색 문제란 모듈 로봇 시스템이 유한의 필드 내에 놓인 대상을 발견하는 문제이다. 여기서 필드는 벽으로 둘러싸인 m×n의 2차원 정사각 격자 영역으로 한다(그림 8). 각 모듈은 필드의 크기나 대상의 위치를 모르고, 탐색 시작 시에 자신이 필드의 어느 위치에 놓여 있는지도 모른다.

모듈 로봇 시스템이 필드 내의 모든 셀을 방문할 수 있다면, 대상은 반드시 발견할 수 있다. 5개의 모듈이 있으면, 그림 9에 나타낸 경로를 따라 모듈 로봇 시스템을 이동시키는 형상 열을 구성할 수 있다. 그러나 모듈 로봇 시스템이 경로의 도중에서 탐색을 시작할 가능성도있고, 필드의 남쪽 끝에 도달해도 북쪽 측에 미방문의 셀이 존재할 가능성이 있다. 그래서 남서쪽의 모퉁이에 도달한 시점에서 탐색 경로를 90도 회전시켜 다시 탐색을 한다. 이것에 의해 모듈 로봇 시스템에 모든 셀을 방문하게 할 수 있다. 단, 이번에는 모듈 수에 주목하고 있기 때문에 그림 7 (b)의 초기 배치를 제외한다. 이러한 교착 상태를 제외해도 4개 이하의 모듈군에서는 필드 전체를 이동할 수 없는 경우도 볼 수 있다.

마지막으로 모듈이 동서남북을 합의하고 있는 경우를 생각한다. 이 경우 모듈 간의 대칭성은 완전히 해소되어 있기 때문에 2개의 모듈로도 이동 능력을 획득할 수 있고, 3개의 모듈로 탐색 문제를 해결할 수 있다. 

정리 3  모듈 로봇 시스템이 탐색 문제를 해결하기 위해 필요충분한 모듈의 개수는 모듈군이 방향에 합의하고 있는 경우는 3개이며, 모듈군이 방향에 합의하고 있지 않는 경우는 5개이다.

맺음말

이 글에서는 저기능의 익명 계산 주체군이 구성하는 분산 시스템의 합의 형성, 특히 형상 형성에 관한 결과를 소개했다. 소개한 결과의 대부분은 자기안정성에 기초하는 이론 보증을 갖고 있으며, 분자 로봇 시스템의 설계에 유용하다.

 

이 글에서는 모두를 소개할 수는 없었지만, 분자 로봇 시스템에 관련된 분산 시스템 모델, 문제의 정식화, 분산 알고리즘은 최근 활발히 연구되고 있다. 분야 횡단적인 의논이 진행돼 분자 로보틱스, 제어이론, 이론계산기 과학, 관련된 모든 분야에 새로운 지식을 얻을 수 있기를 기대하고 있다.

야마우치 유키코, 규슈대학 대학원 시스템정보과학연구원