Efficient Coordination and Synchronization of Multi-Robot Systems Under Recurring Linear Temporal Logic

기술 요약: 반복적 선형 시제 논리(LTL) 하에서의 효율적인 다중 로봇 시스템 협업 및 동기화

문제 정의
본 논문은 선형 시제 논리(LTL)로 정식화된 복잡하고 상호 의존적인 작업을 완수하기 위해 다중 에이전트 시스템(MAS)을 조정하고 동기화하는 과제를 다룹다. 특히 저자들은 무한히 자주 만족되어야 하는 **반복적 작업(recurring tasks)**에 초점을 맞춘다. 에이전트의 수와 작업의 복잡성이 증가함에 따라, 기존의 중앙 집중식 계획이나 곱 부키 오토마타(Product Büchi Automata, PBA) 방식에 의존할 경우 확장성과 충돌 없는 운영을 보장하기 어려워진다. 또한, 기존 방식들은 실제 하드웨어 배포 시 동작 지연을 처리하고 협업 동작의 동시 실행을 보장하는 견고한 메커니즘이 부족한 경우가 많다.

방법론
제안된 솔루션은 오프라인 계획 합성(offline plan synthesis)과 온라인 조정 및 동기화를 결합한 **상향식 접근 방식(bottom-up approach)**을 채택한다. 이 프레임워크는 Python과 ROS2로 구현되었다.

1. 시스템 모델링 및 작업 명세:

   • 관심 영역(Region of Interest, ROI): 작업 공간을 세밀한 격자로 분할하는 대신, 시스템은 ROI 세트를 기반으로 한 유한 전이 시스템(Finite Transition System, FTS)을 사용하여 에이전트의 움직임을 모델링한다. 이는 상태 공간의 크기를 크게 줄여준다.
   • 반복적 LTL: 저자들은 반복되는 작업($\phi_r = \phi'_1 \land \square \diamond \phi'_2$)을 위한 특정 LTL 하위 클래스를 정의한다. 이러한 구조는 작업 명세를 위반하지 않으면서 상태 사이에 유한한 우회 경로(detour)를 삽입할 수 있게 한다.
   • 동작 모델: 에이전트는 로컬 동작, 협업 동작(도움이 필요한 동작), 그리고 보조 동작을 수행한다. 협업은 관련된 모든 동작이 동시에 시작될 때만 성공한 것으로 정의된다.

2. 오프라인 초기 계획:

   • 각 에이전트의 FTS 상에서 반복적 작업을 만족시키기 위해, 표준 LTL 계획 기법(LTL2BA 및 모델 체킹)을 사용하여 초기 최적 계획을 오프라인에서 생성한다.

3. 온라인 조정 (요청-응답-확인 사이클):

   • 요청(Request): 에이전트가 협업 동작을 예상할 때, 필요한 보조 동작, 대상 지역, 명목상 시작 시간을 명시하여 요청을 브로드캐스트한다.
   • 응답(Reply): 요청을 받은 에이전트들은 더 복적인 PBA를 피하기 위해, 자신의 FTS 상에서 수정된 다익스트라(Dijkstra) 알고리즘을 사용하여 요청된 지역으로의 잠재적 우회 경로를 계산한다. 이후 자신의 가용성과 예상 시작 시간을 응답한다.
   • 확인(Confirmation, 최적화): 요청 에이전트는 목표 시작 시간으로부터의 편차를 최소화하는 최적의 보조 에이전트 집합을 선택하기 위해 혼합 정수 계획법(Mixed Integer Program, MIP)을 구성한다.
   • 필터링(Filtering): MIP의 복잡성을 줄이기 위해 필터링 절차가 도입된다. 이는 목표 시간에 대한 근접성을 기준으로 에이전트의 부분 집합을 사전 선택하며, 이 과정은 전체 문제를 풀지 않고도 해당 부분 집합이 MIP의 최적해를 포함하고 있음을 증명한다.

