계획하는 에이전트

(Agents That Plan)

인공지능-지능형 에이전트를 중심으로 : Nils J.Nilsson 저서, 최중민. 김준태. 심광섭. 장병탁 공역, 사이텍미디어, 2000  (원서 : Artificial Intelligence : A New Synthesis 1998), Page 121~130 

기억 대 계산 (Memory Versus Computation)

상태공간 그래프 (State-Space Graphs)

명시적인 상태공간의 탐색 (Searching Explicit State Spaces)

특징기반 상태공간 (Feature-Based State Spaces)

그래프 관련 용어 (Graph Notation)

참고문헌 및 토론 (Additional Readings and Discussion)

기억 대 계산

반응형 에이전트 (reactive agent, 그림 2.2, 5.1, 5.3) 의 행동 함수 (action function) 에는 계산하는 부분이 거의 없다. 본질적으로 이들 에이전트의 행동은 에이전트의 설계자에 의해 결정되어 있거나, 학습 또는 진화 과정에 의하여 선택된다. 행동 함수는 주어진 특징 벡터에 대한 행동을 규정하는 테이블이나 생성 규칙 또는 조합형 논리회로 등으로 구현될 수 있다. 이러한 구현 형태는 컴퓨터 과학의 고전적인 공간시간 절충 (space-time tradeoff) 의 공간쪽 끝에 해당하는 것이다. 즉 이러한 방법은 설계자의 지식을 그대로 옮겨 놓는 공간기반, 또는 기억기반 (memory-based) 의 구현이라고 할 수 있다.

복잡한 환경에서 복잡한 임무를 수행해야 하는 반응 기계는 방대한 양의 메모리를 필요로 하게 된다. 더구나 그러한 반응 기계의 설계자는 모든 가능한 상황에 대한 적절한 반응을 고려하는 초인적인 예측력을 가져야 한다. 따라서 우리는 시간보다 공간을 중시하고 명시적인 설계보다 적응하는 것을 고려하게 되었다. 우선 행동함수에 반응 기계의 설계자가 수행해야 할 계산의 일부를 도입하기로 하자. 물론 이러한 계산은 시간이 걸리지만 이렇게 함으로써 설계자의 부담을 덜고 에이전트의 필요한 메모리 양을 줄일 수 있다.

우리가 고려할 수 있는 계산 중 하나는 어떤 주어진 상황에서 수행 가능한 행동들의 결과를 예측하는 것이다. 물론 반응 기계의 설계자는 이러한 예견되는 결과를 기반으로 설계해야 할 것이다. 설계자 (또는 학습 과정) 는 여전히 어떤 계산을 해야 하는지 명시하여야 하지만, 이러한 계산을 수행하는 프로그램은 일반적으로 모든 결과를 저장하는 것보다 훨씬 적은 양의 메모리를 필요로 한다. 또한 설계자에게는 모든 가능한 상황에 대하여 계산을 미리 수행하는 것보다 계산 방법을 명시하는 것이 쉬울 것이다. 아마도 가장 중요한 것은 만일 이러한 결과-예측 계산이 자동적으로 학습될 수 있다면 에이전트는 설계자가 미리 예측할 수 없었던 환경에서도 적절한 행동을 선택할 수 있을 것이란 점이다.

행동에 대한 결과를 예측하려면 에이전트는 자신이 존재하는 세계에 대한 모델과 자신의 행동이 그러한 세계에 미치는 영향에 대한 모델을 가지고 있어야 한다. 그렇게 되면 일련의 행동들은 시뮬레이션을 통하여 안전하고 효과적이라는 것이 밝혀질 때까지 실제적으로 취해질 필요가 없는 것이다.

상태공간 그래프

예를 들어 A, B, C 세 개의 장난감 블록이 바닥에 놓여 있는 격자공간으로 구성된 세계를 생각해 보자. 로봇이 수행해야 할 임무는 A 는 B 위에, B 는 C 위에, 그리고 C 는 바닥에 있도록 블록을 쌓는 것이라고 하자. 우리에게는 어떤 행동들이 수행되어야 하는지 명백하지만, 로봇에게는 그렇지 못하다. 로봇이 각각의 행동이 주변 환경에 미치는 영향에 대한 모델을 가지고 있다고 하자. 이들은 행동이 취해지기 전의 상태를 나타내는 모델과 행동이 취해진 후의 상태를 나타내는 모델의 쌍으로 나타낼 수 있다. 이 예에서 로봇은 다른 블록이 위에 있지 않은 어떤 블록 를 바닥이나 또는 다른 블록이 위에 있지 않은 블록의 위 로 이동할 수 있다고 하고, 이러한 일련의 행동들을 move 라는 스키마 (schema) 의 사례 (instance) 로 모델링하자. 여기서 는 A, B 또는 C 가 될 수 있고, 는 A, B, C 또는 Floor 가 될 수 있으며, 이 스키마의 어떤 사례 (예를 들어 move(A, A)) 는 수행 가능하지 않은 행동을 나타내게 된다. 이러한 스키마의 사례를 연산자 (operator) 라고 한다. 즉 연산자는 행동의 모델이다.

