Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

인공지능의 세계에서 의사결정을 내리는 일은 종종 규칙이 완벽하게 알려진 보드 위에서 벌어지는 확률 게임처럼 취급됩니다. 로봇이 미로를 탐색하는 상황을 상상해 보십시오. 만약 엔지니어들이 바닥이 얼마나 미끄러운지, 로봇의 바퀴가 어떻게 회전할지를 정확히 알고 있다면, 그들은 출구까지 가는 완벽한 경로를 계산할 수 있습니다. 이것이 많은 의사결정 시스템의 표준 모델입니다. 그러나 현실 세계는 결코 그렇게 정밀하지 않습니다. 센서는 고장 나고, 재료는 마모되며, 데이터에는 노이즈가 섞여 있습니다. 즉, 로봇이 미끄러지거나 자동차가 경로를 이탈할 정확한 확률은 결코 진정으로 알 수 없으며, 오직 가능한 범위 내에서만 추정될 뿐입니다. 이러한 불확실성이 가미되면 문제는 훨씬 더 어려워집니다. 지형의 거동을 확신할 수 없을 때 어떻게 안전한 경로를 계획할 것인가의 문제입니다. 나아가 자율 주행이나 의료 로봇 공학과 같은 안전이 필수적인 분야에서는, 단순히 목적지에 빠르게 도착하는 것뿐만 아니라 시스템이 결코 위험한 상태에 진입하지 않거나 특정 논리적 사건의 순서를 영원히 따르지 않도록 보장하는 것이 목표입니다.

인도 공과대학교 봄베이(IIT Bombay)와 난양 공과대학교(NTU)의 연구진은 이러한 불확실성과 엄격한 논리적 안전성 사이의 까다로운 접점을 다루었습니다. 그들은 에이전트가 세상을 부분적으로만 볼 수 있고, 움직임의 규칙이 고정된 숫자가 아니라 가능한 값들의 집합에 속하는 문제 유형에 집중했습니다. 연구팀은 이 복잡하고 불확실한 의사결정 문제를 푸는 것이, 숨겨진 정보를 가진 두 명의 대립하는 플레이어가 참여하는 잘 알려진 유형의 게임을 푸는 것과 수학적으로 동일하다는 것을 증명했습니다. 이러한 양방향 연결을 확립함으로써, 그들은 수십 년간 축적된 기존의 게임 이론 지식을 빌려와 이 불확실한 로봇 문제들을 해결하는 데 드는 계산적 난이도를 즉각적으로 결정할 수 있었습니다. 그들의 연구는 이러한 시나리오에서 안전성을 보장하는 것이 얼마나 어려운지를 밝혀냈으며, 어떤 유형의 논리적 목표에 대해서는 기존의 방법들로 해결 가능하지만, 다른 유형의 경우에는 너무 복잡하여 어떤 알고리즘도 합리적인 시간 내에 해결할 수 없음을 보여주었습니다.

그들 발견의 핵심은 서로 다른 두 수학적 세계를 연결하는 데 있습니다. 한쪽에는 에이전트(예: 자율 주행 자동차)가 자신의 정확한 위치를 모르고 새로운 상태로 이동할 확률 또한 정확히 모르는 상태에서 행동을 선택해야 하는 상황을 묘사하는 데 사용되는 모델인 '강건한 부분 관측 마르코프 결정 과정(robust partially observable Markov decision process)'이 있습니다. 단일 확률 대신, 시스템은 가능한 확률들의 '구름' 안에서 작동합니다. 다른 한쪽에는 두 명의 플레이어가 (한 명은 성공하려 하고 다른 한 명은 이를 저지하려 하며) 보드에 대한 부분적인 정보만을 가진 채 차례대로 움직이는 모델인 '부분 관측 확률 게임(partially observable stochastic game)'이 있습니다. 연구자들은 만약 목표가 단순히 보상을 극대화하는 것이라면, 이 두 모델이 서로 변환될 수 있다는 것을 이미 알고 있었습니다. 그러나 목표가 "보행자를 절대 치지 않는다"라거나 "결국 병원에 도착하여 그곳에 영원히 머문다"와 같은 엄격한 논리적 규칙으로 바뀌면, 이 연결 고리는 끊어집니다. 새로운 연구는 이러한 복잡한 논리적 규칙이 적용되는 경우에도 두 모델이 여전히 완벽하게 동등하다는 것을 증명합니다.

