[논문]미지의 환경에서 동작하는 SLAM 기반의 로봇 커버리지 알고리즘

박정규; 전흥석; 노삼혁

doi:10.9708/jksci.2010.15.1.061

미지의 환경에서 동작하는 SLAM 기반의 로봇 커버리지 알고리즘
A Robot Coverage Algorithm Integrated with SLAM for Unknown Environments 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.15 no.1, 2010년, pp.61 - 69

박정규 (홍익대학교 컴퓨터공학과) , 전흥석 (건국대학교 컴퓨터응용과학부) , 노삼혁 (홍익대학교 정보컴퓨터공학부)

초록
AI-Helper

로봇이 동작하는 환경을 완벽하게 커버리지 하기 위해서는 전체환경 지도를 가지고 있어야 한다. 그러나 대부분의 기존 커버리지 알고리즘은 로봇이 동작하기 전 사전에 생성된 지도가 있어야 동작 한다. 이런 이유로 기존의 커버리지 알고리즘은 미지의 환경에 바로 적용할 수 없는 문제를 가지고 있다. 미지의 환경에서 로봇이 모든 영역을 커버리지 하기위해서는 로봇스스로 환경 지도를 생성할 수 있어야한다. 본 논문에서는 SLAM 알고리즘을 통합하여 미지의 환경에서 로봇이 환경 지도를 생성하며 생성된 지도를 기반으로 커버리지를 수행하는 DmaxCoverage 알고리즘을 제안한다. 시뮬레이션 실험을 통해서 DmaxCoverage 알고리즘이 기존의 커버리지 알고리즘에 비해서 효율적임을 증명하였다.

Abstract ▼ AI-Helper

An autonomous robot must have a global workspace map in order to cover the complete workspace. However, most previous coverage algorithms assume that they have a grid workspace map that is to be covered before running the task. For this reason, most coverage algorithms can not be applied to complete coverage tasks in unknown environments. An autonomous robot has to build a workspace map by itself for complete coverage in unknown environments. Thus, we propose a new DmaxCoverage algorithm that allows a robot to carry out a complete coverage task in unknown environments. This algorithm integrates a SLAM algorithm for simultaneous workspace map building. Experimentally, we verify that DmaxCoverage algorithm is more efficient than previous algorithms.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 SLAM 알고리즘을 커버리지 알고리즘과 통합하여 로봇이 사전 정보가 없는 상황에서 동작할 수 있는 방안을 제안하고 있다.
이런 방식으로 나머지 사각형을 구하면 총 10개의 사각형을 구할 수 있다. 본 논문에서는 사각형 타일링한 목록을 구성할 때 드는 시간과 생성된 목록에서 모든 영역을 처리하는 영역을 선택할 때의 시간을 줄이기 위해 물체를 고려하는 타일링을 수행하고 있다.
본 논문에서는 새로운 커버리지 알고리즘으로 DmaxCoverage 알고리즘을 제안하고 있다. DmaxCoverage 알고리즘은 기존의 커버리지 알고리즘의 문제를 해결하기 위해 SLAM 알고리즘을 통합하고 있다.
본 논문에서는 환경의 사전 정보를 가지고 있지 않은 상태에서 영역을 커버리지 할 수 있는 DmaxCoverage 알고리즘을 제안한다. DmaxCoverage 알고리즘은 로봇이 처리해야 하는 영역을 작은 영역으로 나누어 처리하는 커버리지 알고리즘과 환경 지도를 생성하는 SLAM 알고리즘으로 구성되어 있다.
본 논문은 로봇 커버리지 알고리즘과 환경 정보 생성을 동시에 고려하고 있다. 기존 커버리지 알고리즘 분야에서 많은 연구들이 이루어 졌다.

가설 설정

