일반 다각형 환경에서 3차원 C-공간 장애물 구성에 관한 연구

유견아 덕성여자대학교 자연과학연구소 2002 자연과학 논문집 Vol.8 No.-

형상공간(configuration space)은 움직이는 로봇을 점의 이동으로 간주하고 주변의 환경을 이에 따라 적절히 변화시켜 표현한 공간이다. C-공간에서 로봇운동을 계획하는 일은 컴퓨터 기하학을 이용하여 보다 체계적이고 알고리즘적인 접근을 보장한다. 로봇을 점으로 간주했을 때 로봇이 움직이는 환경의 장애물들을 그에 따라 적절히 확장해주어야 하는데 바로 C-공간 장애물을 구성하는 일이 C-공간을 이용한 운동계획을 하기 위한 첫 걸음이다. 이제까지의 연구결과는 주로 로봇이나 환경을 구성하는 장애물들을 다각형으로 제한하고 로봇의 직선이동(translation)운동을 전제로 얻어진 것이어서 실제 문제에 응용할 수 있는 범위가 제한되었다. 본 연구에서는 이러한 제약조건들을 완화시켜 원형 장애물과 로봇의 회전 운동을 포함할 수 있는 일반적인 알고리즘으로 확장하기 위한 방법을 제안한다.

출발점과 목표점을 일반화 가시성그래프로 표현된 맵에 포함하기 위한 빠른 알고리즘

유견아,전현주,Yu, Kyeon-Ah,Jeon, Hyun-Joo 한국시뮬레이션학회 2006 한국시뮬레이션학회 논문지 Vol.15 No.2

가시성그래프는 최소 탐색 공간으로 게임환경을 모델링하여 효과적으로 길을 찾을 수 있도록 하는 방법으로 잘 알려져 있다. 일반화 가시성그래프는 가시성그래프의 가장 큰 단점으로 지적되는 "벽-껴안기" 문제를 해결하기 위해 확장된 장애물의 경계 위에 생성된 가시성그래프이다. 일반화 가시성그래프에 의해 구해진 경로는 근사 최적이며 자연스럽게 보이는 장점이 있다. 본 논문에서는 변화하는 출발점과 목표점과 정적인 장애물 사이를 움직이는 게임 캐릭터에 효과적으로 일반화 가시성그래프를 적용하는 방법을 제안한다. 일반화 가시성그래프는 일단 생성되면 최소 탐색공간을 보장하지만 그 생성 자체는 노드사이의 링크의 교차 여부론 일일이 체크하여야 하므로 시간이 많이 소요된다. 아이디어는 먼저 정적인 장애물만으로 지도를 생성해 놓고 출발점과 목표점을 빠르게 포함시키는 것이다. 출발점과 목표점의 포함 부분이 여러 번 반복되어야 하는 과정이므로 출발점과 목표점을 빠르게 포함시키는데에 연산 기하학 분야의 회전 plane-sweep 알고리즘을 이용할 것을 제안한다. 시뮬레이션 결과는 전체 그래프를 매번 생성하는 것보다 제안한 방법의 실행시간이 39%-68% 정도 향상되었음을 보여준다. The visibility graph is a well-known method for efficient path-finding with the minimum search space modelling the game world. The generalized visibility graph is constructed on the expanded obstacle boundaries to eliminate the "wall-hugging" problem which is a major disadvantage of using the visibility graph. The paths generated by the generalized visibility graph are guaranteed to be near optimal and natural-looking. In this paper we propose the method to apply the generalized visibility graph efficiently for game characters who moves among static obstacles between varying start and goal points. Even though the space is minimal once the generalized visibility graph is constructed, the construction itself is time-consuming in checking the intersection between every two links connecting nodes. The idea is that we build the map for static obstacles first and then incorporate start and goal nodes quickly. The incorporation of start and goal nodes is the part that must be executed repeatedly. Therefore we propose to use the rotational plane-sweep algorithm in the computational geometry for incorporating start and goal nodes efficiently. The simulation result shows that the execution time has been improved by 39%-68% according to running times in the game environment with multiple static obstacles.

일반화 가시성그래프에 의해 계획된 경로이동 시뮬레이션

