KR102494926B1

KR102494926B1 - 무인기 운행을 위한 로컬 동적 맵 생성 장치 및 방법

Info

Publication number: KR102494926B1
Application number: KR1020210114616A
Authority: KR
Inventors: 김경대; 이진우; 이원재
Original assignee: 재단법인대구경북과학기술원
Priority date: 2021-08-30
Filing date: 2021-08-30
Publication date: 2023-02-06
Anticipated expiration: 2041-08-30

Abstract

본 발명은 무인기(Unmanned Aerial Vehicle, UAV)의 안전한 운행을 위한 로컬 동적 맵(Local Dynamic Map, LDM)을 생성하는 기술에 관한 것이다. 본 발명의 일측면에 따르면 무인기는, 무인기 주변 환경을 스캔하여 스캔 데이터를 생성하고, 무인기의 속도를 센싱하는 센서부; 무인기의 주변 환경을 각각 점유 확률 및 속도를 나타내는 복수의 복셀로 구성되는 3차원 그리드로 표현하는 로컬 동적 맵을 생성하는 LDM 관리부; 및 생성된 로컬 동적 맵에 따라 무인기의 운행을 제어하는 운행 제어부를 포함할 수 있다.

Description

무인기 운행을 위한 로컬 동적 맵 생성 장치 및 방법{APPARATUS AND METHOD FOR GENERATING DYNAMIC LOCAL MAP FOR OPERATION OF UAV}

본 발명은 무인기(Unmanned Aerial Vehicle, UAV)의 안전한 운행을 위한 로컬 동적 맵(Local Dynamic Map, LDM)을 생성하는 기술에 관한 것이다.

무인기의 안전한 운행을 위해는 무인기 주변의 장애물에 대한 정확한 인식이 요구된다. 이를 위해 종래에는 점유 그리드 맵(Occupancy Grid map, OGM)으로 무인기의 주변 환경을 표현하는 기술이 제안되고 있으나, 이는 점유 유무만 확인할 수 있고 장애물의 형체나 장애물의 속도를 인지할 수 없는 한계가 있다.

한국공개특허 제10-2015-0136209호, "다중 영상 기반 장애물 회피 시스템 및 방법" 한국공개특허 제 10-2021-0065837호, " 점유　격자　지도　생성 장치 및 방법"

본 발명의 목적은 점유 그리드 및 파티클 필터에 기반한 로컬 동적 맵을 생성하는 기술을 제공하는 것이다.

또한, 본 발명의 목적은 장애물의 형상 및 이동을 인지할 수 있는 동적 로컬 맵을 생성하는 기술을 제공하는 것이다.

또한, 본 발명의 목적은 무인기 하드웨어 자원의 사용량을 줄일 수 있는 동적 로컬 맵을 생성하는 기술에 제공하는 것이다.

본 발명의 일 측면에 따르면, 무인기 주변 환경을 각각 점유 확률 및 속도를 나타내는 복수의 복셀로 구성되는 3차원 그리드로 표현하는 로컬 동적 맵을 생성하는 방법에 있어서, 복수의 복셀 중 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터의 시간 k-1에서의 속도를 기반으로, 시간 k에서 로컬 동적 맵 상에서의 위치를 예측하는 단계; 적어도 하나의 장애물 클러스터의 예측된 위치를 기반으로, 시간 k에서 복수의 복셀 각각의 점유 확률을 예측하는 단계; 로컬 동적 맵 상에 분포된 파티클들의 시간 k-1에서의 속도를 기반으로, 시간 k에서의 속도를 예측하는 단계; 예측된 파티클들의 속도를 기반으로, 시간 k에서 파티클들의 로컬 동적 맵 상에서 위치를 예측하는 단계; 시간 k에서 무인기 주변 환경을 스캔하여 스캔 데이터를 생성하는 단계; 생성된 스캔 데이터를 기반으로 시간 k에서의 복수의 복셀 각각의 예측된 점유 확률을 업데이트하는 단계; 업데이트된 점유 확률을 기반으로 파티클들의 시간 k에서의 가중치를 업데이트 하는 단계; 파티클들의 예측된 속도 및 업데이트된 가중치를 기반으로 결정되는 복수의 복셀 각각의 속도를 이용하여, 시간 k에서 파티클들의 속도를 업데이트 하는 단계; 및 시간 k에서 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터를 재생성하는 단계를 포함하는. 방법이 제공된다.

