문법적 진화기법과 조건부 확률을 이용한 청소 로봇의 이동 패턴 계획

국문 초록 (Abstract)

청소 로봇은 가정에서 사용 가능한 대표적인 지능형 로봇이다. 고가형 청소 로봇은 센서로부터 정보를 제공받아 높은 커버리지 성능을 가진 알고리즘이 존재하지만, 저가형의 청소 로봇엔 적용하기 어렵다. 본 논문은 저가형의 청소 로봇과 같은 환경에서 효율적인 움직임을 구현하기 위해 문법적 진화기법기반의 청소 로봇의 이동 패턴을 계획하는 알고리즘을 제안한다. 이를 위해 배커스-나우르 표기법을 사용하여 이동 패턴 문법을 정의하고 진화연산을 통해 최적화된 프로그램을 생성하였다. 이와 더불어 프로그램생성 과정에서 획득한 문법 요소 간 조건부 확률 정보를 활용하였다. 제안 알고리즘의 성능 검증을 위해 청소 로봇 시뮬레이션을 활용하여 기존 알고리즘과 성능을 비교하였으며 실험 결과를 통해 본 논문에서 제안한 기법의 효율성을 확인하였다.

다국어 초록 (Multilingual Abstract)

The cleaning robot is popularly used as a home appliance. The state-of-the-art cleaning robot can clean more efficiently by using information gathered from its sensor, which is difficult for low-price cleaning robots due to limitation in this aspect. In this paper, we suggested a method for the moving pattern of cleaning robot based on grammatical evolution. Optimized program is generated by using moving pattern grammar, which is defined by Backus-Naur form. In addition, conditional probability is used between each of the grammar elements during the program creation process. The proposed method is evaluated by robot simulation in order to verify its performance and further compare it with existing algorithms. The experiment results showed that the proposed method is better than the compared algorithms.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련연구
• 3. 제안기법
• 4. 실험 및 결과 분석
• 5. 결론 및 향후 과제
• References

참고문헌 (Reference)

1 김병수, "청소로봇의 성능 및 소비자의 반응" 한국로봇학회 5 (5): 38-43, 2008

2 Acar, E. U., "Path planning for robotic demining: Robust sensorbased coverage of unstructured environments and probabilistic methods" 22 (22): 441-466, 2003

3 O’Neil, Michael, "Grammatical Evolution" Springer US 33-47, 2003

4 Koza J R, "Genetic Programming, Search Methodologies"

5 Choset, Howie, "Coverage of known spaces: The boustrophedon cellular decomposition" 9 (9): 247-253, 2000

6 Viet, H. H., "BA*: an online complete coverage algorithm for cleaning robots" 39 (39): 217-235, 2013

7 John H. Holland, "Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence" MIT Press 1992

8 Galceran, Enric, "A survey on coverage path planning for robotics" 62 (62): 1258-1276, 2013

9 Prassler, E., "A short history of cleaning robots" 9 (9): 211-226, 2000