본 연구는 다수 로봇 무리가 분산된 공간을 커버하기 위한 일체형(cohesive) 구성(configuration) 제어기를 제시한다. 목표는 로봇이 무리를 이루는 동안에도 네트워크에 대한 불완전한 지식만을 가지고서 단절에 강건한 조밀하고 볼록한(convex) 네트워크를 구축하는 것이다. 제어기는 두 가지 서로 다른 알고리즘의 통합된 프레임워크로 구성된다. 첫째, 경계 힘(boundary force) 알고리즘을 제시한다. 이는 액체 분자 사이의 표면장력(surface tension) 힘이라는 개념을 차용한 물리 기반 swarm intelligence이다. 이러한 힘을 기존의 무리 이동(flocking)과 결합하면 로봇 네트워크의 전체 형상에 대한 지식 없이도 볼록하고 조밀한 구성을 생성한다. 둘째, 로봇들은 단일 로봇의 제거가 국소 토폴로지를 변화시키는 영역인 국소 관절점(local articulation point)을 식별함으로써, 어떤 구성이 단절 직전에 있는지를 분산적으로 결정한다. 이러한 점이 감지되면 로봇들은 클러스터링(clustering)으로 행동을 전환하여, 취약한 영역 주변에 로봇들을 집합시켜 모든 관절점을 제거하고 연결된 구성을 유지한다. 마지막으로, 대규모 파편화(massive fragmentation)에 대해 로봇 구성이 갖는 위험 수준을 객관적으로 나타내는 취약성 지수(vulnerability index)를 도입하였다. 각 알고리즘의 이론적 성능 분석을 제시하고, 저비용 로봇 세트를 사용한 시뮬레이션 및 실험으로 결과를 검증한다.

본 논문은 관절 구조를 갖춘 와이어 구동 수술용 로봇 팔에 대한 전방기구학 모델과 역기구학 해를 포함하는 경로 생성 알고리즘을 제시한다. 제안된 방법은 단일 포트 수술(single-port surgery)을 위한 와이어 구동 수술용 로봇에 적용되었다. 이 로봇은 단일 포트 내 작업 공간에 적합하도록 이중 세그먼트를 갖는 뱀과 같은 형태의 로봇 팔과, 강성을 확보하기 위한 관절 구조를 가진다. 모델의 정확도는 매우 중요한데, 이는 소형 수술용 로봇 팔은 대개 개루프 제어로 구동되기 때문이다. 연속체 로봇 본체를 기술하고 제어하기 위해서는 곡률 모델이 널리 사용된다. 그러나 제안한 모델은 관절 구조를 갖춘 연속체 로봇 팔과는 상당히 달라 구동 와이어의 늘어짐(slack) 또는 관절 강성의 감소를 초래할 수 있다. 실제 하드웨어 구조에 부합하도록 프레임 변환(frame transformation) 방법을 통해 정확한 전방기구학 모델을 도출하였다. 관절 구조에 대해서는 대칭 곡률 모델과 달리 비대칭(asymmetric) 모델로부터, 관절 공간(joint space)에서 와이어 길이 공간(wire-length space)으로의 역기구학 모델을 결정하였다. 경로 생성 알고리즘은 개루프 제어(open-loop control)에서 각 구동기(actuator)로 전송할 명령을 생성해야 한다. 작업 공간(task space)에서 관절 공간(joint space)으로의 역기구학을 해결하는 두 가지 실시간 경로 생성 알고리즘을 설계하고, 시뮬레이션 및 실험을 통해 비교하였다. 한 알고리즘은 순차 이차계획법(sequential quadratic programming, SQP)을 이용한 최적화 방법이며, 다른 알고리즘은 PID(비례-적분-미분; Proportional-Integral-Derivative) 제어 알고리즘을 활용한 미분 기구학(differential kinematics)을 사용한다. 각 알고리즘의 장점과 한계에 대해 논의한다.