그림 1 블록을 이동한 결과

그림 1 에 모든 블록들이 바닥에 있을 때 취해질 수 있는 행동들의 이러한 모델에 의한 결과를 나타내었다 (알아보기 쉽도록 각각의 상황을 그림으로 나타내었다. 네모 그림은 사람이 알아보기 쉽게 하기 위한 것이고, 리스트 표현은 리스트 처리 에이전트를 위한 것이다). 결과 중에서 ((AB) (C)) 와 ((A) (BC)) 가 다른 결과들에 비하여 목표 ((ABC)) 에 더 가깝게 생각된다. 따라서 단일 행동에 대한 예측되는 결과만을 고려한다면 로봇은 move(A, B) 나 move(B, C)를 다른 행동보다 선호할 것이다. 물론 로봇은 아직 실제 행동을 취하지는 않은 상태이다.

시뮬레이션을 통하여 한 단계 앞을 보는 것만으로도 유용한 예측을 할 수 있으며, 몇 단계 앞 혹은 임무가 완료될 때까지의 모든 단계를 미리 본다면 지름길을 찾을 수도 있고, 맹목적으로 진행하는 것을 피할 수도 있다. 여러 가지 선택 가능한 순차적인 행동들의 결과를 기억해 두기 위한 가장 효과적인 자료 구조는 방향성 그래프 (directed graph) 이다. 에이전트가 일련의 행동을 취하여 만들어낼 수 있는 세계들은, 각 상황의 표현을 노드 (node) 로 하고 연산자를 아크 (arc) 로 하는 방향성 그래프로 나타낼 수 있다 (이 장에서 사용되는 그래프 이론의 용어와 개념들은 나중에 정식으로 정의할 것이다). 그래프 노드는 아이콘 (icon) 또는 특징 (feature) 들을 기반으로 표현할 수 있다. 두 가지 형태를 모두 고려하겠지만, 우선 아이콘으로 표현하기로 하자.

만일 서로 다른 상황의 수가 충분히 작다면 모든 가능한 행동과 상황을 나타내는 그래프가 명시적으로 구성될 수 있을 것이다. 예를 들어 그림 2 는 세 개의 블록을 다루는 데 있어서의 모든 상황과 행동을 나타낸다. 이러한 실세계 모델과 행동들의 그래프를 상태공간 그래프 (state-space graph) 라고 한다. 그림을 단순화하기 위하여 노드 사이의 반대되는 두 행동 중 하나만을 나타내었지만 각 행동들은 역으로도 할 수 있는 것이다. 이 그래프로부터 만일 초기 상황이 ((A)(B)(C)) 라는 표현으로 주어지고, 주어진 임무는 ((ABC)) 라고 표현되는 상황을 만드는 것이라면 로봇은 {move(B, C), move(A, B)} 라는 순차적인 행동을 수행해야 한다는 것을 쉽게 알 수 있다.

가능한 세계들을 그래프로 표현함으로써 얻을 수 있는 장점은 그래프 안의 어느 노드도 목표 상황-사람과 같은 외부 요소에 의해 명시된-을 나타낼 수 있다는 것이다. 이러한 임무 설정의 유연성은 우리가 지금까지 보아온 단일 용도의 에이전트와는 대조적인 것이다. 설정된 목표를 이룰 수 있는 행동들을 찾기 위하여 로봇은 단지 그래프 안에서 초기 상태를 표현하는 노드 (시작노드, start node) 로부터 설정된 목표 상태를 나타내는 노드 (목표노드, goal node) 까지의 경로 (path) 를 찾으면 된다. 목표를 이루기 위한 행동들은 찾아진 경로상의 아크로부터 읽어들이면 되는 것이다. 예를 들어, 로봇에게 주어진 임무가 바닥 위에 A, B, C 순으로 블록을 쌓는 것이고, 초기 상태가 바닥 위에 C, B, A 순으로 블록이 쌓여 있는 것이었다면, 필요한 행동 순서는 {move(A, Floor), move(B, A), move(C, B)} 가 될 것이다. 그림 2 의 그래프를 보고 이러한 경로를 찾는 것은 사람에게는 쉬운 일이다. 그러나 에이전트는 이러한 경로를 찾기 위하여 다양한 그래프 탐색 (search) 방법을 사용하여야 한다.

