[논문]3차원 가상환경에서 동작하는 지능형 에이전트의 구조와 경로 찾기 행위

김인철; 이재호

doi:10.3745/kipstb.2003.10b.1.001

문제 정의

첫째는 어떤 이동점을 직접 방문하기 전에는 그 이동점과 인접한 다른 이동점들의 연결상태 즉 부분 경로 그래프를 사전에 알고 있지 못 하다는 점과 둘째는 비록 특정 이동점을 방문해도 이 이동점에 연결된 모든 인접 이동점들을 파악하는 일은 에이전트의 인지범위의 제한을 받는다는 점과 셋째는 찾고자 하는 목표점들의 위치좌표를 알지 못하기 때문에 각 목표점까지의 거리에 대한 아무런 추정치나 휴우리스틱(heuristic) 정 보가 없다는 점, 그리고 마지막으로 이 단계에서는 목표점 의 위치를 파악하는 것이 주된 목적이므로 찾고자 하는 목표점까지 반드시 최단 경로로 도달할 필요가 없다는 점 등 이다. 따라서 본 연구에서는 KGBot의 효과적인 월드 탐색을 위해서 현재 위치에서 인접한 미 방문 이동점과 방문한 지 가장 오래된 이동점들을 우선적으로 탐색해가는 일종의 실시간 깊이-우선 팀.색(Real-time Depth-First Search, RDFS)을 적용하였다.
UM-PRS는 목표-지향 성과 더불어 환경변화에 대한 높은 반응성도 가지고 있으며, 높은 수준에서 에이전트의 행위를 기술할 수 있어 에이전트의 개발과 수정이 용이하다는 장점이 있다. 또한 본 논문에서는 지도상에 흩어져 있는 이동점들을 따라 돌아다니며 숨어있는 목표점들의 위치를 파악하는 행위, 이와 같은 탐색 과정을 통해 자신이 놓여진 월드의 경로 그래프를 효과적으로 작성하는 행위, 끝으로 이렇게 작성된 경로 그래프에 기초하여 목적지까지 최적 경로를 실시간적으로 찾아가는 행위 등 KGBot의 지능행위에 대해 자세히 설명하였다. 그리고 끝으로 서로 다른 3차원 지도상의 실험을 통해 이러한 KGBot의 제어엔진과 경로 찾기 행위의 우수성을 입증하여 보았다.
본 논문에서는 3차원 일인칭 액션 게임을 지능형 에이전 트 연구용 테스트베드로 확장한 Unreal Tournament 게임과 Gamebots 시스템을 소개하였다. 그리고 이들이 제공하 는 3차원 가상환경 안에서 적과 일대일 Domination 게임을 효과적으로 진행해가는 지능형 NPC인 KGB况를 설계하고 구현하였다.
본 논문에서는 KGBot의 월드 탐색 전략인 Rotate & Go 와 제어엔진인 UM-PRS의 효율성을 검증하기 위한 실험을 전개하였다. 먼저 월드 탐색 전략의 효율성 분석을 위해서는 본 논문에서 제안한 Rotate & Go 전략과 단순한 Go & Go 전략간의 비교 실험을 전개하였고, 제어엔진의 효율성 분석을 위해서 는 BDI 제어엔진인 UM-PRS와 순수 반응형(pure reactive) 제어엔진간의 비교 실험을 전개하였다.
본 논문에서는 대표적인 온라인 3차원 일인칭 액션 게임인 Unreal Tournament 게임과 이것에 기초한 지능형 에이 전트 연구용 테스트베드인 Gamebots 시스템을 소개한다. 그리고 이들이 제공하는 3차원 가상환경에서 효과적으로 동작하는 지능형 NPC인 KGBot의 설계와 구현에 대해 설명한다.
KGBot는 범용의 BDI 에이전트 구조인 UM-PRS14]를 제어엔진으로 채용 하고 있으며, 복잡한 행위들을 효과적으로 기술하기 위해 계층화된 지식베이스를 가지고 있다. 본 논문에서는 특히 지도상에 흩어져 있는 이동점들(waypoints)에 대한 제한적인 센 서정보에만 의존하여 자신이 놓여진 월드의 지도를 작성하고, 이동 경로를 찾는 KGBot의 행위에 대해 자세히 설명한다. 그리고 끝으로 서로 다른 3차원 지도상의 실험을 통해 이러한 KGBot의 경로 찾기 행위의 성능을 분석해본다.
본 연구에서는 복잡한 3차원 가상공간에서의 일대일 Dom ination 게임을 위해 UM-PRS 제어엔진과 순수 반응형 제 어엔진 중 어느 쪽이 더 효과적인지 비교하여 보았다. 이를 위해 게임서버로부터 전달되는 실시간 동기 및 비동기 센 서정보에 따라 즉각적으로 행동을 결정하는 순수 반응형 에 이전트를 별도로 구현한 다음, UM-PRS 제어엔진을 채용한 KGBot와 동일한 지도안에서 경쟁하며 일대일 Domination 게임을 하도록 시행하여 보았다.