일 실시예에서, 시간 k-1에서 무인기의 속도 정보를 기반으로 시간 k-1 무인기의 위치를 업데이트 하는 단계; 및 로컬 동적 맵 상에서 무인기의 위치를 나태내는 시간 k에서의 좌표가 시간 k-1의 좌표와 동일하도록 로컬 동적 맵을 재 생성하는 단계를 더 포함하되, 스캔 데이터를 생성하는 단계는 로컬 동적 맵이 재 생성된 후에 수행될 수 있다.

일 실시예에서, 시간 k에서 재 생성되는 로컬 동적 맵의 사이즈는 시간 k-1에서 로컬 동적 맵의 사이즈와 동일할 수 있다.

일 실시예에서, 무인기의 시간 k와 시간 k-1의 위치 차이는 복셀 사이즈의 정수배일 수 있다.

일 실시예에서, 시간 k-1에서 파티클들의 개수는 미리 설정된 개수이며, 시간 k에서의 파티클들의 개수가 미리 설정된 개수 미만이면 미리 설정된 개수가 되도록 파티클들의 가중치를 기반으로 리샘플링을 수행하는 단계를 더 포함할 수 있다.

또한, 본 발명의 다른 측면에 따르면, 무인기 주변 환경을 스캔하여 스캔 데이터를 생성하고, 무인기의 속도를 센싱하는 센서부; 무인기의 주변 환경을 각각 점유 확률 및 속도를 나타내는 복수의 복셀로 구성되는 3차원 그리드로 표현하는 로컬 동적 맵을 생성하는 LDM 관리부; 및 생성된 로컬 동적 맵에 따라 무인기의 운행을 제어하는 운행 제어부를 포함하되, LDM 관리부는, 복수의 복셀 중 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터의 시간 k-1에서의 속도를 기반으로, 시간 k에서 로컬 동적 맵 상에서의 위치를 예측하고, 적어도 하나의 장애물 클러스터의 예측된 위치를 기반으로, 시간 k에서 복수의 복셀 각각의 점유 확률을 예측하고, 로컬 동적 맵 상에 분포된 파티클들의 시간 k-1에서의 속도를 기반으로, 시간 k에서의 속도를 예측하고, 예측된 파티클들의 속도를 기반으로, 시간 k에서 파티클들의 로컬 동적 맵 상에서 위치를 예측하고, 시간 k에서 무인기 주변 환경을 스캔하여 스캔 데이터를 생성하며, 생성된 스캔 데이터를 기반으로 시간 k에서의 복수의 복셀 각각의 예측된 점유 확률을 업데이트하고, 업데이트된 점유 확률을 기반으로 파티클들의 시간 k에서의 가중치를 업데이트 하며, 파티클들의 예측된 속도 및 업데이트된 가중치를 기반으로 결정되는 복수의 복셀 각각의 속도를 이용하여, 시간 k에서 파티클들의 속도를 업데이트 하여, 시간 k에서 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터를 재생성하는, 무인기가 제공된다.

본 발명의 실시예에 따르면, 점유 그리드 및 파티클 필터에 기반한 로컬 동적 맵을 생성하는 것이 가능하게 된다.

또한, 본 발명의 다른 실시예에 따르면, 장애물의 형상 및 이동을 인지할 수 있는 동적 로컬 맵을 생성하는 것이 가능하게 된다.

또한, 본 발명의 다른 실시예에 따르면, 무인기 하드웨어 자원의 사용량을 줄일 수 있는 동적 로컬 맵을 생성하는 것이 가능하게 된다.

도 1은 본 발명의 일 실시예에 따른 무인기의 블록도.
도 2는 본 발명의 일 실시예에 따른 로컬 동적 맵의 생성 방법의 흐름도.
도 3은 본 발명의 일 실시예에 다른 장애물 클러스터의 이동을 설명하기 위한 도면.
도 4는 본 발명의 일 실시예에 따른 무인기 이동에 따른 로컬 동적 맵을 재생성을 설명하기 위한 도면.
도 5는 본 발명의 일 실시예에 따른 로컬 동적 맵을 생성하는 방법의 블록도.
도 6은 본 발명의 다른 실시예에 다른 무인기의 블록도.

