[AI] 3. CSP (Constraint Satisfaction Problems) - Backtracking Search

지금까지 Search는 Sequence of actions를 구하는 Planning 문제였다.

이번에는 Assignment to variable하기 위한, 즉 Identification 문제에 대해 알아보자.  

Identification 문제는 어떤 Variable에 값을 할당하는데, 할당하기 위한 조건(Constraint)이 주어진 문제이다. 다시 말해 Goal state까지 최적의 Path나 Cost를 찾는 것이아니라, Constraint를 충족하는 Value를 Variable에 assign 하는 것이 Goal이다.

기존의 Standard search는 state를 blackbox라 생각하고 pathing하거나 goal인지 아닌지 판단정도만 했는데 CSP는 state의 내부를 조금 더 들여다본다. 

CSP에서 state는 Variable로 정의되고 Variable은 어떤 값을 갖는데, 그 값은 Domain으로부터 온다. 그리고 Goal test는 Constraint들을 모두 만족했는지를 test하게 된다.

위에서 설명한 CSP 의 대표적인 사례로 Map Coloring 문제를 들 수 있다.

위 문제는 인접한 주에 서로 다른 색을 칠하는 문제이며 위에서 설명한 Notation을 적용하면 아래와 같다.

 1) Variable : WA, NT, Q, NSW, V, SA, T (도시 이름, Standard search에서 state에 해당)

 2) Domain : D = {red, green, blue} (Variable에 할당 될 수 있는 값)

 3) Constraint

    - WA ≠ NT... : 인접 도시간 Assign 되는 값(Color)은 같을 수 없음

 4) Goal (Path나 Cost가 아닌 Variable의 Assign 결과)

    : { WA = red, NT = green, SA = blue, Q = red, NSW = green, V = red, T = green}

또 다른 예제로 N-Queens 문제를 예로 들 수 있다.

위 문제는 N개의 Queen을 서로 가로/세로/대각선 방향으로 놓이지 않게 배치하는 문제며 아래와 같은 Notation을 정의 할 수 있다. (Notation은 문제를 설계하는 사람에 따라 달라질 수 있다.)

 1) Variable : Xij (체스판의 i=행, j=열 번째 cell)

 2) Domain : 0, 1 (Queen이 있는가?)

 3) Constraint : 같은 행(i) 다른 열(j, k)인 경우는 {(0, 0), (0, 1), (1, 0)} 중 1개 값을 가진다.

                    ...

                 

그 외에도 대부분의 Planning문제는 CSP로 풀이될 수 있으며, Timetabling, Assignment, Hardware configuration 등 다양한 현실문제를 해결하는데 좋은 툴로써 활용될 수 있다.

Constraint Graphs

CSP 역시 Graph로 표현할 수 있다. Graph로 표현할 때 Constraint또한 Graph에 ㅁ(네모)으로 표현하기도 한다.

아래는 Constraint를 표현한 Constraint Graph 사례다. (Cryptarithmetic, Sudoku)

Constraint의 경우, 1개 Variable만 연관된 제약조건이면 unary(ex. WA ≠ red), 2개가 연관되면 binary constraint (ex. WA ≠ SA)라 지칭한다. 

간혹 문제에 따라 Constraint가 확률이거나 cost 등 간접적인 제약조건인 경우에는 제약조건을 Soft constraints라 지칭한다.

Formulation

SCP역시 Standard Search 알고리즘과 마찬가지로 아래와 같이 유사한 Notation을 가진다.

 1) Initial state : {} (아무것도 assign 되어 있지 않은 상태)

 2) Successor function : variable에 value를 Assign 하는 행위

 3) Goal test : 현재까지 모든 Variable이 Constraint를 만족하면서 Assign되었는가?

Backtracking Search

Backtracking search는 CSP를 풀기 위한 가장 기본적인 uninformed search 알고리즘이며, DFS 알고리즘에 아래 2가지 Idea를 적용하며, N=25정도의 N-Queen 문제를 풀 수 있을 정도의 성능을 가진다. (속도, 메모리 차원에서 다소 비효율적)

 Idea 1) 어떤 variable을 assign 할지 ordering을 한 후 한번에 1개의 variable만 assign하자.

 Idea 2) assign 하면서 constraint를 check 하자. (= Incremental goal test)