제안 방법

Purpose 부분은 KA의 몸체부분을 성공적으로 수행했을 때 달성할 수 있는 목표를 나타내고, Context 부분은 해당 KA가 적용될 수 있는 실세계 상황을 명시한다. 그리고 KA가 실행되는 동안 계속해서 이 Context가 만족되는지 점검함으로써 KA가 여전히 적용 가능한지를 확인한다. Body 부분은 KA의 Purpose를 달성하기 위해 필요한 실행 단계들을 achieve, execute, assert 등의 다양한 기본 함수(primitive function)들과 부속목표(sub-goal)들, 그리고 조건부 분기 (conditional branch) 등으로 명시하는 것이다.
본 논문에서는 특히 지도상에 흩어져 있는 이동점들(waypoints)에 대한 제한적인 센 서정보에만 의존하여 자신이 놓여진 월드의 지도를 작성하고, 이동 경로를 찾는 KGBot의 행위에 대해 자세히 설명한다. 그리고 끝으로 서로 다른 3차원 지도상의 실험을 통해 이러한 KGBot의 경로 찾기 행위의 성능을 분석해본다.
또한 본 논문에서는 지도상에 흩어져 있는 이동점들을 따라 돌아다니며 숨어있는 목표점들의 위치를 파악하는 행위, 이와 같은 탐색 과정을 통해 자신이 놓여진 월드의 경로 그래프를 효과적으로 작성하는 행위, 끝으로 이렇게 작성된 경로 그래프에 기초하여 목적지까지 최적 경로를 실시간적으로 찾아가는 행위 등 KGBot의 지능행위에 대해 자세히 설명하였다. 그리고 끝으로 서로 다른 3차원 지도상의 실험을 통해 이러한 KGBot의 제어엔진과 경로 찾기 행위의 우수성을 입증하여 보았다. 계획하고 있는 향후 연구로는 현재까지 구현된 기초적인 지능 행위를 바탕으로 팀별 Domination 게임이나 팀별 CTF 게임과 같은 다중 에이전트 환경에서도 효과적으로 동작하는 KGBot 팀에이전트를 개발하는 것이다.
본 논문에서는 3차원 일인칭 액션 게임을 지능형 에이전 트 연구용 테스트베드로 확장한 Unreal Tournament 게임과 Gamebots 시스템을 소개하였다. 그리고 이들이 제공하 는 3차원 가상환경 안에서 적과 일대일 Domination 게임을 효과적으로 진행해가는 지능형 NPC인 KGB况를 설계하고 구현하였다. KGBot는 범용의 BDI 에이전트 구조인 UM- RS를 제어엔진으로 채용하고 있다.
월드 탐색 전략 비교 실험에서는 각각 다른 탐색전략을 적용하였을때 에이전트가 주어진 지도를 얼마나 효율적으로 탐색하였는지를 알아보기 위해, 지도상에 숨어있는 모든 목 표점 (domination point)들과 그들을 연결하는 경로들의 그래프를 작성하는데 소모하는 총 시간을 측정하여 보았다. 동 일 전략을 각 지도별로 10회씩 반복 실험하여 탐색에 걸린 최대 시간, 최소 시간, 그리고 평균 시간을 비교하여 보았다. 그리고 매 실험마다 월드 탐색 제한 시간을 600초로 설정 하였는데, 600초가 지나도 목표점들을 다 찾지 못한 경우에는 실시간 액션 게임의 특성상 사실상 이미 승패가 판가름 난 상태여서 더이상 탐색을 계속하는 것이 무의미하다卫 판단되어 실험을 멈추었다.
본 논문에서는 KGBot의 월드 탐색 전략인 Rotate & Go 와 제어엔진인 UM-PRS의 효율성을 검증하기 위한 실험을 전개하였다. 먼저 월드 탐색 전략의 효율성 분석을 위해서는 본 논문에서 제안한 Rotate & Go 전략과 단순한 Go & Go 전략간의 비교 실험을 전개하였고, 제어엔진의 효율성 분석을 위해서 는 BDI 제어엔진인 UM-PRS와 순수 반응형(pure reactive) 제어엔진간의 비교 실험을 전개하였다. 그리고 이 실험들에는 각각 (그림 15)(a), (二l림 15)(b), (그림 15)(c)에 나타나 있는 Dom-Stalwait, Dom-Condomrned, Dom-Lead- works 등 복잡도가 서로 다른 세 개의 3차원 지도들이 사 용되었다.
KGBot는 하나의 Java 응용 프로그램으로서, 구성요소 중에서 주로 Gamebots 서버와의 통신을 담당하며 가상 게임 환경과의 인터페이스부를 형성하는 인식부와 행동부는 모 두 Java로 구현된 반면, 계획을 세우고 행동을 결정하는 두뇌부분에 해당하는 의사결정부는 앞서 설명한 BDI 기반의 UM-PRS로 구현되었다. 센서정보의 도달간격과 이것을 바 탕으로 의사결정을 하는 UM-PRS의 추론주기, 그리고 이미 결정된 행동에 대한 명령 메시지를 송신하는 간격 간의 차이를 극복하기 위해 인식부, 의사결정부, 행동부 각각을 별도의 스레드(thread)를 가지고 병행 수행토록 하였다. 즉 인식부는 센서정보가 도착하는 대로 자신의 큐(queue)에 담아두었다가 의사결정부인 UW-PRS의 내부 데이터베이스에 사실(fact) 형태로 직접 입력해주며, UM-PRS의 인터프리터는 자신의 실행주기에 맞추어 이 내부 데이터베이스를 참조하여 수행을 계속한다.
반면에 (그림 15)(b)의 Dom-Condomned와 (그림 15)(c)의 Dom- Leadworks는 계단 위와 아래의 2층으로된 복잡한 공간구 조에 많은 수의 이동점들이 분산되어 있고 곳곳에 용암지 대와 같은 위험 지역들이 놓여 있는 복잡한 지도들이다. 월드 탐색 전략 비교 실험에서는 각각 다른 탐색전략을 적용하였을때 에이전트가 주어진 지도를 얼마나 효율적으로 탐색하였는지를 알아보기 위해, 지도상에 숨어있는 모든 목 표점 (domination point)들과 그들을 연결하는 경로들의 그래프를 작성하는데 소모하는 총 시간을 측정하여 보았다. 동 일 전략을 각 지도별로 10회씩 반복 실험하여 탐색에 걸린 최대 시간, 최소 시간, 그리고 평균 시간을 비교하여 보았다.
이 문제를 해결하기 위해 본 연구에서는 월드 탐색과정의 매 단계마다 한 이동점을 방문한 KGBot는 현재 시야에 들 어오는 인접 이동점들에 국한해서 다음 방문점을 선택하지 않고, 현재 방문중인 이동점에서 다음 이동점으로 이동하기 전에 그 지점에서 스스로 몸을 360도 회전하며 좌우 및 후 방에 놓여 있는 인접 이동점들까지 모두 파악한 후 이들 중 에 아직 방문한 적이 없는 미 방문점을 다음 방문점으로 선택하는 방식을 채택하였다. 본 논문에서는 편의상 전자를 Go & Go 탐색전략, 후자를 Rotate & Go 탐색전략이라 부른다.
본 연구에서는 복잡한 3차원 가상공간에서의 일대일 Dom ination 게임을 위해 UM-PRS 제어엔진과 순수 반응형 제 어엔진 중 어느 쪽이 더 효과적인지 비교하여 보았다. 이를 위해 게임서버로부터 전달되는 실시간 동기 및 비동기 센 서정보에 따라 즉각적으로 행동을 결정하는 순수 반응형 에 이전트를 별도로 구현한 다음, UM-PRS 제어엔진을 채용한 KGBot와 동일한 지도안에서 경쟁하며 일대일 Domination 게임을 하도록 시행하여 보았다. 게임은 어느 한쪽이 제한 점수인 100점을 먼저 취득하여 승리할때까지 계속되었고, 따라서 별도의 게임 제한시간은 설정하지 않았다.
게임은 어느 한쪽이 제한 점수인 100점을 먼저 취득하여 승리할때까지 계속되었고, 따라서 별도의 게임 제한시간은 설정하지 않았다. 제어엔진 간의 비교 실험에서도 앞서 설명한 세 가지 지도들을 사용하 였으며, 각 지도별로 10회씩 실험하여 각 에이전트가 획득한 최대 점수, 최소 점수, 평균 점수들을 비교하였다.
제어엔진 간의 비교 실험 결과는[표 2]와 같다. 표에서 알 수 있듯이 본 연구에서 시행한 모든 실험 게임에서 UM- PRS를 제어엔진으로 채용한 KGBot가 먼저 제한 점수 100 점을 취득함으로써 순수 반응형 에이전트를 이겼다. 또한 지도의 복잡도가 커질수록 두 엔진간의 점수차가 더욱 벌 어진 것을 알 수 있다.
한편 본 연구에서는 동작중인 KGBot의 내부에서 실시간으로 관리되는 자신의 신체정보(위치 값, 위치하고 있는 영 역, 체력), 무기정보, 경로 그래프 정보, 게임상태정보(게임 서버 시간, 팀별 점수) 등을 보여주면서, 동시에 이러한 정보에 기초한 KGBot의 월드탐색 및 이동행위를 시각화하여 보여주는 (그림 14)와 같은 행위 분석 도구를 함께 개발하고 이용하였다. 이와 같은 행위 분석 도구를 이용함으로써 에이전트 설계자나 이용자는 KGBot가 수행되고 있는 외부 환경의 상태 정보와 KGBot의 내부 상태 정보를 비교하면서, KGBot가 현재 목표에 맞는 행위를 정상적으로 수행하 고 있는지를 분석하고 평가할 수 있게 해준다.
한편, 제어엔진의 효율성 분석을 위한 실험에서는 BDI 제어엔진인 U皿-PRS와 순수 반응형(pure reactive) 제어엔 진 간의 비교 실험을 전개하였다. 대표적인 BDI 제어엔진 인 UM-PRS의 특징중의 하나는 목표지향적 (goal-oriented) 추론 능력과 문맥 의존적(context-dependant) 행위이다.

