Development of a Multi-criteria Pedestrian Pathfinding Algorithm by Perceptron Learning

Kyeonah Yu(유견아),Chojung Lee(이초정),Inyoung Cho(조인영) 한국컴퓨터정보학회 2017 韓國컴퓨터情報學會論文誌 Vol.22 No.12

Pathfinding for pedestrians provided by various navigation programs is based on a shortest path search algorithm. There is no big difference in their guide results, which makes the path quality more important. Multiple criteria should be included in the search cost to calculate the path quality, which is called a multi-criteria pathfinding. In this paper we propose a user adaptive pathfinding algorithm in which the cost function for a multi-criteria pathfinding is defined as a weighted sum of multiple criteria and the weights are learned automatically by Perceptron learning. Weight learning is implemented in two ways: short-term weight learning that reflects weight changes in real time as the user moves and long-term weight learning that updates the weights by the average value of the entire path after completing the movement. We use the weight update method with momentum for long-term weight learning, so that learning speed is improved and the learned weight can be stabilized. The proposed method is implemented as an app and is applied to various movement situations. The results show that customized pathfinding based on user preference can be obtained.

형상공간 접근 방식에 기반한 모듈식 고정쇠의 적재가능성 분석

유견아(Kyeonah Yu) 제어로봇시스템학회 2003 제어·로봇·시스템학회 논문지 Vol.9 No.5

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

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

동적 환경에서 그룹 이동을 위한 경로 계획

유견아(Kyeonah Yu),조수진(Su-Jin Cho) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.2

가상의 캐릭터가 이동하기 위해 경로를 계획하는 일은 컴퓨터 게임을 포함한 여러 응용 분야에서 필수적인 문제이다. 기존의 로봇 경로 계획과는 달리 하나 이상의 캐릭터가 그룹 이동을 하는 경우가 많으며 이 경우에는 이동 경로의 최단 여부보다는 자연스러운 그룹 이동 등의 질적인 면이 강조된다. 본 논문에서는 리더로 정해진 단일 캐릭터에 대해 정적인 환경에서의 전역 경로를 계획하고 이 경로를 따라 그룹이 이동하며 동적 장애물을 피하도록 지역 경로를 계획하는 2단계 경로 계획 방법을 제안한다. 그룹이 이동할 수 있는 공간은 리더를 중심으로한 정방형 격자 배열을 이용하여 확보하고 이를 격자창이라고 부른다. 멤버 캐릭터들은 격자창 공간 안에서 리더에 대한 상대적인 위치를 잡아 이동하며 격자창이 이동할 수 있는 경로를 계획하기 위해 정적 환경을 격자창에 대한 형태 공간으로 치환하여 로드맵을 구한다. 지역 경로 계획 단계에서는 리더에 대해 인공 포텐셜 필드를 이용하여 동적 장애물을 회피하도록 하고 나머지 멤버들에 대해서는 격자창 내에서 리더에 대한 상대적인 위치를 확보하는 방법으로 연산량을 줄인다. 제안하는 경로 계획 방법을 구현하기 위한 효율적인 알고리즘을 소개하며 정적 환경에서 계획된 경로를 따라 그룹이 이동하면서 동적 장애물에 대해 효과적으로 대처하는 것을 시뮬레이션을 통해 보여 준다. Path planning is an essential problem to make virtual characters navigate in many applications including computer games. In many cases, multiple characters move in a group and qualitative aspects of planned paths are emphasized rather than optimality unlike Robotics. In this paper, we propose a two-level path planning algorithm in which the global path is planned for a single character specified as a leader and then the local path is planned to avoid dynamic obstacles while the group following this path. The space for group movement is achieved in the form of square grid array called a grid window. Member characters are located relatively to the leader within a space and moved. The static environment is reduced to the configuration space of this grid window to generate a roadmap on which a grid window can move. In local path planning, only the leader avoids dynamic obstacles by using an artificial potential field and the rest of members are located relatively to the leader in the grid window, which reduces computational load. Efficient algorithms to implement the proposed planning methods are introduced. The simulation results show that a group can handle with dynamic obstacles effectively while moving along the planned path for a static environment.

NPC의 자연스러운 이동경로를 보장하는 효율적인 상태공간의 생성

유견아(Kyeonah Yu) 한국정보과학회 2007 정보과학회논문지 : 소프트웨어 및 응용 Vol.34 No.4

컴퓨터 게임에서 NPC(non-player character)가 이동하는 자연스러운 경로를 찾기 위해서는 탐색을 위한 공간을 어떻게 표현할 것인가에 대한 연구가 어떤 탐색 방법을 사용할 것인가에 대한 연구못지 않게 중요하다고 할 수 있다. 최근까지 게임 경로 찾기의 동향을 보면 경로 계획을 위한 탐색 방법으로는 A* 알고리즘이 단연 우위를 보이지만 A* 알고리즘을 적용하기 위한 상태 공간 표현 방식으로는 게임을 위해 만들어진 여러가지 표현 방법들이 사용되고 있다. 기존의 방법들은 탐색 공간의 크기가 너무 크거나, 최적의 경로를 찾지 못하거나, 경로가 자연스럽지 못하는 등의 단점 뿐 아니라 노드와 링크의 생성이 자동적이지 못하고 레벨 디자이너에 의존하는 것도 문제점으로 지적되고 있다. 본 논문에서는 경로가 자연스럽게 보이기 위한 성질을 정의하고 이를 충족하는 경로를 생성할 수 있도록 로보틱스 분야의 가시성그래프를 응용한 일반화 가시성그래프를 이용하여 상태공간을 표현할 것을 제안한다. How to represent the search space is as important as which search algorithm to use for finding natural-looking paths for moving NPC (non-player character) in computer games. Recently, various state space representation methods which have been developed for computer games are being used while A* algorithm dominates as the preferred search algorithm. These representation methods show some drawbacks such as the size of state space is too large, there is no guarantee for optimality, the path found is not natural-looking, and the generation of nodes and links is not automatic by depending on a level designer. In this paper the requirements for natural-looking paths are introduced and to find paths satisfying these requirements, the use of the generalized visibility graphs which is the extended version of the visibility graph in Robotics is proposed.

