인공지능
-
[인공지능] Tree structured CSP인공지능 2020. 12. 5. 21:32Tree structured CSP Constraint tree : 모든 변수에 대해서 임의의 두 변수를 잇는 경로가 1개만 존재하는 Graph Tree structured CSP 는 변수의 개수 n에 대해 선형시간에 해결 가능 DAC(Directed Arc Consistency) 변수 X 가 X1, X2, X3, … , Xn 순서로 나열되어 있을 때 i < j 인 모든 i, j에 대해서 Xi 가 Xj 에 대해 arc consistent 하다면 DAC Tree 는 변수들간의 순서를 정해주기 편리함 Topological sort (위상정렬) 아무 변수나 Root 로 지정하고, 상하관계를 만들어주는 단순한 방식 B 를 Root 로 선정한 방식 Time complexity : O(n) 이렇게 만들어진 Topo..
-
[인공지능] CSP Backtracking 탐색인공지능 2020. 12. 5. 20:36Backtracking search d : Domain 의 개수 n : 변수의 개수 d^n 개의 leaf node 수가 필요 Backtracking : DFS 방식으로 searching 하다가 오답임이 확정되면 더 깊이 들어가지 않고 돌아 나오는 기법 문제에 특화된(specific) heuristic 이 아닌 일반적인 heuristic 이 사용됨 값이 할당되지 않은 변수를 찾을 때 사용하는 hueristic SA 를 해결할까? Q를 해결할까? 고민하는 단계를 말함 MRV(Minumum-Remaining-Values) heuristic : fail first 변수에 들어갈 수 있는 Domain 의 수가 몇개 안남아서 실패를 빨리 찾게해주는 기법 Degree heuristic 차수(연결된 간선의 수) 가 높..
-
[인공지능] Path consistency, K-consistency인공지능 2020. 12. 5. 20:16Path Consistency 3개의 변수가 관련된 consistency 로 arc consistency 의 문제점을 해결하기 위해 등장 Arc-consistency 의 문제점 Map coloring 문제를 2개의 color 만으로 해결하는 문제로 축소시켰을 때 이 문제는 답이 없음 답이 없는 경우 AC-3 알고리즘이 Domain 을 다 없애주어야하지만 그러지 못한다는 문제가 있음 ← AC3 알고리즘이 아무것도 하지 않음 Path consistency 정의 Xi 와 Xj 에 값을 할당한 상태에서 {Xi, Xm}, {Xm, Xj} 를 만족하며 Xm 에 할당할 수 있는 값이 있다면 {Xi, Xj} 는 Xm 에 path consistent 함 모든 X 가 path consistent 하다면 해당 CSP 는 p..
-
[인공지능] Local consistency인공지능 2020. 12. 5. 19:29Constraint propagation 변수에 들어갈 수 있는 domain 의 수를 줄임으로서 탐색공간의 축소로 이어짐 constraint propagation 은 search 전에 전처리로 사용되거나 search 중간 중간에 이루어지는 경우가 많음 Local Consistency Node consistency 한 변수의 Domain 전체가 Unary constraint 를 만족한 경우 예를 들어 “A 는 짝수이다.” 라는 constraint 가 있었는데 여기에 “A 는 2가 아니다.” 라는 unary constraint 가 추가된 상황 이 때 “A 는 짝수이다.” 라는 constraint 가 변하지 않고 있으면 node consistency 하지 않은 것이고, “A는 2가 아닌 짝수이다.” 라고 변한..
-
[인공지능] CSP 문제인공지능 2020. 12. 5. 16:51Factored state representation 기존에는 state 가 atomic 하게 표현되었다면 지금부터는 state 를 변수로 표현하는 문제에 대해 다룰 것입니다. 이러한 문제를 CSP(Constraint Satisfaction Problem) 이라고 합니다. state 가 제약조건(Constraint)을 만족하는지 검색하는 것 CSP 는 General-purpose heuristic 이 존재함 : 일반화된 heuristic CSP 문제 정의법 X : 변수 집합 D : 도메인 집합 C : 제약조건 집합 Ci = scope : 제약 조건에 관련된 변수들 rel : 변수들 간의 relation(관계) 예시 : X1 이 A이면, X2 는 B이고, X1이 B이면, X2는 A 이다. State : 할..
-
[인공지능] Game AI 이론인공지능 2020. 12. 5. 16:28Game Multiagent Competitve environment : Contingencies(if-else) Deterministic : 바둑, 체스처럼 Action 에 의한 state가 결정적임. Nondeterministic : 주사위게임처럼 주사위를 던진다는 행위만으로는 다음 state 가 결정적이지 않음 Turn-taking : 턴제 게임 Two-ply : 한 플레이어가 한 턴에 한 번씩만 action Zero-sum : 누군가 이기면(+1) 누군가는 짐(-1) → 합계가 0임, 내가 비기면(0) 상대도 비김(0) perfect-information : 게임에 필요한 모든 정보를 제공 게임의 가장 큰 문제는 search space 가 지나치게 크기 때문에 모든 경우의 수를 고려하여 최적을 알..
-
[인공지능] Partial observable search인공지능 2020. 12. 3. 22:40Partial observation(Local sensing) 지금까지의 vacuum problem 또한 partial observation 임. 옆 방의 dirty 정보를 알 수 없기 때문 따라서 [A, Dirty] percept 가 있으면 1, 3 상태 모두 가능함 → Belief state {1, 3} 을 initial state 로 갖는 문제로 재정의 → 기본적인 방법은 No observation 과 동일 b 는 slippery world 로, vacuum agent 가 움직이는데에 실패할 수 있음 belief state 에서 각 state 마다 적절한 action 을 취함 Initial percept : [A , Dirty] Initial belief state : {1, 3}, Solution..
-
[인공지능] No observation searching인공지능 2020. 12. 3. 22:09No observation searching percept 가 없음 이러한 문제를 Sensorless 또는 conformant 문제라고 함 Sensorless vacuum cleaner 현재 청소기가 어느 방에 있는지, 방이 깨끗한지 더러운지 알 수 없음 initial state : {1,2,3,4,5,6,7,8} → 이 모든 state 가 belief state After “Right” : {2,4,6,8} After “Suck” : {4, 8} Solution : { Right, Suck, Left, Suck } 현재 state 는 알 수 없지만 Action 으로서 belief state 의 수를 줄여나가는 것이 핵심 Fully observable problem 에서 Sensorless problem..