유견아,전현주,Yu, Kyeon-Ah,Jeon, Hyun-Joo 한국시뮬레이션학회 2007 한국시뮬레이션학회 논문지 Vol.16 No.1

최근 컴퓨터 게임에서 중대성이 부각되고 있는 NPC(NonPlayer Character)는 게임의 기본이 되는 이동에 있어서 스스로 장애물과 다른 캐릭터들을 인지하고 자신의 임무를 수행하여야 한다. NPC들의 자연스러운 이동을 위해 고정된 장애물 환경에서 일반화 가시성그래프를 이용하여 경로를 계획하는 방법이 제안된 바 있는데 본 논문에서는 이렇게 생성된 경로를 따라 효율적으로 이동할 수 있게 하기 위한 실행 모듈을 개발한다. 일반화 가시성그래프의 특성에 따라, 계획된 경로는 직선과 원의 호로 이루어져 있는데 본 실행 모듈에서는 이 특성에 적합하고 NPC의 움직임이 자연스럽도록 직선이동 동작, 원 이동 동작, 도착하기 등의 기본 조타 동작을 정의하여 실제 경로 이동의 실행에 이용한다. 또한 이동 중에 나타나는 동적 장애물을 감지하기 위해 충돌감지 기능을 실행 모듈에 포함시키며 감지된 장애물의 종류에 따라 선택적으로 대처하기 위해 의사결정나무를 이용한다. 실행 모듈을 테스트하기 위해 NPC의 경로 이동을 방해하는 다른 NPC가 등장하도록 예제 시나리오를 작성하여 시뮬레이션한다. The importance of NPC's role in computer games is increasing. An NPC must perform its tasks by perceiving obstacles and other characters and by moving through them. It has been proposed to plan a natural-looking path against fixed obstacles by using a generalized visibility graph. In this paper we develop the execution module for an NPC to move efficiently along the path planned on the generalized visibility graph. The planned path consists of line segments and arc segments, so we define steering behaviors such as linear behaviors, circular behaviors, and an arriving behavior for NPC's movements to be realistic and utilize them during execution. The execution module also includes the collision detection capability to be able to detect dynamic obstacles and uses a decision tree to react differently according to the detected obstacles. The execution module is tested through the simulation based on the example scenario in which an NPC interferes the other moving NPC.

부정 훈련 예제를 이용하는 경로 학습 알고리즘의 수렴에 대한 고찰

유견아 덕성여자대학교 열린교육연구소 2010 자연과학 논문집 Vol.16 No.-

컴퓨터 게임이나 가상현실 속의 캐릭터, 로봇, 아바타 등의 자율적 경로 이동은 미리 정해 진 방식대로 움직이는 것이 아니라 상황에 맞는 경로를 찾아낼 수 있어야 가능하다. 이를 가능하게 하기 위해서는 탐색에 의한 단순 경로 찾기의 수준을 넘어 스스로 환경에 적응하 고 학습하는 능력이 있어야 하는데 해법 중의 하나가 인공지능 분야의 기계학습이다. 일반 적으로 경로를 계획하는 과정은 탐색 알고리즘과 탐색 알고리즘에서 취하는 평가함수에 의 하여 결정되는데 본 논문에서는 경로계획을 위한 기계학습을 평가함수를 최적화하는 것으로 정의하고 이를 탐색 알고리즘과 통합하여 구현한다. 즉, 일반적인 탐색을 진행하면서 주어진 훈련예제와의 비교를 통해 평가함수를 구성하는 여러 요소들의 가중치를 조정해 나가는 것 을 말한다. 본 논문에서는 효과적인 학습을 위해 좋은 경로와 나쁜 경로를 대변하는 긍정 예제와 부정 예제를 모두 사용하는 탐색과 통합된 기계학습 알고리즘을 소개하며 이 알고리 즘이 수렴함을 증명한다.

컴퓨터 게임 환경에서 일반화 가시성 그래프를 이용한 경로찾기

유견아,전현주,Yu, Kyeon-Ah,Jeon, Hyun-Joo 한국시뮬레이션학회 2005 한국시뮬레이션학회 논문지 Vol.14 No.3