Triangular-Cell-Based 지도 알고리즘은 Distance Transform 을 확장한 방법이다[11]. 이 알고리즘은 완벽한 커버리지 경로를 구성하기 위해 로봇이 처음 동작할 때 전체 환경 지도를 생성하는 것을 가정하고 있다. 초기 로봇이 환경의 가장 외곽벽을 따라 움직이며(Wall-Following) 환경을 파악 하면서 지도를 생성하고, 생성한 지도를 기반으로 완벽한 커버리지 경로를 생성하게 된다.
로봇이 동작하는 환경을 모두 커버리지 못하는 랜덤 알고리즘의 문제를 해결하기 위해 완벽한 커버리지를 고려하는 많은 연구가 진행되었다[7][8][9][10][11]. 진행된 커버리지 연구들은 로봇이 동작하기 전에 환경에 대한 정보를 가지고 있는 것을 가정하고 있다. 로봇이 환경 전체에 대한 사전 정보를 가지고 있고 시작 위치와 종료 위치를 알고 있을 때 모든 영역을 커버리지할 수 있는 이동 경로를 생성할 수 있다.

제안 방법

DmaxCoverage 알고리즘과 랜덤, 바둑판식 알고리즘의 성능 평가를 하기 위해 동일 환경에서 각각의 알고리즘을 수행하여 커버리지 효율을 비교해 보았다. 각 실험은 그림 3의 환경에서 수행되었으며 로봇의 초기 시작 위치를 다르게 조정하였다.
DmaxCoverage 알고리즘이 환경 정보가 없는 상태에서 커버리지 임무를 수행하기 위해서는 로봇이 실시간으로 환경 지도를 생성할 수 있어야 한다. DmaxCoverage 알고리즘은 실시간 지도를 생성할 수 있도록 Simultaneous Localization and Mapping(SLAM) 알고리즘을 통합 하였다.
로봇이 동작하는 환경으로 그림 3과 같이 아파트 형태의 주거지를 모델링한 지도를 사용하였다. 그림 3의 지도에서 표시된 P1, P2, P3은 로봇의 초기 시작 위치를 나타낸다.
본 논문에서 제안하는 알고리즘의 효율성과 성능을 증명하기 위해서 시뮬레이션 실험을 수행하였다. 실험에서는 랜덤 알고리즘과 바둑판식 알고리즘을 비교 대상으로 하였다.
AMCL은 주어진 환경 지도에서 로봇의 위치를 추정할 때 사용된다. 본 알고리즘에서는 AMCL 알고리즘에서 사용할 환경지도를 작성하기 위해 로봇이 위치한 곳에서 360도 회전을 하면서 최초 지도를 생성한다. 최초 생성된 지도를 기반으로 DmaxCoverage 알고리즘을 적용하여 영역의 커버를 시도하는 동시에 AMCL 방법을 사용하여 로봇의 위치를 추정한다.
본 알고리즘에서는 사각형 타일링에 의해 생성된 사각형의 목록중에서 바둑판식 알고리즘으로 처리 했을 때 가장 효율이 큰 사각형의 순서로 선택하여 처리를 하게 된다. 그러나 이 사각형을 선택하는 것은 잘 알려진 Set Cover 문제로 NPComplete 한 것으로 알려져 있다[19].
그림 5는 DmaxCoverage 알고리즘이 수행되면서 3번의 사각형 타일링이 수행되는 시간을 측정한 것이다. 사각형 타일링을 수행할 때 로봇이 처리한 영역을 물체로 처리하여 사각형 타일링에서 제외할 때의 타일링 시간(tiling-obstacle)과 처리한 영역을 사각형 타일링에서 제외하지 않았을 때의 타일링 시간(tiling-normal)을 측정한 것이다. 사각형 타일링을 수행할 때는 로봇이 생성한 환경 지도의 해상도를 낮추어 32 × 32셀의 그리드 지도를 만들어 사용하였다.
사각형 타일링 방법은 나누어야 하는 영역이 커짐에 따라 사각형 타일링 수행 시간이 비례해서 커지게 되는 문제를 가지고 있다. 제안하는 알고리즘에서는 사각형 타일링 수행 시간을 줄이기 위해서 두 가지를 고려하고 있다.

대상 데이터

논문에서 제안한 알고리즘과 기존의 알고리즘을 비교 평가하기 위해서 Player/Stage 시뮬레이션 환경을 사용하였다[20]. 실험에 사용된 시뮬레이션 프로그램의 버전은 Player 2.1.2/Stage 3.0.1이고, SICK 레이저(LMS200)을 장착한 Pioneer 2DX 로봇을 사용하였다. 로봇은 주행 속도는 0.
본 논문에서 제안하는 알고리즘의 효율성과 성능을 증명하기 위해서 시뮬레이션 실험을 수행하였다. 실험에서는 랜덤 알고리즘과 바둑판식 알고리즘을 비교 대상으로 하였다.

