사우스웨스트 항공은 자사 조종사들의 행방마저 놓쳤다. 그때 나는 챗봇이 물류를 구하지 못하리라는 걸 알았다.

AI에 대한 내 생각을 바꿔놓은 전화는 고객이나 투자자에게서 온 것이 아니었다. 한 친구 — 조종사 — 에게서 온 것이었는데, 그는 2022년 크리스마스를 덴버 국제공항 바닥에서 자며 보냈다.

그가 발이 묶인 것은 날씨 때문이 아니었다. 폭풍은 지나간 뒤였다. 그가 발이 묶인 것은 사우스웨스트 항공이 말 그대로 그가 어디 있는지 놓쳐버렸기 때문이었다. 이 항공사의 승무원 스케줄링 시스템 — SkySolver라는 레거시 최적화 엔진 — 은 몇 시간 지난 승무원 위치를 바탕으로 복구 계획을 계산하고 있었다. 유령 항공사를 위한 스케줄을 만들어내고 있었던 것이다. 내 친구는 스케줄링 핫라인에 전화를 걸어 여덟 시간을 대기했다. 누군가 전화를 받았을 무렵에는, 그들이 방금 계산한 스케줄이 이미 다시 틀려 있었다.

그 주에 사우스웨스트는 16,900편이 넘는 항공편을 취소했다. 200만 명의 승객이 발이 묶였다. 항공사는 10억 달러 넘게 손실을 봤다. 그리고 나를 괴롭힌 부분은 이것이다: 다른 모든 주요 미국 항공사도 같은 폭풍, 같은 얼어붙은 활주로, 같은 인력 부족을 겪었다. 유나이티드, 델타, 아메리칸 — 이들은 모두 48시간 안에 회복했다. 사우스웨스트는 꼬박 일주일 동안 곤두박질쳤다.

나는 하나의 질문으로 계속 되돌아갔다: 왜 다른 항공사들은 휘어졌다가 회복하는데 한 항공사의 소프트웨어는 무너졌을까? 내가 발견한 답은 날씨와는 아무 상관이 없었고, 지난 30년 동안 우리가 복잡한 운영의 연산적 두뇌를 어떻게 구축해 왔는지와 전적으로 관련이 있었다. 그 깨달음이 나로 하여금 VeriPrajna를 세우게 했고 — 그리고 그 완전한 기술적 논거를 담은 이 연구 논문을 쓰게 했다.

하지만 짧게 말하면 이렇다: 우리는 더 이상 효율성에 보상하지 않는 세상에서 효율성을 위해 물류를 최적화해 왔다. 우리는 알려진 질문에 대한 가장 저렴한 답을 찾는 시스템을 구축해 왔지만, 정작 우리에게 필요한 것은 알려지지 않은 질문에 대한 생존 가능한 답을 찾는 시스템이다.

크리스마스를 죽인 위상 구조

사우스웨스트가 왜 무너졌는지 이해하려면, 그래프 이론의 한 개념을 이해해야 한다 — 그리고 들리는 것보다 훨씬 더 흥미롭다고 약속한다.

델타, 유나이티드, 아메리칸은 허브 앤 스포크 네트워크를 운영한다. 항공편은 애틀랜타나 뉴어크 같은 중앙 허브에서 방사형으로 뻗어 나간다. 폭풍이 북동부를 강타하면, 허브 앤 스포크 항공사는 피해를 "방화벽"으로 차단할 수 있다 — 오전 동안 뉴어크로 들어오는 모든 항공편을 취소하고, 하위 그래프를 재설정한 뒤, 재개하는 것이다. 승무원과 항공기가 허브를 통해 자주 순환하며 자연스러운 복구 지점을 만들어낸다.

사우스웨스트는 다른 모델을 개척했다: 포인트 투 포인트. 항공기와 승무원은 선형 사슬을 비행한다 — 볼티모어에서 덴버, 샌디에이고, 피닉스를 거쳐 새크라멘토로. 경제적으로는 탁월하다. 모든 항공기에서 더 많은 비행 시간을 짜낼 수 있다. 하지만 수학적으로는? 그것은 모래 위의 성이다. 첫 구간의 지연은 회항편에만 영향을 주는 것이 아니라 — 사슬 전체로 연쇄된다. 샌디에이고에서 피닉스로 비행할 예정이던 승무원은 덴버에 발이 묶인다. 샌디에이고에서 그들을 기다리던 항공기는 오도 가도 못하게 된다.