In state-of-the-art games, characters can move in a goal-directed manner so that they can move to the goal position without colliding obstacles. Many path-finding methods have been proposed and implemented for these characters and most of them use the A* search algorithm. When .the map is represented with a regular grid of squares or a navigation mesh, it often takes a long time for the A* to search the state space because the number of cells used In the grid or the mesh increases for higher resolution. Moreover the A* search on the grid often causes a zigzag effect, which is not optimal and realistic. In this paper we propose to use visibility graphs to improve the search time by reducing the search space and to find the optimal path. We also propose a method of taking into account the size of moving characters in the phase of planning to prevent them from colliding with obstacles as they move. Simulation results show that the proposed method performs better than the grid-based A* algorithm in terms of the search time and space and that the resulting paths are more realistic.

로드맵 기반 경로에서의 그룹 이동 시뮬레이션

유견아,조수진,김경혜,Yu, Kyeon-Ah,Cho, Su-Jin,Kim, Kyung-Hye 한국시뮬레이션학회 2011 한국시뮬레이션학회 논문지 Vol.20 No.4

The roadmap-based planning is a path planning method which is used widely for a goal-directed movement in Robotics and has been applied to the world of computer animation such as computer games. However it is unnatural for computer characters to follow the path planned by the roadmap method as it is performed in Robotics. Flocking which is used for realistic and natural movements in computer animation enables character's movement by using a few simple rules without planning unlike the roadmap method. However it is impossible to achieve a goal-directed movement with flocking only because it does not keep states. In this paper we propose a simulation method which combines planning based on the road map with reactive actions for natural movements along the path planned. We define and implement steering behaviors for a leader which are needed to follow the trajectory naturally by analysing characteristics of roadmap-based paths and for the rest of members which follow the leader in various manners by detecting obstacles. The simulations are performed and demonstrated by using the implemented steering behaviors on every possible combination of roadmap-based path planning methods and models of configuration spaces. We also show that the detection of obstacle-collisions can be done effectively because paths are planned in the configuration space in which a moving object is reduced to a point. 로드맵 기반 계획은 목표 지향적인 이동을 위해 로보틱스 분야에서 많이 사용되는 경로 계획 방식이며 최근 컴퓨터 게임과 같은 컴퓨터 애니메이션 세계에서 많이 응용되고 있다. 그러나 컴퓨터 캐릭터가 로드맵 방식으로 계획된 경로 이동을 기존의 로보틱스 분야와 같은 방식으로 하면 자연스럽게 보이지 않는 단점이 있다. 컴퓨터 애니메이션 분야에서 실제적이고 자연스러운 이동을 가능하게 하는 플로킹은 로드맵과는 달리 계획에 의존하지 않고 몇 가지 규칙만으로 빠르게 캐릭터의 이동을 가능하게 하지만 상태를 갖지 않으므로 목표 지향적인 이동은 불가능하다. 그러므로 본 논문에서는 로드맵에 의해 경로를 계획하고 계획된 경로를 그룹이 자연스럽게 이동하도록 반응적 행동과 결합하여 시뮬레이션하는 방법을 제안한다. 이를 위해 로드맵 기반 경로의 특징을 분석하여 그룹의 리더가 자연스럽게 궤적을 추종하는데 필요한 조타 행동들과 나머지 멤버들이 주변 장애물 상태를 파악하면서 다양한 방법으로 리더를 따르도록 하는 조타 행동을 정의하고 구현하도록 한다. 구현된 조타 행동들을 이용하여 로드맵 기반 계획 방법들과 형상공간 모델링의 가능한 조합에 대해 이동 시뮬레이션하고 결과를 보여준다. 또한 경로 계획이 움직이는 물체는 점을 환산한 형상공간에서 이루어져 장애물 충돌 감지를 효과적으로 할 수 있음을 보여준다.

가중치 학습과 결합된 전술적 경로 찾기의 구현

유견아,Yu, Kyeon-Ah 한국시뮬레이션학회 2010 한국시뮬레이션학회 논문지 Vol.19 No.2

Conventional path-finding has focused on finding short collision-free paths. However, as computer games become more sophisticated, it is required to take tactical information like ambush points or lines of enemy sight into account. One way to make this information have an effect on path-finding is to represent a heuristic function of a search algorithm as a weighted sum of tactics. In this paper we consider the problem of learning heuristic to optimize path-finding based on given tactical information. What is meant by learning is to produce a good weight vector for a heuristic function. Training examples for learning are given by a game level-designer and will be compared with search results in every search level to update weights. This paper proposes a learning algorithm integrated with search for tactical path-finding. The perceptron-like method for updating weights is described and a simulation tool for implementing these is presented. A level-designer can mark desired paths according to characters' properties in the heuristic learning tool and then it uses them as training examples to learn weights and shows traces of paths changing along with weight learning.

