컴퓨터공학과 김민철·안태훈 박사과정 학생과 AI대학원 서찬양 석사과정 학생(지도, 안희갑 교수)은 알고리즘 분야 최고수준 국제학술대회인 제38회 Symposium on Computational Geometry (2022)에 구두 발표 논문으로 최종 선정되었다. 장애물이 존재하는 평면 공간을 객체 사이트로부터의 측지거리(geodesic distance)를 기준으로 정확히 분할하는 최적시간 알고리즘을 제시한 이 논문은 치열한 경쟁과 심사를 통해 구두 발표논문으로 최종 선정된 64편의 논문 가운데 저자가 모두 아시아 지역 소속인 유일한 논문이다.
장애물이 있는 공간에 대한 farthest-site Voronoi diagram으로 알려진 이 공간 분할은 알고리즘의 계산 난제로 지금까지 최적시간 계산 알고리즘이 알려지지 않았는데, 이 연구는 세계 최초로 최적시간 계산 알고리즘을 제시하였고, 이를 통해 공간의 중심점(geodesic center)도 더 빠른 시간 내에 계산할 수 있게 되었다. 이 연구는 학술적 성과의 우수성을 인정받아 안희갑 교수가 이끄는 알고리즘 연구팀은 산업과 학술에서 최적화 문제를 해결하는 알고리즘을 가장 정확하고 빠르게 설계하는 연구에 주력하고 있다.

장애물이 많은 공간에서 목적지까지 이동할 때 에너지나 이동 시간을 가장 적게 쓰면서 이동하는 경로를 계산하기 위해서는 공간을 분석하고 최적으로 분할하는 기술이 매우 중요하다. 공간 분할은 자동차, 로봇, 드론 등의 객체가 이동하는 공간의 범위, 모양, 크기, 그리고 장애물의 존재에 따라 데이터와 객체로부터 거리를 기준으로 공간을 분할하는 알고리즘 기술이다.
빠른 시간에 최적의 공간 분할을 계산하게 되면 이를 이용해 최근접 이웃탐색(nearest neighbor search), 데이터 군집화(clustering) 등 주요 데이터 처리문제와 로봇의 최단 이동경로를 더욱 빠르게 계산할 수 있게 되어 기계학습, 컴퓨터 비전 등 컴퓨터 기술과 물리와 화학 등에서의 데이터 분석과 모델링, 시뮬레이션의 계산 속도가 획기적으로 개선될 수 있다.
데이터의 종류와 양, 그리고 공간의 복잡도가 기하급수적으로 증가함에 따라 초대규모 데이터와 공간을 효율적으로 분할, 분석하는 방법에 대해 학계와 산업의 관심속에 지속적인 연구가 진행되고 있다. 특히, 공간에 장애물이 존재하는 경우에는 로봇의 최단 이동 경로가 여러개 존재할 수 있고 계산 복잡도가 매우 높아지게 되어, 이러한 계산 한계를 극복하는 최적 계산 알고리즘 연구가 주목을 받고 있다. 알고리즘 연구는 컴퓨터의 성능을 높이지 않고도 한번에 수백만배 이상 성능을 높일 수 있다.

이 연구는 정보통신기획평가원의 소프트웨어 스타랩 연구사업과 인공지능대학원 사업의 지원을 받아 수행되었다.