이론/모형

기존의 커버리지 알고리즘의 단점을 개선하기 위해 DmaxCoverage 알고리즘은 실시간으로 환경 지도를 생성하는 SLAM 알고리즘을 도입하였다. SLAM 알고리즘의 도입으로 DmaxCoverage 알고리즘에서는 사전에 환경 정보가 없는 상태에서 커버리지를 효율적으로 수행할 수 있다.
논문에서 제안한 알고리즘과 기존의 알고리즘을 비교 평가하기 위해서 Player/Stage 시뮬레이션 환경을 사용하였다[20]. 실험에 사용된 시뮬레이션 프로그램의 버전은 Player 2.
DmaxCoverage 알고리즘에서는 환경 지도를 생성하기 위해 SLAM 알고리즘을 사용하고 있다. 사용한 SLAM 알고리즘은 파티클 필터 기반의 Adaptive Monte Carlo Localization (AMCL) 방법으로 로봇의 위치를 추정할 때 사용한다[13][14]. AMCL은 주어진 환경 지도에서 로봇의 위치를 추정할 때 사용된다.
위에 설명한 것과 같이 DmaxCoverage 알고리즘은 처리해야 하는 영역을 나누기 위해 사각형을 나누는 작업을 하게 된다. 영역을 사각형 형태로 나누기 위해 사각형 타일링 방법(Rectangle Tiling Scheme)을 사용하였다[18].
이제부터 DMaxCoverage 알고리즘의 실행 과정을 설명하기 위해 그림 2를 활용하기로 한다. 로봇이 동작해야 하는 환경에 최초 투입되면 로봇은 처음 처리해야 하는 영역을 처리하기 위해 로봇이 가지고 있는 센서를 사용하여 환경 지도를 작성하게 된다.
본 알고리즘에서는 AMCL 알고리즘에서 사용할 환경지도를 작성하기 위해 로봇이 위치한 곳에서 360도 회전을 하면서 최초 지도를 생성한다. 최초 생성된 지도를 기반으로 DmaxCoverage 알고리즘을 적용하여 영역의 커버를 시도하는 동시에 AMCL 방법을 사용하여 로봇의 위치를 추정한다. 또한 로봇이 영역을 커버하면서 센서를 통해 수집한 정보를 사용하여 환경 지도를 계속 업데이트 하게 된다.

성능/효과

