선물이 어디 있는지 모를 때, 다음 행동을 어떻게 정할까요?

인식 계획은 세계에서 무엇이 참인지와 행위자가 무엇을 알고 믿는지를 함께 상태로 다룹니다. 목표도 물건의 위치처럼 세계의 사실일 수 있고, 한 학생이 열쇠 위치를 안다는 지식 상태일 수 있습니다.

행동은 물건을 옮기기만 하지 않습니다. 질문하기·살펴보기·알리기처럼 정보만 바꾸거나, 물리적 변화와 정보 변화를 함께 만들 수 있습니다. 논문은 이 결합을 자동 계획의 대상으로 삼습니다.

고전적 계획은 상태 집합 S, 행동 집합 A, 전이 함수 γ로 이루어진 전이 체계에서 출발합니다. 현재 상태에서 적용 가능한 행동을 차례로 실행해 목표 상태에 도달하는 행동열을 찾습니다.

상태를 명제들의 진리값으로 적으면 가능한 상태 수가 명제 수에 따라 지수적으로 늘 수 있습니다. STRIPS 같은 행동 스키마는 전제와 효과를 이용해 거대한 전이 체계를 더 짧게 표현합니다.

행위자가 정확한 현재 상태를 모르면 후보 상태들의 집합인 믿음 상태를 사용합니다. 관찰은 후보를 줄이고, 관찰하지 못하는 행동 결과는 여러 후보를 남길 수 있습니다.

같은 물리적 세계라도 행위자가 가진 정보가 다르면 다음에 안전하게 선택할 수 있는 행동이 달라집니다. 계획기는 실제 상태와 정보 상태를 구분해 추적해야 합니다.

두 우체국 중 한 곳에 선물이 있고 위치를 모를 때, 먼저 A로 갑니다. A에서 선물을 찾으면 끝나고, 찾지 못하면 B로 가야 합니다. 처음부터 고정한 행동열보다 관찰 결과에 따라 갈라지는 조건부 계획이 알맞습니다.

관찰은 실행 중 불확실성을 줄입니다. 계획 시점에 모든 사실을 모르더라도 각 관찰 결과에 대응하는 가지를 미리 준비할 수 있습니다.

실행 시 불확실성은 계획을 실행하는 행위자가 실제 세계를 모르는 경우입니다. 계획 시 불확실성은 계획을 만드는 쪽이 실제 세계를 모르더라도 실행자는 더 많은 정보를 가질 수 있는 경우까지 포함합니다.

정책은 어떤 정보 상태에서 어떤 행동을 할지 정합니다. 누가 무엇을 알고 있는지 명시하지 않으면, 계획기가 가진 무지와 실행자의 무지를 섞어 잘못된 행동을 허용할 수 있습니다.

인식 모형은 가능한 세계들과 각 세계의 사실, 그리고 행위자마다 구별할 수 없는 세계를 잇는 관계로 구성됩니다. 한 행위자가 연결된 모든 세계에서 A가 참이면 그 행위자는 A를 안다고 표현합니다.

관계는 물리적 이동 경로가 아니라 정보의 구별 가능성을 나타냅니다. 여러 행위자가 있으면 같은 세계 집합 위에 서로 다른 관계가 겹칩니다.

이 예의 가능 세계는 우주 전체가 아니라 “선물이 A에 있다”와 “선물이 B에 있다”라는 두 후보 상황입니다. 둘을 구별할 정보가 없는 학생은 두 상황을 모두 고려합니다. 학생이 “선물은 A에 있다”고 안다고 말하려면, 자신이 남겨 둔 모든 후보에서 그 문장이 참이어야 합니다.

사건 모형은 가능한 사건, 각 사건의 사전조건, 행위자들이 구별하지 못하는 사건 관계를 담습니다. “직원이 예라고 답함”과 “아니라고 답함”은 실제 세계에 따라 적용 가능성이 달라집니다.

행위자가 답을 들었는지, 다른 행위자가 그 답을 들었는지에 따라 사건을 구별하는 관계도 달라집니다. 그래서 하나의 행동이 사실과 여러 사람의 지식을 서로 다르게 갱신할 수 있습니다.

