[인공지능] Propositional Logic - 3

EXAMPLE 2

문제 :

• 문장 α=(A∧B)∨(C∧¬D) 라고 하자
• α가 true인 모델은 몇개가 있는가? (In how many models is a true?)

진리값 평가 과정:

 

각 기호 A,B,C,D는 독립적으로 참 또는 거짓이 될 수 있으므로, 총 2^4=16개의 가능한 모델이 있다.

이 16개의 모델 중에서 문장 α가 참인 모델의 수를 센다.

1. (A∧B)가 참인 모델: A와 B가 모두 참인 경우
   • A=true,B=true,C=true,D=true
   • A=true,B=true,C=true,D=false
   • A=true,B=true,C=false,D=true
   • A=true,B=true,C=false,D=false
2. (C∧¬D)가 참인 모델: C가 참이고 D가 거짓인 경우
   • A=true,B=true,C=true,D=false (이미 위에서 세어짐)
   • A=true,B=false,C=true,D=false
   • A=false,B=true,C=true,D=false
   • A=false,B=false,C=true,D=false

따라서, 문장 α가 참인 모델은 총 7개이다.

 

The Plan

• Tell the logical agent what we know about PacPhysics : logical agent에게 PacPhysics에 대한 정보 전달
  • "PacPhysics"는 Pac-Man 게임의 물리 엔진 또는 규칙을 의미한다.
  • 에이전트에게 PacPhysics에 대한 정보를 전달함으로써, 에이전트는 게임 환경의 기본 규칙과 원칙을 이해한다.
• Ask it what actions have to be true for the goal to be achieved : logical agent에게 목표 달성을 위해 어떤 행동이 참이어야 하는지에 대한 액션 질의
  • 에이전트에게 목표를 달성하기 위해 어떤 액션이 수행되어야 하는지 물어본다.

Example : Partially Observable Pacman

이 예제에서는 "Partially Observable Pacman"이라는 상황을 다룬다. 여기서 Pacman은 맵을 알고 있지만, 북쪽(N), 남쪽(S), 동쪽(E), 서쪽(W)으로 벽이나 틈(gap)만을 인식할 수 있다. 

Formulation : 이 상황에서 우리에게 필요한 변수는 무엇인가?

1. Wall Locations (벽 위치)

• 각 위치에 대한 벽의 존재 여부를 나타내는 변수이다.
• 예: `Wall_0,0`은 [0,0] 위치에 벽이 있다는 것을 나타낸다. `Wall_0,1`은 [0,1] 위치에 벽이 있다는 것을 나타낸니다.
• 총 N개의 위치에 대해 N개의 symbol이 필요하다.

2. Percepts (인식)

• Pacman이 특정 방향으로 벽이나 틈을 인식하는 것을 나타내는 변수이다.
• 예: `Blocked_W`는 Pacman이 서쪽으로 벽에 막혀 있다는 것을 나타낸다.(이렇게 나타내면 안된다) `Blocked_W_0`은 시간 0에서 서쪽으로 벽에 막혀 있다는 것을 나타낸다.
• 총 T개의 시간 단계에 대해 동서남북NSEW 4개의 방향이 있으니 4T개의 symbol이 필요하다.

3. Actions (행동)

• Pacman이 특정 시간에 특정 방향으로 움직이는 것을 나타내는 변수이다.
• 예: `W_0`은 시간 0에 Pacman이 서쪽으로 움직인다는 것을 나타냅니다.
• 총 T개의 시간 단계에 대해 동서남북NSEW 4개의 방향이 있으니 4T개의 심볼이 필요합니다.

4. Pacman’s Location (Pacman의 위치):

• Pacman이 특정 시간에 특정 위치에 있는 것을 나타내는 변수이다.
• 예: `At_0,0_0`은 시간 0에 Pacman이 [0,0] 위치에 있다는 것을 나타낸다. `At_0,1_0`은 시간 0에 Pacman이 [0,1] 위치에 있다는 것을 나타낸다.
• 총 N개의 위치와 T 시간단계가 존재하니 NT개의 심볼이 필요하다

How Many Possible Worlds?

Partially Observable Pacman에서 가능한 세계(possible worlds)의 수를 계산하는 방법

변수의 수 계산:

• N 위치(location)와 T 시간(time) 단계가 있을 때, 총 변수의 수는 N+4T+4T+NT = O(NT) 이다.
• 이는 위치 변수 N, 퍼셉트(percept) 변수 4T, 액션(action) 변수 4T, 그리고 팩맨의 각 시간 단계와 위치에 대한 변수 NT의 합이다.

 

가능한 세계의 수:

