Wumpus World

 Wumpus World는 인공지능 중에서도 문제 해결(Problem Solving; PS) 분야의 문제로써 매우 유명한 예제이다. Logical Agents를 사용 하여 해결하는 문제이며, Logical Agent는 환경에 대한 정보와 판단으로 구성되어있다.
로봇의 이동, 환경의 변화와 같은 입력 값에 따라 Logical Agent의 환경에 대한 정보, 판단의 내용이 바뀌게 되며 이에 따라 다음 행동을 결정한다.

  Wumpus는 괴물의 이름이며, Wumpus가 살고 있는 동굴을 가리켜 Wumpus World라고 한다. 동굴의 환경은 4가지가 있다.

-    평범한 바닥 (Floor)
-    괴물 (Wumpus)
-    구덩이(Pit)
-    보물(Gold)

  이 문제의 목적은 출제자에 따라 다르지만 가장 큰 목적은 구덩이와 괴물을 피해 보물이 있는 곳까지 도달하는 것이다. 문제에 따라 보물을 획득하고 괴물의 위치를 파악하여 괴물을 죽이라는 과제가 추가되기도 한다.
  이 동굴의 특징은 여러 개의 방으로 이루어져 있으며, 동굴 전체는 칠흑같이 어두워서 탐험가(Explorer)가 들고 있는 횃불로는 현재 위치하고 있는 방의 정보 밖에 알 수 없다. 또한 탐험가는 현재 있는 위치에서 전, 후, 좌, 우 네 방향으로 움직일 수 있으며, 가지고 있는 활을 사용하여 괴물을 죽일 수 있다.

  하지만 탐험가는 자신이 있는 곳 밖에 볼 수 없기 때문에, 안전한 탐험을 위해서는 동굴의 상태(state)를 알아야 한다. 상태는 총 3가지가 있으며 다음과 같다.

-    악취(Stench): 괴물의 전, 후, 좌, 우 4방향은 악취가 풍기게 된다.
-    산들바람(Breeze): 구덩이가 있는 방의 전, 후, 좌, 우 4방향은 구덩이로부터 올라오는 산들 바람이 느껴진다.
-    반짝거림(Glitter): 보물이 있는 방에 들어서면 방 어딘가에 있는 보물의 반짝거림을 느낄 수 있다.

  Wumpus World의 핵심은 현재 위치한 곳의 상태를 보고 환경에 대한 정보를 갱신해가면서 안전한 길을 선택하여 탐험을 계속해 나가는 것이다.
  지금부터는 Wumpus World의 구현에 대해 알아보자.


구현

  우선 지금까지의 프로그래밍 언어에서 Wumpus World를 구현하기 위한 idea들을 알아보고 MSRDS를 사용한 환경의 구축을 해보도록 한다.
  Map으로는 그림 3에 나와있는 Basic case를 사용하도록 한다. 그리고 문제 해결을 위해 필요한 Assumption으로는 구덩이(Pit)과 괴물(Wumpus)는 같은 방에 있을 수 없고 탐험가(Explorer)의 출발 위치(Start)와, 그 출발 위치에서 전, 후, 좌, 우의 방은 안전이 보장되어야 한다는 것이다. (즉 Gold이거나 Floor 이어야 한다.)


Wumpus World in ordinary programming language

-    Knowledge base

  앞서 말한 Logical Agent가 판단한 주변 환경 같이 행동을 결정하기 위한 기반이 되는 정보를 Knowledge base라고 하며, 프로그램의 어딘가에 항상 저장되어 있어야 한다. Wumpus World Problem에서는 배열로 그 정보를 저장하며 새로운 정보를 감지 할 때 마다 Update해 주도록 한다.

-    Logical Reasoning

  Logical 프로그래밍에서 사용하는 방법으로 두 개 이상의 정보를 사용하여 삼단논법, 모순 등의 Axiom을 사용하여 부정확하게 정의된 정보를 추론 하는 과정이다.
예를 들어 A, B, C라는 세 사람이 있고
Family(A,B)  A는 B의 가족이다
Family(B,C)  B는 C의 가족이다.
라는 두 개의 정보를 가지고 있다면
추론을 통해 Family(A,C)  A는 C의 가족이다. 라는 정보를 얻어 낼 수 있다.