격자-기반 방식으로 표현된 게임에서 경로찾기를 위한 계층적 탐색의 응용

유견아 덕성여자대학교 자연과학연구소 2008 자연과학 논문집 Vol.14 No.-

컴퓨터 게임의 캐릭터, 로봇, 아바타 등의 자율적인 이동을 위해 가장 많이 사용되는 탐색 알고리즘은 인공지능 분야의 A*이다. 최적 경로를 보장하는 성질 때문에 매력적인 경로 찾기 방법이기는 하지만 기본적으로는 오프라인 탐색 방법이므로 실시간으로 움직이는 캐릭터가 한 지점에서 가만히 최소 비용의 경로 계획에 몰두하다가 갑자기 재빠르게 계획된 경로 이동을 실행하는 모습은 자연스럽지 않다. 특히 격자-기반 표현 방식과 같이 많은 격자수 때문에 상태 공간이 커지면 전체 공간에 대해 한번에 최적 경로를 탐색하는 것은 더욱 부자연스럽다. 본 연구에서는 전체에 대해서는 가시점만을 이용하여 대략적인 경로를 찾아내고 가시점들을 서브목표로 하여 격자들의 정보를 이용한 세부 경로 계획을 시행하여 이와 같은 문제를 해결하고자 한다.

컴퓨터 게임에서의 경로 계획을 위한 캐릭터별 로드맵의 자동 생성

유견아(Kyeonah Yu) 한국멀티미디어학회 2008 멀티미디어학회논문지 Vol.11 No.5

스캔된 문서에서의 도장 검출

유견아(Kyeonah Yu),김경혜(Kyung-Hye Kim) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.12

디지털 시대의 도래에 따라 문서들이 기록 보관되기 위해서 혹은 네트워크를 통해 전송되기 위해서 스캔되는 경우가 많아졌다. 스캔된 문서에서 가장 큰 비중을 차지하는 것은 텍스트이며 텍스트 이외에는 문서 작성자를 나타내는데 사용되는 도장이 가장 많이 포함되어 있다. 스캔된 문서의 중요성이 부각되면서 스캔된 문서로부터 텍스트를 인식하는 연구는 많이 진행되어 상용화된 제품도 개발된 것에 비해 문서가 포함하고 있는 도장에 대한 정보는 버려지고 있는 실정이다. 본 논문에서는 도장이 포함된 컬러 혹은 흑백 문서 영상에서 도장 영역을 검출하여 도장 이미지를 저장하는 방법을 연구한다. 스캔된 문서에서 도장의 외곽선 후보만을 남기고 다른 기타 구성 요소를 제거하는 전처리 과정과 도장의 특징을 이용하여 남은 요소 중에 최종 관심 영역을 선정하는 방법을 제안한다. 또한 검출된 관심 영역의 도장 정보가 텍스트와 겹친 이미지인 경우에는 템플릿 매칭을 통해 데이터베이스로부터 가장 유사한 도장을 찾아 대신 저장할 수 있게 한다. 구현된 시스템은 학교에서 일반적으로 생성되는 여러 유형의 문서들을 대상으로 검증하고 그 결과를 분석한다. As the advent of the digital age, documents are often scanned to be archived or to be transmitted over the network. The largest proportion of documents is texts and the next is seal images indicating the author of the documents. While a lot of research has been conducted to recognize texts in scanned documents and commercialized text recognizing products are developed as highlighted the importance of the scanned document, information about seal images is discarded. In this paper, we study how to extract the seal image area from the color or black and white document containing the seal image and how to save the seal image. We propose a preprocessing step to remove other components except for the candidate outlines of the seal imprint from scanned documents and a method to select the final region of interest from these candidates by using the feature of seal images. Also in case of a seal imprint overlapped with texts, the most similar image among those stored in the database is selected through the template matching process. We verify the implemented system for a various type of documents produced in schools and analyze the results.