6초의 시간이 걸렸다. 3번 째 타일링이 수행되었을 때는 MBR이 확장되어 타일링 가능한 면적이 약 51%로 증가 하였으나 시간은 약 0.4초로 감소하였다.
DmaxCoverage 알고리즘은 기존의 커버리지 알고리즘의 문제를 해결하기 위해 SLAM 알고리즘을 통합하고 있다. SLAM 알고리즘이 통합된 DmaxCoverage 알고리즘의 실험 결과를 통해서 DmaxCoverage 알고리즘이 기존 알고리즘이 처리 할 수 없었던 환경에서 동작할 수 있으며, 랜덤 알고리즘에 비해서 최대 38% 효율적임을 알 수 있었다.
실험 결과 초기 5분 정도까지 DmaxCoverage 알고리즘의 성능이 랜덤 또는 바둑판식 알고리즘에 비해서 성능이 떨어지는 것을 알 수 있다. 이는 DmaxCoverage 알고리즘이 초기 환경지도를 생성할 때 사용하는 시간이 크기 때문이다.
SLAM 알고리즘을 통합한 DmaxCoverage 알고리즘은 사전 정보가 없는 상황에서 로봇이 동작할 수 있도록 로봇 스스로 생성한 지도를 커버리지에 사용한다. 실험 결과에 따르면 DmaxCoverage 알고리즘은 환경 정보가 없는 상태에 적용할 수 있으며 기존의 커버리지 알고리즘에 비해 최대 38% 효율적임을 알 수 있다.
그림 4는 DmaxCoverage 알고리즘과 랜덤, 바둑판식 알고리즘을 사용했을 때 로봇의 동작 시간에 따른 커버리지 완료 비율을 보여주고 있다. 실험 결과에 따르면 DmaxCoverage 알고리즘이 랜덤, 바둑판식 알고리즘에 비해서 최대 38% (P1 지점의 결과), 최소 21%의 성능 향상을 보였다(P3 지점의 결과). DmaxCoverage 알고리즘은 로봇이 처리할 수 있는 영역을 작은 공간으로 나누어 처리함으로 영역의 커버리지 효율이 계속 증가하지만 랜덤, 바둑판식 알고리즘은 복잡한 구역에서 더 이상 청소를 하지 못하고 청소한 구역만을 반복해서 청소하는 문제가 발생하여 영역의 커버리지 비율이 증가하지 못하고 일정 시간 동안 정체되는 현상이 발생되고 있다.
랜덤 알고리즘으로 생성한 환경 지도는 바둑판식 알고리즘 환경지도에 비해서 동작하는 환경을 좀 더 자세히 반영하고 있다. 실험에서는 바둑판식 알고리즘을 적용한 로봇이 환경의 위쪽 부분을 반복해서 처리하여 환경의 아래쪽 모습을 반영하지 못한 것을 알 수 있었다.
FastSLAM 알고리즘에서는 위치를 업데이트하는 계산 복잡도 문제를 줄이기 위해서 로봇의 위치 추정과 위치 표식 추정을 나누어 처리하여 위치 표식을 추정할 때 기존에 가지고 있는 로봇의 모든 위치 정보를 다시 계산하지 않는다. 이 결과 업데이트되는 계산량과 복잡도를 줄여 기존의 SLAM 알고리즘에 비해서 빠른 처리가 가능하다.
로봇이 영역을 처리하는 동안 2가지 상황이 발생할 수 있다. 첫 번째로 로봇이 생성하는 환경 지도가 현재 MBR의 크기보다 확장될 수 있다. 이때는 새로운 MBR을 구하고, 사각형 타일링, Set Cover를 다시 수행하여 새로 생성된 사각형 목록을 기반으로 임무를 수행하게 된다(그림 2: 라인 11).

후속연구

이 문제를 해결하기 위해서 차후 연구과제로 동적인 환경에서 DmaxCoverage 알고리즘을 적용하는 방법에 대해서 연구할 예정이다. 또한 외부의 센서를 사용하는 환경에서 DmaxCoverage 알고리즘 효율을 높일 수 있는 방법에 대해서 연구할 예정이다.
현재 DmaxCoverage 알고리즘은 로봇이 동작하는 환경을 정적이라고 가정하고 있다. 이 문제를 해결하기 위해서 차후 연구과제로 동적인 환경에서 DmaxCoverage 알고리즘을 적용하는 방법에 대해서 연구할 예정이다. 또한 외부의 센서를 사용하는 환경에서 DmaxCoverage 알고리즘 효율을 높일 수 있는 방법에 대해서 연구할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	커버리지 알고리즘은 무엇인가?	많은 경로 탐색 알고리즘에 기본이 되는 것으로 커버리지(Coverage) 알고리즘을 들 수 있다[1][2][3][4][5]. 커버리지 알고리즘은 로봇이 동작하는 환경의 모든 영역을 방문할 수 있도록 이동 경로를 생성해 주는 알고리즘이다.
	DmaxCoverage 알고리즘의 가장 큰 특징은 무엇인가?	DmaxCoverage 알고리즘의 가장 큰 특징은 로봇이 동작하는 환경을 효율적으로 처리할 수 있는 영역으로 나누어 처리하는 것이다. 바둑판식 커버리지 알고리즘을 기반으로 하는 DmaxCoverage 알고리즘은 바둑판식 알고리즘의 효율성을 최대화하기 위해 로봇이 처리할 수 있는 영역을 사각형 형태로 나누어 처리하게 된다.
	바둑판식 경로 알고리즘의 단점은 무엇인가?	바둑판식 알고리즘은 커버리지 하는 영역이 작거나 영역 내부에 장애물이 없을 경우 좋은 효율을 보여준다. 그러나 로봇이 동작하는 환경이 복잡 할 때 처리한 영역을 반복해서 이동하는 문제로 성능이 떨어지는 문제를 가지고 있다.

참고문헌 (20)