원리에 대해서는 글로 보는 것 보다 아래 그림을 통해 예제를 보면 쉽게 이해 된다.

 - 먼저 어떤 variable을 먼저 assign할지 ordering 하는데 위 그림에서는 WA가 먼저 red, green, blue로 assign 되었다.

 - DFS를 수행하면서 다음 variable을 assign 하는데 constraint check를 통해 red를 제외한 green, blue를 assign 한다.

 - 이렇게 terminal node까지 내려간 뒤 DFS의 원리에 따라 상위 노드로 이동한 후 (backtracking) WA를 green, blue로 한 하위 tree를 각각 완성 시킨다.

위 원리를 implementation 하기 위한 Pseudo code는 아래와 같이 Recursive하게 (재귀적으로) 작성할 수 있다.

Improving Backtracking

앞서 언급한 대로 Backtracking 알고리즘은 가장 초기 CSP 알고리즘으로 굉장히 Naive한 알고리즘이다. 따라서 3가지 관점에서 개선 포인트가 있다.

1) Filtering

이미 실패한 상태인데 DFS의 원리에 의해 끝까지 갔다가 다시 backtracking 한다. 이것을 조기에 감지해서 backtracking 횟수를 줄일 수 없을까?

위 Idea에서 온 것이 바로 Forward Checking 개념이다. 

예를 들어 WA에 red를 먼저 assign 했다면 인접한 NT와 SA의 domain 목록에서 red를 삭제한다. 그러면 실제로 assign 할때 domain의 수가 줄어 있기 때문에 훨씬 속도가 빨라질 것이다. 하지만 이렇게 계속 Forward check을 수행하다 보면 위 그림의 NT와 SA처럼 Death end에 다다르는 경우가 발생할 수 있다. 이 문제 해결을 위해 고안된 방법이 바로 Arc consistency 알고리즘이다. 

Arc consistency 알고리즘의 개념은 X(tail) → Y(head)로 Arc가 뻗어 나갔을 때, tail에 assign 될 수 있는 domain이 하나라도 남아 있으면 consistent 하다고 여기는 것이다. 그리고 핵심은 이 과정에서 tail의 Domain에 변동이 있었다면 tail과 관련된 arc에 대한 consistency도 모두 체크하는 것이다.

위 그림에서는 WA에 red가 assign 되었을 때, WA가 tail, NT, SA가 head라면 WA 입장에서는 red외의 색이 NT와 SA에 남아 있음으로 consistent 하다. (red로 assign 해도 상관 없다.) 반면, NT와 SA가 tail일 때는 {red, green, blue}으로 head인 WA에 모두 assign 시킬 수 없음으로 {red}를 삭제해주면 consistent 해진다. 그러면 NT와 SA에서 {red}가 삭제된다. 

그리고 NT와 SA의 Domain에 변동이 있었음으로, 인접한 Arc를 통해 Q, NSW, V와 consistency를 체크하지만 NT와 SA에 선택지가 2개가 있음으로 Domain의 변동은 발생하지 않는다.

만약 다음 Step으로 Q(tail)에 {green}이 assign 된다면 인접한 NT, SA, NSW(head) 모두에 assign 될 수 있음으로 Q 입장에서는 consistent 하지만 NT, SA, NSW가 tail 입장이 되면 {green}이 삭제되어야만 consistent 해 질 수 있음으로 {green}이 삭제된다.

그런데 {green}을 삭제함으로써 NT와 SA에 {blue}만 남게 된다. 이렇게 1개 color로 assign 되면 NT, SA도 이웃한 variable들과 constraint check를 하게 되고, consistent 조건이 깨짐이 모니터링 됨으로써 Q에 green이 온 경우 Dead end라는 것을 조기에 알아 차리게 된다.

위 Arc Consistency 알고리즘이 세월을 거듭해 지속발전 하였으나, AC-3이 현재 가장 대중적으로 사용되고 있으며, AC-3의 Pseudo code는 아래와 같다. 

