[인공지능] Chapter 6. Constraint Satisfaction problems

What is search for?

• Assumptions about the world
  • a single agent
  • deterministic actions
  • fully observed state
  • discrete state space
• Planning: Sequences of actions
  • Goal에 이르는 Path가 중요
  • Paths는 다양한 비용과 깊이(depths)를 가짐
  • Heuristics give problem-specific guidance
• Identification: assignments to variables
  • Goal 그 자체가 중요 (Path가 아니라)
  • 모든 Paths는 같은 depth를 가짐
  • CSPs are a specialized class of identification problems

Constraint Satisfaction Problems

• Standard search problems
  • State is a ‘black box’
    • arbitrary data structure (임의의 데이터 구조)
  • Goal test
    • can be any function over states
  • Successor function can also be anything
• Constraint Satisfaction Problems (CSPs)
  • A special subset of search problems
  • Identification 유형의 문제
    • 경로보다는 Goal 자체가 중요
    • 모든 경로는 같은 깊이값을 가짐
  • 변수
    • 총 N개의 변수 (Xi)
  • 도메인
    • 각 변수 Xi는 d개의 도메인 값(xi)을 가질 수 있다.
  • constraints
    • 변수가 가질 수 있는 값에 제한 존재
  • State
    • defined by variables Xi with values from a domain D
  • Goal test
    • is a set of constraints specifying allowable combinations of values for subsets of variables
    • 변수의 하위 집합에 허용되는 값 조합을 특정하는 제약 조건의 집합
  • Simple example of a formal representation language
  • Standard search algorithms보다 더 강력한 성능을 가진 유용한 general purpose algorithms
  • EXamples
    • Map-coloring
      • 변수: 각 지역의 이름 (WA, NT, Q, NSW, V, SA, T)
      • 도메인: 지역에 칠해질 수 있는 색 (red, green, blue)
      • 제약 조건: 인접한 지역은 같은 색으로 칠해질 수 없음
    • N-Queens
      • 변수: 체스판 위 퀸이 놓일 수 있는 공간 (N*N개)
      • 도메인: 각 좌표 Xij 위에 퀸이 있는지 없는지 확인하는 값 (0, 1)
      • 제약조건: 같은 행, 같은 열, 대각선 방향으로 두 개 이상의 퀸이 놓일 수 없음. 체스판 위에 총 N개의 퀸이 있어야 함

Constraint Graphs

• Binary CSP
  • 각각의 제약들이 최대 두 개의 변수와 연관
  • node가 변수
  • arcs는 제약 조건
  • General-purpose CSP algorithms는 그래프 구조를 사용하여 검색 속도를 높임
  • ex. 수도쿠

Varieties of CSPs

• Discrete Variables (이산 변수)
  • Finit domains (유한 도메인)
    • size d 는 O(d^n) complete assignments를 의미
  • Infinite domains (integers, strings) (무한 도메인)
    • 선형 제약 조건은 해결 가능
    • 비선형 제약 조건은 undecidable
    • ex. 작업 스케줄링, 변수가 각 작업의 시작/종류 시간인 경우
• Continuous variables
  • 선형 제약 조건은 해결 가능 (다항 시간 내에 LP methods를 통해)
  • ex. 허블 망원경 관측의 시작/종료 시간

Varieties of Constrints

• Unary constraints (단항 제약 조건)
  • involve a single variable (equivalent to reducing domains)
• Binary constraints (이진 제약 조건)
  • involve a pairs of variables
• Higher-order constraints
  • involve 3 or more variables
• Preferences (soft constraints)
  • 각 변수 할당에 대한 비용으로 표현 가능
  • Constrained optimization problems 제공

Real World CSPs

• Scheduling problems
• Timetabling problems
• Assignment problems
• Hadware configuration
• Transportation scheduling
• Factory scheduling
• Circuit layout
• Fault diagnosis
• Many real world problems involve real valued variables..

Standard Search Formulation

• Standard search formulation of CSPs
• States defined by the values assigned so far (partial assignments)
  • 초기 상태: the empty assignments, {}
  • 후속 함수 (successor function): 할당되지 않은 변수에 값 할당
  • 목표 테스트 (goal test): 현재 할당이 완료되었으며, 모든 제약 조건을 만족

Backtracking Search

• Basic uninformed algorithm for solving CSPs
• Idea
  • 한 번에 하나의 변수 (One variable at a time)
    • 변수 할당은 순열이므로, 순서를 고정
    • 각 단계에서 단일 변수에 대한 할당만 고려
  • 진행하면서 제약 조건 확인 (Check constraints as you go)
    • 이전 할당과 충돌하지 않는 값만 고려
    • 제약 조건 확인을 일부 계산을 수행
    • Incremental goal test
• Can solve n-queens for n=25

Improving Backtracking

• General-purpose ideas give huge gains in speed
• Filtering
  • Can we detect inevitable failure early? (피할 수 없는 실패를 조기에 감지할 수 있을까?)
• Ordering
  • In what order should its vaues be tried?
• Structure
  • Can we exploit the problem structure?

Filtering

• Forward Checking
  • 할당되지 않은 변수에 대한 도메인을 추적하고 잘못된 옵션 제거
  • 기존 할당에 추가될 때 제약 조건을 위반하는 값 제거
• Constraint Propagation
  • Forward checking는 할당된 변수에서 할당되지 않은 변수로 정보를 전파하지만, 모든 오류를 초기에 감지하지는 못함
  • Constraint propagation
    • 제약 조건에서 제약 조건으로 추론하기

