🤖 AI

An Undecidability Proof for the Plan Existence Problem

이 논문은 행동의 전제 조건의 양상 깊이(modal depth)가 최대 1이고 사후 조건(postconditions)이 없는 경우에도, 모달 논리 기반의 목표 상태에 도달하기 위한 행동 시퀀스의 존재 여부를 결정하는 '계획 존재 문제(plan existence problem)'가 결정 불가능(undecidable)함을 증명합니다.

원저자: Antonis Achilleos

게시일 2026-04-27

📖 2 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Antonis Achilleos

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

🕵️‍♂️ 상황 설정: "기억력이 나쁜 탐정들의 보물찾기"

여러 명의 탐정이 있다고 상상해 보세요. 이 탐정들의 목표는 **"보물이 어디 있는지 정확히 알아내는 것"**입니다. 하지만 이 탐정들은 몇 가지 제약이 있습니다.

불완전한 정보: 탐정들은 보물이 A 방에 있는지 B 방에 있는지 확신하지 못합니다. (이것이 논문에서 말하는 'Kripke 모델' 즉, 가능한 상태들의 집합입니다.)
행동의 제약: 탐정들은 '문 열기', '질문하기' 같은 행동을 할 수 있습니다. 그런데 이 행동들은 **"지금 내가 무엇을 알고 있는가?"**에 따라 할 수 있는지 없는지가 결정됩니다. (이것이 '전제 조건(Preconditions)'입니다.)
단순한 행동: 이 탐정들은 행동을 한다고 해서 세상의 물리적인 상태를 바꾸지는 못합니다. 오직 **"아, 그렇구나!" 하고 깨닫는 것(지식의 변화)**만 가능합니다. (이것이 '후속 조건(Postconditions)이 없음'을 의미합니다.)

❓ 문제의 핵심: "계획을 세울 수 있을까?"

여기서 질문이 생깁니다. "주어진 행동들을 적절히 조합해서, 결국 보물의 위치를 완벽하게 알아내는 '계획(Plan)'을 짜는 것이 컴퓨터로 계산 가능한 일인가?" 하는 점입니다.

수학적으로 이 질문에 답하는 것을 '결정 가능성(Decidability)' 문제라고 합니다. 만약 답이 "예"라면 컴퓨터가 언젠가 답을 내놓겠지만, "아니오"라면 아무리 성능 좋은 슈퍼컴퓨터라도 영원히 답을 못 찾을 수도 있습니다.

😱 논문의 발견: "이 게임은 절대로 풀 수 없다!" (Undecidability)

이 논문의 저자 안토니스 아킬레오스(Antonis Achilleos)는 아주 놀라운 사실을 증명했습니다.

"탐정들이 하는 행동이 아주 단순하더라도(지식의 깊이가 1단계만 되어도), 보물을 찾는 계획이 존재하는지 알아내는 것은 수학적으로 불가능하다!"

이것을 어떻게 증명했을까요? 저자는 **'PCP(Post Correspondence Problem)'**라는, 이미 수학자들이 "풀 수 없다"고 결론 내린 아주 유명하고 복잡한 퍼즐을 이 탐정 게임으로 변신시켰습니다.

비유하자면: "세상에서 가장 풀기 어려운 퍼즐(PCP)을 탐정들의 보물찾기 게임으로 완벽하게 번역할 수 있다. 그런데 그 퍼즐은 풀 수 없다고 알려져 있다. 따라서, 탐정들의 보물찾기 계획을 짜는 것도 결국 그 퍼즐을 푸는 것과 같으므로, 절대로 풀 수 없다!"라고 말하는 것입니다.

💡 왜 이게 중요한가요?

이 결과는 우리에게 두 가지 중요한 메시지를 줍니다.

지식의 힘은 무섭다: 단순히 "무엇을 아느냐"에 따라 행동이 결정되는 시스템은, 아주 단순한 규칙만 있어도 시스템 전체가 예측 불가능할 정도로 복잡해질 수 있습니다.
설계의 가이드라인: 만약 우리가 인공지능(AI)에게 "상대방의 마음이나 지식을 읽고 계획을 세워라"라고 명령하고 싶다면, 아무 규칙이나 주어서는 안 됩니다. 이 논문은 **"너무 자유로운 지식 기반 행동을 허용하면 AI가 영원히 계산만 하다가 끝날 수 있으니, 규칙을 아주 정교하게 제한해야 한다"**는 경고를 주고 있는 것입니다.

📝 요약하자면...

이 논문은 **"상대방이 무엇을 아는지 고려해서 계획을 짜는 인공지능 시스템을 만들 때, 행동 규칙이 아주 단순하더라도 그 계획이 성공할지 실패할지 미리 알아내는 것은 수학적으로 불가능하다"**는 것을 증명한 아주 강력한 '불가능의 증명서'입니다.

1. 연구 문제 (Problem Statement)

본 논문은 인식적 계획(Epistemic Planning, EP) 분야의 핵심 문제인 **'계획 존재 문제(Plan Existence Problem)'**의 결정 가능성(Decidability)을 다룹니다.

