데드라인을 고려하는 효율적인 지능형 로봇 커버리지 알고리즘

전흥석,정은진,강현규,노삼혁,Jeon, Heung-Seok,Jung, Eun-Jin,Kang, Hyun-Kyu,Noh, Sam-H. 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.1

이 논문은 지능형 로봇을 위한 새로운 커버리지 알고리즘을 제안한다. 커버리지 알고리즘의 성능을 향상하기 위한 많은 연구들은 전체 커버리지 완료 시간을 최소화하는데 초점을 맞추어왔다. 그러나, 만일 전체 커버리지를 완료하기에 충분한 시간이 없다면, 최적의 경로는 달라질 수 있다. 이러한 문제를 해결하기 위하여 본 논문에서는 MaxCoverage라고 하는 데드라인이 있을 경우에 가능한 많은 면적을 커버하기 위한 새로운 커버리지 알고리즘을 제안한다. MaxCoverage 알고리즘은 이동 경로를 셋 커버 문제를 위한 그리디 알고리즘을 이용하여 결정한다. 실험 결과에 의하면 MaxCoverage 알고리즘은 임의의 데드라인에 대하여 다른 알고리즘들에 비해 향상된 성능을 보여준다. This paper proposes a new coverage algorithm for intelligent robot. Many algorithms for improving the performance of coverage have been focused on minimizing the total coverage completion time. However, if one does not have enough time to finish the whole coverage, the optimal path could be different. To tackle this problem, we propose a new coverage algorithm, which we call MaxCoverage algorithm, for covering maximal area within the deadline. The MaxCoverage algorithm decides the navigation flow by greedy algorithm for Set Covering Problem. The experimental results show that the MaxCoverage algorithm performs better than other algorithms for random deadlines.

셋 커버 알고리즘을 이용한 효율적인 로봇 청소 알고리즘

전흥석(Heung-Seok Jeon) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.3

본 논문에서는 가장 덜 복잡한 공간부터 청소하는 공간 효율적인 새로운 로봇 청소 알고리즘인 SetClean 알고리즘을 제안한다. 청소 완료 시간이 길어지거나, 예측하기 어려운 경우에는 전체 청소 완료시간을 최적화하기보다는 가능한 빠른 시간에 가장 넓은 공간을 최대한 청소하는 것이 유리한 경우가 있다. 이를 위해 SetClean 알고리즘에서는 전체 공간을 셋 커버 알고리즘을 이용하여 청소 가능한 공간으로 구분하고, 단위 시간 당 청소 효율이 가장 높은 공간부터 청소를 진행하게 된다. SetClean 알고리즘은 해당 청소 가능 구역의 면적뿐만 아니라 로봇의 현재위치로부터 해당 청소 구역까지의 이동 거리, 청소 구역 내에서의 로봇의 회전으로 인한 지연 시간 등을 고려하여 최적의 청소 순서를 결정한다. 실험을 통해 SetClean 알고리즘의 동작 과정 및 성능을 보여준다. In this paper, we propose a new robot cleaning algorithm, which we call SetClean. The new algorithm cleans from the most less complex area. Sometimes, when the cleaning completion time can be longer or can not be estimated, cleaning larger area first is better than optimizing the whole time for cleaning. To do this, SetClean algorithm divides the whole area into cleanable sub-areas using Set Cover algorithm and cleans the area in the order of high efficiency that maximize the cleanable area per unit time. SetClean algorithm decides the navigation flow by considering not only the size of the area but also the distance from the current robot location to the area to be cleaned and the delay time caused by the number of turns within the area. The experimental results show the mechanism and performance of the SetClean algorithm.

아파치 웹 서버에서의 다중 쓰레드 풀 활용 기법 분석

전흥석(Heung Seok Jeon),이승원(Seung Won Lee),강현규(Hyun Kyu Kang) 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.1·2

