Multi-Agent Planning with Spatio-Temporal and Topological Constraints using STL-GO

드론 군집이 단순히 무작위로 비행하는 것이 아니라, 하나의 거대하고 똑똑한 두뇌처럼 움직이는 세상을 상상해 보십시오. 이것은 바로 **멀티 에이전트 시스템(Multi-Agent Systems)**의 영역입니다. 이는 많은 로봇이 협력하여 산불을 끄거나 길 잃은 등산객을 찾는 것과 같은 거대한 문제를 해결하는 컴퓨터 과학의 한 분야입니다. 로봇들이 서로 충돌하거나 자신의 임무를 잊어버리지 않도록 하기 위해, 엔지니어들은 "형식적 방법(formal methods)"을 사용합니다. 이는 로봇들이 따라야 할 엄격한 수학적 규칙집을 작성하는 아주 멋진 방식입니다. 보통 이러한 규칙집은 "빨간불에 멈춰라" 또는 "시속 20마일보다 빠르게 달리지 마라"와 같은 단순한 교통 법규와 같습니다. 하지만 현실 세계는 훨씬 더 복잡합니다. 때때로 로봇은 "내 친구가 근처에 있는가? 그와 대화할 수 있는가? 그가 불을 보았는가?"와 같은 것을 알아야 합니다. 이를 위해서는 시간과 공간뿐만 아니라, 로봇 사이의 연결 형태인 **토폴로지(topology)**를 이해하는 규칙집이 필요합니다. 이것은 개별 자동차를 위한 규칙 목록과, 매 초마다 파트너를 바꾸는 무용단 전체를 위한 규칙집 사이의 차이와 같습니다.

이 논문은 로봇들의 "우정 지도(friendship map)"가 끊임없이 변하는 상황에서, 군집 로봇들이 어떻게 움직임을 계획하도록 가르칠 것인가라는 까다로운 문제를 다룹니다. 저자들은 STL-GO(Spatio-Temporal Logic with Graph Operators, 그래프 연산자가 포함된 시공간 논리)라는 새롭고 매우 강력한 규칙집 언어를 소개합니다. 기존의 언어들은 시간과 공간은 다룰 수 있었지만, 누가 누구와 대화하는지에 대한 복잡하고 변화하는 웹(web)을 다루는 데는 어려움이 있었습니다. 연구진은 이러한 복잡하고 변화하는 규칙들을 받아들여 로봇들을 위한 구체적인 비행 계획으로 변환할 수 있는 두 가지 서로 다른 "번역기"(하나는 혼합 정수 프로그래밍 기반이고, 다른 하나는 만족 가능성 모듈로 이론 기반임)를 구축했습니다. 그들은 위치 탐색 드론(locator drones)과 구조 드론(rescuer drones)이 포함된 시뮬레이션된 구조 임무에서 이 번역기들을 테스트했습니다. 그들의 결과는 이 새로운 방식이 복잡한 팀워크를 처리할 만큼 강력하지만, 특정 작업에 따라 한 방법이 다른 방법보다 더 빠르게 문제를 해결하는 등 계산량이 많을 수 있음을 보여줍니다.

변화하는 군집의 이야기

당신이 로케이터(Locators, 정찰병)와 리스큐어(Rescuers, 영웅)라는 두 종류의 드론으로 구성된 구조 팀의 지휘관이라고 상상해 보십시오. 로케이터들은 불을 찾기 위해 숲을 날아다닙니다. 로케이터가 불을 발견하면, 다음과 같은 순서대로 몇 가지 일을 수행해야 합니다:

1. 감지(Sense): 불이 진짜인지 확인한다.
2. 연결(Connect): 다른 로케이터들과 리스큐어들에게 "여기에 불이 있다!"라고 외친다.
3. 할당(Assign): 도움을 주러 갈 특정 리스큐어를 선택한다.
4. 행동(Act): 리스큐어가 불이 난 곳으로 날아가 생존자를 태우고 안전한 텐트로 옮긴다.

문제는 무엇일까요? "외치는" 부분은 바람, 배터리 잔량, 그리고 드론이 어디를 날고 있는지에 따라 달라진다는 점입니다. 때로는 로케이터가 리스큐어와 대화할 수 있지만, 때로는 그렇지 못합니다. 때로는 리스큐어가 듣기에 너무 멀리 떨어져 있을 수도 있습니다. 누가 누구와 대화할 수 있는지에 대한 지도는 동적 그래프(dynamic graph), 즉 매 초마다 변하는 연결의 웹입니다.

저자들이 해결한 문제는 이것입니다: 연결 상태가 계속 변하는 상황에서도 규칙을 준수하도록 하는 컴퓨터 프로그램을 어떻게 작성하여, 이 모든 드론의 완벽한 비행 경로를 찾아낼 것인가?

마법의 규칙집: STL-GO

저자들은 STL-GO라는 특별한 언어를 사용했습니다. 이 언어를 다음과 같은 명령을 내릴 수 있는 방법이라고 생각하십시오:

• "모든 불은 5분 이내에 로케이터에 의해 발견되어야 한다."
• "발견된 후, 로케이터는 2분 이내에 대화할 수 있는 최소 하나 이상의 리스큐어를 찾아야 한다."
• "그 후 리스큐어는 불이 난 곳으로 날아가 생존자를 텐트로 데려와야 한다."