인식적 계획이란? 에이전트들의 지식(Knowledge)이나 믿음(Belief)을 모델링하여, 주어진 초기 인식 상태(Kripke model)에서 목표(Goal, 논리식 형태)를 달성하기 위한 일련의 인식적 행동(Epistemic Actions) 시퀀스를 찾는 문제입니다.
기존 연구의 한계: 기존에는 행동의 전제 조건(Preconditions)의 모달 깊이(Modal Depth)가 깊거나, 사후 조건(Postconditions)이 존재할 때 이 문제가 결정 불가능(Undecidable)하다는 것이 알려져 있었습니다. 그러나 **"전제 조건의 모달 깊이가 최대 1이고, 사후 조건이 없는 경우"**에 대해서는 결정 가능 여부가 미해결 상태로 남아 있었습니다.

2. 주요 기여 (Key Contributions)

본 논문의 핵심 기여는 전제 조건의 모달 깊이가 1이고 사후 조건이 없는 매우 제한적인 상황에서도 계획 존재 문제가 결정 불가능함을 수학적으로 증명한 것입니다.

새로운 결정 불가능성 증명: 기존에 알려지지 않았던 경계 조건(Precondition depth $\le 1$ , No postconditions)에서의 결정 불가능성을 입증했습니다.
광범위한 적용 범위: 단일 에이전트(Single-agent)뿐만 아니라 다중 에이전트(Multi-agent) 환경, 그리고 다양한 모달 논리 체계(K, KTB, KT4 등)에서도 이 결과가 유효함을 보였습니다.

3. 연구 방법론 (Methodology)

저자는 **포스트의 대응 문제(Post's Correspondence Problem, PCP)**를 인식적 계획 문제로 환원(Reduction)하는 방식을 사용했습니다. PCP는 이미 결정 불가능함이 증명된 고전적인 문제입니다.

환원 전략 (Reduction Plan)

PCP의 인스턴스를 인식적 계획의 인스턴스로 변환하기 위해 계획을 두 단계로 구성합니다.

1단계: 블록 추가 (Stage 1 - Building):
- PCP의 각 블록( $a_i, b_i$ )을 인식적 상태(Kripke model)의 두 갈래 경로(Top sequence와 Bottom sequence)로 인코딩합니다.
- add_i라는 행동을 통해 PCP 블록을 하나씩 경로 끝에 추가하며, 이 과정에서 상태는 점점 길어집니다.
2단계: 검증 및 제거 (Stage 2 - Verification):
- nxt_stg 행동을 통해 1단계를 종료하고 2단계로 전환합니다.
- rmv_bt 행동을 통해 두 경로의 끝에서부터 기호(0 또는 1)를 하나씩 제거합니다.
- 만약 두 경로의 기호가 일치하면 계속 진행할 수 있지만, 일치하지 않으면 '실패 상태(Failed state)'로 빠지게 설계되었습니다.
목표 달성:
- 두 경로가 완전히 비워져서(Empty) 목표 논리식을 만족하면, 이는 PCP의 매치(Match)가 존재함을 의미합니다.

논리적 장치 (Technical Gadgets)

모달 깊이 1의 활용: 사후 조건이 없으므로, 행동을 통해 상태를 직접 수정할 수 없습니다. 대신, 연속적인 행동 적용을 통해 매우 긴 경로를 생성하고, 전제 조건이 '현재 상태에서 즉시 접근 가능한 세계'에만 의존하도록 설계하여 모달 깊이를 1로 유지했습니다.
다중 에이전트 및 프레임 조건 대응: 다중 에이전트 환경에서는 에이전트 간의 관계를 교차(Alternate)시켜 프레임의 제약(대칭성, 추이성 등)이 의도치 않은 연결을 만들지 않도록 '구분자(Separator, #)'와 복제된 상태들을 사용했습니다.

4. 연구 결과 (Results)

단일 에이전트 K 논리: 전제 조건의 모달 깊이가 1이고 사후 조건이 없을 때 계획 존재 문제는 결정 불가능합니다.
다중 에이전트: 에이전트의 수나 접근성 관계(Accessibility relation)의 제약에 상관없이 결정 불가능합니다.
특수 케이스 (결정 가능성):
- 에이전트가 부정적 자기 성찰(Negative Introspection, S5 논리 등) 능력을 갖춘 경우(즉, 자신이 모르는 것을 안다는 성질), 문제는 **결정 가능(Decidable)**하며 NP 범위 내에 있음을 보였습니다.

5. 연구의 의의 (Significance)

이론적 완성도: 인식적 계획의 복잡도를 결정하는 요소 중 '전제 조건의 깊이'와 '사후 조건의 유무' 사이의 경계를 명확히 규명함으로써, 이 분야의 결정 가능성 지도를 완성하는 데 기여했습니다.
설계 지침 제공: 인식적 계획 알고리즘을 설계할 때, 단순히 전제 조건을 단순화(모달 깊이 1)하는 것만으로는 계산 복잡도를 제어할 수 없음을 경고합니다. 대신, 에이전트의 논리적 특성(예: 부정적 자기 성찰)이나 행동의 분리 가능성(Separability) 등을 고려하는 것이 실질적인 결정 가능성을 확보하는 길임을 시사합니다.