웹 서버 혹은 웹 애플리케이션 서버는 급증하는 웹 사용자들의 요구에 효율적으로 대처하기 위하여 일반적으로 다중 쓰레드 모델을 적용하고 있다. 그러나 이러한 다중 쓰레드 모델이 새로운 웹 환경의 특정한 상황에서 다중 프로세스 모델에 비해 오히려 더 나쁜 성능을 보이는 경우가 있다. 본 논문에서는 이러한 문제를 해결하기 위하여 두 가지 접근 방법을 통해 다중 쓰레드 모델의 성능 저하에 대한 원인을 분석한다. 그 중 첫 번째로, 다양한 응용 환경에서의 다중 쓰레드 모델과 프로세스 모델을 비교한다. 두 번째로는 효율성을 위하여 일반적으로 제공되는 프로세스/쓰레드 풀 모델에서 동적인 지시자들의 설정값에 의한 영향을 분석한다. 본 논문에서는 자체 제작한 웹 클라이언트 시뮬레이터와 아파치 웹 서버 2.0 을 연동하여 이러한 실험들을 진행하고 결과 및 분석 내용을 제시한다. Web servers or web application servers, in general, adopt multi-thread model for efficient handling of many user requests. However, the multi-thread model always does not show the better performance than multi-process model. Sometimes, in a certain specific case, it can show worse performance than multi-process model. In this paper, to trace the cause of the decreased performance of multi-thread model, we experiment and analyze the performance of the multi-thread model by using two approaches. At first, we compare the performance of the multi-process model and multi-thread model for various application environments. Second, we observe the effects of variations of web server's dynamic directives, which are used to increase the flexibility of the web server for various system environments. For the experiments, we integrated a web client simulator, which was written by us, with the Apache 2.0 web server. This paper shows and analyze the results of the experiments.

자율 지능형 로봇을 위한 그룹화 기반의 효율적 커버리지 알고리즘

전흥석(Heung Seok Jeon),노삼혁(Sam H. Noh) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.2

최근 슬램 알고리즘의 실현을 통해 주변 환경에 대한 맵 정보가 획득 가능할 경우에 격자 그리드 기반의 Boustrophedon 경로 기반 커버리지 알고리즘이 매우 효율적인 것으로 알려져 있다. 그러나 Boustrophedon 경로 기반 알고리즘은 실내 공간에 장애물이 복잡하게 존재할 경우에는 급격히 성능 저하 현상이 발생한다. 따라서 본 논문에서는 복잡한 실내 공간에서도 효율적으로 빠른 시간 내에 청소를 완료할 수 있는 Group-k 알고리즘을 제안하고 구현한다. Group-k 알고리즘은 전체 공간을 장애물의 복잡성에 근거하여 전체 공간을 그룹화하고 각 그룹별 우선순위를 부여하여 전체 작업 순서를 효율적으로 제어한다. 구현 기반의 실험에 의하면, 본 논문에서 제안된 알고리즘은 Boustrophedon 경로 기반 알고리즘에 비해 약 20%의 성능 향상을 보여준다. The coverage algorithm based on Boustrophedon path has been known to be the most efficient in places without or less obstacles If the map of an environmental area thru SLAM algorithm can be obtainable However, the efficiency of the coverage algorithm based on Boustrophedon path drops drastically when obstacles are complex. In this paper, we propose and implement a new algorithm, which we call Group-k, that efficiently handles the complex area. The Group-k algorithm groups the obstacles and prioritizes the covering sequences with complex rank of the groups. Implementation-based experiments show about 20% improved performance when applying the new algorithm, compared to the Boustrophedon path algorithm.

홈 서버 기반의 저비용 지능형 청소로봇 시스템

전흥석(Heung Seok Jeon),박병상(Byung Sang Park),김정애(J.A Kim),김혜경(H.K. Kim),오영준(Y.J.Oh),이경희(K.H. Lee),나대영(D.Y. Na) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.2Ⅰ

지능형 청소로봇이란 사람을 대신하며 로봇 스스로가 집안을 청소할 수 있는 로봇을 말한다. 현재까지 출시된 지능형 로봇들 가운데 신뢰성 있는 청소로봇들은 대부분 고가형 청소로봇이다. 고가형 로봇은 위치 정보를 기억하고, 경로를 계산하기 위해 많은 기억장치와 컴퓨팅 자원을 가지고 있기 때문에 200-400만원대의 높은 가격에 판매되고 있다. 이것은 결국 청소로봇의 보편화에 큰 어려움으로 작용하고 있다. 따라서 본 논문에서는 개인용 컴퓨터를 이용하여 정보를 기억하고, 경로를 계산함으로써 청소로봇의 기능을 단순화하여 보다 저렴하고 신뢰성 있는 청소로봇 시스템을 제안한다.

Real-time Laying Hens Sound Analysis System using MFCC Feature Vectors

Heung Seok Jeon(전흥석),Deayoung Na(나대영) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.3

산란계사와 같이 매우 좁은 환경에서 많은 개체를 사육하는 경우 작은 환경 변화에도 큰 피해를 받을 수 있다. 이와 같은 문제를 해결하기 위해 본 연구에서는 끊임없이 소리를 발생하는 산란계의 특성을 이용하여 산란계 발성음 분석 시스템을 제안한다. 기존의 산란계 발성음 시스템은 산란계사의 제한된 상황만을 고려하거나 실제 산란계사에 적용하기에는 어려움을 가지고 있다. 이러한 문제를 극복하기 위하여 본 논문에서는 MFCC 특징 벡터를 이용한 9가지의 산란계 소리분석을 통해 실제 산란계사 환경에서 발생하는 수 있는 7가지의 상황을 실시간으로 감지할 수 있는 새로운 산란계 발성음 분석 모델을 제안한다. 본 논문에서 제안한 분석 모델을 실제 산란계사에서 성능 평가를 진행한 결과, 평균 AUC 0.93의 분류 성능을 나타내어 기존의 주파수 기반의 특징 분석 방법에 비해 약 43% 향상된 결과를 보여주었다. Raising large numbers of animals in very narrow environments such as laying hens house can be very damaged from small environmental change. Previously researched about laying hens sound analysis system has a problem for applying to the laying hens house because considering only the limited situation of laying hens house. In this paper, to solve the problem, we propose a new laying hens sound analysis model using MFCC feature vector. This model can detect 7 situations that occur in actual laying hens house through 9 kinds of laying hens sound analysis. As a result of the performance evaluation of the proposed laying hens sound analysis model, the average AUC was 0.93, which is about 43% higher than that of the frequency feature analysis method.

실내 공간의 복잡성을 고려한 실용적 청소 알고리즘

전흥석(Heung Seok Jeon),조재욱(Jaewook Jo),노삼혁(Sam H. Noh),나대영(D.Y. Na) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.2

청소로봇은 대부분 랜덤방식 또는 바둑판식의 청소알고리즘으로 운용된다. 랜덤 알고리즘은 전체 청소 시간이 오래 걸린다는 단점을 가지고 있다. 랜덤 알고리즘의 문제를 해결하기 위한 바둑판식 알고리즘은 현재까지 가장 좋은 알고리즘으로 알려져 있으나 장애물이 복잡한 공간에서는 청소시간이 길어지는 단점을 가지고 있다. 이런 문제점을 해결하기 위하여 본 논문에서는 Group- k 라는 새로운 청소 알고리즘을 제안한다. Group- k 알고리즘은 청소시간을 단축시키는 목적보다는 청소시간은 같더라도 복잡한 구역일수록 나중에 청소함으로써 가능한 빠른 시간 내에 가장 많은 면적을 청소하는 것을 목표로 한다. 즉 인접한 복잡한 장애물들을 하나의 그룹으로 구성하고 그룹의 복잡성을 계산하여 복잡성이 낮은 그룹부터 먼저 청소하는 방식이다. 시뮬레이션에 기반한 실험을 통해 Group- k 알고리즘이 복잡한 장애물 구역을 그룹화하여 복잡한 공간을 효율적으로 청소함을 보여준다.

복잡한 공간에서 그룹화 기반의 실용적 지능형 청소 로봇 알고리즘

전흥석(Heung Seok Jeon),조재욱(Jae Wook Jo),노삼혁(Sam H. Noh) 제어로봇시스템학회 2006 제어·로봇·시스템학회 논문지 Vol.12 No.5

멀티 프로세스와 멀티 쓰레드 기법의 효율적 활용을 위한 아파치 2.0 웹 서버의 성능 분석

전흥석(Heung Seok Jeon),이승원(Seung Won Lee) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅰ

아파치 웹 서버는 사용자들에게 좀더 빠른 서비스를 제공하기 위해 멀티 프로세스 모델을 사용해 왔다. 그러나 최근 들어 웹 서비스를 사용하는 사람들이 급격히 증가함에 따라 멀티 프로세스 구조보다 더 빠르고 더 많은 요청을 처리할 수 있는 구조가 요구 되어진다. 이러한 문제를 해결하기 위해서 생성 및 문맥전환 등에 있어서 오버헤드가 프로세스 보다 더 적다고 알려진 멀티 쓰레드 모델을 도입하게 된다. 하지만 멀티 쓰레드를 사용하는 것이 항상 멀티 프로세스를 사용하는 것보다 더 좋은 성능을 보여주진 않는다. 본 논문에서는 멀티 프로세스와 멀티 쓰레드를 주어진 상황에 따라 어떻게 활용하는 것이 응답시간과 처리율 면에서 더 효율적인지를 알아보기 위하여 시뮬레이터를 제작하여 아파치 웹 서버의 성능을 측정한다. 실험을 통해 아파치 웹 서버의 다양한 지시자에 대한 설정 값에 따라 멀티 프로세스와 멀티 쓰레드 구조의 성능이 달라 질 수 있음을 확인하고 이의 결과를 제시한다.

장애물을 제외한 가장 큰 공간을 찾는 기법

황정환,전흥석,Hwang, Jung-Hwan,Jeon, Heung-Seok 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.2

최근 청소로봇을 위한 여러 가지 알고리즘들이 개발되면서 다양한 청소로봇들이 개발되고 있다. 그 중 청소로봇이 청소하는데 있어 청소시간의 제약이 있을 경우 효율적으로 청소할 수 있는 알고리즘인 DmaxCoverage 알고리즘이 있는데 이 알고리즘을 구현하는데 장애물이 존재하지 않는 비어있는 공간을 찾기 위해 Rectangle Tiling기법을 사용하고 있다. Map을 그리드 형태의 수많은 사각형으로 나타낼 경우 사각형을 찾는 기법 중 수학적 방법으로 Rectangle Tiling이 최적의 값을 찾아줄 수 있다. Rectangle Tiling 기법은 그리드 형식의 map에서 생성될 수 있는 사각형들의 모든 경우의 수를 찾는 것이다. 이때 그리드선의 간격이 촘촘하고 map의 크기가 클 경우 많은 사각형이 생성됨으로 많은 시간을 소모해야 하는 문제점이 있다. 본 논문에서는 Rectangle Tiling에 근접한 정확성과 보다 개선된 속도를 제공하는 Four Direction Rectangle Scanning(FDRS)기법을 제안한다. FDRS기법은 존재하는 모든 사각형을 찾는 것이 아니라 물체가 존재하는 셀의 상하좌우만을 검색하여 빈 공간을 찾는 기법이다. 이 두 알고리즘을 비교하여 FDRS의 효율이 뛰어남을 실험을 통해 보여준다. Recently, many cleaning robots have been made with various algorithms for efficient cleaning. One of them is a DmaxCoverage algorithm which efficiently clean for the situation when the robot has a time limit. This algorithm uses Rectangle Tiling method for finding the biggest rectangle that doesn't have any obstacle. When the robot uses grid map, Rectangle Tiling method can find the optimal value. Rectangle Tiling method is to find all of the rectangles in the grid map. But when the grid map is big, it has a problem that spends a lot of times because of the large numbers of rectangles. In this paper, we propose Four Direction Rectangle Scanning(FDRS) method that has similar accuracy but faster than Rectangle Tiling method. FDRS method is not to find all of the rectangle, but to search the obstacle's all directions. We will show the FDRS method's performance by comparing of FDRS and Rectangle Tiling methods.