[논문]멀티로봇에 대한 전체영역 경로계획

남상현; 신익상; 김재준; 이순걸

멀티로봇에 대한 전체영역 경로계획
Complete Coverage Path Planning for Multi-Robots 원문보기

한국정밀공학회지 = Journal of the Korean Society for Precision Engineering, v.26 no.7 = no.220, 2009년, pp.73 - 80

남상현 (청주대학교 전자정보공학부) , 신익상 (농촌진흥청 국립농업과학원) , 김재준 (경희대학교 기계공학과) , 이순걸 (경희대학교 기계공학과)

Abstract ▼ AI-Helper

This paper describes a path planning algorithm, which is the minimal turning path based on the shape and size of the cell to clean up the whole area with two cleaning robots. Our method divides the whole cleaning area with each cell by cellular decomposition, and then provides some path plans among of the robots to reduce the rate of energy consumption and cleaning time of it. In addition we suggest how to plan between the robots especially when they are cleaning in the same cell. Finally simulation results demonstrate the effectiveness of the algorithm in an unknown area with multiple robots. And then we compare the performance index of two algorithms such as total of turn, total of time.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문은 청소로봇의 경로계획 시 셀 영역의 모양과 크기에 따라 셀 내부의 최소 방향전환 경로계획을 설계함으로써 기존의 방식보다 방향 전환 횟수가 적은 멀티로봇을 이용한 전 영역 청소계획방식을 제안하였다. 이동로봇이 방향전환을 하기 위해서는 우선 정지 후 회전을 해야만 됨으로 많은 시간이 소비되며 정지 후 가/감속을 하기 위해서는 많은 전력이 소비된다.
이 논문에서는 이 논문의 장점을 보이기 위해 기조의 셀분할 방식과 제안하는 멀티로봇의 경로계획을 비교하였다. 제안된 방법은 실내환경에서 협력하여 청소하기 위해 멀티로봇을 적용하였고 두 알고리즘의 실행인덱스를 비교하였다.

가설 설정

그림 7 는 부분정점의 모양에 따라 6 가지 청소패턴을 나타낸 것이다. 여기서, 그림 7(d), (e), (f)는 각각 그림 7(a), (b), ©와 셀의 방향만 틀릴 뿐 청소형태는 동일함을 알 수 있다. 그리고, 3 면이 닫혀있는 오목한 형태의 지역은 그림 7(a) 또는 (e)의 경로계획을 하면 된다.

제안 방법