(AC-3 이전 버전은 효율적이지 않고 이후 버전은 구현이 너무 어렵다고 한다.)

여기서 헷갈리지 말아야 할 것은, AC-3는 CSP문제를 해결하는 알고리즘이 아니라 Backtracking Search를 개선시키기 위한 Filtering Tool (남은 Domain의 수를 줄여주는 역할) 이라는 것을 기억해야 한다. 간혹 AC-3 자체가 CSP 솔루션으로 오인하는 경우가 있으니 주의하자.

(실제로 AC-3 알고리즘을 Implementation 한 코드를 보면 CSP문제 내에서 옵션으로써 동작하며, 남아 있는 Domain의 수를 줄여주는 역할을 한다한다.)

참고로 K-Consistency는 Arc-Consistency를 이론적으로 일반화 시킨 것이다. Arc-Consistency는 K=2인 2-Consistency 알고리즘이다. 

K-Consistency의 Idea는 만약 2개 variable의 consistency를 만족시킬 수 있다면(Arc-consistency) consistency를 1개 추가하여 3개 consistency에 대해서도 만족시킬 수 있고, 이렇게 3개이상의 consistency를 동시에 고려한다면 위와 같은 상황을 사전에 방지할 수 있다. 

(3개 consistency를 동시에 고려함으로 저런 상황이 오기 전에 death end로 판단한다.)

다만 k가 커질수록 높은 computing power를 요구하기 때문에 통상 Arc(k=2) consistency를 주로 사용한다.

Strong K-Consistency는 K-Consistency와 반대로, K-consistency가 만족한다면, K-1, K-2... consistency도 만족하다는 가정을 하고, 이론적으로 backtracking 없이 linear time으로 CSP를 풀 수 있다고 한다. 참고 정도로 기억해두면 좋을 것 같다.

2) Ordering

어떤 variable을 먼저 assign 할지, value는 어떤 순서로 assign 할 것인지?

이 두가지를 ordering 하는 것도 성능에 어느정도 영향을 미친다.

첫 번째로 variable ordering의 경우 assign 될 수 있는 value(domain의 원소)가 적은 것부터 할당 하는 것이 유리하며, 이를 MRV(Minimum Remaining Value)라 한다. MRV는 쉽게 생각하면 '어려운 것부터 풀어라'로 해석하면 이해하기 쉽다. 실제로 {red, green, blue}가 모두 남아 있다면 선택지가 많기 때문에 쉬운 문제인 반면 {red, green}중 택해야 한다면 상대적으로 어려운 문제다. 이렇게 어려운 문제를 먼저 해결해두면 다른 문제는 상대적으로 쉬운 문제이기 때문에 더욱 효율적으로 Backtracking을 할 수 있다. 이런 특성 때문에 "Fail-Fast Ordering"이라 불리기도 한다.

두번째로 value ordering의 경우는 반대로 LCV(Least Constraining Value)가 유리하다. 풀어 말하면 constraint가 별로 남아 있지 않는 (쉬운) value를 선택하란 뜻이다. 예를 들어 위 그림에서 3번째 도시에 {red}를 assign하면 인접 도시에 할당될 value의 보기가 많다. 하지만 blue는 그렇지 않다. 왜 굳이 이렇게 해야 하냐면, variable은 다 할당되어야 하지만 value는 모든 domain을 쓸 필요가 없기 때문에다. 가령, {red, green}으로 문제 해결이 가능하면 {blue}는 굳이 쓸 필요가 없으니 아껴두는 것이다. 

이런 ordering 기법을 사용하면 기존에 N=25의 한계를 넘어 N=1,000인 N-Queens 문제를 해결할 수 있게 된다고 한다.

3) Structure

마지막 개선 관점인 Structure에서는 state space structure를 변경함으로써 알고리즘의 성능의 향상을 기대하는 것이다. (실제로 성능 향상을 확인할 수 있다.)

예를 들어 위 그래프의 T는 모든 Variable 과 constraint가 없는 상태로 Independent 하기 때분에 어느 색이 할당 되어도 상관 없다. 이 관점을 활용하여 CSP문제를 작은 Independent sub-problems로 쪼개어 접근하면 exponential한 시간이 걸렸던 CSP문제를  linear time에 해결할 수도 있다.

