[go: up one dir, main page]

KR20140086245A - 제한된 시간 내에서의 로봇 커버리지 방법 및 시스템 - Google Patents

제한된 시간 내에서의 로봇 커버리지 방법 및 시스템 Download PDF

Info

Publication number
KR20140086245A
KR20140086245A KR1020120156492A KR20120156492A KR20140086245A KR 20140086245 A KR20140086245 A KR 20140086245A KR 1020120156492 A KR1020120156492 A KR 1020120156492A KR 20120156492 A KR20120156492 A KR 20120156492A KR 20140086245 A KR20140086245 A KR 20140086245A
Authority
KR
South Korea
Prior art keywords
cell
coverage
robot
quot
robots
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Abandoned
Application number
KR1020120156492A
Other languages
English (en)
Inventor
노상현
지상훈
Original Assignee
레드원테크놀러지 주식회사
지상훈
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 레드원테크놀러지 주식회사, 지상훈 filed Critical 레드원테크놀러지 주식회사
Priority to KR1020120156492A priority Critical patent/KR20140086245A/ko
Publication of KR20140086245A publication Critical patent/KR20140086245A/ko
Abandoned legal-status Critical Current

Links

Images

Classifications

    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B25—HAND TOOLS; PORTABLE POWER-DRIVEN TOOLS; MANIPULATORS
    • B25J—MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES
    • B25J9/00—Programme-controlled manipulators
    • B25J9/16—Programme controls
    • B25J9/1679—Programme controls characterised by the tasks executed
    • B25J9/1682—Dual arm manipulator; Coordination of several manipulators
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B25—HAND TOOLS; PORTABLE POWER-DRIVEN TOOLS; MANIPULATORS
    • B25J—MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES
    • B25J19/00—Accessories fitted to manipulators, e.g. for monitoring, for viewing; Safety devices combined with or specially adapted for use in connection with manipulators
    • B25J19/06—Safety devices
    • B25J19/061—Safety devices with audible signals

Landscapes

  • Engineering & Computer Science (AREA)
  • Robotics (AREA)
  • Mechanical Engineering (AREA)
  • Multimedia (AREA)
  • Manipulator (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)

Abstract

본 발명은 다중 로봇이 작업 공간을 커버리지하는 방법에 관한 것으로서, 이 방법은 다중 로봇에 대하여 최소 시간 속도 프로파일을 생성하고, 최소 시간 속도 프로파일을 기초로 하여 다중 로봇에 대하여 작업 공간 중 방문 위치의 수효를 할당하며, 다중 로봇이 방문 위치의 수효에 따라 작업 공간을 커버리지하도록 한다.

Description