그래프 이론 용어로 말하면, 포인트 투 포인트 네트워크에서 의존성 그래프의 지름은 허브 앤 스포크보다 훨씬 더 크다. 단일 혼란의 폭발 반경이 억제되지 않는다.

내가 우리 사무실 화이트보드에 이것을 처음 그려본 그날 밤을 기억한다. 나와 우리 팀은 사우스웨스트의 실패가 소프트웨어 문제인지 네트워크 설계 문제인지를 두고 논쟁하고 있었다. 그것이 둘 다라는 내 주장에 답답해하던 우리 엔지니어 중 한 명이 실제 항공편 데이터를 불러와 의존성 사슬을 그리기 시작했다. 우리는 그 연쇄가 지도 위로 펼쳐지는 것을 지켜봤다. 볼티모어의 지연이 덴버로 파급되었고, 그것이 샌디에이고로의 연결을 끊었고, 그것이 피닉스로 비행할 예정이던 승무원을 발이 묶이게 했고, 그것이…

"이건 사슬이 아니야," 그가 말했다. "이건 균열이야."

그가 옳았다. 그리고 그 균열은 그것을 고쳐야 할 소프트웨어에게는 보이지 않았다.

SkySolver는 왜 멈춰버렸을까?

SkySolver는 대부분의 물류 최적화를 구동하는 것과 동일한 수학적 기반 위에 구축되어 있다: 혼합 정수 선형 계획법과 열 생성이라 불리는 기법이다. 이들은 1950년대 이래로 우리가 원자를 전 세계로 옮기는 방식을 지배해 온 분야인 운영 연구의 일꾼들이다.

쉬운 말로 그 작동 방식은 이렇다: 시스템은 세상의 스냅샷을 찍고 — 모든 승무원이 어디 있는지, 모든 항공기의 상태가 무엇인지 — 시간을 정지시킨 뒤, 모든 항공편을 처리하는 수학적으로 가장 저렴한 방법을 계산한다. 일일 4,000편을 운항하는 주요 항공사의 경우, 가능한 승무원 대 항공편 조합의 수는 사실상 무한하다. 열 생성은 "유망한" 조합을 반복적으로 생성하고 탐색 범위를 좁혀가며 이를 처리한다.

그것은 우아하다. 그것은 강력하다. 그리고 그것은 그 DNA 안에 치명적인 가정 하나가 새겨져 있다: 그것이 생각하는 동안 세상은 가만히 멈춰 있다는 것.

정상 운영 중에는 30분에서 60분의 솔버 주기가 괜찮다. 하지만 붕괴 사태 동안, 사우스웨스트 네트워크의 상태는 몇 분마다 바뀌고 있었다. 전화선이 넘쳐나 승무원들은 자신의 위치를 보고할 수 없었다. SkySolver에 공급되는 데이터는 몇 시간이나 낡은 것이었다. 시스템은 더 이상 존재하지 않는 세상을 최적화하고 있었다.

혼란의 속도가 정보의 속도를 넘어설 때, 최적화는 우아하게 저하되지 않는다. 그것은 붕괴한다.

이것이 내가 부르는 최적화-실행 격차이다 — 솔버가 얼마나 빨리 계산할 수 있는지와 현실이 얼마나 빨리 움직이는지 사이의 치명적인 불일치다. 그리고 이는 항공사에만 국한된 것이 아니다. 나는 항만 물류, 철도 배차, 제조 공급망에서 동일한 실패 패턴을 봐 왔다. 수학은 같다. 취약성도 같다.

내가 물류에 챗봇을 믿기를 멈춘 순간

사우스웨스트 위기 약 6개월 후, 나는 한 투자자와의 회의에 앉아 있었는데 그는 완전한 확신을 가지고 내게 말했다. "그냥 GPT를 써요. 스케줄링 데이터로 파인튜닝하세요. 문제 해결."