w를 “선물이 A에 있는 상황”, e를 “A에 있다는 답을 들은 사건”이라고 합시다. 행동 뒤의 상태 (w,e)는 이 상황에서 이 답을 들었다는 하나의 쌍입니다. 쉼표 앞뒤를 각각 다른 상태로 나누지 않습니다.

정직하게 답하는 직원에게 A에 있는지 물었다면, A에 있는 상황과 “없다”는 답의 조합은 제외됩니다. 가능한 조합만 남기고, 학생이 어느 답을 들었는지에 따라 어떤 상태를 구별할 수 있는지 다시 정합니다. 이 계산을 곱 갱신이라고 합니다.

논문은 초기 지적 인식 모형, 유한한 행동 집합, 목표식으로 계획 과제를 정의합니다. 행동을 차례로 적용한 뒤 목표가 모든 관련 결과에서 성립하도록 계획을 찾습니다.

초기 모형이 실제 세계를 하나 가리키는 지적 모형인지, 가능한 여러 세계만 주어진 비지적 모형인지에 따라 실행 의미가 달라집니다. 글은 원문의 지적 모형 정의를 기준으로 설명합니다.

순차 계획은 미리 정한 행동열을 그대로 실행합니다. 조건부 계획이나 정책은 실행 중 도달한 정보 상태에 따라 다음 행동을 고릅니다.

정책은 구별할 수 없는 두 상태에 서로 다른 행동을 지정해서는 안 됩니다. 행위자가 어느 상태인지 알 수 없는데 다른 선택을 요구하면 실제로 실행할 수 없는 계획이 됩니다.

강한 정책은 정책을 따르는 모든 가능한 최대 실행이 유한하게 끝나고 목표에 도달하도록 요구합니다. 어느 한 운 좋은 실행만 성공하는 정책은 강한 정책이 아닙니다.

관찰 결과나 다른 행위자의 반응이 여러 갈래일 때 각 갈래를 모두 검사해야 합니다. 반복이 끝없이 이어지는 경우도 성공으로 셀 수 없습니다.

공개 발표는 모든 행위자가 같은 내용을 듣고 그 사실도 서로 압니다. 사적 질문이나 몰래 보기에서는 일부 행위자만 정보를 얻고, 다른 사람은 어떤 사건이 일어났는지 모를 수 있습니다.

사적 행동은 거짓 믿음이나 비대칭 정보를 만들 수 있어 단순한 동치 관계만으로 표현하기 어려운 경우가 있습니다. 논문은 더 일반적인 인식 모형이 필요할 수 있음을 설명합니다.

다중 행위자 계획에서는 각 행위자가 자기 정보만으로 행동해야 합니다. 공개된 행동과 관찰 구조가 충분하면 직접 메시지를 보내지 않아도 상대가 무엇을 알게 되었는지를 추론해 역할을 나눌 수 있습니다.

이런 암묵적 조정은 누가 어떤 행동을 관찰하는지에 의존합니다. 행동의 공개 범위를 잘못 가정하면 실제로는 실행할 수 없는 공동 계획이 됩니다.

아닙니다. 논문은 일반적인 인식 계획의 계획 존재 문제가 매우 제한된 조건에서도 결정불가능해질 수 있음을 정리합니다. 두 행위자, 공통지식 연산자 없음, 명제 효과 없음이라는 조건에서도 일반 문제는 끝나는 판정 절차를 갖지 않습니다.

반면 전제조건의 형태와 행동 종류를 제한하면 결정 가능한 조각이 생깁니다. 명제적 사전조건과 후조건 없음에서는 PSPACE-완전 결과가 있고, 공개·사적 발표의 특정 조각은 NP-완전으로 정리됩니다.

가능합니다. 가능 세계와 지식 관계로 현재의 무지를 표현하고, 사건 모형과 곱 갱신으로 행동 뒤의 정보 변화를 계산하며, 균일하고 모든 실행에서 성공하는 정책을 찾습니다.

다만 일반 문제 전체가 언제나 계산 가능한 것은 아닙니다. 행위자 수, 사전조건과 후조건의 언어, 공개 범위, 목표와 정책의 종류에 따라 결정가능성과 복잡도가 달라집니다. 실제 적용에서는 이 범위를 먼저 고정해야 합니다.