CS188 Introduction to Artificial Intelligence – (1-3) Search

Posted on by

이 문서는 Berkely University의 CS188 Introduction to Artificial Intelligence의 강의자료를 번역 및 정리한 것입니다. 본 자료는 오류 또는 오역을 포함할 수 있으며 보다 정확한 내용은 원문 출처를 참조하시기 바랍니다.

Informed Search

Uniform Search는 complete하고 optimal하지만 탐색 과정에서 모든 방향으로 노드를 확장하기 때문에 느리다. 만약 탐색에서 집중해야하는 부분을 알 수 있다면, 성능을 향상시키고 목표에 더 빠르게 도달할 수 있다. 이것이 informed search의 초점이다.

Heuristics

휴리스틱(Heuristics)은 목표 상태까지의 거리를 추산하게 하는 추진력이다. 휴리스틱 함수는 상태를 입력으로 받아 상응하는 추정을 출력한다. 휴리스틱 함수는 해결하고자하는 탐색 문제에 한정된다. 그런 이유로 우리는 아래에서 다룰 A* 탐색에서 휴리스틱 함수가 목표까지의 남은 거리의 하한선이 되길 원하고, 휴리스틱은 일반적으로 relaxed problem (기존 문제의 제약 조건들이 제거된 문제)의 해답이라는 것을 볼 것이다.

Pacman으로 돌아가서 앞서 기술했던 경로 문제를 생각해보자. 이 문제를 풀기 위해 공통적으로 쓰이는 휴리스틱은 맨해튼 거리 (Manhattan distance)로 두 점 (x1, y1), (x2, y2)가 있을 때 |x1 – x2| + |y1 – y2|로 정의된다.

위 그림은 맨해튼 거리로 풀 수 있는 완화된 문제를 보여준다. Pacman이 미로의 가장 오른쪽 아래에 가려고 한다고 가정하자. 맨해튼 거리는 미로에 벽이 없을 때 Pacman의 현재 위치에서 목표 위치까지의 이동 거리와 같다. 이 거리는 완화된 탐색 문제의 정확한 답이다. 그리고 이에 상응하는 것은 실제 탐색 문제의 추산된 목표 거리다.

휴리스틱으로 인해서 에이전트가 Action을 선택할 때 목표에 더 근접할 것이라 추산되는 상태를 선호할 수 있게하는 로직을 쉽게 구현할 수 있게 되었다. 이 선호 개념은 매우 강력하며 아래의 두 탐색 알고리즘에 의해 활용된다. 바로 Greedy와 A* 알고리즘이다.

Greedy Search

최소 휴리스틱 value를 가지는 노드(목표에서 가장 가까운 상태에 상응한다)를 Fringe에서 선택하는 탐색 전략이다.

Greedy 탐색은 UCS와 우선 순위 큐 Fringe에서 UCS와 동일하게 동작한다. 차이점은 UCS가 backward cost(경로상의 모든 가중치의 합)을 쓰는데 반해, greedy는 추산된 forward cost를 휴리스틱 value의 형태로 사용한다는 점이다.

Greedy 탐색은 Heuristic 함수가 제대로 선택되지 않았을 때, 목표 상태를 찾거나 Optimal인 목표 상태를 찾는데 실패할 수 있다. 일반적으로 시나리오에 따라서 예측 불가능하게 움직여 곧장 정답으로 직진할 수도 있지만 DFS처럼 움직이면서 모든 잘못된 영역들을 탐색할 수도 있다.

A* Search

A* (A star) 탐색은 Fringe에서 가장 적은 estimated total cost를 다음 확장을 위해 선택하는 전략이다. total cost는 시작 지점으로부터 목표 지점까지의 전체 비용을 말한다.

Greedy 탐색이나 UCS와 같이 A* 탐색 또한 우선 순위 큐를 Fringe로 사용한다. 앞선 두 방법과의 차이는 노드에 우선 순위를 부여하는 방식인데, total backward cost (시작 점으로부터 현재 노드까지의 비용) + estimated forward cost (현재 노드로부터 목표까지 추산되는 heuristic cost)를 기준으로 greedy와 동일하게 동작한다.

A* search는 적절한 heuristic이 주어졌을 때 complete하며 optimal하다. A*는 앞서 다룬 탐색 전략들의 장점들을 모두 가지고 있다. 일반적으로 greedy의 optimal과 UCS의 complete의 속성을 모두 갖는다.

Admissibility and Consistency

지금까지 우리는 heuristic의 개념과 greedy와 A* search의 적용 사례를 살펴보았다. 여기에선 좋은 휴리스틱(good heuristic)이란 무엇인지 살펴본다. 그 전에 UCS, greedy, A*에서 우선순위 큐의 노드 순서를 결정하는 함수를 아래의 정의들로 재정의해보자.

g(n)

UCS에 의해 계산된 total backward cost (시작 노드로부터 현재 노드까지의 비용)

h(n)