그림 2 상태공간 그래프

목표까지의 경로에 있는 아크상의 연산자들을 하나의 순서 (sequence) 로 만든 것을 계획 (plan) 이라고 하며, 이러한 순서를 찾는 것을 계획수립 (planning) 이라고 한다. 어떤 행동 순서의 결과로 나타나는 상태의 순서를 예측하는 과정을 투영 (projecting) 이라고 한다. 물론, 목표를 이루기 위하여 이러한 방법으로 찾아진 일련의 행동을 수행하기 위해서는 몇 가지 가정이 필요하다. 에이전트는 모든 가능한 상황들을 그래프의 노드로 표현할 수 있어야 하며, 각 상태 사이에 어떠한 행동이 취해져야 하는지에 대한 정확한 모델이 있어야 한다. 로봇의 행동은 항상 이 모델에 맞게 작용해야 하며, 로봇 팔에 미끄러짐이나 오차가 있어서는 안된다. 에이전트의 인식 시스템은 정확하게 시작 노드를 인식해야 한다. 또한 주변의 상태를 변화시키는 다른 에이전트나 동적인 작용이 있어서는 안된다. 만일 이러한 모든 가정이 성립하고, 목표 상태를 탐색하기 위한 충분한 시간이 주어진다면, 목표를 달성하기 위한 완전한 행동 순서가 주변 환경에 대한 감지 피드백 (sensory feedback) 없이도 계획되고 수행될 수 있다.

이러한 가정들이 대부분의 실제 응용에서는 성립되지 않지만, 그래프 탐색에 의한 계획 방법은 매우 유용하며 중요한 모델이다. 이 방법은 조금 더 일반화하여 앞에서 언급한 가정들이 일부 완화된 환경을 만들거나, 그러한 환경에 적응하는 시스템의 한 부분으로 포함될 수 있다. 이 문제에 대해서는 계획, 행동 그리고 학습에서 다시 다룰 것이다. 이 장에서는 그래프에서 경로를 탐색하는 문제를 그래프 전체가 미리 저장되어 있는 경우에 쓸 수 있는 매우 단순한 탐색 과정으로 설명하였다. 보통 이런 경우에는 그래프가 충분히 작기 때문에 효율적인 탐색 기법에 대해 크게 신경쓸 필요가 없다. 다음의 두 장에서는 미리 저장해 놓을 수 없을 정도로 매우 크며, 따라서 효율적인 탐색을 수행해야만 하는 방대한 그래프에 적용할 탐색 기법들에 대해 설명할 것이다.

명시적인 상태공간의 탐색

명시적인 (explicit) 그래프의 탐색 기법은 그래프 노드를 따라 마커 (marker) 를 전달하는 것과 같다. 우선 시작 노드를 0 이라고 하고, 목표 노드를 만날 때까지 아크를 따라 물결이 번지듯이 연속적으로 다음의 정수를 노드에 지정해 나간다. 그리고 나서 목표 노드에서부터 시작 노드까지 역으로 숫자가 감소하는 순서로 경로를 찾는다. 이렇게 찾아진 시작 노드에서 목표 노드까지의 경로상에 있는 행동들이 바로 목표를 이루기 위하여 취해야 하는 행동들이 된다. 이러한 방법은 그래프 안에 노드의 개수를 이라 할 때 스텝이 걸리게 된다 (만일 목표 노드가 하나라면 이 과정은 목표 노드에서 시작하여 시작 노드에서 끝나도록 역방향으로 구현할 수도 있다). 이러한 과정에 의하여 노드에 지정된 정수들은 시작 노드에 전역 최소값 (global minimum) 이 있는 인공적인 전위 함수 (potential function) 라고 할 수 있다. 그러면 목표에서 시작까지의 역경로는 이 함수의 기울기 (gradient) 를 따라 존재하게 된다.

그림 3 탐색의 단계

((BAC)) 를 ((ABC)) 로 변환하는 문제에 대한 마커 전달 과정이 그림 3 에 나타나 있다. 이 방법은 너비우선 탐색 (breadth-first search) 에 해당하며 Moore[Moore 1959] 에 의해 처음 제안되었다.