본 명세서에 개시되어 있는 본 발명의 개념에 따른 실시예들에 대해서 특정한 구조적 또는 기능적 설명들은 단지 본 발명의 개념에 따른 실시예들을 설명하기 위한 목적으로 예시된 것으로서, 본 발명의 개념에 따른 실시예들은 다양한 형태로 실시될 수 있으며 본 명세서에 설명된 실시예들에 한정되지 않는다.

본 발명의 개념에 따른 실시예들은 다양한 변경들을 가할 수 있고 여러 가지 형태들을 가질 수 있으므로 실시예들을 도면에 예시하고 본 명세서에 상세하게 설명하고자 한다. 그러나, 이는 본 발명의 개념에 따른 실시예들을 특정한 개시형태들에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 변경, 균등물, 또는 대체물을 포함한다.

제1 또는 제2 등의 용어를 다양한 구성요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의해 한정되어서는 안 된다. 상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만, 예를 들어 본 발명의 개념에 따른 권리 범위로부터 이탈되지 않은 채, 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소는 제1 구성요소로도 명명될 수 있다.

어떤 구성요소가 다른 구성요소에 "연결되어" 있다거나 "접속되어" 있다고 언급된 때에는, 그 다른 구성요소에 직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성요소가 존재할 수도 있다고 이해되어야 할 것이다. 반면에, 어떤 구성요소가 다른 구성요소에 "직접 연결되어" 있다거나 "직접 접속되어" 있다고 언급된 때에는, 중간에 다른 구성요소가 존재하지 않는 것으로 이해되어야 할 것이다. 구성요소들 간의 관계를 설명하는 표현들, 예를 들어 "~사이에"와 "바로~사이에" 또는 "~에 직접 이웃하는" 등도 마찬가지로 해석되어야 한다.

본 명세서에서 사용한 용어는 단지 특정한 실시예들을 설명하기 위해 사용된 것으로, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 명세서에서, "포함하다" 또는 "가지다" 등의 용어는 설시된 특징, 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것이 존재함으로 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.

다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가진다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥상 가지는 의미와 일치하는 의미를 갖는 것으로 해석되어야 하며, 본 명세서에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.

이하, 실시예들을 첨부된 도면을 참조하여 상세하게 설명한다. 그러나, 특허출원의 범위가 이러한 실시예들에 의해 제한되거나 한정되는 것은 아니다. 각 도면에 제시된 동일한 참조 부호는 동일한 부재를 나타낸다.

도 1은 본 발명의 일 실시예에 따른 무인기의 블록도이다.

도 1을 참조하면, 무인기(1000)는 센서부(1100), LDM 관리부(1200) 및 운행 제어부(1300)를 포함할 수 있다.

센서부(1100)는 무인기(1000) 주변 환경을 센싱하여 센싱 데이터를 생성할 수 있다. 구체적으로, 센서부(1100)는 무인기(1000)의 주변 환경을 스캔하여 무인기(1000)의 주변에 장애물의 존부에 대한 스캔 데이터를 생성할 수 있다.

일 실시예에서, 센서부(1100)는 라이다 센서, 레이더 센서 등일 수 있다.

또한, 센서부(1100)는 무인기(1000)의 속도, 이동 방향 등의 센싱하여 무인기(1000) 이동 데이터를 생성할 수 있다.

일 실시예에서, 센서부(1100)는 자이로 센서, 가속도 센서 등일 수 있다.

LMD 관리부는 점유 그리드 및 파티클 필터를 기반으로 장애물 존재를 인식할 수 있는 무인기(1000)의 주변 환경에 대한 로컬 동적 맵을 생성할 수 있다.

로컬 동적 맵은 복수의 복셀(voxel)로 구성되는 3차원 그리드로 표현될 수 있다. 각 복셀은 큐브 형태로 점유 확률 및 속도를 표현하며 로컬 동적 맵 상에서 특정 좌표에 대응할 수 있다. 여기서, 속도는 로컬 동적 맵 상에서의 위치, 속도 및 방향을 포함하는 벡터일 수 있다.

일 실시예에서, 로컬 동적 맵은 2 이상의 복셀에 대한 클러스터링이 수행된 장애물 클러스터를 표현할 수 있다. 장애물 클러스터는 무인기(1000)의 주변 환경에 존재하는 장애물로 인식될 수 있다. 장애물 클러스터는 위치가 고정된 장애물 또는 고유의 속도로 이동하는 장애물일 수 있다.