대상 데이터

본 연구에서는 Gamebots 시스템이 제공하는 3차원 가상 환경에서 동작하는 지능형 NPC인 KGBot의 효율적인 구현 을 위해 대표적인 BDI 에이전트 구조인 UM-PRS⑸를 제어 엔진으로 채용하였다. UM-PRS는 목표-지향적인 추론(goal- directed reasoning)과 반응적 행위 (reactive behavior)■& 통 합한 범용의 BDKBelief-Desire-Intention) 에이전트 구조이다.

이론/모형

이러한 실시간 온라인 알고리즘들은 언제나 최 적의 해 경로(optimal solution path)를 보장할 수는 없지만, 전통적인 오프라인 탐색 알고리즘들에 비해 차적의 해 경로 (sub-optimal solution path)를 매우 빨리 찾을 수 있다고 알려져 있다. 본 연구에서 목적지까지 가능한 빨리 도달해야 하는 KGBot의 경우에도 실제 이동에 소요되는 시간뿐만 아니라 이동계획에 소요되는 시간까지 실시간 제약성을 가지므로, 오프라인 탐색 방법인 A*와 IDA* 알고리즘 대신 실시간 온라인 탐색 방법인 LRTA* 알고리즘을 적용하였다. (그림 13)은 월드 탐색을 통해 작성된 부분 경로 그래프를 이용하여 현재 위치의 노드에서 출발하여 목표노드에 도달할 때까지 반복되는 KGBot의 실시간 최단 경로찾기 알고리즘 인 LRTA* 알고리즘을 간략히 표현하고 있다.
따라서 본 연구에서는 KGBot의 효과적인 월드 탐색을 위해서 현재 위치에서 인접한 미 방문 이동점과 방문한 지 가장 오래된 이동점들을 우선적으로 탐색해가는 일종의 실시간 깊이-우선 팀.색(Real-time Depth-First Search, RDFS)을 적용하였다. 하지만 여기에 부가적으로 고려해야 할 한가지 중요한 문제는 각 이동점에서 인접 이동점들을 파악할 수 있는 KGBot의 인지범위의 한계성이다.