어떤 노드의 자식 노드들에 마커를 표시하는 것을 노드의 확장 (expansion) 이라고 한다. 확장을 하면 마커가 있는 노드의 마커가 있지 않은 모든 이웃 노드에 마커를 표시하게 된다. 여기서 중요한 문제는 마커가 노드들 중에서 어떤 노드를 다음으로 확장할 것인가 하는 것이다. 너비우선 탐색에서는 아직 확장되지 않은 노드들 중에서 가장 작은 값을 가진 노드를 확장한다. 즉 라면, 로 표시된 노드들을 확장하기 전에 로 표시된 모든 노드들을 먼저 확장하는 것이다. 다른 탐색 방법들은 다른 방법으로 노드 확장 순서를 결정한다. 여기에 대해서는 나중에 더 자세히 언급할 것이다.

특징기반 상태공간

노드를 나타내기 위하여 아이콘 모델을 사용하면 상태 공간을 설명하는 것이 매우 간단하였다. 각 상태에 어떤 행동을 취하였을 때의 결과를 쉽게 시각화할 수 있었다. 그래프의 각 노드를 특징 (feature) 들로 나타내도록 그래프를 정의할 수도 있으며, 이때에는 각 행동이 특징들을 어떻게 변화시키는지를 표현하는 방법이 필요하다. 이러한 결과를 표현하기 위한 한 방법으로 STRIPS[Fikes & Nilsson 1971, Fikes, Hart, & Nilsson 1972] 라는 시스템이 소개되었다. 기본적인 아이디어는 연산자를 세 개의 리스트로 표현하는 것이다. 첫째, 전제조건 리스트 (precondition list) 는 특정 행동이 적용되기 위하여 1 의 값을 가져야 하는 특징들과 0 의 값을 가져야 하는 특징들을 지정한다. 둘째, 삭제 리스트 (delete list) 는 행동이 취해진 후 1 에서 0 으로 값이 바뀌어야 하는 특징들을 지정한다. 셋째, 추가 리스트 (add list) 는 행동이 취해진 후 0 에서 1 로 값이 바뀌어야 하는 특징들을 지정한다. 삭제 리스트나 추가 리스트에 언급되어 있지 않은 특징의 값은 바뀌지 않는다. 이 세 가지 리스트가 행동의 결과를 표현하는 STRIPS 연산자가 된다. 특징기반 공간에서 STRIPS 사용하는 방법에 관한 논의는 나중에 특징에 관련된 연산을 위한 보다 유력한 기법을 소개한 뒤에 하기로 하겠다.

그림 4 신경망에 의한 특징 벡터의 예측

시간 에서의 특징 벡터와 에서의 행동으로부터 시간 에서의 특징 벡터를 예측할 수 있도록 신경망을 훈련시킬 수도 있다 [Jordan & Rumelhart 1992]. 그림 4 에 이러한 신경망을 나타내었다. 이 그림에는 하나의 계층 (layer) 만을 나타내었지만, 은닉 유닛 (hidden unit) 으로 구성된 중간층 (intermediate layer) 도 사용될 수 있다. 훈련 과정을 거치고 나면 이러한 신경망은 다양한 행동의 결과로 나타날 수 있는 특징 벡터들을 계산해내는 데 이용될 수 있다. 그 결과는 다시 신경망의 입력으로 사용되어 두 단계 앞의 특징 벡터를 예측하는 데 사용될 수 있으며, 같은 방식으로 계속 진행할 수 있다. 통계적 클러스터링 (clustering) 기법을 기반으로 한 이와 비슷한 방법이 이동 로봇을 제어하는 데 사용된 바 있다 [Mahadevan 1992, Connell & Mahadevan 1993a]. 이 방법을 사용하는 경우에는 예측 과정에서의 어쩔 수 없는 오차 때문에 여러 단계 앞을 계획하는 것은 무의미하다고 알려져 있다.

그래프 관련 용어

다음 장에서 방대한 상태 공간을 다루기 위한 기법들을 제시하기 전에, 그래프와 그래프 탐색에 대한 설명을 위해 사용되는 용어들을 정의하는 것이 도움이 될 것이다. 우리가 정의하려는 용어들을 설명하기 위한 그래프와 트리의 예를 그림 5 에 나타내었다.

그림 5 그래프와 트리 용어

그래프 (graph) 는 노드 (node) 의 집합으로 구성된다. 어떤 노드의 쌍은 아크 (arc) 로 연결되어 있으며, 아크는 한 노드에서 다른 노드로 방향성 (directed)을 가지고 있다. 이러한 그래프를 방향성 그래프 (directed graph) 라고 한다. 우리의 경우에는 노드는 현 세계의 상태 (state) 를 나타내고, 아크는 행동 (action) 을 나타낸다. 만일 하나의 아크가 노드 에서 로 연결되어 있다면 이때 노드 를 노드 의 자식 (successor 또는 child) 노드라고 하고, 를 의 부모 (parent) 노드라고 한다. 우리가 다루는 그래프의 경우에는 각 노드는 유한 개의 자식 노드만을 가지고 있다. 한 쌍의 노드는 서로 상대방의 자식일 수도 있다. 이 경우에는 한 쌍의 아크를 하나의 에지 (edge) 로 대치한다. 에지만을 가지고 있는 그래프를 무방향성 그래프 (undirected graph) 라고 한다. 앞으로 나오는 그래프 그림에서 화살표로 표시된 것은 아크 (arc) 를, 그렇지 않은 것은 에지 (edge) 를 나타내기로 하자.