이동로봇이 방향전환을 하기 위해서는 우선 정지 후 회전을 해야만 됨으로 많은 시간이 소비되며 정지 후 가/감속을 하기 위해서는 많은 전력이 소비된다. 그러므로 청소할 영역의 모양에 따라 최소의 방향전환을 하도록 플로우네트웍을 이용한 셀 분할방식을 제안하였다. 넓은 청소영역을 여러 플로우네트웍으로 분리하여 해석함으로써 좀더 쉽게 경로계획을 할 수 있었다.
본 논문의 2 절에서는 전체영역경로계획의 대표적인 3 가지 경로계획을 살펴보았다. 그리고 3 절에서는 청소공간의 맵을 완성하기 위한 벽 추종 (wallfollowing) 방식과 임계점(critical Point)을 기준으로청소영역을 셀들로 나누는 셀 분할방식에 대하여 살펴 보았다. 그리고 플로우네트웍을 이용한 전체영역 경로계획과 최소 방향전환을 위한 셀 내부경로계획에 대해 세부적으로 설명하였고 멀티로봇이 공통된 셀을 청소 시 협력해서 경로계획을 수행하는 방법에 대해 제안하였다.
그리고 플로우네트웍을 이용한 전체영역 경로계획과 최소 방향전환을 위한 셀 내부경로계획에 대해 세부적으로 설명하였고 멀티로봇이 공통된 셀을 청소 시 협력해서 경로계획을 수행하는 방법에 대해 제안하였다. 그리고 4 절에서는 기존의 방식과 제안된 방식의 전 영 역경로계획을 시뮬레이션으로 비교하였고, 마지막으로 5 절에서 결론을 도출하였다.
본 알고리즘은 전체 청소영역을 셀들로 분리한 후 셀들을 플로우네트웍으로 표현하고 셀들 사이의 경로를 최적화하였다. 그리고 각 셀에 입출력 부분정점을 설계해서 각 셀의 모양에 따라 셀의 모양에 맞는 최적의 경로들을 생성해주는 전 영역 경로계획을 작성하였다. 본 논문의 2 절에서는 전체영역경로계획의 대표적인 3 가지 경로계획을 살펴보았다.
그리고 3 절에서는 청소공간의 맵을 완성하기 위한 벽 추종 (wallfollowing) 방식과 임계점(critical Point)을 기준으로청소영역을 셀들로 나누는 셀 분할방식에 대하여 살펴 보았다. 그리고 플로우네트웍을 이용한 전체영역 경로계획과 최소 방향전환을 위한 셀 내부경로계획에 대해 세부적으로 설명하였고 멀티로봇이 공통된 셀을 청소 시 협력해서 경로계획을 수행하는 방법에 대해 제안하였다. 그리고 4 절에서는 기존의 방식과 제안된 방식의 전 영 역경로계획을 시뮬레이션으로 비교하였고, 마지막으로 5 절에서 결론을 도출하였다.
본 논문에서 제안한 최소 방향전환 경로계획의 장점을 보이기 위하여, 기존의 셀 분할 방식을[11] 이용한 멀티로봇의 경로계획과 제안하는 멀티로봇의 경로계획 알고리즘을 시뮬레이션으로 비교하여보았다.
본 논문에서는 멀티로봇이 방향전환 때 많은 시간과 전력을 소비하기 때문에 청소 할 영역의 모양에 따라 최소의 방향전환을 갖도록 청소공간을 여러 플로우 네트워크로 분리하여 해석하는 방법 15 을 제안하였다. 본 알고리즘은 전체 청소영역을 셀들로 분리한 후 셀들을 플로우네트웍으로 표현하고 셀들 사이의 경로를 최적화하였다.
15 을 제안하였다. 본 알고리즘은 전체 청소영역을 셀들로 분리한 후 셀들을 플로우네트웍으로 표현하고 셀들 사이의 경로를 최적화하였다. 그리고 각 셀에 입출력 부분정점을 설계해서 각 셀의 모양에 따라 셀의 모양에 맞는 최적의 경로들을 생성해주는 전 영역 경로계획을 작성하였다.
전체 경 로계 획 을 하기 위한 셀 경 로, Partly {Cel", Celk, Cell*와 같다. 이동로봇이 방향전환을 하기 위해서는 우선 정지 후 회전을 해야만 됨으로 많은 시간과 많은 전력이 소비되므로 기존의 방식보다 방향 전환 횟수와 총시간을 시뮬레이션으로 비교 하였다.
방문한 셀의 값은 증가하고 주위에서 가장 낮은 값을 가진 셀로 이동하는 경로 계획을 말한다. 이때발생되는 많은 방향전환을 줄이기 위하여 셀의 값으로 거 리함수와 방향전환 함수를 이용하였다J
비교하였다. 제안된 방법은 실내환경에서 협력하여 청소하기 위해 멀티로봇을 적용하였고 두 알고리즘의 실행인덱스를 비교하였다.
완료되었다. 즉, 로봇들은 LRF 와 함께 실내 환경의 크기와 장애물의 윤곽을 얻기 위해 벽 추종 항해를 실행하였다. 벽추종시 로봇 왼쪽의 센서 데이터는 벽으로 인식되고 오른쪽의 센서 데이터는 장애물로 인식하게 된다.

대상 데이터

이 논문에서 기술한 알고리즘은 MSRS(Microsoft Robotics Studio)를 이용하여 시뮬레이션 하였다. 실험을 하기 위한 시뮬레이션 환경은 5m*5m 실내이고 2개의 장애물이 놓여있고 장애물 정보는 알 수 없다.

이론/모형

경로계획을 나타내었다. 넓이 우선방식, BFS(breadth first search)을 이용하였고, 로봇은 시작 셀(Cell)로부터 가장 가까운 셀로 경로계획을 함을 볼 수 있다.
멀티로봇이 효율적인 협동작업을 위해 실시간으로 셀을 할당하는 동적 분할방식을 이용하였다. 이 방법은 청소영역을 셀 분할하고 로봇들에게 셀들이 할당된 후 할당된 셀들은 플로우네트웍으로표현하고 셀들 사이의 경로를 최적화 하게 된다.
실내환경에서 벽과 장애물을 인식하기 위해 LRF(Laser Range Finder) 를 이용해 벽주종 (wallflowing) 을 한다. 청소로봇은 서로 반대방향에서 시계방향으로 이동하고 두 대의 로봇이 다른 로봇의 출발점에 도착할 때 벽 추종 방식은 완료된다.
환경을 나타내었다. 이 논문에서 기술한 알고리즘은 MSRS(Microsoft Robotics Studio)를 이용하여 시뮬레이션 하였다. 실험을 하기 위한 시뮬레이션 환경은 5m*5m 실내이고 2개의 장애물이 놓여있고 장애물 정보는 알 수 없다.

성능/효과

테이블 2는 로봇이 청소지 역을 30cm/s 으로 빠르게 청소할 때, 기존의 기존의 알고리즘과 제안된 알고리즘을 이용하여 청소가 완료되었을 때 전체 회전수와 총 소비되는 시간을 볼 수 있다" 제안된 알고리즘은 기존의 방식보다 전체 회전수와 소비되는 시간이 22.4%와 15%로 줄어들었다. 시뮬레이션 결과에서, 제안된 멀티로봇이 기존의 알고리즘보다 적은 회전과 총소비 시간을 가짐으로써 기존의 알고리즘 보다 더 효율적인 경로계획을 제공한다.
넓은 청소영역을 여러 플로우네트웍으로 분리하여 해석함으로써 좀더 쉽게 경로계획을 할 수 있었다. 각 셀들 사이의 경로계획을 한 후 셀 내부의 최적의 경로계획을 함으로써 제안한 전체영역경로계획을 완성하였다. 그리고 시뮬레이션을 이용해 제안된 전체영역경로계획방식이 기존의 방식보다 효율성이 양호함을 보였다.
각 셀들 사이의 경로계획을 한 후 셀 내부의 최적의 경로계획을 함으로써 제안한 전체영역경로계획을 완성하였다. 그리고 시뮬레이션을 이용해 제안된 전체영역경로계획방식이 기존의 방식보다 효율성이 양호함을 보였다.
4%와 15%로 줄어들었다. 시뮬레이션 결과에서, 제안된 멀티로봇이 기존의 알고리즘보다 적은 회전과 총소비 시간을 가짐으로써 기존의 알고리즘 보다 더 효율적인 경로계획을 제공한다.

참고문헌 (21)

Ryu, J. C., Park, K. H., Lee, S. G. and Rhim, S. S, "A Study on Development of Performance Metrics for Autonomous Cleaning Robot," Journal of the Korean Society for Precision Engineering, Vol. 23, No. 7, pp.7-13, 2006
Ge, S. S. and Cui, Y. J., "New potential function for mobile robot path planning," IEEE Trans. Robotics and Automat., Vol. 16, No. 5, pp. 615-620, 2000

상세보기
Zelinsky, A., Jarvis, R. A. and Byrne, J. C., "Planning paths of complete coverage of an unstructured environment by a mobile robot," Proc. IEEE Int. Conf. Robot. Automat., pp. 533-538, 1993
Hofner, C. and Schmidt, G., "Path planning and guidance techniques for an autonomous mobile cleaning robots," Robotics and Autonomous Systems, Vol. 14, No. 2-3, pp. 199-212, 1995

상세보기
Schmidt, G. and Hofer, C., "An advanced planning and navigation approach for autonomous cleaning robot operations," Proc. IEEE Int. Conf. Intelligent Robots and Sys., Vol. 2, pp. 1230-1235, 1998
Carvalho, R. N., Vidal, H. A., Vieira, P. and Ribeiro, M. I., "Complete coverage path planning and guidance for cleaning robots," Proc. IEEE Int. Symp. Industrial Electronics, Vol. 2, pp. 677-682, 1997
Zenlinsky, A., "A mobile robot exploration algorithm," IEEE Trans. Robotics and Automation, Vol. 8, No. 6, pp. 707-717, 1992

상세보기
Oh, J. S., Park, J. B. and Choi, Y. H., "Complete coverage navigation of clean robot based on the triangular cell map," Proc. IEEE Int. Symp. Industrial Electronics, Vol. 3, pp. 2089-2093, 2001
Gabriely, Y. and Rimon, E., "Spanning-tree based coverage of continuous areas by a mobile robot,"Proc. IEEE Int. Conf. Robot. Automat., Vol. 2, pp.1927-1933, 2001
Acar, E. U., Choset, E. U., Zhang, Y. and Schervish,M., 'Path planning for robotics demining: robust sensor-based coverage of unstrucured environments and probabilistic methods,' Int. J. Robot. Res., Vol.22, No. 7-8, pp. 441-466, 2003

상세보기
Choset, H., "Coverage of known spaces: the boustrophedon cellular decomposition," Autonomous Robots, Vol. 9, No. 3, pp. 247-253, 2000

상세보기
Acar, E. U. and Choset, H., "Critical point sensing in unknown environments," Proc. IEEE Int. Conf.Robot. Automat., Vol. 4, pp. 3803-3810, 2000
Acar, E. U., Choset, H., Rizzi, A. A., Atkar, P. N. andHull, D., "Morse decompositions for coverage tasks," Int. J. Robot. Res., Vol. 21, No. 4, pp. 331-334, 2002

상세보기
Nam, S. H., Suk, S. W., Moon, S. B. and Lee, K. M.,"Obstacle recognition and localization for vacuum cleaning robots employing vision cameras," Proc.32nd Int. Symp. Robot., pp. 1266-1270, 2001
Nam, S. H. and Moon, S. B., "Minimal Turning Path Planning for Cleaning Robots Employing Flow Networks," Journal of Control, Automation, and Systems Engineering, Vol. 11, No. 9, pp. 789-794, 2005

원문보기 상세보기
Weiss, M. A., "Data Structures and Algorithm Analysis In C," Addison Wesley Longman, pp. 295-303, 1997
Hert, S. and Richards, B., "Multiple Robot MotionPlanningParallel Processing + Geometry," Sensor Based Intelligent Robote, LNCS 2238, Springer, pp.195-215, 2002

상세보기
Jager, M. and Nebel, B., "Dynamic Decentralized Area Partitioning for Cooperating Cleaning Robot," Proc. IEEE Int. Conf. Robot, Vol. 4, pp. 3577-3582, 2002
Saitov, D., Umirov, U., Park, J. I., Choi, J. W. and Lee,S. G., "Effective Map Building Using a Wave Algorithm in a Multi-Robot System," International Journal of Precision Engineering and Manufacturing,Vol. 9, No. 2, pp. 69-74, 2008
Kim, E.-S. and Joo, K.-S., "Moving Path Following of Autonomous Mobile Robot using Fuzzy," Journal of the Korean Society for Precision Engineering, Vol.17, No. 5, pp. 84-92, 2000
Cha, Y.-Y., "Global Path Planning of Mobile Robot Using String and Modified SOFM," Journal of the Korean Society for Precision Engineering, Vol. 25, No. 4, pp. 69-76, 2008

저자의 다른 논문 :

LOADING...

표제어: 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

연합인증