🤖 AI

Declarative Problem Solving in UAM Strategic Deconfliction

이 논문은 도심 항공 모빌리티의 전략적 충돌 회피를 위한 답변 집합 프로그래밍(ASP) 접근 방식을 제안하며, 벤치마킹을 통해 ASP가 소규모 및 중규모 비행 계획 시나리오에서 제약 프로그래밍보다 우수한 실행 속도와 확장성을 제공함을 입증한다.

원저자: Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

게시일 2026-07-24

📖 2 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

우리 도시 위의 하늘이 훨씬 더 바빠지려 하고 있다고 상상해 보세요. 단지 몇 대의 비행기와 헬리콥터만 있는 것이 아니라, 거대한 드론이나 에어 택시 같은 수천 대의 전기 비행체들이 빌딩 사이를 누비며 물건을 배달하거나 사람들을 직장으로 실어 나르는 미래를 보고 있는 것입니다. 이것을 도심 항공 모빌리티(UAM)라고 부릅니다. 큰 문제는 무엇일까요? 만약 모든 사람이 원할 때마다 날아다닌다면, 서로 충돌하거나 거대한 공중 교통 체증에 갇히게 될 것입니다. 이를 해결하기 위해 과학자들은 비행체가 이륙하기도 전에 모두의 비행 경로를 계획하는 방법이 필요합니다. 이것을 "전략적 충돌 회피(strategic deconfliction)"라고 하는데, 이는 단순히 "두 개의 비행체가 동시에 같은 위치에 있지 않도록 보장하는 것"을 의미하는 멋진 표현입니다. 이를 해결하기 위해 연구자들은 초지능적인 퍼즐 해결사 역할을 하는 특별한 컴퓨터 언어를 사용합니다. 한 가지 유형의 해결사는 "제약 프로그래밍(Constraint Programming, CP)"인데, 이는 책을 내보내기 전 모든 규칙을 하나하나 확인하는 매우 엄격한 사서와 같습니다. 또 다른 유형은 "답 집합 프로그래밍(Answer Set Programming, ASP)"으로, 이는 모든 안전 규칙에 부합하는 최선의 설계도를 빠르게 스케치해내는 창의적인 건축가와 같습니다.

이 논문은 이 창의적인 건축가 방식(ASP)을 사용하여 UAM 교통 퍼즐을 해결하는 STRADA라는 새로운 시스템을 소개합니다. 이탈리아의 연구진인 저자들은 이 창의적인 접근 방식이 엄격한 사서 방식(CP)보다 바쁜 도시의 하늘 속 혼돈을 더 잘 처리할 수 있는지 알아보고 싶었습니다. 그들은 "차선"(공중의 보이지 않는 고속도로와 같은)을 사용하여 하늘의 디지털 모델을 구축했고, 수천 대의 비행체가 그 차선을 통해 이동하는 것을 시뮬레이션했습니다. 그들은 비행체의 수를 늘리거나 이륙 시간 범위를 넓히거나 좁힘으로써 시스템을 테스트했습니다.

결과는 마치 단거리 선수와 마라톤 선수의 경주와 같았습니다. 비행체의 수가 적거나 중간 정도(약 300대까지)일 때, ASP 시스템(STRADA)은 믿을 수 없을 정도로 빨라서 몇 초 만에 안전한 비행 계획을 찾아냈습니다. 이는 단 하나의 해결책을 찾는 데도 오랜 시간이 걸렸던 CP 시스템보다 훨씬 빨랐습니다. 하지만 ASP 시스템에는 함정이 있었습니다. 바로 컴퓨터 메모리를 많이 사용한다는 점이었습니다. 연구진이 5,000대의 비행체가 있는 매우 붐비는 하늘이나 매우 넓은 이륙 시간 범위를 시뮬레이션하려고 했을 때, ASP 시스템은 너무 많은 생각을 담으려다 과부하가 걸린 뇌처럼 메모리가 부족하여 충돌하며 멈춰버렸습니다. 반면, CP 시스템은 속도는 느렸지만 메모리 관리 능력은 훨씬 뛰어났습니다. 비록 작업을 끝내는 데 영겁의 시간이 걸리기는 했지만, 쉽게 멈추지는 않았습니다.