첫 번째 예시는 Tree-Structured CSP이다. Graph가 Cycle이 없다면 오른쪽과 같이 Tree구조로 표현될 수 있으며, Tree는 한쪽 방향의 edge만 갖도록 정렬 할 수가 있다.(DAG : Directed Acyclic Graph, 방향성이 있고 cycle이 없는 그래프, Linearized 됐다고도 표현한다.)

이런식으로 Graph를 Linearized 된 Tree로 표현하면 앞서 설명한 Arc-consistency(AC-3) 알고리즘을 활용해 CSP문제를 푸는데 상당히 용이하다.

Tree-Structured CSP가 한쪽 방향성을 갖도록 정렬되어 있어 n번째 variable부터 역순으로 Arc-consistency를 체크하면서 1번째 variable에 한번 도달하면, 가능한 Domain만 남고, 먼저 소개했던 AC-3 때처럼 cross-check & backtracking 할 필요가 없다.

위 그림을 예로 들면, F에 {blue}가 있음이 체크 되었고, constraint 조건에 의해 D에 있는 {blue} color가 삭제되고, {red, green}만 Domain에 남는다. 그리고 순차적으로 C, B, A variable을 체크하면 가능한 Domain만 남는다. 이제 남은 것은 다시 A부터 순차적으로 value를 assign 하면서 문제를 성공시키면 끝난다. (MRV, LCV 연계)

(※ 앞서 Arc Consistency를 설명할 때 처럼 Domain을 제거하고, cross check하고 이상이 있는 경우 backtracking하는 과정이 없음)

이렇게 Tree-Structure를 활용해 CSP 문제를 푼다면, variable이 n개 있는 경우 총 시간 복잡도는 O(n*d^2)으로 linear한 시간 복잡도를 가지게 된다.

다만, Graph는 항상 Tree structure로 변경 될 준비가 되어있는것은 아니다. 위 그림처럼 cycle이 있는 Graph의 경우 Tree로 표현하기가 쉽지 않은데, 이 경우 다소 극단적으로 Tree-Structure로 만들어 버리는 Cut-set conditioning 알고리즘이 있다. 위 그림의 좌측은 cycle이 잇는 graph였지만 SA를 삭제함으로써 Linearize 된 Tree 구조로 변경된다. 이때 삭제된 SA를 Cut-set이라고 부른다.

생각보다 매우 무지막지한 알고리즘으로 보이지만 그 효과는 상당하다. 위 그림처럼 Cut-set을 정하고, Cut-set에 할당될 수 있는 Domain으로 문제를 나눈다음, Cut-set을 제외한 Tree structured 문제를 앞서 설명한 Tree-Structured CSP으로 각각 해결한다. 마치 Divide and Conquer(분할정복) 처럼 큰 문제를 작은 문제로 쪼개서 분할하고 최종적으로 취합하는 형태를 가지는데, 아래의 수식처럼 Cut-set의 size가 작으면 작을수록 시간 복잡도(time complexity)측면에서 큰 이득을 가져올 수 있다. 

(c = cut-set size, n = num. of variable, d = num. of values in domain)

Tree-Structured CSP (with Cut-set conditioning) 외에도 structure를 변경하여 문제를 푸는 방법에는 Tree decomposition이 있다.

Tree decomposition은 일종의 Divide and Conquer(분할 정복) 알고리즘을 활용한 것인데, 전체 트리를 작은 문제로 쪼개서 mega-variable을 선언하고, 각 mega-variable을 tree structure로 엮은 것이다. 위 그림에서는 4개의 mega-variable을 선언하여 tree로 역었는데, 각 mega-variable은 1개의 공통된 variable을 공유하는 constraint를 추가로 가지게 된다. (agree on shared variable) 이렇게 structure를 변경하면 Divide and Conquer의 원리에 따라 각 mega variable이 constraint를 만족시키면서 variable을 assign 시킨다음 tree-structured CSP 알고리즘을 돌려서 전체 문제를 해결할 수 있다.