Fair Hungarian Algorithm for Swarming Drone Flight Formation Transformation
SungTae Moon · Journal of KIISE · 2022
평창 올림픽 이후 군집 비행 시스템을 활용한 드론 쇼는 기술과 문화의 융합으로 많은 사람들에게 깊은 인상을 심어 주었다. 군집 비행을 위해서는 다수 드론과 안정적인 통신, 정확한 위치 인식, 그리고 충돌없는 최단 형상 변환 기술이 필요하다. 특히, 형상 변환 기술은 드론 쇼의 핵심 기술로써 제한된 비행 시간 안에 최대한 많은 형상을 표현하기 위해 형상 변경 시 할당 문제로 최적화를 수행한다. 할당 문제는 헝가리안 알고리즘을 통해 이동 거리 합을 최소화할 수 있다. 하지만, 헝가리안 알고리즘을 군집비행에 적용한 경우, 전체 이동 거리 합은 최소화할 수 있지만, 개별 드론의 이동량을 고려하지 않아 배터리 소진으로 전체 운용 시간이 단축되는 문제가 발생하였다. 본 논문에서는 형상 변환 시간을 가능한 최소화하면서 드론들의 배터리 소모량을 공평하게 소모하여 운용 시간을 최대화하기 위한 공평한 헝가리안 알고리즘을 제안한다. 그 결과, 드론들의 배터리 사용량을 공평하게 유지함으로써 특정 드론의 배터리 소진으로 인한 드론쇼 중단 문제를 개선하였고, 같은 조건에서 보다 많은 형상을 선보일 수 있었다. 이 알고리즘은 100대의 드론으로 군집 비행을 함으로써 검증하였다.