greedy에서 쓰이는 휴리스틱 함수 또는 estimated forward cost (현재 노드에서 목표 노드까지의 추정된 비용)

f(n)

estimated total cost (시작 노드로부터 현재 노드를 거쳐 목표 노드까지의 추정 비용)을 표시하는 함수. f(n) = g(n) + h(n)

좋은 휴리스틱의 구성요건을 묻기에 앞서 A* 탐색이 Heuristic 함수에 관계없이 항상 completeness와 optimality를 만족하는지 살펴보자. 아주 간단한 반례로 이 명제가 거짓이라는 것을 보일 수 있다.

h(n) = 1 – g(n)이라고 정의하면 f(n) = g(n) + 1 – g(n) = 1이다. 이렇게 되면 우선 순위 큐의 모든 노드들은 같은 값을 가지게 되며, 결과적으로 먼저 들어온 순서로 나오게 된다. 따라서 간선의 가중치를 고려하지 않는 BFS와 같이 동작하게 된다. 간선의 가중치를 고려하지 않는 BFS가 optimal하지 않다는 것은 앞서 살펴보았으므로 명제가 거짓임을 증명하였다.

A* 탐색의 optimality를 위해 요구되는 조건은 admissibility다. Admissibility 제약 조건이란 admissible한 휴리스틱 함수를 통해 추산된 값은 음수일수도 없으며, 실제 값보다 overestimate 하지 않는다는 말이다.

h*(n)을 주어진 노드 n에 대한 실제 forward cost라고 할 때, 모든 노드에 대해서 0 <= h(n) <= h*(n)을 만족해야한다.

[Theorem]

주어진 탐색 문제에 대해 휴리스틱 함수 h가 admissibility 제약 조건을 만족한다면, A* 트리 탐색은 optimal solution을 반환한다.

증명
주어진 탐색 문제에 대해 두 개의 가능한 목표 상태가 탐색 트리 내에 존재한다고 가정하자. 각각 optimal한 A와 그렇지 않은 B다. 시작 상태에서 A에 도달할 수 있으므로, 그 중간 상태인 ancestor 노드 n은 Fringe에 반드시 존재한다. 아래의 3가지 서술에 따라 이 노드 n이 B보다 이전에 Fringe에서 선택된다는 것을 보일 수 있다.

1. A와 B는 둘 다 목표 상태이며, A는 optimal이고 B는 아니기 때문에 g(A) < g(B)이다.

2. h(A) = h(B) = 0이다. admissible한 휴리스틱의 정의에 따르면 h(n)은 실제 forward cost보다 클 수가 없다. 목표 상태에서는 forward cost가 당연히 0이기 때문에 0 <= h(n) <= h*(n) = 0이므로 h(n) = 0이다. A와 B는 둘 다 목표 상태이므로 h(A) = h(B) = 0이다.

3. 노드 n에 대해서 g(n) + h*(n)은 시작 노드로부터 A에 도달하는 비용 f(A)이자 g(A)와도 같다. (forward cost가 0이므로) 휴리스틱의 admissibility에 따라 f(n) = g(n) + h(n) <= g(n) + h*(n) = f(A)이다.

1과 2를 더하면 f(A) = g(A) + h(A) < g(B) + h(B) = f(B)에서 f(A) < f(B)이다.

여기에 3을 더하면 f(n) <= f(A) < f(B)이므로 f(n) < f(B)이므로 n은 B보다 항상 Fringe에서 먼저 선택된다. 이를 통해 A의 모든 ancestor 노드는 B보다 먼저 확장된다는 것을 증명했다.

위 방식의 한가지 문제는 상태 그래프 상에 가중치가 0인 사이클이 있는 경우에 여기에 갇혀 Solution에 도달하지 못한다는 점이다. 이를 해결하기 위해 이미 expanded된 노드를 저장하는 closed로 표시하는 set을 저장해서 막을 수 있다. 이런 optimization이 더해진 트리 탐색을 graph search (그래프 탐색)이라 부른다. 아래의 의사 코드를 참조하자.

여기서 closed set을 list가 아닌 disjoint set에 저장했다는 점에 주목하자. list는 멤버십 체크에 O(n)의 시간이 소요되는 반면에 set은 O(1)이다. 그래프 탐색의 또 다른 주의점은 admissible한 휴리스틱 함수에서도 optimality가 깨질 수 있다는 점이다. 다음의 상태 공간 그래프와 그에 상응하는 검색 트리를 살펴보자. 가중치와 휴리스틱 값이 표시되어 있다.

위의 예제에서 optimal한 경로는 총 비용 5를 가지는 S -> A -> C -> G다. 최저깅 아닌 다른 경로는 S -> B -> C -> G가 있다. 하지만 노드 A의 휴리스틱 값(4)이 B의 휴리스틱 값(1)보다 너무 크기 때문에, 노드 C는 노드 B에 의해 먼저 탐색되게 된다. 그러면 노드 C에 대한 backward cost가 3이 된채로 C는 closed가 되기 때문에 나중에 A를 통해서 C를 탐색할 수가 없게된다. 따라서 S -> B -> C -> G를 리턴하게 될 것이다.

