Knowledge, The Wumpus World, Logical Reasoning

Knowledge

- 3,4 장에서 사용한 지식은 domain-specific 이라는 한계를 가지고 있었다. (n-puzzle문제 등)

- 7장부터는, Logic 을 지식을 표현하는 방법으로 사용할 것이다.

 

 

Knowledge-Based Agents

- Knowldege base (KB) 

•  지식표현언어로 구성된 sentence 들의 집합

- Inference

• 어떤 문장들로부터 새로운 문장을 추론해낸다.
• 
• tell과 ask 는 다양한 문제에서 공통으로 구현되는 함수이다.

- declarative approach

• TELL, ASK 는 공통으로 구현된 것을 사용할 수 있다.
• LISP, PASCAL 에서 사용된다.
• 이와 상반되는 접근법을 procedural approach 라고 하며, C, JAVA 등에서 사용된다.

 

 

The Wumpus World

- agent 는 내가 현재 위치한 state 만 알 수 있고, 괴물과 함정이 어디 있는지는 알지 못한다.

- 이때 hint 가 주어지는데, 함정의 주변에는 breeze 가 존재하며, 괴물의 주변에는 stench 가 존재한다.

- 사용자는 괴물과 함정을 피해서 gold 를 얻고 다시 나가는 게임이다.

 

 

The Task Environment

- wampus 게임의 task environment 를 정의해보자.

- Performance measure

- Environment

 

- Actuators

 

- Sensors

 

 

Main Challenges of the Wumpus World

- task environtment 는 discrete, static, single-agent, sequential, partially observable 하다.

- transition model 이 incomplete 하다. 즉, agent 가 악취, 바람 등으로 추론할 수는 있지만 가보기 전까지는 상태를 완벽하게 알지 못한다.

- 따라서 player 는 logical reasoning 이 필요하다.

 

 

An Example Logical Reasoning

- 처음 게임을 시작한 initial state 는 항상 안전하다. 또한 현재 상태에서 악취가 나거나 바람이 불지 않으므로 1.2, 2.1 는 안전함을 알 수 있다.

 

- 2.1 칸으로 이동한 후 바람이 부는 것을 감지하였다. 바람은 1.1 을 제외한 2.2 나 3.1 에서 불고 있을 것이다. 2.2 나 3.1 은 안전하지 않으므로 다시 1.2 칸으로 가야한다.

 

- 1.2 칸으로 이동한 후 악취를 감지하였다. 따라서 1.3 이나 2.2 둘 중에 괴물이 있다는 것인데, 2.1 에서는 악취가 나지 않았으므로 1.3 에 무조건 괴물이 있음을 추론할 수 있다. 또한, 현재 1.2에 바람이 불지 않으므로 2.2 에 함정이 없음을 확신할 수 있다. 따라서 2.2와 3.1 중 함정은 3.1에 존재함을 추론할 수 있다. 

- 이러한 과정들을 Logical Reasoning 이라고 한다.

- agent 는 지금까지 주어진 정보들(sentence)로 결론(sentence)을 이끌어 낼 수 있다.

-> sentence 에서 sentence 를 만들어 낼 수 있다. 만약, 주어진 sentence(정보) 가 맞다면, 이끌어 낸 sentence(결론)도 맞을 것이다.

 

 

 

Logic

- Syntax of logic : 주어진 sentence 가 문법적으로 맞는지 확인하는 규칙

- Semantics of logic : 주어진 sentence 가 특정한 world(혹은 model) 에 대해서 참인지 거짓인지 여부

- 만약 sentence a가 model m에서 참이라면, 

• m satisfies a
• m is a model of a 

- a를 만족시키는 model 집합 : M(a)

 

 

Logical Entailment

- 문장은 다른 문장으로부터 논리적으로 따라나온다. 

• a |= B
• -> a 가 참이고 B가 참이라면, a entails B

- Formal definition of the logical entailment

• a |= B 이라는 것은, M(a) 가 M(B) 의 부분집합 이라는 뜻이다.

- In Mathematics

-> M(x=0) 은 M(xy=0) 의 부분집합이다.

-> 역인 xy = 0 entails x = 0 은 성립하지 않는다. (x는 0일 수도 있고 y가 0일 수도 있음)

 

 

Logical Entailment in the Wumpus World

- 현재 agent 는 2.1 에서 어디에 함정이 있는지를 궁금해 하는 상황이다.

- Knowledge base (KB) 

• [1,1] 에는 아무것도 없다.
• [2,1] 에는 바람이 분다. (percept 로 부터 알게된 것)
• wumpus world 의 규칙들로부터 나온 agent 지식

- a1 : [1,2] 에는 함정이 없다.

- KB |= a1 가 참인가?

 

- a2 : [2,2] 에는 함정이 없다.

- KB |= a2 가 참인가?

 

 

- [1,2], [2,2], [3,3] 에 국한하여 model 이라고 생각하자.

-> 총 8개의 모델이 존재할 수 있다.

 

- 그러나 knowledge base 를 참으로 하는 모델은 3개이다.

- [1,1] 에서 바람이 불지 않았었기 때문에 1,2 에는 함정이 존재할 수 없기 때문이다.

- 한편 a1 을 만족하는 모델은 4개로, M(KB) 는 M(a1) 에 포함된다. 따라서 KB |= a1 이 참임이 증명된다. 즉, [1,2] 는 함정이 없다는 것이 참이된다.

 

- 한편, a2 를 만족하는 모델은 4개이고, M(KB) 는 M(a1) 에 포함되지 않는다. 따라서 KB |= a2 는 참이라고 할 수 없다. (entail 하지 않는다고 거짓이라고 할 수 없다. 알 수 없는 것이다.)