STL-GO의 "그래프 연산자(Graph Operators)"는 핵심 비법입니다. 이 연산자들은 규칙집이 다음과 같이 말할 수 있게 해줍니다: "현재의 연결 지도를 확인하라. 로케이터로부터 리스큐어까지의 경로가 존재하는가?" 이는 단순히 "좌표 X, Y로 가라"고 말하는 것보다 훨씬 어렵습니다. 이는 컴퓨터가 팀의 네트워크 형태를 지속적으로 재평가하도록 요구하기 때문입니다.

두 가지 번역기: MIP와 SMT

규칙을 쓰는 것도 중요하지만, 로봇을 실제로 날게 하는 것은 또 다른 문제입니다. 컴퓨터는 이러한 고차원적인 규칙들을 단계별 이동 목록(예: "앞으로 5미터 전진, 왼쪽으로 회전")으로 번려해야 합니다. 논문은 이 작업을 수행하기 위한 두 가지 서로 다른 "번역기"를 제시합니다:

1. MIP 번역기 (혼합 정수 프로그래밍, Mixed-Integer Programming): 이것을 매우 엄격하고 세부 사항에 집착하는 회계사라고 상상해 보십시오. 이 방식은 단순히 '어떤' 계획이 아니라, '최선의' 가능한 계획을 찾으려고 노력합니다. "배터리를 가장 적게 사용하는 경로를 찾아라"와 같은 명령을 내릴 수 있습니다. 이는 에너지를 절약하고 싶을 때 유용하지만, 마치 거대한 스도쿠 퍼즐을 풀면서 저글링을 하는 것처럼 느리고 무거울 수 있습니다.
2. SMT 번역기 (만족 가능성 모듈로 이론, Satisfiability Modulo Theory): 이것을 번개처럼 빠른 탐정이라고 생각하십시오. 이 방식은 '최선의' 계획을 찾는 데 관심이 없습니다. 그저 '작동하는' 계획 하나를 찾고자 할 뿐입니다. 이 방식은 "이 모든 규칙을 만족하는 것이 가능한가?"라고 묻습니다. 만약 가능하다면, 해결책을 제시합니다. 보통 회계사보다 훨씬 빠르지만, 연료 효율성과 같은 요소를 최적화할 수는 없습니다.

구조 시뮬레이션

아이디어를 테스트하기 위해 저자들은 산불 구조 시뮬레이션을 만들었습니다. 그들은 **로케이터(Locators)**와 **리스큐어(Rescuers)**가 등장하는 시나리오를 설정하고, 컴퓨터에게 다음과 같은 임무를 계획하도록 요청했습니다:

• 불은 서로 다른 지점에서 발생할 수 있음.
• 드론들은 서로 대화할 수 있는 거리에 있는지에 따라 통신하고 작업을 할당해야 함.
• 이 모든 과정은 특정 시간 제한 내에 이루어져야 함.

그들은 다양한 팀 규모(로케이터 5명에서 9명까지)와 다양한 복잡도 수준(단순 감지, 통신 추가, 작업 할당 추가)으로 시뮬레이션을 실행했습니다.

그들이 발견한 사실은 다음과 같습니다:

• SMT 번역기는 속도광이었습니다. 거의 모든 테스트에서 SMT 번역기는 MIP 번로보다 훨씬 빠르게 유효한 비행 계획을 찾아냈습니다. 예를 들어, 9명의 로케이터와 3명의 리스큐어가 모든 유형의 연결을 처리하는 경우, SMT 번역기는 약 16.5초 만에 문제를 해결했지만, MIP 번역기는 1,480초 이상이 걸렸으며 (그 시간 동안에도 절대적인 최적의 계획을 찾지 못하고 단지 좋은 계획을 찾았을 뿐입니다).
• MIP 번역기는 최적화 도구였습니다. 저자들이 MIP 번역기에게 가장 직접적이고 연료 효율적인 경로를 찾도록 요청했을 때, 그것은 드론의 움직임을 형성하는 데 훌륭한 역할을 했으나, SMT 번역기는 그저 작동하는 아무 경로를 제공할 뿐이었습니다.
• 복잡성이 중요합니다. 더 많은 규칙(예: 특정 통신 링크나 작업 할당 요구)을 추가할수록 문제의 난이도는 높아졌습니다. 하지만 MIP 번역기가 가장 큰 어려움을 겪었는데, 팀 규모가 커짐에 따라 변수와 제약 조건의 수가 폭발적으로 증가했기 때문입니다.

이것이 왜 중요한가

이 논문은 로봇 군집의 모든 문제를 해결했다고 주장하는 것이 아닙니다. 저자들은 자신들의 결과가 환경이 완벽하게 예측 가능한(갑작스러운 돌풍이나 무선 통신 장애가 없는) 시뮬레이션에 기반하고 있다는 점을 주의 깊게 명시하고 있습니다. 실제 세상은 훨씬 더 무질서하며, 이러한 계획들은 실시간으로 조정되어야 할 수도 있습니다.

하지만 저자들은 로봇 팀을 위한 복잡하고 변화하는 규칙을 작성하는 것이 가능하며, 컴퓨터가 이를 통해 어떻게 비행할지를 결정할 수 있다는 것을 성공적으로 보여주었습니다. 그들은 "회계사"(MIP)가 미세 조정에는 훌륭하지만, 임무가 가능한지 여부를 빠르게 판단하는 데는 "탐정"(SM-T)이 종종 더 나은 선택임을 입증했습니다. 이는 역동적인 실제 재난 상황에서 잘 조율된 인간 구조대처럼, 상황에 맞춰 팀워크를 조정하며 협력할 수 있는 로봇 군집을 향한 중요한 진전입니다.