AI heuristic sub problem, Learning

Subproblem

 

8 퍼즐 문제의 서브 문제로, 1 ~ 8까지 모두 고려하지 않고 1 ~ 4까지만 고려하는 문제로 축소시켜둔 모습입니다.

Sub problem 의 Path cost <= Original problem 의 Path cost 이므로 admissible 합니다. 따라서 이 또한 heuristic 으로 사용 가능합니다.

 

Pattern Database

거의 모든 경우의 subproblem state 의 cost 를 저장해두는 방식입니다. goal state 에서 시작하여 action을 무작위로 적용시켜 나가면서 DB화시킵니다.

 

여러 Sub problem 을 사용하는 것도 가능합니다.

예를 들어 1-2-3-4 문제와 5-6-7-8 문제로 쪼개어 두 개의 sub problem 으로 만들고, 두 휴리스틱 중 더 큰 값은 이용하여 정답을 찾아나가는 방식을 사용할 수도 있을 것입니다.

이 때 주의할 점은 두 휴리스틱의 h(n) 값을 단순 덧셈하여 이용하는 것은 안됩니다. 두 했을 때 admissibility 를 잃기 때문이며 덧셈을 이용하기 위해서는 각 sub problem 에 보정치를 주어야합니다.

예를 들면 1-2-3-4 문제에서는 1,2,3,4 번 타일이 움직인 횟수만 카운트하고, 5-6-7-8 문제에서는 5,6,7,8번 타일이 움직인 횟수만 카운트한다면 이는 admissible 할 것입니다.

 

Leraning heuristic from Experience

원본 문제를 많이 풀어봄으로서 적절한 Path cost 를 예측하는 함수 f를 학습시키는 원리입니다.

Pattern DB와 다른 점은

1. Pattern DB 는 Sub problem 을 쓴다.   Leraning 은 Complete problem 을 쓴다.

2. Pattern DB 는 실제 관측값을 그대로 저장하여 활용한다.   Learning 은 함수 f에 의해 생성된 예측값을 활용한다.

 

기존 패턴에 없던 stat에 대해서도 예측이 가능한것을 원하기 때문에 실제 데이터를 그냥 활용하지 않습니다.

 

Learning 에서는 서로 다른 state 여도 같은 결과를 내는 경우에 대응하기 위해 state 자체를 활용하는것보다는 state에서 feature 를 추출하여 feature에 대해서 예측을 하는 방법을 사용합니다.

feature 를 예로 들자면

• 잘못된 위치에 있는 tiles 의 수

• 인접한 타일의 수

그러한 함수 f는 출력으로 path cost 를 내놓게 됩니다.