An Algorithm for Local Dynamic Map Generation for Safe UAV Navigation

Abstract

In recent years, researches for perception of the flight environment and collision avoidance control have been actively conducted for the safe navigation for unmanned aerial vehicles (UAVs) used in various fields such as surveillance, agriculture, transportation, rescue and military. Accurate and real-time perception of the surrounding environment, such as the free area and the recognition of dynamic and static obstacles, is essential for path planning and control for navigation to avoid collision. The perception system of the UAV needs to recognize information such as the position and velocity of all objects in the surrounding local area regardless of the type of the object. At the same time, a probability based representation taking into account the noise of the sensor is also essential. In addition, a software design with efficient memory usage and operation time is required in consideration of the hardware limitations of the UAVs. In this paper, we propose a 3D Local Dynamic Map(LDM) with essential elements of the aforementioned UAV perception system. The proposed LDM uses a circular buffer as a data structure to ensure low memory usage and fast operation speed. Probability based occupancy map is created using sensor data, and the position and velocity of each object are calculated through clustering between grid voxels using this occupancy map and velocity estimation based on particle filter. The objects are predicted using the position and velocity of each object, and this is reflected in the occupancy map. This process is continuously repeated, and the flying environment of the UAV can be expressed in a three-dimensional grid map and the state of each object. For the evaluation of the proposed LDM, we constructed a simulation environment and the UAV for outdoor flying. In the simulation, multiple environments with dynamic and static obstacles are created, and the UAV equipped with a virtual LiDAR sensor is created in those situations. The UAV for outdoor flying is constructed with a LiDAR sensor and computing board for sensor data processing and LDM algorithm running. As an evaluation factor, the occupancy grid accuracy is evaluated, and the ground truth velocity and the estimated velocity are compared. |최근 몇 년간 무인기는 정찰, 감시, 농업, 운송, 구조, 국방 등의 다양한 분야에서 사용이 크게 증가하고 있다. 이에 따라 충돌을 회피하는 안전한 무인기의 주행을 위해 주행 환경의 인지, 충돌 회피 제어와 관련된 연구도 활발히 이루어지고 있다. 충돌을 회피하는 주행에 대한 경로 계획, 제어를 위해서는 주행 가능 영역, 동적 및 정적 장애물 인지 등 주변 환경에 대한 정확하고 실시간 인지가 필수적이다. 무인기의 인지 시스템은 물체의 종류와 관계없이 주변 로컬 영역에 존재하는 모든 물체의 위치 속도 등의 정보를 인지함과 동시에 센서의 노이즈를 고려한 확률기반의 표현이 필요하다. 또한 무인기의 하드웨어적 한계를 고려하여 메모리 사용 및 연산 시간이 효율적인 소프트웨어 설계가 필요하다. 본 논문에서는 앞서 언급한 무인기 인지 시스템의 필수 요소들을 갖춘 3차원 로컬 동적 맵을 제안한다. 제안하는 로컬 동적 맵은 데이터 구조로 원형 버퍼를 활용하여 적은 메모리 사용량과 빠른 연산속도를 확보한다. 센서 데이터를 활용하여 확률 기반의 누적 맵을 작성하며 이 누적 맵을 이용한 그리드 셀 간 클러스터링과 파티클 필터 기반의 속도 추정을 통해 각 물체 별 위치 및 속도를 연산한다. 각 물체 별 위치와 속도를 이용하여 이동할 위치를 예측하고 이를 기존 누적 맵에 반영한다. 이 과정이 지속적으로 반복되어 무인기 주행 환경을 3차원 그리드 맵과 물체 별 상태로 표현할 수 있다. 제안하는 로컬 동적 맵의 평가를 위해 우리는 시뮬레이션 환경과 실외 주행용 무인기를 구성했다. 시뮬레이션에서는 동적 및 정적 장애물이 존재하는 여러 환경을 만들고 해당 상황에서 가상의 라이다 센서가 장착된 무인기를 생성했다. 실외 주행용 무인기는 시뮬레이션과 동일하게 라이다 센서를 장착하여 구성했다. 평가 지표로 실제 장애물 점유 영역에 대한 정확성을 평가했고 실제 속도와 추정된 속도의 비교를 수행했다. 그 결과 속도 추정 결과를 반영한 예측과정으로 인해 기존의 누적 맵 작성 방식에 비해 동적환경에서 더 정확한 그리드 맵을 작성할 수 있었고 추정된 속도 또한 실제 속도와 유사한 것을 확인할 수 있었다.