Decentralized Trajectory Planning for Quadrotor Swarm in Cluttered Environments with Goal Convergence Guarantee

Abstract

This dissertation presents an online distributed multi-agent trajectory planning (MATP) algorithm for a quadrotor swarm in a maze-like dynamic environment. For deadlock resolution, the proposed algorithm utilizes the subgoal optimization method that ensures the agent converges to the subgoal without deadlock and uses a waypoint from a grid-based multi-agent path planning (MAPP) algorithm to guide the subgoal to the desired goal. In addition, the proposed algorithm adopts a safe flight corridor (SFC) and linear safe corridor (LSC) for static obstacle avoidance and inter-agent collision avoidance. As a result, the proposed algorithm guarantees collision avoidance, the feasibility of the constraints, and goal convergence in a static obstacle-rich environment under a limited communication range. For dynamic obstacle avoidance, a relative safe flight corridor (RSFC) is introduced to cover the reachable region of the dynamic obstacles. Moreover, priority-based MAPP is adopted to prevent other agents' interference when avoiding dynamic obstacles. To verify the proposed algorithm, the simulation was conducted in an empty space, random forest, and maze. In an obstacle-free space, the proposed method can compute the trajectories for 70 agents on average 9.69 ms per agent with an Intel i7 laptop and shows the perfect success rate. Also, our method shows 44.7% shorter flight time than buffered Voronoi cell (BVC) and 23% shorter than with our previous work. The proposed algorithm shows the highest success rate and shortest flight time compared to state-of-the-art baseline algorithms. In particular, the proposed algorithm shows over 90% success rate when the velocity of moving obstacles is below the agent's maximum speed. The safety and robustness of the proposed algorithm were validated through a hardware demonstration with ten quadrotors and one pedestrian in a maze-like environment.

본 논문에서는 동적 장애물이 있는 미로와 같은 환경에서 쿼드로터 군집을 위한 온라인 분산 다중 로봇 경로 계획 알고리즘을 제안한다. 제안하는 방법은 교착 상태 해소를 위해 에이전트가 목표지점에 수렴할 수 있도록 중간 목표 지점을 최적화하는 방법을 사용하였으며 그리드 기반 다중 에이전트 경로 계획 알고리즘에서 계산되는 경로점들을 사용하여 중간 목표점을 최종 목표점으로 유도하는 방법을 사용한다. 제안하는 알고리즘은 안전 비행 복도 (safe flight corridor)을 사용하여 정적 장애물과의 충돌을 방지하며 선형 안전 복도 (linear safe corridor)를 사용하여 에이전트 간의 충돌을 방지한다. 그 결과, 제안하는 방법은 제한된 통신 범위 아래에서도 정적 장애물 환경에서 충돌 회피, 제한 조건들의 실현 가능성, 목적지 수렴을 보장한다. 또한 본 논문에서는 상대적 안전 비행 복도 (relative safe flight corridor)을 사용하여 장애물의 도달 가능 영역을 우회하는 방법으로 동적 장애물을 회피하는 방법을 제안한다. 그리고 좁은 환경에서는 에이전트가 서로 뭉치는 현상이 자주 발생하게 되므로 우선순위 기반의 다중 에이전트 경로 계획 알고리즘을 사용하여 동적 장애물을 회피할 때 다른 에이전트들이 간섭하는 현상을 방지한다. 제안하는 방법을 검증하기 위해 장애물이 없는 공간, 랜덤 포레스트, 미로 환경에서 시뮬레이션을 진행하였다. 제안하는 방법은 장애물이 없는 공간에서 Inter i7 노트북으로 에이전트당 평균 9.69 ms만에 70개의 에이전트에 대한 경로를 생성할 수 있으며 100%의 성공률을 보여주었다. 또한, 제안하는 방법은 보로노이 기반 방법 (buffered Voronoi cell) 보다 비행시간이 44.7% 더 짧았으며 기존 선행 연구보다 비행시간이 23% 더 짧은 것으로 나타났다. 그리고 제안하는 방법은 동적 장애물이 있는 환경에서는 최신 알고리즘과 비교했을 때 가장 높은 성공률과 낮은 비행시간을 보여주는 것을 확인하였다. 특히 제안하는 방법은 동적 장애물의 속도가 에이전트의 최대속도 이하일때 90% 이상의 성공률을 보여주었다. 제안하는 알고리즘의 안전성과 강건성을 검증하기 위해 보행자가 있는 미로 같은 환경에서 실험을 10대의 쿼드로터를 진행하는 실험을 진행하였으며 충돌 또는 교착상태가 발생하지 않음을 확인하였다.