제한된 시간 내에서의 로봇 커버리지 방법 및 시스템 {METHOD AND SYSTEM FOR COVERAGE OF MULTIPLE MOBILE ROBOTS WITHIN CONSTRAINED TIME}
본 발명은 로봇 커버리지 방법 및 시스템에 관한 것으로, 더 자세하게는 제한된 시간 내에서의 다중 이동 로봇 커버리지 방법 및 시스템에 관한 것이다.
커버리지 알고리즘은 미리 알려지거나 또는 알려지지 않은 환경에서 타겟 작업 공간의 모든 지점으로 로봇을 안내할 수 있도록 한다. 효과적인 커버리지 알고리즘이 구축되면, 그것은 영역 커버리지 작업뿐만 아니라 센서 커버리지 문제에도 적용 할 수 있다. 로봇 자동화를 위한 커버리지 알고리즘이 요구되는 응용 분야로서 지역 검사, 지도 구축(map building), 감시, 정찰, 바닥 청소, 페인트 분사, 제초 작업, 지뢰 제거, 그리고 수확 등이 있다.
커버리지 문제는 많은 연구자들에 의해 다양한 전략을 사용하여 연구되어 왔다. 로봇 커버리지의 작업 공간 모델링을 위한 가장 널리 알려진 두 가지 접근 방법은 셀적 분해와 그리드 기반의 표현 방법으로, H. Choset and P. Pignon의 “Coverage path planning: The boustrophedon cellular decomposition,” Int. Conf. on Field and Service Robotics, Canberra, Australia, 1997 와, H. Choset, “Coverage of known space: The boustrophedon cellular decomposition,” Autonomous Robots, vol.9, pp.247-253, 2000 등의 연구가 있다.
이외에도 다양한 방법으로 커버리지를 수행하는 방법이 연구되어 왔으나, 셀적 분해 방법이나 그리드 기반의 커버리지 방법 등은 로봇이 누락없이 모든 셀을 방문하여 작업 공간의 완전한 커버리지를 보장하기 위하여 주로 로봇의 경로 계획에 중점을 두고 있다.
KR 10-2012-0054669 A
본 발명이 해결하고자 하는 과제는 다중 이동 로봇이 최소 시간 내에 작업 공간 전체를 커버리지할 수 있도록 하는 다중 로봇 커버리지 방법 및 시스템을 제공하는 것이다.
본 발명의 실시예에 따른 작업 공간을 다중 로봇이 커버리지하도록 하는 로봇 커버리지 방법은, 상기 작업 공간을 미리 정해진 크기의 그리드 셀로 분할하는 단계, 상기 다중 로봇에 대하여 상기 작업 공간 중 두 개의 방문 위치 사이의 최소 시간 속도 프로파일을 생성하는 단계, 상기 최소 시간 속도 프로파일을 기초로 하여 상기 다중 로봇에 대하여 상기 작업 공간 중 방문 위치의 수효를 할당하는 단계, 그리고 상기 다중 로봇이 상기 방문 위치의 수효에 따라 상기 작업 공간을 탐색하는 단계를 포함한다.
본 발명에 의하면 다중 로봇에 대하여 최소 시간 속도 프로파일을 생성하고 작업 공간 중 방문 위치의 수효를 할당함으로써 최소 시간 내에 다중 이동 로봇이 작업 공간을 커버리지할 수 있다.
도 1은 본 발명의 실시예에 따른 커버리지 제어 방법이 적용되는 이동 로봇을 개략적으로 도시한 도면이다.
도 2는 본 발명의 실시예에 따른 로봇 커버리지 제어 방법에 대한 설명에 참조되는 도면이다.
도 3은 본 발명의 실시예에 따른 커버리지 제어 방법을 위한 최소 시간 속도 프로파일을 나타낸 도면이다.
도 4 및 도 5는 작업 공간의 셀적 분해에 대한 설명에 참조되는 도면이다.
도 6 및 도 7은 본 발명의 실시예에 따른 로봇 커버리지 방법에 대한 설명에 참조되는 도면이다.
도 8 및 도 9는 본 발명에 따른 로봇 커버리지 방법에 대한 설명에 제공되는 흐름도이다.
본 명세서 및 청구범위에 사용된 용어나 단어는 통상적이거나 사전적인 의미로 한정해서 해석되어서는 아니 되며, 발명자는 그 자신의 발명을 가장 최선의 방법으로 설명하기 위해 용어의 개념을 적절하게 정의할 수 있다는 원칙에 입각하여 본 발명의 기술적 사상에 부합하는 의미와 개념으로 해석되어야만 한다.
따라서 본 명세서에 기재된 실시예와 도면에 도시된 구성은 본 발명의 가장 바람직한 실시예에 불과할 뿐이고 본 발명의 기술적 사상을 모두 대변하는 것은 아니므로, 본 출원시점에 있어서 이들을 대체할 수 있는 다양한 균등물과 변형 예들이 있을 수 있음을 이해하여야 한다.
그러면 첨부한 도면을 참고로 하여 본 발명의 실시예에 대하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 상세히 설명한다.
도 1은 본 발명의 실시예에 따른 커버리지 제어 방법이 적용되는 이동 로봇을 개략적으로 도시한 도면이다.
도 1을 참고하면, n개의 2-자유도 바퀴형(wheeled) 이동 로봇은 다음 [수학식 1]과 같이 표현된다.
[수학식 1]
Figure pat00001
여기서
Figure pat00002
는 각각 i 번째 로봇의 최대 속도 및 최대 가속도이다. 예를 들어 DC 모터로 구동되는 이동 로봇의 최대 속도는 DC 모터의 최대 RPM과 기어 비에 의존하고, 최대 가속도는 모터 토크와 로봇의 유효 관성(effective inertia)에 의존한다.
각 로봇의 운동학 모델은 다음 [수학식 2]와 같이 표현된다.
[수학식 2]
Figure pat00003
여기서
Figure pat00004
Figure pat00005
에 대하여,
Figure pat00006
,
Figure pat00007
Figure pat00008
,
Figure pat00009
이다. 이때,
Figure pat00010
는 전역 참조 좌표계(global reference coordinate frame)
Figure pat00011
에서 i 번째 이동 로봇의 자세를 나타내고,
Figure pat00012
는 선속도 및 각속도이다.
Figure pat00013
는 각각 왼쪽 및 오른쪽 모터의 속도이고, (D, S)는 두 구동 바퀴의 직경과 두 모터를 연결하는 모터 축의 길이이다.
도 2는 본 발명의 실시예에 따른 로봇 커버리지 제어 방법에 대한 설명에 참조되는 도면이다.
도 2에 도시한 것처럼 다중 이동 로봇의 협력 커버리지 문제는 다음 [수학식 3]과 같이 m×r개의 방문 위치를 정의함으로써 표현될 수 있다.
[수학식 3]
Figure pat00014
여기서
Figure pat00015
는 전역 참조 좌표계에서의 방문 위치이다.
도 2에서 각 방문 위치는 영역 커버리지 또는 센서 커버리지 문제에 대하여 이동 로봇의 단위 커버리지 영역을 나타내는 그리드 셀의 중앙에 대응한다. 영역 커버리지의 경우 그리드 셀의 크기는 이동 로봇의 길이와 같거나 작은 것으로 가정한다. 센서 커버리지에 대하여는 로봇 센서의 즉각적인 단위 커버리지 영역은 그리드 셀의 크기와 동일한 것으로 가정한다.
그러면 제한된 시간 내에서 협력 커버리지 알고리즘은 다음과 같은 사항이 요구된다.
i) m×r개의 방문 위치는 경로 트리(path tree)를 따라 n개의 로봇에 적절히 할당된다.
ii) n개의 로봇은 제한된 시간 T내에서 가능한 한 빠르게 할당된 방문 위치를 방문할 것이 요구된다.
iii) 협력 커버리지의 최소 실행 시간은
Figure pat00016
에 대응하고, 여기서
Figure pat00017
는 i 번째 로봇의 최소 커버리지 시간이다.
그러므로 협력 커버리지 알고리즘은 방문 위치의 부분 집합
Figure pat00018
과
Figure pat00019
의 방문 위치를 차례로 나타내는i 번째 로봇의 경로 트리
Figure pat00020
를 생성해야 한다. 모든 방문 위치의 모든 부분 집합과 그 경로 트리는
Figure pat00021
에 대하여
Figure pat00022
,
Figure pat00023
,
Figure pat00024
, 그리고
Figure pat00025
를 충족한다. 여기서
Figure pat00026
는
Figure pat00027
의 커버리지 시간을 나타낸다.
협력 커버리지 제어 문제는 제한된 시간 내에서 [수학식 3]의 m×r개의 위치를 커버하도록 [수학식 1]의 n개 로봇을 조종하는 협력 커버리지 제어 전략을 찾는 것으로 기술할 수 있다. 본 실시예에서 방문 위치는 도 2에 도시한 그리드 셀의 중앙 위치에 대응하는 것으로 설명하지만 이에 한정되지 않으며 임의의 위치일 수 있다.
이렇게 시간이 제한된 상태에서 제어 목적을 달성하기 위하여, [수학식 1]의 각 이동 로봇의 능력은 경로 트리의 실행을 위하여 로봇을 조정하는 것뿐만 아니라 방문 위치의 수를 할당하는 것까지 고려할 필요가 있다.
우선 이러한 사항을 고려하여 두 방문 위치 사이의 최소 시간 속도 프로파일과 함께 실행 시간의 면에서 각 이동 로봇이 대략 동일한 수의 방문 위치를 가지도록 할당한다.
작업 할당에서 각 이동 로봇의 모터 특성에 맞추어 그룹 모션 제어의 실행 시간을 동기화한다.
이동 로봇
Figure pat00028
의 빠르기를 다음 [수학식 6]과 같이 정의한다
[수학식 6]
Figure pat00029
여기서
Figure pat00030
는 두 방문 위치 사이의 최소 이동 거리이고,
Figure pat00031
. 이 경우 그리드 셀은 모든 j, k에 대하여
Figure pat00032
또는 를 나타내도록 균일한 것으로 가정한다. 물론 그리드 셀이 균일하지 않더라도 본 발명의 실시예에 따른 커버리지 제어 방법을 적용하는 데 문제가 없다.
도 3은 본 발명의 실시예에 따른 커버리지 제어 방법을 위한 최소 시간 속도 프로파일을 나타낸 도면이다.
도 3에 [수학식 6]에 대응하는 두 개의 다른 최소 시간 속도 프로파일이 도시되어 있으며, 이것은 이동 거리와 i 번째 로봇의 최대 속도 및 최대 가속도에 의존한다.
먼저 다음 [수학식 7]과 같이
Figure pat00034
에 대하여 n 색인 사이의 최대 시간 지표를 선택한다.
[수학식 7]
Figure pat00035
그런 후
Figure pat00036
와
Figure pat00037
의 비를 계산하고 다음 [수학식 8]과 같이 그것을 정수로 변환한다.
[수학식 8]
Figure pat00038
여기서
Figure pat00039
는 실수 x의 정수 부분을 취하는 함수이다.
계산된 정수
Figure pat00040
를 가지고 각 이동 로봇에 할당되는 방문 위치의 수효
Figure pat00041
는 다음과 같이 결정된다.
Figure pat00042
Figure pat00043
,
Figure pat00044
Figure pat00045
여기서 m×r은 전체 방문 위치의 수효이다.
그러면 두 방문 위치 사이의 각 이동 로봇을 조종하기 위하여 최소 시간 속도 프로파일을 구축하는 방법에 대하여 설명한다.
속도 프로파일 설계에서 이동 로봇은 제한된 시간 내에서 동기화하여 커버리지 제어를 할 수 있는 것으로 간주한다. 물론 각 이동 로봇의 능력은 상이하다. 방문 위치 사이의 이동 거리의 수효에 대하여 고려해야 하는 첫 번째는 로봇의 빠르기이다. 이동 로봇 Ri의 빠르기에 대한 성능 지표로서 [수학식 6]의 최소 시간 지표
Figure pat00046
와 최대 시간 지표
Figure pat00047
가 속도 계획에 사용된다.
만일
Figure pat00048
이라면
Figure pat00049
로 두고, 또한
Figure pat00050
로 둔다.
Figure pat00051
에 대하여
Figure pat00052
로 둔다.
그러면, (
Figure pat00053
)이고 (
Figure pat00054
)이면 속도 프로파일은 다음 [수학식 9]와 같고,
[수학식 9]
Figure pat00055
Figure pat00056
이와 달리 (
Figure pat00057
)이고 (
Figure pat00058
)이면 다음 [수학식 10]과 같고,
[수학식 10]
Figure pat00059
그렇지 않고
Figure pat00060
이면 다음 [수학식 11]과 같다.
[수학식 11]
여기서
Figure pat00062
,
Figure pat00063
,
Figure pat00064
,
Figure pat00065
, 그리고
Figure pat00066
.
각속도는 다음 [수학식 12]와 같이 정의된다.
[수학식 12]
Figure pat00067
여기서
Figure pat00068
.
그러므로 [수학식 13]과 같이 m개의 방문 위치에 대한 n개의 최소 시간 속도 프로파일이 존재한다.
[수학식 13]
Figure pat00069
도 4는 작업 공간의 셀적 분해에 대한 설명에 참조되는 도면이다.
앞서 설명한 바와 같이 작업 공간은 도 4에 도시한 것처럼 미리 정해진 크기의 영역 A = W×W로 이루어진 그리드 셀(grid cell)로 나누어진다. 여기서 각 셀이 정방형이고 그 크기가 동일한 것으로 하였으나 이에 한정되지 않으며 정방형이 아니거나 임의의 크기로 이루어질 수도 있다. 한편, 로봇이 차지하는 영역은 영역의 커버리지 문제를 위해 영역 A보다 크거나 같은 것으로 가정하고, 또한, 센서 커버리지 작업에 대한 즉각적인 센서 측정의 범위 R에 대한 W=
Figure pat00070
R에 대해서도 크거나 같은 것으로 가정한다.
도 4에서 좌표 프레임의 원점은 커버리지 업무를 위하여 센터 그리드(center grid)라고 불리는 그리드 셀 상에서 로봇의 스타트 위치(starting position)에 대응한다.
Figure pat00071
에 대하여
Figure pat00072
위치에서 그리드 셀
Figure pat00073
의 중심 좌표는
Figure pat00074
로 나타내고,
Figure pat00075
의 서브 골(sub-goal)이라 한다. 따라서,
Figure pat00076
는 스타트 위치에서 그리드 셀
Figure pat00077
의 중심을 나타낸다.
작업 공간의 셀 분해를 통해 그리드들은 다음 [수학식 14]와 같이 인접 셀의 집합으로 그룹화된다.
[수학식 14]
Figure pat00078
여기서, 두 개의 좌표값 (i, j)는 다음 [수학식 15]와 같이 순열
Figure pat00079
로부터 반복적으로 선택된다.
[수학식 15]
Figure pat00080
Figure pat00081
여기서,
Figure pat00082
이다.
예를 들면, 처음 세 개의 셀 그룹은 다음과 같이 결정된다.
Figure pat00083
이와 같은 정의에서,
Figure pat00084
위첨자 1은 시작 위치
Figure pat00085
로부터 North CW(북쪽 시계방향)이나 East CCW(동쪽 반시계 방향)으로 로봇 이동의 초기 방향에 대한 제1 사분면을 나타낸다.
셀 집합의 증분은 다음 [수학식 16]과 같이 정의할 수 있다.
[수학식 16]
Figure pat00086
여기서,
Figure pat00087
이다.
또한, 짝수 k에 대하여,
ⅰ)
Figure pat00088
는 y축에 대하여
Figure pat00089
의 대칭 변위로
ⅱ)
Figure pat00090
는 y = -x 에 대하여
Figure pat00091
의 대칭 변위로
ⅲ)
Figure pat00092
는 x축에 대하여
Figure pat00093
의 대칭 변위로 정의한다.
홀수 k에 대하여,
ⅰ)
Figure pat00094
는 y = -x 에 대하여
Figure pat00095
의 대칭 변위로
ⅱ)
Figure pat00096
는 x축에 대하여
Figure pat00097
의 대칭 변위로
ⅲ)
Figure pat00098
는 y축에 대하여
Figure pat00099
의 대칭 변위로 정의한다.
이에 따라, 다음 [수학식 17]과 같이 된다.
[수학식 17]
Figure pat00100
여기서 위첨자 i는 i 번째 사분면을 나타내고, 각
Figure pat00101
는 다음의 [표 1]에서 네가지 케이스 중 하나를 나타낸다.
[표 1]
Figure pat00102
로봇 주행의 이동 방향 측면에서, 첨자 i는 다음 [수학식 18]의 네 가지 케이스와 탐색 가능한 8 방향을 구별한다.
[수학식 18]
Figure pat00103
이와 같은 정의에 따른 사분면 및 로봇 이동의 8 방향은 도 5에 도시한 바와 같다. 도 5는 작업 공간의 셀적 분해에 대한 설명에 참조되는 도면이다.
공간 셀 분해 모델에 대한 예로서, 제4 분면의 처음 세 개의 셀 그룹
Figure pat00104
는 다음과 같이 표현된다.
Figure pat00105
초기 위치에서 South CW 또는 West CCW로 로봇의 이동 방향은 다음 [수학식 19]와 같이 그리드 셀의 집합을 모델로 선택할 수 있다.
[수학식 19]
Figure pat00106
여기서 두 좌표값 (i, j)는 순열
Figure pat00107
로부터 반복적으로 선택된다.
[수학식 20]
Figure pat00108
Figure pat00109
여기서,
Figure pat00110
이다.
그리드 셀 집합의 증분은 다음과 같이 정의된다.
[수학식 21]
Figure pat00111
,
여기서, 짝수 k에 대하여
Figure pat00112
이고, 홀수 k에 대하여
Figure pat00113
이다.
다른 사분면에서의 그리드 셀 그룹은 [수학식 17]과 같이 정의된다.
한편, 셀 타입은 다음과 같다.
Figure pat00114
: 는 장애물이 없는 지역에 속하는 셀,
Figure pat00115
: 셀이 부분적으로 장애물이나 작업 공간의 경계에 중첩되고, 서브 골
Figure pat00116
에 도달할 수 있도록 중심이 있는 셀,
Figure pat00117
: 셀이 부분적으로 장애물이나 작업 공간의 경계에 중첩되고, 중심은 서브 골에 도달할 수 없도록 중심이 있는 셀, 그리고
Figure pat00118
: 장애물에 의해 완전히 점유된 셀을 의미한다.
이와 같은 분류에서, 셀
Figure pat00119
에 대한 좌표의 서브 골
Figure pat00120
는 이동 로봇에 의해 도달할 수 있고,
Figure pat00121
은 도달할 수 없다. 또한,
Figure pat00122
은 네개의 방향으로 접근가능하지만,
Figure pat00123
은 적어도 하나의 접근 가능한 방향을 가지며,
Figure pat00124
는 접근 방향이 없다.
이와 같은 작업 공간의 모델에 기초하여 본 발명은 공간 셀 확산(spatial cell diffusion) 커버리지 방법을 사용한다.
장애물이 없는 자유 공간의 문제를 고려하면, 자유 지역 셀
Figure pat00125
와, 경계 셀
Figure pat00126
로 분류할 수 있으며, 경계 셀은 다음과 같이 브리지 셀(bridge cell), 정션 셀(junction cell), 브룩 셀(brook cell)로 분류된다.
여기서, 브리지 셀은 로봇이 CW 로부터 CCW 혹은 그 반대로 이동 방향을 변경하는 경계 셀로 정의된다. 정션 셀은 두 개 이상의 서브 그룹으로 향후 스윕 영역(sweep region)을 분리하는 경계 셀로 정의된다. 브룩 셀(brook cell)은 스윕 방향이 장애물 경계나 작업 공간의 경계선에 부합하는 셀로 정의한다. 이와 같은 정의에 따라, 도 7은 브리지 셀, 정션 셀, 브룩 셀의 일 예를 나타낸 것이다.
도 8 및 도 9는 본 발명에 따른 로봇 커버리지 방법에 대한 설명에 제공되는 흐름도이다.
도 8을 참조하면, 먼저, 커버리지를 위한 탐색 초기화 과정이 수행된다(S200). 탐색 초기화 과정에서, 로봇의 현재 위치 및 방향, 알려진 작업 공간에서 수행되는 오프라인(off-line) 커버리지의 경우 그레이코드화된 그리드 맵, 미지의 작업 공간에서 수행되는 온라인(on-line) 커버리지의 경우 그레이코드의 인코딩 규칙 및 서치 등이 로봇의 입력으로 사용될 수 있다. 또한, 다중 로봇에 대하여 두 개 이상의 서브 영역으로 타겟 작업 공간을 나누고 각 서브 영역에서 독립적으로 다음 과정을 수행할 수 있다.
탐색 초기화 과정에서, 로봇 커버리지의 스타트 위치를 센터 그리드로 설정한다. 그리고, 센터 그리드에서 전역 x-y 좌표계를 설정하고, 로봇에 구비된 전역 x-카운터와 y-카운터를 리셋한다. 또한, 사분 번호 i (i= 1, 2, 3, 4)를 선택한다. 사분면 번호가 i 가 선택된 경우, 탐색을 위한 하나의 방향을 결정한다.
탐색 초기화가 완료되면, 타겟 작업 공간에 대한 탐색을 시작한다(S220). 로봇은 스타트 위치에서 인접한 셀로 이동하여 탐색을 수행한다. 예를 들면, 로봇은 바깥쪽으로 나선형으로 셀 간 이동하여 로봇이 스윕(sweep)한 영역이 확장되도록 작업 공간을 탐색한다. 로봇의 이동에 따라, 글로벌 및 로컬 x-y 카운터를 증가 또는 감소시키고, 방문한 셀들을 카운트한다.
오프라인 탐색의 경우, 셀 그룹
Figure pat00127
을 참조하여 로봇의 주변 그리드 셀에 대하여 선택된 탐색 방향에 따라 그레이코드화된 셀을 주행한다. 두 인접 셀은 서로 하나의 첨자 숫자만이 다르므로, 그레이코드는 탐색 트리에 대응한다. 오프라인 탐색의 경우, 로봇은 장애물의 크기를 파악하기 위해 장애물을 일주할 수 있으며, 장애물 주위를 커버리지 경로로 계획할 수 있다.
온라인 탐색의 경우, 선택된 탐색 방향에 따라 로봇을 둘러싼 그리드 셀을 주행하면서 그레이코드로 이루어진 셀 그룹
Figure pat00128
을 생성한다.
이와 같은 과정에 의해, 작업 공간에 대한 맵 탐색이 완료되는 경우까지, 작업 공간에 대한 맵 탐색을 진행한다(S240, S260). 즉, 그레이코드의 관점에서, 모든 그리드 셀에 대한 탐색이 완료되면 맵 탐색은 완료된다.
도 9는 맵 탐색 과정에서, 로봇이 경계 셀에 도달한 경우를 나타낸 것이다. 로봇이 경계 셀에 도달한 경우, 경계 셀의 종류에 따라 다음과 같은 과정이 수행된다.
도 9를 참조하면, 두 개 이상의 소그룹으로 향후 스윕할 그리드 셀을 분리하는 정션 셀의 경우(S241), 정션 셀과 분리된 셀 그룹의 개수를 기록한 후, 셀 확산의 방향과 일치하는 셀을 포함하는 제1 영역을 커버한다(S243). 제1 영역을 커버한 후, 로봇은 기록된 정션 셀로 돌아간다(S245). 로봇이 분리된 영역의 커버리지에서 기록된 정션 셀로 돌아가기 위해 로봇에 카운터가 사용될 수 있다.
그리고, 로봇이 나머지 영역을 커버한다(S247). 나머지 영역을 커버한 후, 로봇은 기록된 정션 셀로 돌아간다.
만일, 지역을 커버하기 전에 일치하지 않는 셀이 나타나는 경우, 그 셀을 새로운 로컬 좌표 시스템과 지역 x-y 카운터를 갖는 새로운 시작 셀로 설정할 수 있다.
경계 셀이 브리지 셀인 경우(S249), 로봇의 탐색 방향을 변경한다(S251). 즉, CW에서 CCW, 또는 CCW에서 CW로 로봇의 탐색 방향을 변경한다. 브룩 셀인 경우에는(S253), 그래도 셀을 커버한다(S255).
새로운 시작 셀인 경우에는(S257), 새로운 로컬 좌표 시스템과 x-y 카운터를 설정하도록 한다(S259).
이와 같은 과정에 의해, 작업 공간에 대한 탐색이 완료되어, 그레이코드 그룹으로 작업 공간을 모델링할 수 있으며, 작업 공간의 모든 지점을 커버리지할 수 있다.
도 6 및 도 7을 참고하면, 도 6은 장애물이 없는 자유 영역에서 본 발명에 따른 커버리지 방법을 나타낸 것이고, 도 7은 비자유 영역에서 본 발명에 따른 커버리지 방법을 나타낸 것이다.
도 6에서, 로봇의 초기 방향은 North CW로 설정되어 있다. 도 6에서,
Figure pat00129
는 커버리지 영역을 확장하면서 로봇이 CW에서 CCW로 자신의 이동 방향을 변경하는 브릿지 셀에 해당한다. 도 7에서,
Figure pat00130
은 정션 셀에 해당하며, 브룩 셀은 작업 공간의 경계를 따라 표시된다.
탐색을 위해 순서대로 정렬된 셀 그룹은 다음과 같이 그레이코드의 집합으로 표현된다.
Figure pat00131
Figure pat00132
셀 그룹
Figure pat00133
,
Figure pat00134
,
Figure pat00135
는 [표 1]의 표준 공간 셀 분해와 다르며, 이는 CW에서 CCW 혹은 그 반대로 브릿지 셀에서 탐색 방향이 변경되기 때문이다. 그러나, 경계 셀 주변의 셀 확산은 셀 그룹의 방문에 대한 이동의 방향 순서와 일치한다. 그렇지 않으면, 정션 셀 후 새로 시작하는 셀이 생성되었을 것이다.
도 7의 경우, 비자유 공간에서 본 발명에 따른 로봇 커버리지 방법을 나타낸 것이다. 도 7에서, 로봇은 장애물을 피하면서 일관된 탐색 방향으로 다음 셀로 주행한다.
한편, 본 발명에 따른 커버리지 방법에서, 그레이코드 대신 검색 트리의 표현이 사용되기 때문에, 메모리 요구 사항은 시작과 정션 셀을 포함하는 중요한 셀에 대하여
Figure pat00136
로 줄여준다. 또한, 본 발명에 따른 방법을 수행하기 위한 로봇 커버리지 시스템을 구성하는 경우, 본 발명에 따른 방법은 로봇 제어기에 의해 수행될 수 있으며, 이와 같은 로봇 제어기는 로봇 내에 설치할 수도 있다.
이와 같이 본 발명에 따른 로봇 커버리지 방법은 작업 공간의 구성과 무관하게 작업 공간의 모든 지점을 로봇이 커버리지할 수 있도록 한다.
본 발명의 다른 실시예는 다양한 컴퓨터로 구현되는 동작을 수행하기 위한 프로그램 명령을 포함하는 컴퓨터로 읽을 수 있는 매체를 포함한다. 이 매체는 지금까지 설명한 다중 이동 로봇의 커버리지 제어 방법을 실행시키기 위한 프로그램을 기록한다. 이 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 이러한 매체의 예에는 하드디스크, 플로피디스크 및 자기 테이프와 같은 자기 매체, CD 및 DVD와 같은 광기록 매체, 플롭티컬 디스크(Floptical Disk)와 자기-광 매체, 롬, 램, 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 구성된 하드웨어 장치 등이 있다. 또는 이러한 매체는 프로그램 명령, 데이터 구조 등을 지정하는 신호를 전송하는 반송파를 포함하는 광 또는 금속선, 도파관 등의 전송 매체일 수 있다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다.
이상에서 본 발명의 예시적인 실시예에 대하여 상세하게 설명하였지만 본 발명의 권리범위는 이에 한정되는 것은 아니고 다음의 청구범위에서 정의하고 있는 본 발명의 기본 개념을 이용한 당업자의 여러 변형 및 개량 형태 또한 본 발명의 권리범위에 속하는 것이다.