일 실시예에서, 장애물 클러스터는 미리 설정된 기준값 이상의 점유 확률을 갖는 2 이상의 복셀로 구성될 수 있으며, 장애물 클러스터를 구성하는 복셀들은 미리 설정된 인전하는 거리에 있는 복셀들로 구성될 수 있고, 클러스터를 구성하는 복셀들의 수는 미리 설정된 개수일 수 있다. 즉, 장애물 클러스터는 기준값 이상의 정유 확률을 갖는 서로 인접하는 미리 설정된 개수의 복셀로 구성될 수 있다.

이하, LDM에 생성에 대한 상세한 설명은 도 2 내지 도 5를 참조하여 후술한다.

운행 제어부(1300)는 생성된 로컬 동적 맵을 기반으로 장애물을 회피하는 등의 무인기(1000)의 운행을 제어할 수 있다.

도 2는 본 발명의 일 실시예에 따른 로컬 동적 맵을 생성하는 방법의 흐름도이다.

이하, 도 2에 도시된 방법은 도 1에 도시된 무인기(1000)에 의해 수행되는 것을 예시로 이하 설명한다.

단계 S2100에서, 장애물 클러스터의 위치가 예측된다. 구체적으로 무인기(1000)는 시간 k-1에서의 LDM을 기반으로 시간 k에서 장애물 클러스터의 위치를 예측할 수 있다. 여기서, 장애물 클러스터는 시간 k-1에서 LDM에 포함된 장애물 클러스터의 위치 및 속도를 기반으로 상기 장애물 클러스터의 시간 k에서의 위치를 예측할 수 있다. 이때, 장애물 클러스터의 속도는 장애물 클러스터를 구성하는 복셀들의 평균 속도로 결정될 수 있다.

일 실시예에서, 도 3을 참조하면, 무인기(1000)의 위치를 중심 좌표로 하는 로컬 동적 맵 상에서 장애물 클러스터의 이동 예시가 도시되어 있다. 설명의 명확성을 위해 로컬 동적 맵이 2차원 맵인 경우를 예시로 설명하나 이는 3차원 맵인 경우에도 동일하게 적용됨은 자명하다. 시간 k-1에서 로컬 동적 맵의 좌측 상단은 5개의 복셀로 구성되고 우측 상단 방향으로 속도를 가지는 장애물 클러스터 1이 도시되어 있으며, 우측 하단에는 3개의 복셀로 구성되며 속도를 가지지 않는 장애물 클러스터 2가 도시되어 있다. 장애물 클러스터 1은 t-1에서 우측 상단을 향하는 속도를 가지고 있으므로 t-1과 t 사이의 시간 간격 및 t-1에서 장애물 클러스터의 속도를 기반으로 t에서 장애물 클러스터의 위치가 우측 상단으로 이동할 것을 예측하는 것이 가능하게 된다. 또한, 장애물 클러스터 2는 시간 k-1에서 속도를 가지지 않으므로 시간 k에서도 동일한 위치를 유지할 것임을 예측하는 것이 가능하게 된다. 여기서, 각 장애물 클러스터의 속도는 각 장애물 클러스터를 구성하는 복셀들의 평균 속도를 의미할 수 있다.

단계 S2200에서, 시간 k에서 LDM의 점유 확률이 예측된다. 구체적으로, 무인기(1000)는 장애물 클러스터의 예측된 위치를 기반으로 시간 k에서의 점유 확률을 예측할 수 있다.

일 실시예에서, 도 3에 도시된 바와 같이, 장애물 클러스터 1은 우측 상단으로 이동하고 장애물 클러스터 2는 이동이 없었으므로, 시간 k-1에서 장애물 클러스터 1을 구성하는 복셀들에 대응하는 좌표들의 점유 확률을 시간 k에서 장애물 클러스터 1을 구성하는 복셀들에 대응하는 좌표들의 점유 확률로 반명함으로써, 시간 k에서의 LDM을 구성하는 복수의 복셀들 각각의 점유 확률을 예측할 수 있다.

단계 S2300에서, 파티클들이 예측된다. 구체적으로, 무인기(1000)는 시간 k-1에서 LDM을 기반으로 시간 k에서의 파티클들의 속도 및 위치를 예측할 수 있다. 여기서, 파티클들은 LDM에 분산되어 있으므로, 하나의 복셀안에 복수의 파티클이 존재할 수 있으며, 각 파티클들의 속도 및 위치는 상이할 수 있다.