게임 캐릭터의 전술적 행동을 위한 위치 평가 함수의 학습

유견아(Kyeonah Yu) 한국정보과학회 2011 정보과학회논문지 : 소프트웨어 및 응용 Vol.38 No.2

컴퓨터 체스 등에서 보드 형세를 평가하기 위해 소개되었던 위치 평가 함수는 컴퓨터 게임의 인공지능 캐릭터의 전술적 행동을 결정하는 기반 요소로 이용될 수 있다. 위치 평가 함수는 여러 특성들의 가중치 합으로 정의되는데 특성의 중요도를 적절히 반영하도록 가중치를 정하는 것이 중요하다. 본 논문에서는 감독학습 방법을 이용하여 위치 평가 함수의 가중치를 학습한다. 가중치 학습은 현재의 가중치로 계산된 출력과 목표값의 차를 최소화하는 단층 퍼셉트론의 학습 규칙을 응용하고 이 갱신 방법의 수렴에 대해 증명한다. 시뮬레이션에서는 학습에 의해 가중치가 자동적으로 설계자의 의도에 맞게 수정됨을 보여줄 뿐 아니라 학습된 위치 평가 함수를 전술 요소를 반영한 경로찾기에 응용할 수 있음을 보여준다. The position evaluation function which is originally introduced to evaluate the board configuration of computer chess can be used as a key element to determine the tactical behavior of AI characters in computer games. The position evaluation function is defined as a weighted sum of features, and it is important to assign weights properly according to the importance of features. In this paper the weight factor of a position evaluation function is learned by using a supervised learning technique. The weight learning is performed in a way similar to the single-layer Perceptron learning which minimizes the difference between the output of the current weights and the target, and the convergence of this weight update method is proved. The simulation result shows that the weights can be modified automatically according to the designer's intention and the learned position evaluation function can be applied to path-finding considering tactical features.

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

유견아(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.

가시성그래프에 의해 최소 여유공간을 보장하는 길찾기

전현주(Hyunjoo Jeon),유견아(Kyeonah Yu) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.2

최근 게임에서 자주 등장하기 시작한 랜덤 지형 맵 생성기법으로 인해 단순한 경로 찾기가 아닌 지형분석을 통한 복잡한 경로 찾기 문제가 많은 관심을 받고 있다. 이에 로보틱스 분야에서 경로 찾기에 이용되는 가시성그래프(Visibility Graph, Vgraph)가 지형분석과 경로 찾기를 동시에 해결할 수 있는 방법으로 제안되고 있다. Vgraph를 이용하면 지형의 로드맵을 효과적으로 생성할 수 있을 뿐 아니라 A* 알고리즘과 결합하여 최적의 경로를 찾는 것을 보장하는 장점이 있다. 그러나 Vgraph에 의해 구해진 경로는 장애물의 정점에서 정점으로 이동하기 때문에 항상 장애물의 모서리를 향해 움직이며 벽에 붙어가는 듯이 보여 부자연스러운 것이 단점이다. 본 논문에서는 설계자가 요구하는 여유공간 c만큼 장애물을 확장하여 확장된 장애물에 대해 가시성그래프를 생성함으로써, Vgraph의 장점은 유지하며 단점을 보완할 수 있는 방법에 대해 제안한다.

손그림 자동분석에 기반한 퍼지 추론 심리진단 응용의 개발

김수경(Su-Kyung Kim),유견아(Kyeonah Yu) 한국디지털콘텐츠학회 2021 한국디지털콘텐츠학회논문지 Vol.22 No.3

일반화 가시화 그래프의 구현

안진영(Jinyoung Ahn),유견아(Kyeonah Yu) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.2Ⅰ

가시화 그래프(visibility graph, Vgraph)는 로봇의 경로를 계획할 때, 최적의 경로를 구하기 위해 널리 이용되는 지도 접근 방식중의 하나이다. 원래 Vgraph는 다각형으로 모델링된 로봇이 다각형 환경의 평면상에서 움직일 때 움직이는 로봇을 점으로 환산한 환경인 형상공간(configuration space, C-공간)에서 정의되었는데 이를 원형 로봇 혹은 일반화 다각형(generalized polygon) 환경으로 확장한 것이 일반화 가시화 그래프(GVgraph)이다. 본 논문에서는 기존의 다각형 환경에서 정의된 Vgraph를 형성하는 알고리즘과 동일한 시간복잡도로 GVgraph를 구현하는 알고리즘을 소개하고 미세 운동계획(fine motion planning)에 응용하는 예를 보여준다.