전체 글
-
[인공지능] 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..
-
[인공지능] And-Or Tree인공지능 2020. 12. 3. 00:09Partially observable, Nondeterminitic world Partially observable : state 의 정보가 전부 다 주어지지 않는 문제 주어지는 percept 를 통해서 가능한 state 의 경우의 수를 줄이는데 큰 도움을 줌 Nondeterministic : state 가 action 을 취했을 때 다음 state 가 확정적이지 않음 (확률적으로 결정) percept 를 통해 다음 state 가 무엇인지 알려줌 Contingency plan : state 가 확률적으로 정해질 때 상황에 따라 대응이 달라지는 것 (if-else) : agent 가 만나는 percept 에 따라 action 이 바뀜 Erratic Vacuum World 더러운 방을 suck 하면 현재 방..
-
[인공지능] Genetic 알고리즘 (유전 알고리즘)인공지능 2020. 12. 2. 23:52Genetic Algorithm (유전 알고리즘) Stochastic beam search 의 변형 current state 에 action 을 취함으로서 successor를 만들어내는 Stochastic beam search 와는 달리 두 개의 state 를 합침으로서 새로운 successor를 생성 Population : k 개의 랜덤 생성된 state Individual : 각 state individual 은 string 으로 표현됨 Next Population 의 생성 랜덤으로 생성된 k(여기선 4)개의 state(population) 에 대해 fitness function 으로 평가 평가 점수가 높을 수록 부모로 선택될 확률이 높으며 부모로 선택되면 이들끼리 crossover 되며 offspr..