스튜어드 러셀의 인공지능을 읽어보자(6) : 검색을 통한 문제 해결

안녕하세요! 다시 돌아온 인공지능 시간입니다. 저번 글을 읽지 않으셨다면 

startagainbornagain.tistory.com/73

스튜어드 러셀의 인공지능을 읽어보자(5) : 환경의 속성과 에이전트의 종류

읽고 오시면 좋을 거 같아요!

 

검색을 통한 문제 해결

저번 장들에서는 논의한 가장 단순한 에이전트는 상태 -> 동작으로의 직접적인 사상(mapping)에 기초해서 동작을 선택하는 반사 에이전트였습니다. 그런 에이전트들은 여러 환경에 적응하지 못하는데 상태 - 동작 사상이 저장할 수 없을 정도로 크고, 학습 역시 너무 오래 걸릴 것이기 때문입니다.

 

반면 목표 기반 에이전트(Goal Based Agent)미래의 동작들과 해당 결과들의 적합도를 고려합니다.

이번에는 목표 기반 에이전트인 문제 해결 에이전트(problem-sovling agent)를 설명합니다. 이 에이전트 보다 진보한 분해된 표현이나 구조적 표현을 사용하는 목표 기반 에이전트를 흔히 계획 수립 에이전트(planning agent)라고 부릅니다.(나중에 자세히 다뤄볼게요!)

 

이번 장에서는 문제(problem)와 해답(soluton)을 엄밀하게 정의하고 그 정의들을 이해하는 데 도움이 되는 예제 몇 가지를 제시하는 것으로 문제 해결에 대한 논의를 시작합니다. 특히 정보가 없는(uninformed)검색 알고리즘 그 어떤 문제도 풀 수 있는 알고리즘도 존재하나 문제를 효율적으로 풀 수 없습니다., 또 반대로 정보가 있는(informed) 알고리즘은 해답이 있을 만한 곳에 힌트가 주어지면 상당히 효율적으로 문제를 풀 수 있습니다.

 

문제 해결 에이전트

에이전트가 목표(goal)을 정하고 그 목표를 달성하기 위해 행동한다면 그러한 최대화를 달성하기가 좀 더 간단해지는 경우가 있습니다. 그럼 왜 에이전트에게 목표가 필요할까요? 

루마니아 주 자료 출처(위키백과)

루마니아 도시 아라드에서 한 에이전트가 관광을 즐기고 있다고 상상해봅시다.

루마니아 아라드 출처: 위키백과

이 에이전트는 이제 부카레스트에서 비행기를 타고 떠나야 하며 해당 항공권은 환불이 안된다고 합니다.

이 경우 에이전트는 부카레스트에 도달하는 것을 목표가 되는 것이 합리적입니다.

목표가 생기면 에이전트가 달성하고자 하는 목적들이 제한되며, 따라서 고려행 할 동작들도 제한됩니다.

결과적으로 행동을 조직화하기가 쉬워지며 현재 상황과 에이전트의 성과 측정에 기초한 목표 형식화(goal formulation)는 문제 해결의 첫 단계입니다.

 

만약 우리가 한 발짝씩 가는걸 한 단계라고 생각합시다. 그러면 우리가 목표까지 도달해야할 단계가 몇 개일까요? 네 그런 세부 수준에서는 세계가 너무 불확실해서 해답을 구성하는 단계들이 너무 많아질 것이기 때문에 주저진 목표를 달성하기 위해 고려할 동작들과 상태들을 결정하는 공정을 문제 형식화(problem formulation)라고 부릅니다.

 

이제 차를 타고 공항까지 가는데 여러 도시를 지나야 한다면 그리고 어디가 가장 빠른지 모른다면(미지라면)? 그냥 가능한 동작 중 하나를 무작위로 선택하는 수 밖에 없습니다. 

 

잘 정의된 문제와 해답

형식적으로 문제(problem)를 다음 다섯 요소로 정의 할 수 있습니다.

 

• 에이전트가 시작하는 초기 상태(initial state)
• 에이전트가 할 수 있는 동작들의 서술. 특정 상태 s가 주어졌을 때 Action은 s에서 에이전트가 할 수 있는 동작들의 집합을 돌려준다. 이러한 동작들 각각을 s에서 적용 가능(applicable))한 동작이라고 칭한다.
• 각 동작이 하는 일에 대한 서술. 이것의 공식적인 이름은 전이 모형(transition model)이다. 전이 모형은 함수 RESuLT(s,a)로 명시되는데, 이 함수는 상태 s에서 동작 a를 수행해서 나온 상태를 돌려줌 또한 후행자(successor)라는 용어도 사용한다 후행자는 주어진 상태에서 하나의 동작으로 도달할 수 있는 임의의 상태를 말한다
• 초기상태, 동작들, 전이 모형의 조합은 문제의 상태 공간(state space)을 암묵적으로 정의한다. 상태 공간이란 초기 상태에서 시작해서 임의의 동작열을 통해 도달할 수 있는 모든 상태의 집합이다. 상태 공간은 노드가 상태이고 노드들 사이의 링크가 동작인 유향 네트워크(directed network), 즉 그래프를 형성합니다.

네 일단 오늘은 여기까지고요 루마니아 여행기로 설명이 되어있어서 저도 루마니아로 그대로 써봤습니다 공항까지 가는데 하나의 경로(path)가 있고요 주어진 상태가 목표 상태인지 판정하는 목표 판정(goal test) 경로에 대한 비용이드는 경로 비용(path cost)과  단계비용(step cost)이 있습니다.

 

다음에는 문제 형식화에 대해 알아보도록 하겠습니다.