Claims (1)

  1. 작업 공간을 다중 로봇이 커버리지하도록 하는 로봇 커버리지 방법으로서,
    상기 작업 공간을 미리 정해진 크기의 그리드 셀로 분할하는 단계,
    상기 다중 로봇에 대하여 상기 작업 공간 중 두 개의 방문 위치 사이의 최소 시간 속도 프로파일을 생성하는 단계,
    상기 최소 시간 속도 프로파일을 기초로 하여 상기 다중 로봇에 대하여 상기 작업 공간 중 방문 위치의 수효를 할당하는 단계, 그리고
    상기 다중 로봇이 상기 방문 위치의 수효에 따라 상기 작업 공간을 탐색하는 단계
    를 포함하는 로봇 커버리지 방법.
KR1020120156492A 2012-12-28 2012-12-28 제한된 시간 내에서의 로봇 커버리지 방법 및 시스템 Abandoned KR20140086245A (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020120156492A KR20140086245A (ko) 2012-12-28 2012-12-28 제한된 시간 내에서의 로봇 커버리지 방법 및 시스템

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020120156492A KR20140086245A (ko) 2012-12-28 2012-12-28 제한된 시간 내에서의 로봇 커버리지 방법 및 시스템

Publications (1)

Publication Number Publication Date
KR20140086245A true KR20140086245A (ko) 2014-07-08

Family

ID=51735564

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020120156492A Abandoned KR20140086245A (ko) 2012-12-28 2012-12-28 제한된 시간 내에서의 로봇 커버리지 방법 및 시스템

Country Status (1)

Country Link
KR (1) KR20140086245A (ko)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20200063879A (ko) * 2018-11-28 2020-06-05 성균관대학교산학협력단 인공지능 기반 환경 적응형 시간 동기화 군집 로봇 커버리지 방법 및 시스템
WO2020153628A1 (ko) * 2019-01-22 2020-07-30 삼성전자주식회사 로봇 및 그 제어 방법
CN112799398A (zh) * 2020-12-25 2021-05-14 珠海市一微半导体有限公司 基于寻径代价的清洁路径规划方法、芯片及清洁机器人
US12493298B2 (en) 2020-12-25 2025-12-09 Amicro Semiconductor Co., Ltd. Cleaning path planning method based on pathfinding cost, chip, and cleaning robot

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20200063879A (ko) * 2018-11-28 2020-06-05 성균관대학교산학협력단 인공지능 기반 환경 적응형 시간 동기화 군집 로봇 커버리지 방법 및 시스템
WO2020153628A1 (ko) * 2019-01-22 2020-07-30 삼성전자주식회사 로봇 및 그 제어 방법
KR20200094831A (ko) * 2019-01-22 2020-08-10 삼성전자주식회사 로봇 및 그 제어 방법
US11938637B2 (en) 2019-01-22 2024-03-26 Samsung Electronics Co., Ltd. Robot and control method thereof
CN112799398A (zh) * 2020-12-25 2021-05-14 珠海市一微半导体有限公司 基于寻径代价的清洁路径规划方法、芯片及清洁机器人
WO2022134483A1 (zh) * 2020-12-25 2022-06-30 珠海一微半导体股份有限公司 基于寻径代价的清洁路径规划方法、芯片及清洁机器人
US12493298B2 (en) 2020-12-25 2025-12-09 Amicro Semiconductor Co., Ltd. Cleaning path planning method based on pathfinding cost, chip, and cleaning robot

Similar Documents

Publication Publication Date Title
CN113110457B (zh) 在室内复杂动态环境中智能机器人的自主覆盖巡检方法
US10712749B2 (en) Discovery and monitoring of an environment using a plurality of robots
KR101372482B1 (ko) 이동 로봇의 경로 계획 방법 및 장치
Sudhakara et al. Trajectory planning of a mobile robot using enhanced A-star algorithm
Lindhé et al. Flocking with obstacle avoidance: A new distributed coordination algorithm based on voronoi partitions
Bogdan Rusu et al. Leaving Flatland: Efficient real‐time three‐dimensional perception and motion planning
JP2021510433A (ja) ロボットの自律的動作計画及びナビゲーションのためのシステム並びに方法連邦政府による資金提供を受けた研究開発の記載
CN109978272B (zh) 一种基于多个全向移动机器人的路径规划系统及方法
Kumar et al. Robot path pursuit using probabilistic roadmap
KR20140086245A (ko) 제한된 시간 내에서의 로봇 커버리지 방법 및 시스템
Finean et al. Where should I look? Optimized gaze control for whole-body collision avoidance in dynamic environments
Janchiv et al. Complete coverage path planning for multi-robots based on
Madhevan et al. Identification of probabilistic approaches and map-based navigation in motion planning for mobile robots
Okada et al. Exploration and observation planning for 3D indoor mapping
Kusnur et al. Complete, decomposition-free coverage path planning
KR101297608B1 (ko) 미지 환경에서의 로봇 커버리지 방법 및 시스템
Gu et al. Path planning for mobile robot in a 2.5‐dimensional grid‐based map
Zenkevich et al. Dynamic switching of multi-agent formation in unknown obstacle environment
Pal et al. A focused wave front algorithm for mobile robot path planning
Barth A dynamic programming approach to robotic swarm navigation using relay markers
Ratnayake et al. OENS: an octomap based exploration and navigation system
CN118276562A (zh) 自移动机器人的移动控制方法及装置
Sun et al. Robot path planning by using improved a* algorithm and dynamic window method
CN115237125A (zh) 一种无人配送消毒小车的智能线路规划方法
Kuznetsov et al. Algorithm of target point assignment for robot path planning based on costmap data

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20121228

PG1501 Laying open of application
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20171228

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20121228

Comment text: Patent Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20190321

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20191001

PC1904 Unpaid initial registration fee