나는 그것이 왜 통하지 않을지 설명하려 했다. 그는 내 말을 끊었다: "하지만 그건 추론할 수 있잖아요. 수학 문제를 푸는 걸 봤어요."

그 대화가 내가 표현하려 애써온 무언가를 명확하게 만들었다. 업계 전체가 범주 오류를 범하고 있었다 — 대규모 언어 모델의 언어적 유창함을 복잡한 시스템을 관리하는 데 필요한 운영적 추론과 혼동한 것이다. 벤더들은 레거시 솔버 위에 채팅 인터페이스를 씌운 "AI 코파일럿"으로 시장을 넘쳐나게 하고 있었다. 배차 담당자가 "덴버 스케줄을 어떻게 복구하죠?"라고 물으면, LLM은 그것을 아래에 있는 바로 그 고장 난 최적화 엔진에 대한 API 호출로 번역한다.

그것은 멈춰버린 엔진 위에 페인트칠만 새로 한 것이다.

근본적인 문제는 이것이다: LLM은 시퀀스에서 다음 토큰을 예측하도록 설계된 확률적 엔진이다. 그것들은 세계 모델을 갖추지 않은 채 추론의 형태를 흉내낸다. 인지 과학 용어로 말하면, 그것들은 거대한 시스템 1 엔진이다 — 빠르고 직관적인 패턴 매칭이다. 물류 최적화는 시스템 2 과제다 — 느리고 신중하며 단계별로 제약 조건을 검증하는 것이다.

그리고 제약 조건 문제가 위험해지는 지점이다. 창작 글쓰기에서는 99% 정확도가 훌륭하다. 승무원 스케줄링에서는 99% 정확도가 불법이다. LLM이 7시간 59분의 휴식을 취한 조종사를 8시간을 요구하는 항공편에 배정하는 스케줄을 생성하면, 스케줄 전체가 무효가 된다. LLM은 실현 가능성 제약 조건의 엄격한 이진적 본질을 자연스럽게 다루지 못한다. 그것들은 논리적 정확성보다 언어적 일관성을 우선시한다.

스케줄을 설명할 수 있는 챗봇은 스케줄을 복구할 수 있는 에이전트와 같지 않다.

외판원 문제와 같은 조합 문제에 대한 벤치마크가 이를 대규모로 확인해 준다. 노드 수가 늘어날수록, LLM은 도시를 두 번 "방문"하고, 다른 도시들은 아예 건너뛰며, 긴 시퀀스에 걸쳐 상태를 놓친다. 그것들은 분기하는 미래를 시뮬레이션하거나 되짚어 갈 수 없다. 그것들은 나비 효과 — 지금의 작은 스케줄링 결정이 사흘 후 재앙을 일으킬 수 있다는 현실 — 에 눈이 멀어 있다.

실제로 통하는 것: AI에게 그래프로 사고하도록 가르치기

그렇다면 레거시 솔버는 너무 느리고 LLM은 너무 신뢰할 수 없다면, 무엇을 구축해야 하는가?

이것이 나와 우리 팀이 수년간 답해 온 질문이며, 우리가 도달한 아키텍처는 그래프 강화 학습 위에 구축되어 있다 — 그래프 신경망(네트워크 위상 구조를 이해하기 위해)과 강화 학습(동적 의사결정 정책을 학습하기 위해)의 융합이다. 우리는 스케줄을 계산하는 것에서 스케줄링하는 법을 학습하는 것으로 옮겨갔다.

모든 것을 열어젖힌 통찰은 놀라울 만큼 단순했다: 물류 네트워크는 스프레드시트가 아니다. 그것들은 그래프다. 공항은 노드다. 항공편은 간선이다. 창고는 노드다. 트럭은 간선이다. 전통적인 기계 학습 아키텍처 — 이미지나 텍스트를 위해 설계된 종류 — 는 이 관계적 구조를 다루기 어려워한다. 그래프 신경망은 이를 위한 본래의 아키텍처다.