요약하자면, 이 논문은 소규모 또는 중규모 규모의 도시 하늘에 대해서는 창의적인 ASP 방식이 빠르고 효율적이기 때문에 승자라고 제안합니다. 하지만 하늘이 너무 붐비거나 계획 규칙이 너무 느슨해지면, 이 시스템은 벽에 부딪힙니다. 저자들은 자신들의 새로운 방법이 미래의 항공 교통을 관리하기 위한 훌륭한 첫걸음이지만, 메모리 부족 없이 더 큰 인파를 감당할 수 있는 방법을 찾아야 한다고 결론지었습니다. 또한 그들은 자신들의 아이디어가 실제 세계에서도 유효한지 확인하기 위해 실제 데이터와 다양한 컴퓨터 시스템에서 테스트할 계획입니다.

기술 요약: UAM 전략적 충돌 회피를 위한 선언적 문제 해결

문제 정의

본 논문은 항공 교통 관리(Air Traffic Management)의 핵심 계층인 **도심 항공 모빌리티(UAM) 전략적 충돌 회피(Strategic Deconfliction, SD)**를 다룬다. 항공 이동체(드론, 에어 택시, eVTOL 등)의 수요가 인구 밀집 지역에서 증가함에 따라, 공중 충돌 및 기존 교통량과의 충돌 위험이 높아지고 있다. 핵심 문제는 두 항공기가 시간 또는 공간 측면에서 지정된 안전 거리 또는 **간격(headway, $h$ )**을 위반하지 않도록 일련의 스케줄링된 비행 경로를 생성하는 것이다.

이 문제는 $(N, F)$ 의 쌍으로 정식화된다. 여기서 $N$ 은 항공 네트워크(노드는 진입/진출 지점 또는 웨이포인트, 엣지는 일방향 통로를 나타냄)를 나타내는 유향 그래프이고, $F$ 는 스케줄링될 비행(flights)의 집합이다. 각 비행 $f_i$ 는 경로(비순환 부분 그래프), 시작/종료 노드, 속도, 그리고 요청된 이륙 시간 간격 $[e_i, l_i]$ 로 정의된다. 목표는 각 비행에 대해 특정 경로와 출발 시간을 할당하여 다음을 만족하는 것이다:

비행은 요청된 간격 내에 출발한다.
동일한 시작 노드를 공유하는 비행들은 최소 $h$ 만큼 떨어진 서로 다른 출발 시간을 가진다.
임의의 시점에 동일한 노드나 레인을 점유하는 비행들은 최소 $h$ 이상의 안전한 시간적 간격을 유지한다.
총 지연 시간(실제 이륙 시간과 가장 빠른 요청 시간의 차이)을 최소화한다.

방법론

저자들은 **ASP(Answer Set Programming)**를 기반으로 한 STRADA(Scalable Trajectory Resolution Architecture for Deconfliction using ASP) 프레임워크를 제안한다. 이 접근 방식은 전통적인 수치적 방법 및 기존의 제약 프로그래밍(Constraint Programming, CP) 인코딩과 대조된다.

1. 모델링 접근 방식

STRADA는 레인이 유향 그래프인 레인 기반 항공 구조를 사용하여 SD 문제를 모델링한다. 이 프레임워크는 두 가지 변형을 지원한다:

정속(Constant Speed): 모든 비행은 모든 레인에서 고정된 속도를 유지한다.
가변 속도(Variable Speed): 장애물이나 기상 조건을 고려하여 레인별로 속도를 조정할 수 있으며, 이를 위해 속도 술어(predicate)의 수정이 필요하다.

clingo 솔버를 사용하여 구현된 ASP 인코딩은 다음을 활용한다:

사실(Facts): 네트워크 토폴로지(노드, 엣지, 길이), 간격 제약 조건, 비행 명세(경로, 속도, 시간 창)를 정의하기 위해 사용된다.
규칙(Rules): 거리와 속도를 기반으로 레인을 통과하는 비행의 도착 예정 시간(ETA)을 계산한다.
무결성 제약(Integrity Constraints): 안전 제약 조건이 위반되는 잘못된 답집합(answer sets)을 제거한다(예: 충분한 시간 간격 없이 동일한 노드에 있는 두 비행, 또는 동일한 레인에서 경로가 겹치는 두 비행).
최적화(Optimization): 모든 비행의 지연 합계를 최소화하기 위해 #minimize 지시어가 사용된다.

2. 비교 베이스라인