R. D. Schraft, M. Hagele, and H. Volz, "Service robots: the appropriate level of automation and the role of users/operators in the task execution," In Proceedings of the International Conference Systems, Man, and Cybernetics, Vol. 4, pp.163-169, Le Touquet, France, Oct. 1993.
R. N. Carvalho, H. A. Vidal, P. Vieira and M. I. Ribeiro, "Complete Coverage Path Planning and Guidance for Cleaning Robots," In Proceedings of the IEEE International Symposium on Industrial Electronics, pp.677-682, Guimaraes, Portugal, Jul. 1997.
S. H. Yoon, S. H. Park, B. J. Choi, and Y. J. Lee, "Path Planning for Cleaning Robots: A Graph Model Approach," In Proceedings of the International Conference on Control, Automation and Systems, pp. 2861-2864, Cheju, Korea, Oct. 2001.
S. C. Wong and B. A. MacDonald, "A topological coverage algorithm for mobile robots," In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. 2, pp. 1685-1690, Las Vegas, U.S.A., Oct. 2003.
N. Agmon, M. Hozon, and G. A. Kaminka, "Constructing Spanning Trees for Efficient Multi-Robot Coverage," In Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1698-1703, Florida, U.S.A., May 2006
J. Jones, "Robots at the Tipping Point: The Road to the iRobot Roomba," IEEE Robotics and Automation Magazine, 2006.
R. A. Jarvis and J. C. Byrne, "Robot Navigation: Touching, Seeing and Knowing," In Proceedings of the Australian Conference on Artificial Intelligence, Nov. 1986.
H. Choset and P. Pignon, "Coverage Path Planning: the Boustrophedon Cellular Decomposition," In Proceedings of the International Conference on Field and Service Robotics, Canberra, Australia, Dec. 1997.
A. Zelinsky, R. A. Jarvis, J. C. Byrne, and S. Yuta, "Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot," In Proceedings of the International Conference on Advanced Robotics, pp.533-538, Tokyo, Japan, Nov. 1993.
A. Zelinsky, "Using path transforms to guide the search for findpath in 2D," International Journal of Robotics Research, Vol. 13(4), pp. 315-325, Aug. 1994.

상세보기
J. S. Oh, Y. H. Choi, J. B. Park, and Y. F. Zheng, "Complete Coverage Navigation of Cleaning Robots Using Triangular-Cell-Based Map," IEEE Transactions on Industrial Electronics, Vol. 51(3), pp. 718-726, Jun. 2004.

상세보기
S. J. Julier, J. K. Uhlmann, and H. F. Durrant-Whyte. "A New Approach for Filtering Nonlinear Systems," In Proceedings of the American Control Conference, Vol. 3, pp. 1628-1632, Seattle, WA, Jun. 1995.
D. Fox, J. Hightower, L. Liao, D. Schulz, and G. Borriello, "Bayesian Filtering for Location Estimation," IEEE Pervasive Computing, Vol. 2, No. 3, pp. 24-33, Jul.-Sep. 2003

상세보기
D. Fox, W. Burgard, and S. Thrun, "Active Markov Localization for Mobile Robots," Robotics and Autonomous Systems, Vol. 25, No. 3-4, pp. 195-207, Nov. 1998

상세보기
S. Thrun, D. Fox, W. Burgard, and F. Dellaert, "Robust Monte Carlo Localization for Mobile Robots," In Proceedings of the National Conference on Artificial Intelligence, Vol. 128, No. 1-2, pp. 99-141, May, 2000.
G. Dissanayake, P. Newman, H. F. Durrant-Whyte, S. Clark, and M. Csobra, "A Solution to the Simultaneous Localisation and Mapping (SLAM) Problem," IEEE Transactions on Robotics and Automation, Vol. 17, pp.229-241, 2001.

상세보기
M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit, "FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem," In Proceedings of the AAAI National Conference on Artificial Intelligence, pp. 593-598, Alberta, Canada, Jul.-Aug. 2002.
I. Stewart, "Squaring the Square," Scientific American, Vol. 277, pp. 94-96, Jul. 1997.
U. Feige, "A Threshold of ln n for Approximating Set Cover," Journal of the ACM (JACM), Vol. 45, No. 4, pp.634-652, Jul. 1998.

상세보기
The Player Project, http://playerstage.sourceforge.net/

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증