4. 계획 적응 및 동기화:

   • 즉각적인 솔루션을 찾을 수 없는 경우, 요청 에이전트는 동작을 지연(self-loop 삽입)시키고 사이클을 재시도한다.
   • 에이전트들이 선택되면, 이들은 우회 경로를 포함하도록 계획을 업데이트한다.
   • 동기화: 특정 메커니즘은 동시 실행을 보장한다. 에이전트들은 협업 지점에 도달하면 "준비 완료(Ready)" 메시지를 보낸다. 요청 에이전트는 모든 "준비 완료" 메시지를 받은 후에만 "시작(Start)" 명령을 보내어, 모든 에이전트가 동일한 순간에 협업 동작을 시작하도록 보장한다.

주요 기여

• 반복적 LTL 프레임워크: 유연한 계획 적응을 가능하게 하는 우회 경로 삽입이 용이한 특정 LTL 구문을 도입하였다.
• 계산 효율성:
  • ROI 표현: 격자 기반 분할을 ROI 기반 FTS로 대체하여 상태 공간 크기를 평균 88.7% 감소시켰다.
  • PBA 대비 FTS: 계획 적응을 위해 곱 부키 오토마타 대신 더 단순한 FTS를 사용하여 상태 수를 평균 84.8% 줄였다.
  • MIP 필터링: 최적성을 유지하면서 대규모 $N$에 대한 계산 부하를 획기적으로 낮추는 필터링 절차를 통해 최적화 문제에 참여하는 에이전트 수를 줄였다.
• 견고한 동기화: 동작 지연을 처리하고 협업 작업의 동시 실행을 보장하는 ROS2 프레임워크 내의 새로운 동기화 메커즘을 개발하였다.
• 실제 환경 검증: 이질적인 하드웨어(Turtlebot3 및 Hebi Rosie 로봇)에 배치된 소프트웨어 패키지를 개발하였다.

실험 결과

• 하드웨어 실험: 시스템은 4.2m × 5.2m 작업 공간에서 9대의 로봇 팀(Hebi Rosie 3대, Turtlebot3 6대)과 함께 검증되었다. 로봇들은 순찰, 물체 제거, 협업 적재/점검을 포함하는 반복적 작업을 성공적으로 수행하였다. 실험을 통해 에이전트들이 서로 다른 시간에 도착하더라도 협업 동작을 동기화할 수 있음을 입증하였다.
• 확장성 시뮬레이션: 최대 90대의 에이전트를 대상으로 시뮬레이션을 수행하였다. 결과에 따르면 필터링 절차는 에이전트 수가 증가함에 따라 확인 시간을 크게 단축시켰으며, 시스템은 이러한 규모에서도 작업과 협업을 성공적으로 완료하였다.
• 복잡도 분석: ROI 표현과 FTS 기반 접근 방식이 이전의 격자 기반 및 PBA 기반 방식에 비해 상태 공간 크기를 대폭 감소시킴(Turtlebot의 경우 최대 96.4%)을 데이터로 확인하였다.

의의 및 주장
본 논문은 제안된 방식이 반복적 LTL 제약 조건 하에서 다중 로봇 협업을 위한 계산 효율적이고 확장 가능한 솔루션을 제공한다고 주장한다. 오프oline 계획과 통신 기반의 온라인 적응을 통합함으로써, 이 방법은 중앙 집중식 PBA 구축의 지수적 복잡성을 피하면서도 그래프 탐색 방법의 결정론적 보장을 유지한다. 저자들은 상용 로봇 플랫폼에 대한 성공적인 배포와 대규모 시뮬레이션에서 보여준 확장성을 바탕으로, 본 시스템이 광범위한 응용 분야에 적응 가능하다고 단언한다. 본 연구는 유한 시간 작업 제약의 한계를 해결하고, ROI 및 필터링을 통해 계산 효율성을 높이며, 시뮬레이션만이 아닌 물리적 실험을 통해 접근 방식을 검증함으로써 기존 연구([13])를 확장하였다.