Consistency of A Single Arc

• An arc X→ Y is consistentwhich could be assigned without violating a constraint
• iff for every x in the tail there is some y in the head

Arc Consistency of an Entire CSP

A simple form of propagation makes sure all arcs are consistent.

forward checking을 통해 일반화할 수 있는 원칙

도메인 값이 제거된 변수와 맞닿아 있는 다른 변수 또한 도메인 값을 다시 한 번 확인

Limitation of Arc Consistency

• After enforcing arc consistency
  • 하나의 솔루션만 남을 수 있음
  • 여러 솔루션이 남을 수 있음
  • 솔루션이 하나도 남지 않을 수 있음 (알지 못함)
• Arc consistency는 백트래킹 탐색에서도 가능

K-Consistency

• Increasing degrees of consistency
  • 1-consistency (Node consistency)
    • 각 단일 노드의 도메인은 해당 노드의 단항(unary) 제약 조건을 충족하는 값을 갖는다.
  • 2-consistency (Arc consistency)
    • 각 노드 쌍에 대해 한 노드에 대한 일관된 할당을 다른 노드로 확장할 수 있다.
  • K-consistency
    • 각 k 노드에 대해 k-1에 대한 일관된 할당을 k번째 노드로 확장할 수 있다.
    • K가 높을수록 계산 비용이 크다 (k=2 일 때, Arc consistency)

Strong K-Consistency

• Strong k-consistency
  • also k-1, k-2, … , 1 consistent
• Claim
  • strong n-consistecy means we can solve without backtracking (bactracking 없이도 풀 수 있음)
    • 임의의 변수에 대한 할당을 선택
    • 새로운 변수 선택
    • 2-consistency에 의해, 첫 번째 변수와 일치하는 choice가 존재
    • 새로운 변수 선택
    • 3-consistency에 의해, 처음 두 변수와 일치한 choice가 존재
    • …
  • Lots of middle ground between arc consistency and n-consistency (k=3, called path consistency)

Ordering

• Minimum Remaining Values (MRV)
  • Choose the variable with the fewest legal left values in its domain
  • most constrained variable (가장 제약이 많은 변수 선택)
    • 곧 할당될 값으로 계속 작동할 가능성이 높다는 뜻
    • 만약 선택되지 않은 채로 남을 경우 백트래킹으로 이어진다는 뜻
    • 이후에 골라 백트래킹을 해야한다할지라도, 빨리 백트래킹을 하는게 시간적으로 효율적
  • Fail-fast ordering
• Least Constraining Value (LCV)
  • 변수 선택이 주어졌을 때, constraint가 가장 적은 값을 선택
  • 나머지 변수에서 가장 적은 값을 제외하는 값을 선택
  • 가장 선택지가 많은 값 선택

Structure

• Tree-structured CSPs
  • Theorem
    • 제약 조건 그래프에 loop가 없는 경우, CSP는 O(nd^2)시간 내에 해결 가능
    • 이러한 속성은 probabilistic reasoning에도 적용 가능 (syntactic restrictions과 complexity of reasoning의 관계에 대한 예시)
  • Algorithm
    • Order
      • 뿌리 변수를 선택
      • 부모가 자식 앞에 오도록 변수 정렬
        • 트리를 loop가 없는 방향 그래프로 만든다.
        • 루트 노드가 tail이 된 형태로 간선을 연결
      • Remove backward
        • arc consistency에 따라 backwards pass
        • 부모 노드의 도메인 값이 변경되면 부모 노드오 ㅏ연결된 노드의 도메인 값을 확인
      • Assign forward
        • 부모 노드와 자식 노드 간의 순서가 확인되면 forward assignment 시작
        • 도메인 값을 확인 하는게 아니라, 각 변수에 할당할 색을 남아있는 도메인에서 선택
    • Runtime
      • O(nd^2)
  • Claims
    • After backward pass, all root-to-leaf arcs are consistent
    • If root-to-leaf arcs are consistent, forward assignment will not backtrack

Improved structure

• Nearly Tree-Structured CSPs
  • 조건
    • instantiate a variable (변수를 인스턴스화)
    • prune its neighbors’ domain (이웃 도메인을 잘라냄)
  • Cutset conditioning
    • Cutset
      • 특정 변수들을 그래프에서 떼어냈을 때, 트리가 되는 가장 작은 규모의 변수들
    • 나머지 제약조건 그래프가 트리가 되도록 변수 집합을 인스턴스화
    • Cutset size c는 O((d^c)(n-c)d^2) 의 속도 (c 가 작을 경우 매우 빠름)

 

Tree Decomposition

• Idea
  • create a tree-structured graph of mega-variables
  • Each mega-variable encodes part of the original CSP
  • Subproblems overlap to ensure consistent solutions

Iterative Algorithms for CSPs

• Local search methods typically work with ‘complete’ state (모든 변수가 할당된 상태)
• To apply to CSPs
  • 만족되지 않은 제약 조건이 있는 과제를 받음
  • 연산자가 변수 값을 재할당
  • No fringe. Live on the edge
• Algorithm (While not solved)
  • 변수 선택
    • 충돌하는 변수 무작위 선택
  • 값 선택 (최소 충돌 휴리스틱)
    • 가장 적은 제약 조건을 위반하는 값 선택

Summary

• CSPs are a special kind of search problem
  • States
    • partial assignments
  • Goal test
    • defined by constraints
• Basic solution
  • Backtracking search
• Speed-ups
  • Ordering
  • Filtering
  • Structure
• Iterative min-conflicts is often effective in practice