방향성 트리 (directed tree) 는 방향성 그래프의 특수한 경우로, 한 개의 노드를 제외하고 모든 노드가 하나의 부모만을 가지고 있는 것을 말한다. 부모가 없는 하나의 노드를 루트 (root)노드라고 한다. 트리의 노드 중 자식이 없는 노드는 단말 (leaf) 노드라고 한다. 루트 노드의 깊이 (depth) 를 0 이라고 하며, 다른 노드의 깊이는 부모 노드의 깊이 더하기 1 로 정의된다. 무방향성 트리 (undirected tree) 는 무방향성 그래프의 특수한 경우로, 어떤 두 노드 사이에도 유일한 경로가 존재하는 경우를 말한다.
이론적인 분석을 위해 정의되는 트리 중에는 단말 노드를 제외한 모든 노드가 똑같이 개의 자식을 가지는 경우가 있다. 이런 경우 를 그 트리의 분기 계수 (branching factor) 라고 한다.

에 대하여 이 의 자식인 노드의 순서 를 노드 에서 까지의 길이 (length) 인 경로 (path) 라고 한다 (또는 노드를 연결하는 아크의 순서로 경로를 정의할 수도 있다). 노드 에서 까지 경로가 존재하면 가 로부터 접근 가능 (accessible) 하다고 하며, 노드 를 노드 의 후손 (descendant) 이라고 하고, 를 노드 의 조상 (ancestor) 이라고 한다.

경우에 따라서는 어떤 행동을 취하는 데 드는 비용을 나타내기 위하여 아크에 양의 값 (cost) 을 부여하는 것이 편리할 때도 있다. 노드 에서 로의 아크 의 값을 (또는 ) 로 나타내기로 하자. 경우에 따라서는 이 값들이 모두 어떤 아주 작은 양의 수 보다는 크다고 가정할 필요가 있다. 어떤 두 노드 사이의 경로의 값은 그 경로상의 모든 아크의 값을 합한 것이 된다. 어떤 문제에서는 두 노드 사이에 최소 (minimal) 값을 갖는 경로를 찾을 필요가 있다. 이러한 경로를 최적 경로 (optimal path) 라고 한다.

가장 단순한 문제는 초기 상태를 나타내는 노드 에서 다른 상태를 나타내는 노드 까지의 경로를 찾는 것이 될 것이다. 조금 더 유용한 문제는 노드 에서 목표 조건 (goal condition) 을 만족하는 노드들의 집합에 포함되는 어느 한 노드까지의 경로를 찾는 것이다. 이러한 노드의 집합을 목표 집합 (goal set) 이라고 하며, 이 집합 안의 각 노드를 목표 노드 (goal node) 라고 한다.

그래프가 명시적으로 주어졌을 때 모든 노드에서 어떤 노드 까지의 경로를 찾고자 할 때도 있다. 이러한 경로의 집합은 을 루트로 하는 트리를 형성하며, 이 트리를 그 그래프의 신장트리(spanning tree) 라고 한다 (신장트리가 트리이려면 앞서 언급한 트리의 정의가 약간 수정되어야 한다. 연습문제 2 를 보라).

상태공간을 그래프로 표현하기 때문에, 노드라는 단어를 경우에 따라서 그래프의 노드를 의미하거나, 노드가 나타내는 상태를 의미하거나, 또는 그 상태의 표현 (자료 구조나 특징 집합) 을 의미하는 말로 사용할 것이다. 마찬가지로, 아크라는 단어도 그래프의 아크를 의미하거나, 아크가 나타내는 행동, 또는 그 행동을 표현하는 연산자를 의미할 수 있다.

참고문헌 및 토론

그래프와 그래프 알고리즘에 대한 상세한 내용은 [Cormen, Leiserson, &Rivest 1990, 로봇시각]을 참고하라. 다양한 문제들이 그래프에서의 경로를 찾는 문제로 귀결되므로, 이 장과 다음의 계속되는 장에서 다루는 기법들은 에이전트의 계획 문제뿐 아니라 다른 여러 분야에도 적용될 수 있다.