• 각 변수는 참 또는 거짓의 값을 가질 수 있으므로, 가능한 세계의 수는 2^(N+4T+4T+NT) 또는 O(2^(NT))이다.
• 예시:
  • N=200 위치와 T=400 시간 단계가 있다면, 가능한 세계의 수는 대략 10^(24000) 이다.
     

Each world is a complete “history” : 각 세계는 완전한 “이력”(history)

• 각 가능한 세계는 시간이 지남에 따라 각 위치의 상태의 완전한 이력( history)을 나타낸다. 

Pacman’s Knowledge Base: Map

Pacman의 지식 베이스(Knowledge Base)에 중 Map에 대한 설명이다.

1. Pacman Knows Where the Walls Are (Pacman은 벽의 위치를 알고 있다)
   • Pacman은 특정 위치에 벽이 있는지 알고 있다. 각 Wall_x,y 변수는 [x,y] 위치에 벽이 있다는 사실을 나타낸다.
   • 예:  Wall_0,0 ∧  Wall_0,1 ∧  Wall_0,2 ∧  Wall_0,3 ∧  Wall_0,4 ∧  Wall_1,4 ∧  …
   • Wall_0,0은 [0,0] 위치에 벽이 있다는 것을 나타낸다. 이와 같이, Wall_0,1, Wall_0,2, Wall_0,3, Wall_0,4, Wall_1,4 등은 각각 해당 위치에 벽이 있다는 것을 나타낸다.
2. Pacman Knows Where the Walls Aren’t (Pacman이 벽이 없는 위치를 알고 있다):
   • Pacman은 특정 위치에 벽이 없다는 것도 알고 있다. ¬Wall_x,y는 [x,y] 위치에 벽이 없다는 사실을 나타낸다
   • 예:  ¬ Wall_1,1 ∧ ¬ Wall_1,2 ∧ ¬ Wall_1,3 ∧ ¬ Wall_2,1 ∧ ¬ Wall_2,2 ∧   …
   • ¬Wall_1,1은 [1,1] 위치에 벽이 없다는 것을 나타낸다. 이와 같이, ¬Wall_1,2, ¬Wall_1,3, ¬Wall_2,1, ¬Wall_2,2 등은 각각 해당 위치에 벽이 없다는 것을 나타낸다.

Pacman’s Knowledge Base: Initial State

Pacman의 지식 베이스(Knowledge Base)에 중 초기 상태에 대한 설명이다.

1. Pacman doesn’t know where he is : Pacman의 초기 위치는 알려져 있지 않다
   • Pacman은 게임이 시작될 때 본인이 어디에 있는지 정확한 위치를 모른다.
2. But he knows he’s somewhere! : 그러나 pacman은 어딘가에는 위치하고 있다는 것은 안다
   • Pacman은 맵의 특정 위치 중 하나에 있어야 한다. 이를 표현하기 위해 논리적으로 각 가능한 시작 위치에 대한 명제를 OR 연산으로 연결한다.
   • 예시) At_1,1_0 ∨ At_1,2_0 ∨ At_1,3_0 ∨ At_2,1_0 ∨ …
   • 이는 Pacman이 (1,1) 또는 (1,2) 또는 (1,3) 또는 (2,1) 등의 위치 중 하나에 있음을 나타낸다. 여기서 _0은 시간 단계 T가 0, 즉 게임의 시작을 나타낸다.

Pacman’s Knowledge Base: Sensor Model

이 부분은 Pacman의 지식 베이스에서 센서 모델에 대한 정보를 설명.

센서 모델은 Pacman의 지각(Percepts 즉, 센서 입력)이 어떻게 발생(arise)하는지에 대한 상태 facts(State facts).

<Percept variable at t> ⇔ <some condition on world at t>

• 각 지각 변수는 특정 시간 t에서 세계의 특정 상태와 연관된다. 

 

Pacman이 시간 t에서 서쪽에 벽을 감지한다면 , 팩맨은 x,y에  위치하고 벽은 x-1, y 에 위치한다.

• Blocked_W_0 ⇔  ((At_1,1_0 ∧  Wall_0,1) v (At_1,2_0 ∧  Wall_0,2) v (At_1,3_0 ∧  Wall_0,3) v …. )
• N개의 location 모두에서 팩맨의 현재 위치를 전부 가정하고 그 상태에서 Blocked_W_0를 고려하면 각각에 At 위치에서 Wall 위치를 계산해 and 연산자를 통해 묶어줘야한다.
• 4T sentences, each of size O(N) : NSEW 4개의 방향으로 T개의 시간 단계가 존재하기 때문에 문장(sentence)는 총 4T개 이며 각각의 문장당 N개의 location이 있기 때문에 O(N)의 크기를 가진다.
• these are valid for any map : 이 모델은 어떤 맵(any Map)에도 적용될 수 있습니다. 