성능/효과

또한 Rotate & Go 전 략의 경우, 지도의 복잡도가 증가할수록 탐색에 소요된 시 간은 증가하였지만 전체적으로 매우 효율적인 탐색으로 인해 지도의 복잡도에 비해 총 탐색시간의 증가는 완만하였다. Dom-Stalwart와 같이 장애물이 없고 지도의 구성이 매우 간단한 경우에는 Go&Go 전략이 오히려 Rotate & Go 전략 보다 빨리 목표점들을 탐색할 수 있었지만, Dom-Condomned 와 Dom-Leadworks처럼 지도가 두 개의 층으로 구성되거나 경로의 굴곡이 심한 경우에는 Rotate & Go 전략이 매우 효과적임을 알 수 있었다.
동 일 전략을 각 지도별로 10회씩 반복 실험하여 탐색에 걸린 최대 시간, 최소 시간, 그리고 평균 시간을 비교하여 보았다. 그리고 매 실험마다 월드 탐색 제한 시간을 600초로 설정 하였는데, 600초가 지나도 목표점들을 다 찾지 못한 경우에는 실시간 액션 게임의 특성상 사실상 이미 승패가 판가름 난 상태여서 더이상 탐색을 계속하는 것이 무의미하다卫 판단되어 실험을 멈추었다.
하지만 그럼에도 불구하고 일대일 Domination 게임환경 안에서 두 제어엔진의 효율성을 실증적으로 비교할 수 있는 현실 적인 방법은 실제로 그 게임환경 안에서 직접 두 에이전트 를 서로 경쟁시켜 보는 것이다. 따라서 이러한 의미에서 본 연구의 실험 결과는 순수 반응형 제어엔진에 비해 UM- PRS 제어엔진의 우수성을 보여주었다. 하지만 이러한 결과 는 본 연구에서 가정하는 일대일 Domination 게임타입의 특성에도 그 원인이 있는 것으로 판단된다.