우리는 그래프 어텐션 네트워크를 사용하여 물류 네트워크 전체의 상태를 인코딩한다. 모든 개체 — 조종사, 항공기, 공항 — 는 정적 속성(항공기 유형, 승무원 자격)과 동적 상태(현재 지연, 정비 상태, 누적된 피로)를 모두 포착하는 고차원 임베딩을 가진 노드가 된다. 그것들 사이의 연결은 비행 시간, 기상 위험, 승무원 배정에 관한 정보를 담는다.

그 마법은 메시지 전달이라 불리는 것에 있다. 눈보라가 덴버를 폐쇄하면, GNN은 덴버의 임베딩을 갱신한다. 그 갱신은 연결된 모든 간선 — 모든 도착 항공편, 모든 승무원 배정 — 을 따라 흘러간다. 덴버로 비행할 준비를 하고 있는 볼티모어의 조종사는 출발하기도 전에 자신의 임베딩에 "위험 신호"를 받는다. 시스템은 연결성을 본다. 그것은 폭발 반경을 이해한다. 이런 종류의 위상적 인식은 레거시 시스템이 사용하는 평평한 표 형식 데이터 표현에서는 불가능하다.

이 그래프 인식 계층 위에서, 우리는 강화 학습 에이전트를 실행한다. RL 에이전트는 상태를 관찰하고, 행동을 취하고(승무원 교체, 항공편 취소, 출발 지연, 승무원을 새 위치로 데드헤딩), 보상을 받는다. 수백만 번의 훈련 반복에 걸쳐, 그것은 장기적 결과를 극대화하는 정책을 학습한다.

그 표현 — 장기적 — 이 전부다. 휴리스틱은 이렇게 말할지도 모른다: "이 항공편을 취소하지 마라, 수익을 잃는다." 우리 RL 에이전트는 이렇게 학습한다: "이 항공편을 취소하지 않으면, 승무원이 덴버에 발이 묶이고, 내일 열 편을 잃는다. 지금 취소하라." 그것은 시스템적 생존을 위한 전략적 희생을 학습한다.

아직 일어나지 않은 재난을 위해 AI를 어떻게 훈련시키는가?

당연히 살아 있는 항공사에서 강화 학습 에이전트를 훈련시킬 수는 없다. 현실 세계에서의 시행착오는 수백만 달러의 비용이 들고 안전 위험을 만든다. 여기서 디지털 트윈이 등장한다 — 그리고 나는 공항을 3D로 렌더링한 대시보드를 말하는 것이 아니다.

우리의 디지털 트윈은 상태 전이 엔진이다. 우리는 모든 항공기를 기체별 정비 주기로, 모든 게이트를, 모든 승무원을 개별 피로 카운터와 계약 상태로 모델링한다. 우리는 규정집을 디지털화한다 — FAA Part 117, 노조 계약, 정비 매뉴얼. 모든 상태 전이는 이 규칙들에 대조되어 검사된다.

그런 다음 우리는 혼돈을 주입한다.

우리는 확률적 생성기를 사용하여 일주일 안에 10,000년치의 운영을 시뮬레이션한다. 우리는 초대형 폭풍, 대규모 기계적 운항 중단, 노동 파업을 만들어낸다. 우리는 에이전트를 쉬운 날들 — 맑은 날씨, 가벼운 스케줄 — 로 시작하게 한 뒤, 점진적으로 난이도를 높여, 사우스웨스트 붕괴 사태를 가벼운 불편처럼 보이게 만들 연쇄적 실패들을 도입한다.

우리가 2022년 12월 사우스웨스트 위기를 우리 시뮬레이터로 처음 돌려본 때를 기억한다. 우리는 벤치마크 대상으로 삼기 위해 레거시 솔버의 대리물을 만들어 뒀었다. 레거시 솔버는 SkySolver가 했던 것과 정확히 똑같이 했다 — 데이터 지연에 멈춰버렸고, 잘못된 상태에 대해 최적화했고, 발이 묶인 승무원들의 똑같이 뒤엉킨 난장판을 만들어냈다. 복구 시간: 시뮬레이션된 7일.