A* 탐색의 completeness와 optimality를 위해 admissibility보다 더 강한 제약 조건인 consistency가 필요하다. consistency의 주된 아이디어는 휴리스틱 함수가 모든 노드로부터 목표 지점까지의 추정 비용을 실제보다 같거나 적게 (not overestimate) 추정하는 것 뿐만 아니라 그래프 상에서 간선으로 이어진 모든 두 노드에 대해서도 똑같은 원칙으로 동작해야 한다는 점이다.

즉, 간선으로 연결된 모든 노드 A와 C에 대해서 h(A) – h(C) <= cost(A, C)를 만족해야한다. 즉, A에서 목표 지점까지의 추산되는 비용은 A와 C를 잇는 간선의 가중치와 C에서 목표 지점까지의 추산되는 비용보다 클 수가 없다.

[Theorem]

주어진 탐색 문제에 대해, consistency를 만족하는 휴리스틱 함수 h를 쓰는 A* 탐색은 optimal solution을 반환한다.

증명
증명을 위해 우선 A* 탐색을 consistent한 휴리스틱으로 수행한다. 탐색을 위해 fringe에서 노드를 꺼낼 때마다 우리는 그 노드에 대해 optimal한 경로를 찾았다는 것을 보일 것이다.

consistency 제약 조건을 사용해서 어떤 plan을 따르더라도 노드의 f(n) 값이 감소하지 않는다는 것을 증명할 수 있다.
consistency 제약 조건을 사용하면 노드 n과 그 자손 n’에 대해 아래의 식이 성립한다.

f(n’) = g(n’) + h(n’)
= g(n) + cost(n, n’) + h(n’)
>= g(n) + h(n)
= f(n)

즉, 간선이 존재하는 부모와 자식 노드의 모든 쌍 (n, n’)에 대해 f(n’) >= f(n)이다. 따라서 어떤 path 상에서 f(n)은 감소하지 않는다. 이걸 가지고 어떤 노드 n이 fringe에서 제거될 때마다 optimal path를 발견했다는 것을 증명할 수 있다.
먼저 주어진 명제가 거짓이라고 가정해보자.

노드 n이 fringe에서 제거될 때 시작 노드에서 n까지의 경로가 optimal이 아니라고 가정하자.

그렇다면 아직 fringe에 n의 optimal한 경로를 위한 ancestor n”이 존재해야한다. 그런데 n”이 fringe에 남아있으려면 f(n”)은 f(n)보다 큰 값이어야한다. 여기에서 모순이 발생한다. 위에서 우리는 f이 감소하지 않는다고 했다. f(n”)이 이미 f(n)보다 큰 상황에서 감소하지 않기 때문에 n”에서 expand한 결과는 무조건 현재 제거된 노드 n의 f(n)보다 클 수밖에 없다.

이제 남은 건 optimal 한 goal A는 항상 optimal이 아닌 모든 다른 노드 B보다 먼저 fringe에서 제거된다는 것만 보이면 된다. 목표 지점에서 h(A) = h(B) = 0이다. 따라서 f(A) = g(A) < g(B) = f(B)이므로 f(A)가 작은 값이므로 A가 먼저 제거된다.

따라서 우리는 consistent heuristic한 조건에서 A* 그래프 탐색이 optimal하다는 결론을 내릴 수 있다.

Dominance

지금까지 A* 탐색의 optimality를 유지하기 위한 admissibility와 consistency의 속성을 살펴보았다. 이제 다시 원래의 문제인 좋은 휴리스틱에 대한 질문으로 돌아가 어떻게 다른 휴리스틱이 다른 것에 비해 좋다는 것을 구분할지를 살펴본다. 이것을 위한 표준 측정방법은 dominance다.

만약 휴리스틱 a가 b보다 dominant 하면, 상태 공간 그래프의 모든 노드 n에 대해 h_a(n) >= h_b(n)를 만족해야한다.

즉, 더 나은 휴리스틱은 그렇지 않은 것보다 항상 목표치에 더 가까운 값을 리턴한다. 또한 trivial한 휴리스틱은 h(n) = 0으로 정의되며, A* search를 UCS처럼 동작하게 한다. 모든 admissible한 휴리스틱은 trivial한 휴리스틱보다 dominant하다.

여러 admissible한 휴리스틱들에 대한 max 함수 또한 항상 admissible하다.

Summary

여기까지 우리는 탐색 문제에 대해 논했으며, 4개의 구성요소인 state space, successor function, start state, goal state에 대해 다루었다. 그리고 BFS, DFS, UCS, Greedy, A* Search에 대해 다루었다.

2019. 12. 15. CS188 Introduction to Artificial Intelligence – (1-3) Search