컴퓨터 게임 환경에서의 효율적인 멀티 에이전트 공간탐사

• 영문명: Efficient Multi-Agent Exploration in Computer Game Environments
• 발행기관: 한국컴퓨터게임학회
• 저자명: 최은미(Eun mi Choi) 김인철(in cheol Kim)
• 간행물 정보: 『한국컴퓨터게임학회논문지』제9호, 1~11쪽, 전체 11쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2006.12.30

국문 초록

최근 들어 다수의 NPC들을 포함하는 다양한 컴퓨터 게임들이 개발되고 있으며, 이들이 효율적으로 공간을 탐사하고 공간 맵을 작성하는 기술에 대한 관심 또한 높아지고 있다. 본 논문에서는 다수의 협력적 에이전트들을 이용하여 매우 효율적으로 미지의 공간을 탐사할 수 있는 멀티 에이전트 그래프 탐색 알고리즘을 제안한다. 멀티 에이전트를 이용하여 효율적으로 공간탐사를 수행하기 위해서는 에이전트 간의 충돌과 간섭효과 그리고 탐사 영역의 중복성 문제를 해결하여야 한다. 본 논문에서 제안하는 멀티 에이전트 그래프 탐색 알고리즘인 MADFS는 이와 같은 문제를 해결하기 위해 에이전트 간에 이루어져야 할 효과적인 정보교환과 이를 바탕으로 하는 방문노드 선택전략을 포함하고 있다. 이 알고리즘은 공간탐사에 참여하는 각 에이전트의 자율적 탐색을 최대한 보장하면서도 에이전트들의 중복탐사를 최소화함으로써 탐사의 높은 효율성을 얻을 수 있다. 본 논문에서는 대표적인 3차원 온라인 게임 환경인 Unreal Tournament 게임과 지능형 캐릭터 에이전트인 KGBot를 이용한 실험을 통해 제안한 탐색 알고리즘의 완전성과 효율성을 분석한다.

영문 초록

Nowadays various computer games are being developed to include multiple NPCs, and the techniques to make them efficiently explore a new world and build a world map get attracting much interest. This paper presents a multi-agent graph search algorithm which is able to efficiently explore an unknown space with multiple cooperative agents. In order to efficiently explore an unknown space with multiple agents, we have to solve the problems regarding conflicts, interferences and redundant explorations between participating agents. The suggested multi-agent graph search algorithm, MADFS, includes an effective communication scheme and a node selection strategy to meet these problems. The MADFS algorithm can guarantee the high efficiency of the overall exploration process as well as the individual autonomy of the participating agents. Through some experiments using a representative 3D online game, UT, and an intelligent character agent, KGBot, we analyze completeness and efficiency of the suggested algorithm.

목차

요약

ABSTRACT

Ⅰ. 서론

Ⅱ. 관련연구

Ⅲ. 멀티 에이전트 공간탐사

Ⅳ. 구현 및 실험

Ⅴ. 결론

참고문헌

키워드

Space Exploration Real-Time Graph Search Multi-Agent Online Games