우리는 그래프를 탐색하기 위한 다양한 자연스러운 노드 기반 및 간선 기반 국소 전략에 대한 하한을 제시한다. 본 연구는 이 문제를 임의의 그래프의 맥락에서뿐 아니라 로봇에 의한 공간의 기하학적 탐색이라는 추상화에서도 다룬다. 두 경우 모두 이전에 광범위하게 연구되어 왔다. 우리는 탐색 경로에서 다음 단계를 선택하기 위해 마지막 방문 시각(time-of-last-visit) 또는 대안적으로 가장 덜 빈번하게 방문된(least-frequently-visited) 지역적 탐욕 전략을 사용하는 국소 탐색 정책을 고려한다. 이 두 전략은 이전에 Cooper et al. (2011)이 간선에 마지막 방문 또는 방문 빈도에 대한 카운터가 부착된 시나리오에 대해 고려한 바 있다. 본 연구에서는 카운터가 노드에 연관되는 경우를 다루며, 이는 기하학적 공간의 이중 그래프(dual graphs)에서는 직관적으로 더 자연스럽고 또한 더 효율적일 가능성이 있다고 주장할 수 있다. 그런데도 놀랍게도, 이러한 대안적 전략들은 탐색에 대해 최악의 경우 초다항/지수 시간의 성능을 보이는 반면, 간선에 대한 가장 덜 빈번하게 방문된 전략은 Cooper et al. (2011)이 제시한 바와 같이 다항식으로 상계되는 탐색 시간을 갖는다.

우리는 개별 로봇의 능력이 제한된 로봇 군집(swarm)이 미지의 환경을 다중로봇 시스템으로 삼각분할(triangulation)하여 이를 기반으로 탐색, 커버리지, 감시를 조직하기 위한 근본적인 틀을 제시한다. 국소적으로는 하나의 개별 삼각형은 단일 로봇이 관리하기 쉽고 작은 영역을 커버한다. 반면 전역적으로는 삼각분할의 위상(topology)이 전체 환경의 기하를 근사적으로 포착한다. 이를 결합하면, 다중로봇 시스템은 탐색, 지도작성, 항법(navigation), 순찰(patrol)을 수행할 수 있다. 알고리즘은 로봇들이 자신의 알고리즘을 수행하는 동안 읽고 쓸 수 있는 삼각형에 정보를 저장할 수 있다. 이는 견고하면서도 다재다능한 물리적 데이터 구조(physical data structure, PDS)를 형성한다. 우리는 다중로봇 네트워크를 사용하여 미지의 2차원 유클리드 공간(two-dimensional Euclidean space)을 삼각분할하는 분산(distributed) 접근을 연구한다. 그 결과로 생성되는 PDS는 작업공간(workspace)의 간결한 표현이며, 각 삼각형에 대한 분산 지식을 포함하고, 삼각분할의 쌍대 그래프(dual graph)를 부호화하며, 보조 데이터(auxiliary data)에 대한 읽기 및 쓰기를 지원한다. 이러한 보조 정보를 저장하고 처리하는 능력은 단순한 로봇들이 복잡한 문제를 해결할 수 있게 해준다. 우리는 쌍대 그래프 항법(dual-graph navigation), 순찰, 위상학적 보로노이 테셀레이션(topological Voronoi tessellation)의 구성, 비볼록 영역(non-convex regions)에서의 지오데식 중심(geodesic centers) 위치 파악을 위한 분산 알고리즘을 개발한다. 또한, 구성된 삼각분할의 품질 및 삼각분할에서의 쌍대 그래프 연결성(connectivity)에 대한 이론적 성능 보장을 제공한다. 더 나아가, 물리적 항법에서의 경로 길이가 최단경로 유클리드 거리(shortest-path Euclidean distance)보다 상수 배 이내임을 보인다. 우리는 이러한 이론적 결과를 시뮬레이션과 열두 대 이상 로봇을 활용한 실험으로 검증한다.

본 논문에서는 여러 로봇이 연결성을 유지하면서 다양한 형태의 장애물을 회피하기 위해 자신의 구성(configuration)을 변형할 수 있게 하는 완전 분산형 알고리즘인 변형 구성 제어(deformable configuration control)를 제시한다. 로봇이 장애물에 접촉하면, 개별 로봇의 충돌(bumped) 상태를 공유하여 장애물의 폭을 먼저 추정하고, 장애물 우회(detouring)와 벽에 튕겨 나감(bouncing off a wall) 사이에서 적절한 장애물 회피 시나리오를 선택한다. 둘째로, 두 시나리오 모두에서 로봇은 장애물을 회피하기 위해 부모를 따르는(following motion) 운동 모델로 자신의 운동 모델을 전환한다. 마지막으로 로봇은 장애물로부터 완전히 벗어났는지 판단하기 위해 최대 트리 각(tree angle)을 계속 감지하고, 군집(flock) 형성 운동 모델로 복귀한다. 로봇들이 장애물을 회피하는 동안 연결성을 유지하기 위한 이론적 분석을 제공한다. 시뮬레이션 결과, 연결성을 유지한 채 36대의 로봇 집단이 1) 작은 막대, 2) 좁은 통로, 3) 큰 벽의 세 가지 서로 다른 유형의 장애물을 성공적으로 회피함을 보여준다.