Pacman’s Knowledge Base: Transition Model

전이 모델은 각 상태 변수(state variable)가 각 시간 단계에서 어떻게 값을 얻는지를 설명한다.

각 Time 에서 상태 변수(state varaible)의 값(value)을 어떻게 결정하는가?

 

우리는 여기서 예시로 At_3,3_17과 같은 위치 변수(location variable)를 고려할 것이다. (이 변수는 시간 17에서 Pacman이 (3,3) 위치에 있는지를 나타낸다.)

 

후속 상태 공리(Successor-State Axiom)

상태 변수 X는 후속 상태 공리( successor-state axiom )에 따라 값을 얻는다.

• X_t​⇔[X_(t−1)​∧¬(some action_(t−1)​ made it false)]∨[¬X_(t−1)​∧(some action_(t−1)​ made it true)]
• 이 공리는 X_t가 참이 될 조건을 설명한다. X_t는 X_(t-1)이 참이고 특정 액션이 X_t를 거짓으로 만들지 않았을 때, 또는 X_(t-1)이 거짓이고 특정 액션이 X_t를 참으로 만들었을 때 참이다.

Pacman 위치

At_3,3_17의 값은 다음과 같이 결정된다.

• At_3,3_17 ​​⇔[ At_3,3_16 ​​∧¬((¬Wall_3,4​∧N_16​)∨(¬Wall_4,3​∧E_16​)∨…)]∨[¬ At_3,3_16 ∧((At_3,2_16​​∧¬Wall_3,3​∧N_16​)∨(At_2,3_16​​∧¬Wall_3,3​∧E_16​)∨…)]
• 이 식은 At_3,3_17이 참이 될 조건을 설명한다. At_3,3_16이 참이고 특정 액션이 At_3,3_17를 거짓으로 만들지 않았거나, At_3,3_16이 거짓이고 특정 액션이 At_3,3_17를 참으로 만들었을 때 At_3,3_17는 참입니다.
• 이건 좀 더 분석적으로 다가가보자!

How Many Sentences?

지식 베이스(KB)에 필요한 문장의 수와 이에 관련된 고려 사항에 대해 설명한다.

 

지식 베이스(KB)의 대부분은 O(NT) 전이 모델 문장에 의해 차지(occupied)된다.

• 각 문장은 대략 10줄의 텍스트에 해당한다.
• 예를 들어, N=200, T=400이라면, 이는 대략 800,000줄의 텍스트 또는 20,000페이지에 해당한다.

이러한 많은 수의 문장이 필요한 이유는 명제 논리가 제한된 표현력을 가지고 있기 때문이다. 명제 논리로 복잡한 상황이나 전이를 표현하려면 많은 수의 문장이 필요하다.

 

실제로 우리가 직접 20,000페이지의 논리 문장을 작성하는 것은 아니다. 대신, 코드를 사용하여 이러한 문장을 모두 생성할 것이다. 이는 자동화된 방식으로 지식 베이스를 구축하는 방법을 의미한다.

 

일차 논리에서는 O(1) 전이 모델 문장만 필요하다. 이는 일차 논리가 명제 논리보다 더 풍부한 표현력을 가지고 있어, 동일한 정보나 전이를 표현하는 데 더 적은 수의 문장이 필요하다는 것을 의미한다.

 

상태 공간 탐색( State-space search )에서는 원자 상태( atomic states )를 사용한다. 이 경우, 전이 모델 표현을 어떻게 작게 유지할 수 있을까? => 알아보기

Some Reasoning Tasks

1. Localization with a Map and Local Sensing
   • 주어진 초기 지식 베이스( initial KB )와 일련의 지각과 행동( percepts and actions )을 기반으로 현재 위치를 파악(Localization)한다.
   • Given an initial KB, plus a sequence of percepts and actions, where am I?
2. Mapping with a Location Sensor:
   • 초기 지식 베이스(initial KB) 와 일련의 지각과 행동(percepts and actions) 을 기반으로 지도를 생성(Mapping)한다.
   • Given an initial KB, plus a sequence of percepts and actions, what is the map?
3. Simultaneous Localization and Mapping (SLAM):
   • 주어진 정보를 기반으로 현재 위치와 지도를 동시에 파악(Localization and Mapping)한다.
   • Given an initial KB , plus a sequence of percepts and actions, where am I and what is the map?
4. Planning:
   • 목표에 도달하기 위한 행동 시퀀스를 찾는다.
   • Given an initial KB , plus a sequence of percepts and actions, what action sequence is guaranteed to reach the goal?

ALL OF THESE USE THE SAME KB AND THE SAME ALGORITHM!!

위의 모든 추론 작업은 동일한 지식 베이스와 알고리즘을 사용한다.