우리 GRL 에이전트는 우리 중 누구도 예상하지 못한 일을 했다. 그것은 전면적인 연쇄가 일어나기 몇 시간 전에 덴버에서 포인트 투 포인트 균열 패턴이 나타나는 것을 감지했다. 그런 다음 그것은 우리가 지금 선제적 방화벽 전략이라 부르는 것을 실행했다 — 덴버로 들어오는 항공편의 20%를 일찍 취소하여 혼란을 국지적으로 가두고, 승무원을 피닉스로 데드헤딩하여 2차 운영 기지를 만들었다.

동부 해안 네트워크는 95% 가동 상태를 유지했다. 총 취소 편수는 66% 감소했다. 붕괴 사태는 지역적 혼란으로 억제되었다.

우리 엔지니어 — 화이트보드에 균열을 그렸던 바로 그 사람 — 는 그저 화면을 응시했다. "이게 네트워크를 살리려고 덴버를 희생했어," 그가 말했다. "어떤 인간 배차 담당자도 12월 22일 오전 6시에 그럴 배짱은 없었을 거야."

그가 옳았다. 그리고 그것이 요점이다. 그 에이전트는 시뮬레이션 속에서 수천 번의 위기를 "겪어냈다". 그것은 레거시 솔버가 무너지는 상태 공간의 가장자리를 탐색했고, 생존이 어떤 모습인지를 학습했다. 아키텍처의 완전한 기술적 분석 — GAT 임베딩, PPO 훈련 루프, 행동 마스킹 — 을 위해, 나는 전체 연구를 발표했다.

블랙박스 문제는 어떤가?

사람들은 항상 여기서 반박하고, 마땅히 그래야 한다. "항공사 운영의 통제권을 신경망에 넘기라는 말인가요? 그게 불법 스케줄을 환각하지 않으리라는 걸 어떻게 알죠?"

이것은 안전이 중대한 AI에서 가장 중요한 반론이며, 이를 일축하는 사람은 진지하지 않은 것이다. 우리가 그것을 어떻게 해결하는지 여기 있다.

우리는 절대 신경망이 최종 결정을 직접 출력하도록 두지 않는다. 우리는 우리가 부르는 샌드위치 아키텍처를 사용한다 — 강화 학습으로 유도되는 정수 계획법을 위한 NICE 프레임워크에서 영감을 받았다. 신경망 계층(우리 GRL 에이전트)은 복잡하고 잡음이 많은 상태를 분석하고 행동에 대한 확률 분포를 제안한다. 그런 다음 결정론적 기호 계층 — 운영의 모든 강경 규칙을 인코딩한 제약 엔진 — 이 마스크를 적용한다. 신경망이 규정을 위반하는 행동(조종사가 근무 시간을 초과, 항공기가 미해결 정비 항목을 안고 비행)을 제안하면, 기호 계층은 그 행동의 확률을 0으로 설정한다.

시스템은 불법적인 행동을 실행할 수 없다. "아마 하지 않을 것"이 아니다. 할 수 없다.

이것은 우리에게 놀라운 것을 준다: 학습된 AI 정책의 최적성과 형식 논리의 안전 보장을 함께. 그리고 이것은 반대 방향에서도 연산 문제를 해결한다. 레거시 솔버가 십억 가지 가능성을 탐색하는 대신, 신경망이 트리를 가장 유망한 열 개의 가지로 잘라낸다. 솔버는 그 몇 안 되는 선택지만 검증하고 미세 조정하면 된다. 연산 시간은 몇 시간에서 몇 초로 떨어진다.

이것은 단지 항공사에 관한 이야기가 아니다

사우스웨스트 붕괴 사태는 가장 극적인 사례이지만, 그것이 드러낸 취약성은 보편적이다. 우리는 동일한 GRL + 디지털 트윈 아키텍처를 해상 항만과 철도 네트워크에 맞게 적용하고 있다.

항만에서는, 지연된 선박이 접안 슬롯을 놓치고, 크레인이 재배정되며, 컨테이너 픽업 예정이던 트럭이 몇 시간씩 줄을 선다. 우리는 "정박지 에이전트"가 "터미널 에이전트"와 실시간으로 협상하는 에이전트형 AI를 배치하여, 혼란이 전개될 때 게이트 혼잡의 봉우리와 골짜기를 완만하게 다듬는다.

