[인공지능] 6. Constraint Satisfaction Problems

1. Problem Formulation as a CSP

 : 문제 상황을 표현하는 방법 중에서는 factored represetation이 있다. 어떤 문제가 어떤 제한사항, 조건들(Constraint)를 만족시켜야 풀린다고 해보자. Factored representation은 각 states를 variable을 활용해 표현하는 것이고(goal state 또한 그렇다), 이 variable에 할당된 value값이 constraint을 만족하는 값일 때 문제를 해결했다고 말하는 것이다.

  즉, 어떤 값을 할당할 수 있는 variable과 논리연산자를 이용해 어떤 문제 상황을 표현한다고 할 때, 이런 문제들을 Constraint Satisfaction Problem이라고 한다. 

 ( 지금까지는 autonomic representation을 사용했었는데, 이제부터는 state의 내부를 들여다 봐 내부 정보에 접근할 것이다.)

 

   CSP search algorithms은 structure of states에서 이점을 가지고, 문제별로 다른 heuristic을 사용하는 대신 일반적인 general heuristics을 사용해 복잡한 문제를 해결할 수 있다. constraints를 만족하지 않는 variable/value 의 조합들을 알아내, search space의 많은 부분을 한꺼번에 pruning하여 없앰으로써 search space를 한 번에 확 줄일 수 있다. 

 

 

CSP의 components에는 X, D, C가 있다

 ① X는 변수들 variables의 집합이다. {X1, X2, ... , XN}

 ② D는 각 변수들마다 정의되는 domains의 집합이다.(정의역) {D1, D2, ... , DN}

    한 변수는 Domain 안의 값들 중에서 값을 가질 수 있다.

 ③ C는 constraints의 집합으로, 허용 가능한 value들의 조합을 말한다. 즉 변수들이 어떤 값을 가져야 하는지에 대한 조건을 말한다.

    constraint는 <Scope, rel> 의 한 쌍으로 이루어지는데, scope 는 조건을 구성하는 변수들의 집합이고, rel은 그 변수들이 가질 수 있는 값들이 어떤 관계를 가지고 있는지에 대한 relation 이다. 즉 조건이다. 

  ex) <(X1,X2) , X1 = X2 >

 

대표적인 CSP는 바로 이 색칠 문제이다. (b) 그래프에서 인접한 두 정점에는 서로 다른 value를 할당하는 문제인 것이다. 

CSP문제는 constraint graph로 보기 편하게 바꾸곤 한다. node가 각각 problem의 variable이 되고, 간선은 constraint에 존재하는 두 variable을 이어준다.

 

위 문제를 CSP로 나타내면 다음과 같다.

 

X = { WA, SA, V, NSW, Q, NT, T }

D = { D1, ..., D7 } , Di = {red, green, blue} // 각 variable은 red, green, blue의 값을 가질 수 있다. 그런 variable이 총 7개

C = { SA ≠ WA , SA ≠ NT ..., NSW ≠V} // 인접한 두 정점은 색이 달라야 한다

 

그래서 각 Variable에 어떠한 value를 할당하는 것이 CSP에서의 state이다. 

 ex) {Xi = vi , Xj = vj , ... }

 

이렇게 모든 variable에 값이 할당되었다면 complete assignment, variable의 일부에만 value값이 할당되었다면 partial assignment라고 한다. 또한 assignment가 어떠한 constraints도 어기지 않았다면 이것을 consistent 또는 Legal assignment라고 부른다. 따라서 CSP에서의 solution은 consistent하고 complete 한 asignment가 된다. 

그래서 우리는 문자로 된 문제를 CSP로 나타낼 수 있어야 한다.

 

EX) 차의 부품을 결합하자 : 앞 , 뒤 바퀴 축을 달고, 네개의 바퀴를 고정시키고, 각 바퀴의 너트를 고정시키고, 마감처리를 해야 한다. 그리고 마지막으로 잘 합쳐졌는지 확인해야 한다. 축을 다는데는 10분, 바퀴다는데는 1분, 나사조이는데는 2분이 걸리고 마감엔 3분이 걸린다. 또한 축->바퀴->나사->마감 순으로 진행되어야 한다. 30분 안에 조립해보자.

 

X = { axles_f, axles_b, wheel_fr, wheel_fl, wheel_br, wheel_bl, nut_fr, nut_fl, nut_br, nut_bl, cap_fl, cap_fr, cap_bl, cap_br, inspect }

 

D = { D1, D2, ... , D15 } , Di = { 1, ... ,27 } // 마지막 3분은 점검하는데 써야해요 따라서 앞 단계까지 27분 컷 해야함

 

C =  {

axles_f + 10 <= wheel_fr, axles_f + 10 <= wheel_fl,

(바퀴 설치하기 시작하는 시간은 차축 설치하고 나서 최소한 10분이 흐른 뒤어야 함)

axles_b + 10 <= wheel_br, axles_b + 10 <= wheel_bl, 

wheel_fr + 1 <= nut_fr, wheel_fl +1 <= nut_fl, wheel_br +1 <= nut_br, wheel_bl + 1 <= nut_bl,

nut_fr + 2 <= cap_fr,...

(axles_f + 10 <= axles_b) or (axles_b + 10 <= axles_f)}

∩ {X != Inspect | X + dx <= inspect }

 

 

또한 숫자 암호 역시 CSP로 풀 수 있다.

X = { F, T, U, W, R, O, C3, C2, C1}

D = {D1,...,D9}, Di = {0,...9}

C = { F!=T!=U!=W!=R, O+O = 10*C1 + R, W+W+C1 = U + 10*C2, T+T+C2 = O+10*C3, C3 = F, F != 0 }

 

 

이 외에도 Sudoku, 8-queens 문제 등을 해결할 수 있다.

 

 

 

Advantage of CSP

 - CSP는 매우 다양하고 많은 문제들을 자연어처럼 natural하게 표현할  수 있다.

 - 그래서 다른 search technique을 사용해 설계하는 것보다 문제 자체를 활용해 해결하는 것이 더 쉬운 경우가 많다.

 - CSP로 문제를 풀면 다른 state-space searchers보다 훨씬 빠르다. 왜냐면 CSP 는 general한 문제풀이 방법이 있어서 search space를 빠르게 없애 나갈 수 있기 때문이다. CSP를 통해 solution이 아닌 것, 즉 constraint를 위배하는 partial assignment들은 빠르게 pruning 해나갈 수 있다!