일 실시예에서, 파티클들의 예측은 논문 “Hybrid sampling bayesian occupancy filter. 2014 IEEE Intelligent Vehicles Symposium Proceedings. IEEE, 2014”에 설명된 예측 모델이 사용될 수 있다.

일 실시예에서, 파티클의 속도는 수학식 1에 따라 예측될 수 있다.

즉, i 번째 파티클의 시간 k에서 속도

는 시간 k-1에서 속도

에

(zero mean normal distribution noise with covariance Σ를 더한 값으로 예측될 수 있다.

일 실시예에서, 파티클의 위치는 수학식 2에 따라 예측될 수 있다.

즉, I 번째 파티클의 시간 k에서 위치는

는 시간 k-1에서 위치

에다가 파티클의 예측된 시간 k에서 속도와 시간 k-1과 시간 k간의 차이를 곱한 값을 더함으로써 예측될 수 있다.

단계 S2400에서, 무인기(1000)의 위치가 업데이트 된다. 구체적으로, 무인기(1000)는 시간 k-1에서 무인기(1000)의 로컬 동적 맵 상에서 위치 및 속도를 기반으로 시간 k에서 로컬 동적 맵 상에서 위치 및 속도를 업데이트할 수 있다. 다만, 이때, 무인기(1000)는 시간 k에서와 시간 k-1에서 무인기(1000)의 위치가 로컬 동적 맵 상에서 동일한 좌표를 갖도록 로컬 동적 맵을 재 생성할 수 있다.

예를 들어, 도 4를 참조하면, 시간 k-1에서 무인기(1000)가 로컬 동적 맵 상에서 중심 좌표인 0번 복셀의 좌표에 위치했으나 시간 k에서 무인기(1000)가 6번 복셀로 이동된 경우에, 무인기(1000)는 6번 복셀이 다시 로컬 동적 맵의 중심 좌표가 되도록 로컬 동적 맵을 재생성할 수 있다. 이때, k-1에서 로컬 동적 맵에 포함되어 있던 13, 8, 3, 23, 18, 19, 15, 16 및 17번 복셀의 정보는 사라지고 시간 k에서 새로 추가된 무인기(1000) 주변 영역에 대한 복셀로 재구성될 수 있다. 이때, 무인기(1000)는 메모리 사용량을 줄이고 빠른 데이터 처리를 위해, 링 버퍼(circular buffer) 어레이를 사용할 수 있다.

또한, 무인기(1000)의 이동은 무인기(1000)의 회전은 고려되지 않으며, 로컬 동적 맵을 구성하는 복셀의 단위의 정수배로 결정될 수 있다.

단계 S2500에서, LDM의 점유 확률이 업데이트된다. 구체적으로, 무인기(1000)는 시간 k에서 주변 환경에 대한 스캔을 수행하여 스캔 데이터를 생성하고, 생성된 스캔 데이터를 기반으로 LDM을 구성하는 복수의 복셀들 각각에 대한 점유 확률을 업데이트 할 수 있다.

단계 S2600에서, 파티클들이 업데이트된다. 구체적으로, 무인기(1000)는 시간 k에서 업데이트된 점유 확률을 기반으로 파티클들을 업데이트할 수 있다.

일 실시예에서, 각 파티클들이 분포된 위치에 대응하는 복셀의 업데이트된 점유 확률을 시간 k-1에서 파티클들의 가중치에 더함으로써, 시간 k에서의 파티클들의 가중치를 업데이트할 수 있다.

일 실시예에서, 각 파티클들이 분포된 위치에 대응하는 복셀의 속도를 기반으로 각 파티클들의 속도를 수학식3에 따라 업데이트할 수 있다.

즉, 업데이트된 i 번째 파티클의 속도

는 시간 k에서 j 번째 복셀의 속도

에

(zero mean normal distribution noise with covariance Σ을 더함으로써 산출될 수 있다.

여기서, 시간 k에서 j 번째 복셀의 속도

는 수학식 4에 따라 산출될 수 있다.

즉, 시간 k에서 j 번째 복셀의 속도

는 각 복셀에 대응하는 각 파티클들의 시간 k에서 예측된 속도와 업데이트된 가중치의 곱들의 합을, 각 복셀에 대응하는 각 파티클들의 가중치들의 합으로 나눔으로써 산출될 수 있다.

단계 S2700에서, 장애물 클러스터가 재생성된다. 구체적으로, 무인기(1000)는 시간 k에서 각 복셀들의 점유 확률을 기반으로, 기준값 이상의 점유 확률을 갖는 인접하는 복셀들을 클러스터링하여 장애물 클러스터를 생성할 수 있다.

단계 S2700에서, 파티클들을 리샘플링된다. 구체적으로, 무인기(1000)는 파티클들의 개수를 미리 설정된 개수로 유지하기 위해 무인기(1000)의 이동 또는 장애물의 이동에 따라 파티클들의 개수가 감소한 경우, 시간 k에서 업데이트된 가중치를 기반으로 리샘플링함으로써, 파티클들의 개수를 미리 설정된 개수로 유지할 수 있다.

또한, 동적 로컬 맵을 생성하는 초기에는 각 복셀의 점유 확률은 0.5로 설정되고, 파티클들은 동적 로컬 맵 상에 균등하게 분배되고 속도는 랜덤분포, 가중치는 동일하게 설정될 수 있다.

도 5는 본 발명의 일 실시예에 따른 로컬 맵 생성 방법을 설명하기 위한 블록도이다.

도 5를 참조하면, 시간 k-1에서 로컬 동적 맵은 k-1에서 점유 확률을 기반으로 2이상의 복셀들을 클러터링하여 장애물 클러스터를 생성하고, 클러스터의 속도는 리 샘플링된 파티클들의 속도를 기반으로 결정된다. 시간 k에서 장애물 클러스터의 이동에 따라 로컬 동적 맵을 구성하는 복수의 복셀의 점유 확률을 예측하고, 파티클들의 위치 및 속도가 예측된다. 이후 무인기(1000)가 이동하게 되면 무인기(1000)에 이동에 따라 로컬 동적 맵이 재생성된다. 무인기(1000)는 시간 k에서 주변 환경을 스캔하고 스캔 데이터를 기반으로 로컬 동적 맵을 구성하는 복수의 복셀들의 점유 확률을 업데이트한다. 업데이트된 점유 확률을 기반으로 파티클들의 속도 및 가중치를 업데이트할 수 있다. 파티클들의 개수를 유지하기 위해 업데이트된 가중치를 기반으로 파티클들을 리샘플링할 수 있다. 시간 k에서 복셀들의 점유 확률을 기반으로 2이상의 복셀들을 클러스터링하여 장애물 클러스터를 생성할 수 있다. 시간 k에서의 클러스터의 위치 및 속도, 파티클들의 위치, 속도, 가중치를 기반으로 다시 반복하여 시간 k+1에서 장애물 클러스터의 위치 및 속도를 결정할 수 있다.

도 6은 본 발명의 다른 실시예에 따른 무인기의 블록도이다.

도 6에 도시된 바와 같이, 무인기(1000)는 프로세서(6100), 메모리(6200), 저장부(6300), 사용자 인터페이스 입력부(6400) 및 사용자 인터페이스 출력부(6500) 중 적어도 하나 이상의 요소를 포함할 수 있으며, 이들은 버스(6600)를 통해 서로 통신할 수 있다. 또한, 무인기(1000)는 네트워크에 접속하기 위한 네트워크 인터페이스(6700)를 또한 포함할 수 있다. 프로세서(6100)는 메모리(6200) 및/또는 저장소(6300)에 저장된 처리 명령어를 실행시키는 CPU 또는 반도체 소자일 수 있다. 메모리(6200) 및 저장부(6300)는 다양한 유형의 휘발성/비휘발성 기억 매체를 포함할 수 있다. 예를 들어, 메모리는 ROM(6240) 및 RAM(6250)을 포함할 수 있다.

이상에서 설명된 장치는 하드웨어 구성요소, 소프트웨어 구성요소, 및/또는 하드웨어 구성요소 및 소프트웨어 구성요소의 조합으로 구현될 수 있다. 예를 들어, 실시예들에서 설명된 장치 및 구성요소는, 예를 들어, 프로세서, 콘트롤러, ALU(arithmetic logic unit), 디지털 신호 프로세서(digital signal processor), 마이크로컴퓨터, FPGA(field programmable gate array), PLU(programmable logic unit), 마이크로프로세서, 또는 명령(instruction)을 실행하고 응답할 수 있는 다른 어떠한 장치와 같이, 하나 이상의 범용 컴퓨터 또는 특수 목적 컴퓨터를 이용하여 구현될 수 있다. 처리 장치는 운영 체제(OS) 및 운영 체제 상에서 수행되는 하나 이상의 소프트웨어 애플리케이션을 수행할 수 있다. 또한, 처리 장치는 소프트웨어의 실행에 응답하여, 데이터를 접근, 저장, 조작, 처리 및 생성할 수도 있다. 이해의 편의를 위하여, 처리 장치는 하나가 사용되는 것으로 설명된 경우도 있지만, 해당 기술분야에서 통상의 지식을 가진 자는, 처리 장치가 복수 개의 처리 요소(processing element) 및/또는 복수 유형의 처리 요소를 포함할 수 있음을 알 수 있다. 예를 들어, 처리 장치는 복수 개의 프로세서 또는 하나의 프로세서 및 하나의 콘트롤러를 포함할 수 있다. 또한, 병렬 프로세서(parallel processor)와 같은, 다른 처리 구성(processing configuration)도 가능하다.

이상과 같이 실시예들이 비록 한정된 도면에 의해 설명되었으나, 해당 기술분야에서 통상의 지식을 가진 자라면 상기의 기재로부터 다양한 수정 및 변형이 가능하다. 예를 들어, 설명된 기술들이 설명된 방법과 다른 순서로 수행되거나, 및/또는 설명된 시스템, 구조, 장치, 회로 등의 구성요소들이 설명된 방법과 다른 형태로 결합 또는 조합되거나, 다른 구성요소 또는 균등물에 의하여 대치되거나 치환되더라도 적절한 결과가 달성될 수 있다.

그러므로, 다른 구현들, 다른 실시예들 및 특허청구범위와 균등한 것들도 후술하는 특허청구범위의 범위에 속한다.

1000: 무인기 1100: 센서부
1200: LDM 관리부 1300: 운행 제어부

Claims

무인기 주변 환경을 각각 점유 확률 및 속도를 나타내는 복수의 복셀로 구성되는 3차원 그리드로 표현하는 로컬 동적 맵을 생성하는 방법에 있어서,
상기 복수의 복셀 중 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터의 시간 k-1에서의 속도를 기반으로, 시간 k에서 상기 로컬 동적 맵 상에서의 위치를 예측하는 단계;
상기 적어도 하나의 장애물 클러스터의 예측된 위치를 기반으로, 상기 시간 k에서 상기 복수의 복셀 각각의 점유 확률을 예측하는 단계;
상기 로컬 동적 맵 상에 분포된 파티클들의 상기 시간 k-1에서의 속도를 기반으로, 상기 시간 k에서의 속도를 예측하는 단계;
예측된 상기 파티클들의 속도를 기반으로, 상기 시간 k에서 상기 파티클들의 상기 로컬 동적 맵 상에서 위치를 예측하는 단계;
상기 시간 k에서 상기 무인기 주변 환경을 스캔하여 스캔 데이터를 생성하는 단계;
생성된 스캔 데이터를 기반으로 상기 시간 k에서의 상기 복수의 복셀 각각의 예측된 점유 확률을 업데이트하는 단계;
업데이트된 점유 확률을 기반으로 상기 파티클들의 상기 시간 k에서의 가중치를 업데이트 하는 단계;
상기 파티클들의 예측된 속도 및 업데이트된 가중치를 기반으로 결정되는 상기 복수의 복셀 각각의 속도를 이용하여, 상기 시간 k에서 상기 파티클들의 속도를 업데이트 하는 단계; 및
상기 시간 k에서 상기 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터를 재생성하는 단계;
를 포함하는. 방법.
제1항에 있어서,
상기 시간 k-1에서 상기 무인기의 속도 정보를 기반으로 상기 시간 k-1 상기 무인기의 위치를 업데이트 하는 단계; 및
상기 로컬 동적 맵 상에서 상기 무인기의 위치를 나태내는 상기 시간 k에서의 좌표가 상기 시간 k-1의 좌표와 동일하도록 상기 로컬 동적 맵을 재 생성하는 단계를 더 포함하되,
상기 스캔 데이터를 생성하는 단계는 상기 로컬 동적 맵이 재 생성된 후에 수행되는 것을 특징으로 하는, 방법.
제2항에 있어서,
상기 시간 k에서 재 생성되는 로컬 동적 맵의 사이즈는 상기 시간 k-1에서 로컬 동적 맵의 사이즈와 동일한 것을 특징으로 하는, 방법.
제2항에 있어서,
상기 무인기의 상기 시간 k와 상기 시간 k-1의 위치 차이는 복셀 사이즈의 정수배인 것을 특징으로 하는, 방법.
제2항에 있어서,
상기 시간 k-1에서 파티클들의 개수는 미리 설정된 개수이며, 상기 시간 k에서의 파티클들의 개수가 상기 미리 설정된 개수 미만이면 상기 미리 설정된 개수가 되도록 상기 파티클들의 가중치를 기반으로 리샘플링을 수행하는 단계를 더 포함하는, 방법.
무인기 주변 환경을 스캔하여 스캔 데이터를 생성하고, 무인기의 속도를 센싱하는 센서부;
무인기의 주변 환경을 각각 점유 확률 및 속도를 나타내는 복수의 복셀로 구성되는 3차원 그리드로 표현하는 로컬 동적 맵을 생성하는 LDM 관리부; 및
생성된 로컬 동적 맵에 따라 무인기의 운행을 제어하는 운행 제어부를 포함하되,
상기 LDM 관리부는,
상기 복수의 복셀 중 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터의 시간 k-1에서의 속도를 기반으로, 시간 k에서 상기 로컬 동적 맵 상에서의 위치를 예측하고,
상기 적어도 하나의 장애물 클러스터의 예측된 위치를 기반으로, 상기 시간 k에서 상기 복수의 복셀 각각의 점유 확률을 예측하고,
상기 로컬 동적 맵 상에 분포된 파티클들의 상기 시간 k-1에서의 속도를 기반으로, 상기 시간 k에서의 속도를 예측하고,
예측된 상기 파티클들의 속도를 기반으로, 상기 시간 k에서 상기 파티클들의 상기 로컬 동적 맵 상에서 위치를 예측하고,
상기 시간 k에서 상기 무인기 주변 환경을 스캔하여 스캔 데이터를 생성하며,
생성된 스캔 데이터를 기반으로 상기 시간 k에서의 상기 복수의 복셀 각각의 예측된 점유 확률을 업데이트하고,
업데이트된 점유 확률을 기반으로 상기 파티클들의 상기 시간 k에서의 가중치를 업데이트 하며,
상기 파티클들의 예측된 속도 및 업데이트된 가중치를 기반으로 결정되는 상기 복수의 복셀 각각의 속도를 이용하여, 상기 시간 k에서 상기 파티클들의 속도를 업데이트 하여,
상기 시간 k에서 상기 기준값 이상의 점유 확률을 갖는 인접하는 복셀들로 구성되는 적어도 하나의 장애물 클러스터를 재생성하는, 무인기.
제6항에 있어서,
상기 LDM 관리부는,
상기 시간 k-1에서 상기 무인기의 속도 정보를 기반으로 상기 시간 k-1 상기 무인기의 위치를 업데이트 하고, 상기 로컬 동적 맵 상에서 상기 무인기의 위치를 나태내는 상기 시간 k에서의 좌표가 상기 시간 k-1의 좌표와 동일하도록 상기 로컬 동적 맵을 재 생성하되,
상기 스캔 데이터는 상기 로컬 동적 맵이 재 생성된 후에 생성되는 것을 특징으로 하는, 무인기.
제7항에 있어서,
상기 시간 k에서 재 생성되는 로컬 동적 맵의 사이즈는 상기 시간 k-1에서 로컬 동적 맵의 사이즈와 동일한 것을 특징으로 하는, 무인기.
제6항에 있어서,
상기 무인기의 상기 시간 k와 상기 시간 k-1의 위치 차이는 복셀 사이즈의 정수배인 것을 특징으로 하는, 무인기
제6항에 있어서,
상기 LDM 관리부는,
상기 시간 k-1에서 파티클들의 개수는 미리 설정된 개수이며, 상기 시간 k에서의 파티클들의 개수가 상기 미리 설정된 개수 미만이면 상기 미리 설정된 개수가 되도록 상기 파티클들의 가중치를 기반으로 리샘플링을 수행하는, 무인기.