후속연구

그리고 끝으로 서로 다른 3차원 지도상의 실험을 통해 이러한 KGBot의 제어엔진과 경로 찾기 행위의 우수성을 입증하여 보았다. 계획하고 있는 향후 연구로는 현재까지 구현된 기초적인 지능 행위를 바탕으로 팀별 Domination 게임이나 팀별 CTF 게임과 같은 다중 에이전트 환경에서도 효과적으로 동작하는 KGBot 팀에이전트를 개발하는 것이다. 이를 위해서는 먼저 팀원들간의 메시지 교환을 위한 통신 프로토콜과 팀 단위 전술행위를 구현하기 위한 효과적인 조정 프로토콜에 관한 연구가 필요할 것으로 생각된다.
따라서 탐색중인 KGBot는 현재 방문하고 있는 이동점을 중심으로 인접한 이동점들 각각 으로의 접근 가능성을 조사한 다음 단방향 경로를 나타내는 에지들을 추가함으로써 하나의 유향 경로 그래프(directed path graph)를 작성한다. 그리고 각 경로의 역방향 접근성을 조사하려면 추가적인 탐색을 통해 경로의 다른쪽 이동점을 실제로 방문해야만 가능하다. 대신 월드 탐색을 위해 KGBot 가 채용하고 있는 Rotate & Go 탐색전략에 따르면, 한 이동점 A에서 접근 가능한 인접 이동점들과 단위 경로들 중에서 다음 방문대상으로 선택된 이동점 B로의 단위 경로는 KGBot 가 다음순간 이동점 B로 이동한 직후 다시 모든 인접 이동 점들의 접근 가능성을 조사할때 그 역 방향의 경로에 대한 조사도 함께 이루어질 수 있다.
계획하고 있는 향후 연구로는 현재까지 구현된 기초적인 지능 행위를 바탕으로 팀별 Domination 게임이나 팀별 CTF 게임과 같은 다중 에이전트 환경에서도 효과적으로 동작하는 KGBot 팀에이전트를 개발하는 것이다. 이를 위해서는 먼저 팀원들간의 메시지 교환을 위한 통신 프로토콜과 팀 단위 전술행위를 구현하기 위한 효과적인 조정 프로토콜에 관한 연구가 필요할 것으로 생각된다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

3차원 가상환경에서 동작하는 지능형 에이전트의 구조와 경로 찾기 행위
Architecture and Path-Finding Behavior of An Intelligent Agent Deploying within 3D Virtual Environment 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (23)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

3차원 가상환경에서 동작하는 지능형 에이전트의 구조와 경로 찾기 행위 Architecture and Path-Finding Behavior of An Intelligent Agent Deploying within 3D Virtual Environment 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (23)

이 논문을 인용한 문헌

저자의 다른 논문 :

김인철 (75) 이재호 (20)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

3차원 가상환경에서 동작하는 지능형 에이전트의 구조와 경로 찾기 행위
Architecture and Path-Finding Behavior of An Intelligent Agent Deploying within 3D Virtual Environment 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper