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

전흥석,정은진,강현규,노삼혁,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.

Business Scenario Assembly™ (BSA) : 인터넷 기반의 효율적인 비즈니스 솔루션 개발 환경에 관한 연구

전흥석(H. Seok Jeon),김태진(Taejin Kim),김태연(Taeyeon Kim),노삼혁(Sam H. Noh) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.2Ⅲ

현재와 미래의 e비즈니스 환경을 인터넷을 중심으로 끊임없이 변화 발전하고 있으나 e비즈니스의 복잡함과 역동적인 특성에 비해 지원해 줄 수 있는 인터넷 기술은 아직 매우 부족한 형편이다. 기존의 많은 개발 도구들은 비용이 많이 들거나 복잡하여 솔루션 개발에 매우 많은 시간과 비용이 소요되는 단점을 가지고 있다. 따라서, 본 논문에서는 소프트웨어 엔지니어가 아니라 비즈니스 실무 담당자가 급변하는 비즈니스 환경에 맞는 최적의 솔루션을 용이하게 구축할 수 있는 Business Scenario Assembly (BSA)라고 하는 개념 및 이의 구현에 대해 소개한다. BSA는 비즈니스 프로세스 주체들이 다양한 비즈니스 시나리오들을 실시간 커뮤니케이션을 통해 쉽게 공유, 재편, 변경하도록 하는 새로운 개념의 e비즈니스 솔루션 개발 도구이다. BSA를 이용한 역동적으로 변화하는 e비즈니스 환경에 최적의 솔루션을 매우 용이하게 구축할 수 있다.

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

전흥석(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만원대의 높은 가격에 판매되고 있다. 이것은 결국 청소로봇의 보편화에 큰 어려움으로 작용하고 있다. 따라서 본 논문에서는 개인용 컴퓨터를 이용하여 정보를 기억하고, 경로를 계산함으로써 청소로봇의 기능을 단순화하여 보다 저렴하고 신뢰성 있는 청소로봇 시스템을 제안한다.

선반입을 이용한 실용적이고 효율적인 데이터베이스 버퍼 관리 알고리즘

전흥석(H. Seok Jeon),노삼혁(Sam H. Noh) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.1B

본 논문에서는 선반입에 근거한 효율적인 디스크 버퍼 관리 정책인 Adaptive W²R 알고리즘을 제안한다. W²R 알고리즘은 버퍼캐쉬를 논리적으로 두개의 영역, 즉, Weighing Room과 Waiting Room으로 분할한다. Weighing Room은 적어도 한번 이상 참조된 블록을 위한 영역이며, Waiting Room은 선반입된 블록을 위한 영역이다. Adaptive W²R 알고리즘은 추가적인 오버헤드 없이 변화하는 파일 참조 형태에 따라 적절하게 Weighing Room과 Waiting Room의 분할율을 실시간으로 유지한다. 트레이스에 기반한 시뮬레이션 결과에 의하면 Adaptive W²R 알고리즘은 변화하는 파일참조형태에 잘 대처하며, 기존의 버퍼관리 정책들에 비해 가장 좋은 성능을 나타낸다.

선반입 통합 기법을 이용한 GNU / Linux 파일 시스템의 성능 향상에 관한 연구

전흥석(H. Seok Jeon),노삼혁(Sam H. Noh) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.2Ⅲ

버퍼 캐쉬의 관리를 위해 많은 교체 정책들과 선반입 정책들이 연구되어져 왔다. 그러나, GNU/Linux를 포함한 많은 실제의 운영체제들은 일반적으로 Least Recently Used (LRU)교체 정책을 사용한다. 본 논문에서는 끊임없이 적극적인 선반입이 이루어지는 가운데 단순하여 실제 시스템에서 채택하기 용이하다. 이 정책은 기본적으로 버퍼 교체를 위하여 LRU 정책을 사용한다. 그러나 정책의 모듈성으로 인해 어떤 교체 정책도 이 정책에 적용될 수 있다. SA-W²R 정책에서는 선반입을 위해 오버헤드가 적어 일반적으로 많이 사용되는 LRU-One Block Lookahead (OBL) 정책을 사용한다. GNU/Linux 커널 버전 2.2.14에 구현 된SA-W²R 정책은 응용 프로그램의 실행 시간에 있어 현재 버전의 GNU/Linux 보다 최고 23%의 성능 향상을 보였다.

선반입을 이용한 효율적인 버퍼 캐쉬 관리 알고리즘

전흥석(H. Seok Jeon),노삼혁(Sam H. Noh) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.5

본 논문은 선반입에 기반한 디스크 버퍼 관리 알고리즘인 W²R 알고리즘을 제안한다. W²R 알고리즘은 어떤 블록을, 언제 선반입할 것인가를 결정하기 위한 복잡한 선반입 정책 대신, LRU-OBL 알고리즘의 접근 방법을 따라 현재 참조되는 블록의 논리적 다음 블록을 선반입한다. LRU-OBL 알고리즘과의 기본적인 차이점은 W²R 알고리즘은 버퍼를 논리적으로 두개의 공간, 즉, Weighing Room과 Waiting Room으로 분할한다는 것이다. 참조되는 블록은 Weighing Room에 반입되고 선반입되는 논리적 다음 블록은 Waiting Room에 저장된다. 이렇게 함으로써, 무조건으로 참조되는 블록의 논리적 다음 블록을 선반입하는 LRU-OBL 정책의 단점을 해결한다. 구체적으로, 선반입되었으나 결코 참조되지 않을, 혹은 실제로 참조된다고 할지라도 교체될 블록보다 더 나중에 참조될 블록들을 위해 재 참조될 가능성이 있는 블록들을 교체하는 문제점들을 해결한다. W²R 알고리즘은 트레이스 기반 시뮬레이션을 통해 버퍼 캐쉬 적중률을 측정한 결과 2Q 알고리즘에 비해서는 최고 23.19 %, LRU-OBL 알고리즘에 비해서는 최고 10.25 %의 성능향상을 나타낸다. This paper proposes a prefetch-based disk buffer management algorithm, which we call W²R (Weighing/Waiting Room). Instead of using elaborate prefetching schemes to decide which block to prefetch and when, we simply follow the LRU-OBL (One Block Lookahead) approach and prefetch the logical next block along with the block that is being referenced. The basic difference is that the W²R algorithm logically partitions the buffer into two rooms, namely, the Weighing Room and the Waiting Room. The referenced, hence fetched block is placed in the Weighing Room, while the prefetched logical next block is placed in the Waiting Room. By so doing, we alleviate some inherent deficiencies of blindly prefetching the logical next block of a referenced block. Specifically, a prefetched block that is never used may replace a possibly valuable block and a prefetched block, though referenced in the future, may replace a block that is used earlier than itself. We show through trace driven simulation that for the workloads and the environments considered the W²R algorithm improves the hit rate by a maximum of 23.19 percentage points compared to the 2Q algorithm and a maximum of 10.25 percentage points compared to the LRU-OBL algorithm.

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

전흥석(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),조재욱(Jae Wook Jo),노삼혁(Sam H. Noh) 제어로봇시스템학회 2006 제어·로봇·시스템학회 논문지 Vol.12 No.5

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

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

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

미지의 환경에서 하이브리드 맵을 활용하는 모바일 로봇의 탐색

박정규(Jung Kyu Park),전흥석(Heung Seok Jeon),노삼혁(Sam H. Noh) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.4

모바일 로봇은 자신의 임무를 수행하기 위해 탐색 기능을 가지고 있어야 한다. 탐색은 감시 로봇, 구조 로봇, 자원 탐사 로봇 등에 사용될 수 있다. 로봇이 환경을 탐색하기 위해서는 지도와 같은 환경에 대한 정보를 가지고 있어야 한다. 그러나 기존에 많이 사용되는 그리드 지도는 용량이 너무 커서 모바일 로봇에 사용하기 힘들다는 문제를 가지고 있다. 본 논문에서는 저 사양의 모바일 로봇에서 사용할 수 있는 하이브리드 지도를 제안한다. 또한 제안하는 하이브리드 지도를 사용하여 모든 영역을 탐색하는 방법을 제안하고 있다. 제안하는 방법은 로봇의 작업 환경을 현재 처리할 수 있는 영역과 처리 할 수 없는 영역으로 나누고, 나누어진 영역을 탐색하는 동시에 지도를 업데이트하며 영역을 확장해 나간다. 탐색이 완료된 영역은 하이브리드 맵 형태로 저장한다. 생성한 하이브리드 맵을 사용하여 로봇은 장애물이 없는 영역으로 이동 경로를 생성할 수 있다. 실험결과에 따르면 기존 그리드 지도에 비해 약 6%의 메모리만을 사용해 환경 지도를 생성할 수 있었다. Mobile robot has the exploration function in order to perform its own task. Robot exploration can be used in many applications such as surveillance, rescue and resource detection. The workspace that robots performed in was complicated or quite wide, the multi search using the several mobile robots was mainly used. In this paper, we proposed a scheme that all areas are searched for by using one robot. The method to be proposed extract a area that can be explored in the workspace then the robot investigates the area and updates the map at the same time. The explored area is saved as a hybrid map that combines the nice attributes of the grid and topological maps. The robot can produce the safe navigation route without the obstacles by using hybrid map. The proposed hybrid map uses less memory than a grid map, but it can be used for complete coverage with the same efficiency of a topological map. Experimental results show that the proposed scheme can generate a map of an environment with only 6% of the memory that a grid map requires.