스튜어드 러셀의 인공지능을 읽어보자(11) : 비결정론적 동작들을 수반한 검색

https://startagainbornagain.tistory.com/96

스튜어드 러셀의 인공지능을 읽어보자(10) : 모의정련

비결정론적 동작들을 수반한 검색

6번 에서는 환경이 완전히 관찰 가능하고 결정론적이며 에이전트는 자신의 각 동작의 효과를 정확히 안다고 가정했었습니다 그런 가정하에서 에이전트는 임의의 동작열로부터 어떤 상태가 나오는지 게산할 수 있으며, 자신이 어떤 상태에 있는지도 항상 알 수 있었습니다. 각 동작 이후 에이전트의 지각들은 새로운 정보를 전혀 제공하지 않습니다(물론 에이전트에게 초기 상태를 말해주긴 합니다.)

 

한 문제의 해답은 고정된 동작열이 아니라, 향후 받을 지각에 따라 어떤 동작을 수행할 것인지를 명시한 하나의 우발적 계획(contigency plan)입니다. 이를 전략(strategy)이라고 부르기도 합니다. 이번 파트에서는 비결정론적 환경을 살펴봅니다. 부분 관찰 가능성은 나중에 이야기 하고요!

 

변덕스러운 진공청소기 세계

https://www.costco.co.kr/Appliances/Home-Appliances/Vacuums/Samsung-POWERmotion-Vacuum/p/619620

진공청소기 세계를 예로 다시 들어보겠습니다. 동작은 Left, Right, Suck 세 가지이고, 목표는 모든 먼지를 빨아들이는 것입니다. 환경이 관찰 가능하고 결정론적이며 완전히 알려졌다면 이 문제는 6장, 7장에서 했었던 알고리즘들로 간단히 풀 수 있으며 그 해답은 하나의 동작열이 됩니다. 

 

이번에는 강력하지만 변덕스러운 진공청소기의 형태로 비결정론을 도입해 봅시다. 변덕스러운 진공청소기 세계에서 Suck 동작은 다음과 같이 작동합니다. 

• 더러운 칸(사각형)에서 이 동작은 해당 칸의 먼지를 치우되, 가끔은 인접한 칸의 먼지도 치운다.
• 깨끗한 칸에서 이 동작은 가끔 카펫에 먼지를 쏟아 붓는다.

이 문제의 엄밀한 형식화를 위해서는 전이 모형(transition model) 개념을 일반화 할 필요가 있습니다.

전이 모형을 상태 하나만 돌려주는 Result 함수로 정의하는 대신, 가능한 결과 상태들의 집합을 돌려주는 Results 함수를 사용하기도 합니다.

 

또한 문제의 해답이라는 개념도 일반화 해야합니다. 예를 들어 상태 1에서 시작한다면, 어떤 하나의 동작열로 문제를 풀 수는 없습니다. 대신 다음과 같은 형태의 우발적 계획이 필요합니다.

 

즉 비결정론적 문제의 해답에는 중첩된 if-then-else 문들이 포함 될 수도 있습니다.

 

AND - OR 검색 트리

검색트리를 구축하는 것으로 시학하여 분기가 일어나는 노드가 OR 환경의 선택에 의해서 동작의 결과는 AND 노드라고 부릅니다.

 

반복 시도

보통의 진공 청소기 세계와 같되 가끔 이동이 실패해서 에이전트가 같은 장소에 머무르게 된다는 점이 다른 '미끄러운' 진공청소기 세계를 생각해 보자. 예를 들어 상태 1에서의 Right 동작은 상태으로 이어집니다. 

 

순환 해답의 정의가 주어졌을 때, 그러한 해답을 실행하는 에이전트는 언젠가는 목표에 도달하게 됩니다. 단, 여기에는 비결정론적 동작의 모든 결과가 언젠가는 발생한다는 가정이 깔려 있습니다.

 

 

오늘은 여기까지고요 다음에는 부분 관찰 가능 환경의 검색에 대해 알아보도록 합시다.