이를 입증하기 위해 연구진은 양방향으로 작동하는 정밀한 번역 메커니즘을 구축했습니다. 먼저, 불확실한 확률을 가진 강건한 의사결정 문제를 두 명의 플레이어가 참여하는 게임으로 변환하는 방법을 보여주었습니다. 이 새로운 게임에서 에이전트는 한 명의 플레이어가 되고, 세상의 불확실성은 대립하는 두 번째 플레이어가 됩니다. 이 두 번째 플레이어는 무작위로 행동하는 것이 아니라, 에이전트를 패배시키기 위해 가능한 옵션 중 최악의 시나리오를 능동적으로 선택합니다. 연구진은 에이절트가 영리한 상대방을 상대로 이 게임에서 이길 수 있다면, 원래의 불확실한 세상에서도 성공할 수 있다는 것을 증명했습니다. 더욱 놀라운 점은 역방환이 가능했다는 것입니다. 그들은 숨겨진 정보를 가진 모든 두 명의 플레이어 게임이 강건한 의사결정 문제로 다시 변환될 수 있음을 보여주었습니다. 이 역단계는 기술적으로 매우 어려웠는데, 왜냐하면 게임에서는 상대방이 에이전트의 움직임을 본 후에 행동하는 반면, 의사결정 문제에서는 환경이 즉시 그 행동을 확정하기 때문입니다. 연구팀은 게임 구조에 짧고 보이지 않는 '일시 정지'를 삽로 넣어, 환경이 원래 문제에서 가졌던 것과 동일한 정보를 갖게 함으로써 이 문제를 해결했습니다. 이 양방향 가교는 한 유형의 문제를 푸는 것에 관한 모든 컴퓨터 과학적 결과가 다른 유형의 문제에도 자동으로 적용된다는 것을 의미합니다.

이러한 동등성의 함의는 자동 추론의 한계를 이해하는 데 있어 즉각적이고 심오합니다. 이 가교를 사용하여 연구진은 다양한 유형의 논리적 목표에 대해 이 문제들을 해결하는 계산 복잡도를 지도화할 수 있었습니다. 그들은 목표 지점에 도달하거나 위험 구역을 피하는 것과 같은 단순한 목표의 경우, 시스템의 크기에 따라 기하급급적으로 증가하는 상당한 컴퓨팅 파워를 요구하긴 하지만 해결 가능하다는 것을 발견했습니다. 그러나 연구는 하나의 한계점을 식별했습니다. 특히 '항상'과 '결국' 조건이 혼합된 두 가지 측면의 불확실한 환경에서의 복잡한 논리적 목표의 경우, 문제는 '결정 불가능(undecidable)'해집니다. 이는 어떤 강력한 컴퓨터 프로그램이라 할지라도 모든 가능한 시나리오에 대해 답을 보장할 수 없음을 의미합니다. 또한 연구진은 에이전트만 눈이 멀고 환경은 모든 것을 보고 있는 일방적 불확실성(one-sided uncertainty)의 난이도를 명확히 하여, 이러한 경우가 완전한 시야 상실 시나리오보다 일반적으로 해결하기 쉽다는 것을 보여주었습니다.

이 작업은 불확실성 하에서 안전한 자율 시스템을 설계할 때 무엇이 계산적으로 가능한지에 대한 완전한 지형도를 제공합니다. 이 연구는 우리가 많은 안전 필수 과업을 처리할 수 있는 알고리즘을 구축할 수 있음을 확인해 주는 동시에, 숨겨진 정보, 적대적 불확실성, 그리고 복잡한 논리적 규칙이 결합될 때 솔루션을 찾는 것이 불가능해지는 근본적인 경계가 존재함을 확인시켜 줍니다. 이 연구는 모든 경우를 해결하는 새로운 알고리즘을 제시하는 것이 아니라, 엔지니어들에게 어떤 문제를 해결할 수 있고 어떤 문제에 완전히 다른 접근 방식이 필요한지를 정확히 알려주는 결정적인 지형도를 제공합니다. 이 두 수학적 프레임워크가 동일하다는 것을 증명함으로써, 연구진은 기존의 방대한 도구와 이론의 라이브러리를 활용할 수 있게 했으며, 이를 통해 이 분야가 앞으로 직면할 도전 과제들을 명확히 이해하며 나아갈 수 있도록 했습니다.