단선 병목이 하나의 잘못된 "교행" 결정으로 수백 마일 떨어진 열차들을 교착 상태에 빠뜨릴 수 있는 철도에서는, 우리 GRL 에이전트가 지연 감소에서 인간 배차 담당자와 휴리스틱 규칙을 15-20% 능가한다. 그것들은 직관에 반하는 수 — 50마일 상류의 급행 열차를 위한 길을 터주려고 화물 열차를 일찍 대기시키는 것 — 를 두는데, 이는 어떤 규칙 기반 시스템도 고려하지 않을 것이다.

패턴은 언제나 같다: 복잡한 네트워크, 강경한 제약 조건, 연쇄적 혼란, 그리고 분 단위로 측정되는 의사결정 창. 레거시 솔버는 따라가지 못한다. LLM은 그것을 추론하지 못한다. 그래프 강화 학습은 할 수 있다.

진정한 ROI는 효율성이 아니다 — 생존이다

사우스웨스트의 일주일간의 붕괴 사태는 12억 달러의 비용이 들었다. 그 단일 사건이 군살 없는 포인트 투 포인트 네트워크를 운영하며 얻은 수년치의 효율성 이득을 지워버렸다. 봉쇄된 수에즈 운하는 세계 경제에 하루에 수십억 달러의 비용을 발생시킨다. 꼬리 위험 — 이제 매년 일어나는 것처럼 보이는 파국적인 "10년에 한 번"의 사건 — 은 더 이상 위험 대장의 각주가 아니다. 10년의 시야에서 보면, 그것은 지배적인 비용 동인이다.

우리 에이전트는 더 똑똑한 완충 관리와 승무원 초과 근무 감축을 통해 정상 운영 중에 2-5%의 운영 비용 절감을 제공한다. 그것은 기본 조건이다. 진정한 가치는 일어나지 않는 것에 있다: 지역적 혼란으로 억제되는 붕괴, 동부 해안에 도달하기 전에 방화벽으로 차단되는 연쇄, 결코 현실화되지 않는 10억 달러짜리 한 주.

효율성은 안정된 세상을 위한 전략이다. 우리는 더 이상 안정된 세상에 살지 않는다.

정적 수학의 시대는 끝났다

나는 이 에세이를 덴버 국제공항 바닥에서 자는 조종사로 시작했다. 그는 여전히 사우스웨스트에서 비행하고 있다. 그들은 그 이후로 시스템 업그레이드에 막대한 투자를 했다. 하지만 더 깊은 문제 — 예측 가능한 혼란의 세상을 위해 만들어진 결정론적 솔버에 대한 업계 전반의 의존 — 는 대체로 해결되지 않은 채 남아 있다.

물류 구원자로서의 생성형 AI를 향한 돌진은 레거시 시스템보다 나를 더 걱정시킨다. 적어도 SkySolver를 운영하는 사람들은 그 한계를 알았다. 고장 난 최적화 엔진 위에 LLM 래퍼를 배치하는 사람들은 대개 모른다. 그들은 유창한 텍스트를 보고 그것을 운영적 추론으로 착각한다. 그들은 스케줄을 설명할 수 있는 챗봇을 보고 그것이 스케줄을 복구할 수 있다고 가정한다.

VeriPrajna를 세우면서 나는 이 일에서 가장 어려운 부분은 수학이 아니라 — 논거라는 것을 배웠다. 수십 년간 신뢰해 온 도구들에 구조적 한계가 있다는 것을 업계에 납득시키는 일. 그 반짝이는 새것(생성형 AI)이 잘못된 문제를 겨냥하고 있다는 것. 실제 해결책은 물류를 그래프로, 혼란을 학습 신호로, 회복력을 바라는 무언가가 아니라 — 훈련하는 무언가로 다시 생각하기를 요구한다는 것.

물류의 미래는 알려진 세상을 위한 가장 저렴한 계획을 찾는 시스템에 속하지 않는다. 그것은 알려지지 않은 세상을 위한 생존 가능한 계획을 찾는 시스템에 속한다. 그것은 어쩌면이 아니다. 그것이 우리가 구축하고 있는 것이다.