ASP 접근 방식은 제약 프로그래밍(CP) 인코딩(Minizinc/Gecode를 사용하여 해결)과 벤치마킹된다. CP는 변수, 도메인, 제약 조건을 통해 문제를 정의하고 모든 조건을 만족하는 해를 찾는 것을 목표로 한다.

주요 기여

본 논문은 세 가지 주요 기여를 한다:

ASP 정식화: UAM 전략적 충돌 회피 문제를 위한 최초의 논리 기반 정식화를 제공하며, 충돌 없는 궤적 계획에 필요한 필수 조건을 정의한다.
STRADA 프레임워크: 항공 네트워크 토폴로지, 드론 플릿(fleet), SD 인코딩을 모델링할 수 있으며, 정속 및 가변 속도 시나리오를 모두 처리할 수 있는 완전한 프레임워크를 도입한다.
경험적 평가: 다양한 비행량, 이륙 간격 크기, 네트워크 토폴로지(Intracity, Intercity, Airport Shuttle, 합성 그리드)에 걸쳐 STRADA(ASP)와 CP를 비교하는 종합적인 확장성 분석을 제시한다.

실험 결과

실험은 900초의 타임아웃 설정과 함께 노트북(AMD Ryzen 5, 8GB RAM)에서 수행되었다. 연구는 비행 수(15~~400), 이륙 간격(5~~50분), 네트워크 크기(3x3 ~ 5x5 그리드)를 변화시키며 진행되었다.

실행 시간 vs. 확장성:
- ASP (STRADA): 작은 규모 또는 중간 규모의 문제(예: 적은 비행 수, 좁은 간격)에서 우수한 실행 속도를 보여준다. 그러나 복잡성이 증가함에 따라 확장성 문제가 발생한다. 높은 비행 수(300 이상) 또는 넓은 이륙 간격의 경우, ASP는 빈번하게 시간 제한에 걸리거나 메모리 부족(Out-of-Memory) 오류를 일으키며, 그라운딩(grounding) 단계에서 "조합 폭발(combinatorial explosion)" 현상을 보인다.
- CP: 일반적으로 ASP보다 훨씬 더 많은 실행 시간을 필요로 하며, 중간 규모의 문제에서도 시간 제한 내에 최적해를 찾는 데 실패하는 경우가 많다. 그러나 CP는 다양한 문제 크기에 걸쳐 더 안정적이고 효율적인 메모리 사용량을 보여주며, ASP가 실패하는 지점에서도 메모리 제한에 거의 걸리지 않는다.
네트워크 토폴로지 영향:
- ASP의 실행 시간은 비행 수에 따라 선형적으로 증가하지만, 더 많은 원자(atoms)와 규칙이 생성됨에 따라 네트워크 크기에 따라 비선형적으로 증가한다.
- 5,000개의 비행이 있는 5x5 그리드에서 메모리 사용량이 약 80 MB에서 7.10 GB로 급증하는 임계점이 관찰되었으며, 이는 고밀도 시나리오에 대한 현재 모델의 한계를 나타낸다.

의의 및 주장

본 논문은 UAM 전략적 충돌 회피를 위한 최초의 ASP 기반 공식화를 도입했다고 주장한다. 저자들은 자신들의 접근 방식이 갖는 세 가지 핵심 장점을 강조한다:

단순하고 읽기 쉬운 모델링: ASP의 선언적 특성은 복잡한 제약 조건을 간결하게 표현할 수 있게 한다.
복잡한 최적화 지원: ASP는 궤적 계획의 조합론적 특성을 효과적으로 처리한다.
적응성: 본 프레임워크는 주요 재프로그래밍 없이 사양 변경(예: 가변 속도)을 수용할 수 있다.

연구의 결론은 ASP가 실시간 전략적 충돌 회피 작업에는 더 빠른 실행 속도를 제공하지만, 고밀도 시나리오에서의 확장성은 현재 메모리 제약에 의해 제한된다는 것이다. 반대로 CP는 메모리 안정성은 더 높지만 성능(시간) 면에서는 열세이다. 저자들은 현재의 실험 파라미터가 현대의 UAM 벤치마크와 일치함을 언급하면서, 향-후 연구에서는 고밀도 도시 환경에서의 확장성을 완전히 평가하기 위해 실제 데이터셋을 통한 모델 검증과 교차 플랫폼 솔버 성능 탐구가 필요하다고 제언한다.