Artificial Intelligence Assignment 2 Seung-Hoon Na October 20, 2018 1 Map coloring 본 과제에서는 M N Grid world 지도상에서 각 region이 rectangle또는 polyomino유형으로 주어질때, K개의 색상(color)만으로 서로 맞닿은 region들을 다른 색으로 칠하는 K-coloring (K 4)문제를 constraint satisfaction problem (CSP) solver에 기반하여 해결하는 것이 목표이다. 본 과제는 다음과 같이 4개의 세부 주제로 나뉜다. 1. Arc consistency 및 backtracking search에 기반한 CSP solver구현 CSP solver를 위한 일반적인 Arc consistency algorithm과 backtracking search을 구현하고 이를 K-coloring CSP 문제에 적용한다. 먼저 Arc consistency algorithm을 통해 각 region변수의 domain제한한 후 Backtracking 알고리즘을 적용하여 해를 구한다. 2. Local search에 기반한 CSP solver구현 Iterative best improvement에 기반한 Local search를 구현하여 K-coloring CSP 문제에 적용한다. 즉, 초기 에 모든 region별 color를 random하게 assign한후, 매 local step별로 하나의 region을 선택하여 그것의 색상을 변경하며, 만족하는 solution을 발견할 때까 지 local step과정을 반복한다. Local minima문제를 회피하기 위해, random walk 또는 random restart도 추가로 적용한다. 3. CSP solver 테스트 인접리스트 그래프상 json포맷의 인접리스트로 표 현된 샘플 지도를 입력받아 상기 두 유형의 CSP solver를 적용하여 해를 출력한다. 4. CSP solver 테스트 및 visualization Grid world map상 Pygame환 경에서 M N Grid world상에서 random map를 생성하고 여기에 상기 두 유형의 CSP solver를 선택적으로 적용하여 얻은 해를 실제 coloring을 통해 visualization한다. 1.1 Grid world 본 과제에서 다루는 M N Grid world의 예는 다음과 같다. 1
여기서, A, B, C, K는 region들을 가리키고, 이들 regions은 대부분 rectangle 유 형 (A, B, C, D, E, F, G, H, I)이며, 일부 regions들은 polyomino 유형 (J, K)이다. 본 과제에서는 region에 속하지 않은 empty grid가 없이, M N Grid world가 주어진 regions에 의해 완전 패킹(perfect packing)된 경우만을 고려한다. Region 그래프 1.1.1 지도(map)는 region들을 정점으로 취하는 region 그래프 G = (V, E)로 기술될 수 있으며, 여기에 노드(node) v V 는 지도상 하나의 region을 가리키고, 에지 (edge) (u, v) E는 두 region u, v가 지도상 맞닿아 있다는 것을 의미한다. Region 그래프를 파일로 저장할 때 인접 리스트 (Adjacency list)표현 방식을 따르고, region의 label을 key로, 인접한 region들의 list를 value로 하는 python dictionary구조를 json형식으로 저장하면 된다. 예를 들어, 위의 Grid world 예를 json포맷으로 기술하면 다음과 같다. { "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" } 1.2 ["B", ["A", ["A", ["A", ["B", ["C", ["C", ["D", ["E", ["F", ["H", "C"], "D", "E"], "D", "G", "F"], "B", "C", "E", "G", "H"], "D", "H", "I"], "G", "J"], "D", "F", "H", "J"], "E", "G", "I", "J", "K"], "H", "K"], "G", "H", "K"], "I", "J"] K-coloring as CSP 본 절에서는 K-coloring를 CSP문제로 형식화한다. CSP문제로 형식화하기 전에, K는 고정된 값으로 가정하자. 4색정리 (Fourcoloring theorem)에 따라, K는 최대 4이면 충분하나, 주어진 region 그래프의 특성에 따라 K < 4이 경우에도 K-coloring이 가능할 수 있다. 주어진 region 그래 프 G = (V, E)에 대해 K-coloring를 만족하는 최소의 K를 chromatic number 라고 일컫고, χ(g)로 표시한다. 만약 주어진 K에 대해 K-coloring을 만족하는 assignment가 없을 경우, 해가 없음 이라는 결과가 리턴되어야 한다. 2
CSP는 1) variables, 2)개별 변수마다 domain, 3) constraint 집합 으로 구성 된다. K-coloring문제를 CSP로 표현하기 위해, 주어진 map인 region graph G = (V, E)이라고 할 때, 변수 (Variable), domain, constraint를 정의하면 다음과 같다. Variable 임의의 region node v V 마다 color를 값으로 취할 수 있는 variable Xv 를 대응시킨다. Domain Variable Xv 에 대해 DomK (Xv )는 K개의 colors로 구성된 집합 이다. 특정한 경우로, 2 K 4인 경우 DomK (Xv )예는 다음과 같다. (2 K 4) K = 2 DomK (Xv ) = {R, B} K = 3 DomK (Xv ) = {R, G, B} K = 4 DomK (Xv ) = {R, G, B, Y } 여기서, R은 red, G는 green, B는 blue, Y 는 yellow를 의미한다 (물론 다른 색깔로 정의해도 된다). Constraint K-coloring에서 constraint은 인접한 두 nodes는 서로 다른 색 상을 가져야 한다는 것이다. 이는 형식적으로,모든 에지 (u, v) E에 대해 아래 constraint로 기술된다. Xu 6= Xv Constraint network 구성시, 위의 Xu 6= Xv constraint마다 다음과 같이 2개의 arc가 추가된다. hxu, Xu 6= Xv i hxv, Xu 6= Xv i 1.3 CSP solver 구현 Arc consistency 구현 Arc consistency 알고리즘은 다음과 같다 (textbook참조). Algorithm 1 Generalized arc consistency algorithm 1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 procedure GAC(hV s, dom, Csi). Returns arc consistent domains for CSP return GAC2(hV s, dom, Csi, {hx, ci c Cs and X scope(c)}) end procedure procedure GAC2(hV s, dom, Csi, to do) while to do 6= do select and remove hx, ci to do let {Y1,, Yk } = scope(c) {X} N D = {x x dom[x] and exists y1 dom[y1 ] yk dom[yk ] such that c(x = x, Y1 = y1,, Yk = yk )} if N D 6= dom[x] then to do = to do {hz, c0 i {X, Z} scope(c0 ), c0 6= c, Z 6= X} dom[x] = N D end if end while return dom end procedure 3
위의 Arc consistency 알고리즘을 위한 python 코드를 작성하고, json포맷 의 region 그래프를 입력받아, 구현된 Arc consistency 알고리즘을 적용하여 Arc consistent domains (각 변수별)을 출력하는 python 테스트 코드도 함께 작성하 시오. 1.4 CSP solver 구현 Backtracking search Backtracking search를 위한 탐색 그래프 (search graph)는 다음과 같이 정의된다. Node 노드는 variables들의 부분집합에 대한 값들의 assignment를 의미 하며, {X1 = v1,, Xk = vk }로 기술된다 1. Neighbor 노드 n의 neighbor N eighbor(n)는 n상에서 아직 값이 할당되 지 않은 변수 Y 를 선택하여 constraints를 위반하지 않은 yi dom(y )를 할당하여, n의 assignment를 확장한 것이다. 형식적으로 기술하면, 노드 n 을 {X1 = v1,, Xk = vk }, Y / {X1 = v1,, Xk = vk }, yi dom(y )에 대해 {X1 = v1,, Xk = vk, Y = yi }가 CSP의 주어진 constraints와 consistent할때, N eighbor(n)은 다음과 같다. N eighbor(n) = {X1 = v1,, Xk = vk, Y = yi } Start node 시작 노드는 empty assignment로, {}이다. Goal node 목표 노드는 모든 variables에 대해 값이 할당된 assignment 이다. Goal node의 assignment는 CSP의 모든 constraints와 consistent해야 한다. 앞서의 grid world map에서 backtracking 탐색의 예는 다음과 같다. 1 Assignment는 변수집합에 대한 assigned values들의 모음이다. 4
위의 그림에서 7는 노드 확장시 constraint를 위반하여 backtracking이 발생한 지 점을 가리킨다. Backtracking이 발생한 지점이후에 해당 노드를 기점으로 하는 탐 색은 수행할 필요가 없다. (즉, Backtracking발생된 노드의 모든 descendant들은 pruning된다.) 상기 Backtracking search에 기반한 CSP solver를 python 코드로 구현하시 오. 또한, json포맷의 region 그래프를 입력받아, 구현된 Backtracking 알고리즘을 적용하여 K-coloring 해를 출력하는 python 테스트 코드도 함께 작성하시오. 추가로, 앞절의 Arc consistency를 적용하여 얻은 Arc consistent domains에 대해 Backtracking search를 수행하는 python 코드를 작성하라. Arc consistency를 적용할때와 그렇지 않을때 Backtracking 알고리즘을 적용시 explored nodes의 수를 각각 비교하시오. 1.5 CSP solver 구현 Local search기반 본 과제에서 구현되어야 하는 Local search알고리즘은 Iterative best improvement로 pseudo-code는 다음과 같다. Algorithm 2 Local search algorithm using iterative best improvement procedure Local search(hv s, dom, Csi) that satisfies the constraints 2 Randomly initialize an assignment π 1. Returns a total assignment π(xi ) = Random(dom[Xi ]) for each Xi V s repeat Choose 1-move Xi = vi from π making the best improvement π 0 = π[xi = vi ]. Revise a total assignment if cost(π 0 ) < cost(π) then π = π 0. Change the current total assignment end if 9 until stoping criterions & cost(π) = 0 10 end procedure 3 4 5 6 7 8 Line2에서는 total assignment π를 랜덤하게 초기화시키는 단계, Line3-9까지 가 Iterative best improvement를 수행하는 루틴이다. 이때, cost(π) 는 주어진 π에 대한 evaluation function으로 K-coloring 문제 에서는, π에 따라 coloring를 수행할 때 제약에 위반된 edges의 갯수 (the number of conflicting edges) 로 정의된다. 형식적으로 기술하면, cost는 X cost(π) = δ (π(xu ) = π(xv )) (u,v) E 여기서 δ(expr)는 expr이 true이면 1을 그렇지 않으면 0을 리턴한다. Line4는 current assignment π에서 하나의 변수를 취하여 값을 변경할때, cost 를 가장 낮추는 (또는 best improvement를 가져오는) local assignment Xi = vi 를 선택하는 과정이다. Line5에서 π[xi = vi ]는 주어진 total assignment π에서 Xi 의 값을 vi 로 변경한 결과 total assignment를 리턴하는 연산을 의미한다. 상기 Iterative best improvement에 기반한 CSP solver를 python 코드로 구현 하시오. 마찬가지로, json포맷의 region 그래프를 입력받아, 구현된 Iterative best 5
improvement 알고리즘을 적용하여 K-coloring 해를 출력하는 python 테스트 코드도 함께 작성하시오. Local minima를 회피하기 위해, random restart (Line2)와 random walk 단계가 추가적으로 수행될 수 있도록 확장된 Iterative best improvement를 작 성하고, 이를 json포맷의 region 그래프를 입력받아 테스트하시오. 여기서, Random walk단계는 Line4에 적용되며, best improvement를 갖는 local assignment를 선택 하는 대신, cost개선과 무관하게 random하게 Xi = vi local assignment를 선택하는 과정이다. 추가로, 앞절의 Arc consistency를 적용하여 얻은 Arc consistent domains에 대해 Iterative best improvement를 수행하는 python 코드를 작성하라. Arc consistency를 적용할때와 그렇지 않을때 Iterative best improvement 알 고리즘을 적용시 local step 의 수 (Line4가 수행된 횟수)를 각각 비교하시오. 1.6 CSP solver 테스트 인접리스트 그래프상 본 과제의 예시의 1) Sample region graph와 2) 세계 지도 region graph의 Json 포맷 file을 읽어들여 여기에 Backtracking search와 Local search에 기반한 CSP 를 수행하여 해를 찾아 출력하는 python 테스트 코드를 작성하고, 결과를 리포트 하시오. Json file포맷 파일은 아래 URL을 참고하시오. 1. Sample region graph http//nlp.jbnu.ac.kr/ai2018/sample map.json 2. World country graph http//nlp.jbnu.ac.kr/ai2018/country adj.json 위의 json file외에 샘플 test로 1개 이상 더 추가하시오. 1.7 CSP solver 테스트 및 visualization Grid world map상 Grid world map을 random하게 생성하고 선택된 CSP solver유형에 대해 Kcoloring을 수행하여 실제 coloring결과를 화면에 보여주는 python 프로그램을 작성하시오. 보드 구성 및 GUI를 위해 Pygame과 PGU를 이용하라. - Pygram https//www.pygame.org/news - PGU https//github.com/parogers/pgu 해당 프로그램의 예시는 다음과 같다. 6
위의 그램에서 보다시피, 프로그램은 세개의 버튼과 4개 유형의 CSP solver중 하 나를 택하는 옵션, K를 선택하는 옵션 그리고 CSP solver를 수행하는 과정에서 출력되는 로그 textbox로 구성된다. K는 default로 4로 하고, 사용자가 선택할 수 있도록 한다. 위 프로그램의 주된 단계를 정리하면 다음과 같다. 1. Random map생성 Grid world M N 상에서 Random map을 생성하기 위해 2D knapsack을 해결하는 다음 rectpack을 이용한다. (다른 방식으로 random map을 생성해도 된다) https//github.com/secnot/rectpack 즉, M N 내의 n개의 rectangle의 (width, height)른 랜덤하게 생성하여, rectpack 의 api를 호출하여 각 rectangle을 배치하는 위치를 얻는다. 초기 에 1개의 rectangle로부터 시작하여 더이상 packing되지 않을때까지 랜덤 rectangle을 1개씩 추가하도록 하라. 이렇게 packing이 완료된 rectangle을 region으로 하고, 추가로 나머지 empty region들은 polyomino유형의 region으로 하여 빈 공간이 없도록 지도를 region으로 채우고, 이를 최종 random map결과로 한다. 2. 인접리스트 graph로 변환 위와 같이 Random map결과가 얻어지면, 이를 CSP solver의 입력 인자와 맟추기 위해 인접리스트 graph로 변환한다. 3. CSP solver적용 변환된 인접리스트 graph에 대해 앞서 구현된 2종류의 CSP solver를 적용하여 해를 찾아 실제 pygame환경에서 visualization한다. 여기서 Arc consistency를 선택적으로 적용할 수 있도록 하여, 총 4종류의 CSP solver가 선택가능하도록 한다. 다음은 상세 요구사항이다. Grid world 크기 Grid cells의 행과 열의 갯수 M 과 N 의 default 값은 30 이며, argparse를 이용하여 command line에서 입력받을 수 있도록 한다. - Argparse참조 https//docs.python.org/3.3/library/argparse.html Random map생성 버튼 본 과제의 sample그림처럼 각 region의 border를 thick line으로 하여 명확히 구분가능하도록 표시해준다. argparse을 통해 옵 션으로 region의 label도 함께 display이 지정되면, 보드에 region의 label도 함께 출력한다. console화면에는 생성된 random map을 인접리스트형태의 json포맷으로 출력한다. K-coloring 수행 버튼 주어진 CSP solver옵션으로 K-coloring을 수행하여 지도상에서 coloring을 수행한다. 로그 textbox에는 각 CSP solver에서 계산 복잡도와 관련된 정보 및 최종 결과를 출력한다. 만약 해를 찾을 수 없으면 Not found를 콘솔과 log에 출력한다. Save 버튼 생성된 random map을 인접리스트형태의 json포맷으로 파일로 저장하고, K-coloring결과에 대해서도 각 region label별 color값의 mapping 정보를 json형태로 출력하여 저장한다. argparse을 통해 옵션으로 저장될 파일의 default directory를 선택하도록 한다. Log 텍스트박스 기술했듯이, 각 CSP solver에서 계산 복잡도와 관련된 정보 및 최종 결과를 출력하면 된다. Backtracking은 explored nodes의 수, Local search의 경우 local steps의 시행 횟수를 출력하고, K-coloring결과에 대해 각 region label별 color값의 mapping정보를 json형태로 출력한다. (기타 도 움이 될만한 추가 정보 출력 권장) 7
1.8 구현 내용 요약 Arc consistency 구현 arc consistency 구현 및 위의 region graph등을 포함한 sample graphs상에서 테스트 Backtracking search 구현Backtracking search 구현 및 위의 region graph 등을 포함한 sample graphs상에서 테스트. 각 테스트별 Arc consistency유 무에 따른 explored nodes수의 비교 Local search 구현Local search 구현 및 위의 region graph등을 포함한 sample graphs상에서 테스트 및 실험. 마찬가지로, 각 테스트별 Arc consistency유무에 따른 local steps수의 비교 CSP solver 테스트 인접리스트 그래프상 World country graph (또는 추 가 데이터)에서 4종류의 CSP solver 비교 (arc consistency적용 유무, backtracking search vs. local search) CSP solver 통합 위의 내용을 모두 통합하여 Pygame과 PGU에 기반한 GUI환경의 CSP solver프로그램 작성. random map생성 버튼 클릭시, map은 지역으로 구분. K-coloring버튼 클릭시, K-coloring수행하여 visualization. 사용자는 옵션으로 CSP solver의 종류 및 K를 선택할 수 있음. 1.7절의 상세 요구사항 참조 K-coloring에 대한 보다 상세한 자료는 다음을 참조하시오. - https//www.sciencedirect.com/science/article/pii/s0305054805002315 - https//www.jair.org/index.php/jair/article/view/10459 - http//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.7559&rep=rep1&type=pdf 2 제출 내용 및 평가 방식 코드는 python으로 본 과제 결과물로 필수적으로 제출해야 내용들은 다음과 같다. 코드 전체 테스트 결과 각 내용별 테스트 코드 및 해당 로그 또는 출력 결과. 결과보고서 구현 방법을 요약한 보고서. 본 과제의 평가항목 및 배점은 다음과 같다. 각 세부내용의 구현 정확성 및 완결성 (80점) 코드의 Readability 및 쳬계성 (10점) 결과 보고서의 구체성 및 완결성 (10점) 8