KAIST, 외부 프로그램 없이 ‘실행 가능한 계획’ 짜는 AI…물류·생산 자동화

외부의 전문 최적화 프로그램에 기대지 않고, AI가 현실의 여러 조건을 모두 만족하는 ‘실행 가능한 계획’을 스스로 만들어내는 기술이 개발됐다.

KAIST 전산학부 김민수 교수 연구팀은 이런 기능을 강화학습으로 구현한 기술 ‘RL-SPH’를 개발했다고 3일 밝혔다. 강화학습은 시행착오를 반복하며 더 나은 선택을 배우는 AI 학습 방식이다. 택배 배송 경로, 공장 생산 일정, 병원 근무표는 모두 여러 조건을 지키면서 가장 효율적인 답을 찾아야 하는 문제인데, 지금까지 AI는 비용이 적은 계획을 제안하더라도 차량 적재량이나 근로시간 같은 현실의 제약을 어기는 경우가 많았다. 그래서 마지막에는 결국 ‘솔버(solver)’라 불리는 전문 최적화 프로그램이 오류를 바로잡아야 했고, AI만으로는 완전한 해결이 어려웠다.

이번 기술이 주목받는 이유는 이 의존 관계를 끊어냈다는 데 있다. AI가 스스로 모든 조건을 만족하는 계획을 만들어내면서도, 실험한 모든 문제에서 실제로 쓸 수 있는 답을 100% 찾아냈다. 연구팀에 따르면 이는 외부 솔버의 도움 없이 AI가 스스로 고품질의 실행 가능한 답을 만들어낸 첫 사례다. 이번 연구는 이태훈 박사과정생이 제1저자로 참여했으며, 세계 최고 권위의 기계학습 학회인 국제 기계학습 학회(ICML)에서 발표됐다.

‘빠른 계획’이 아니라 ‘지킬 수 있는 계획’

물류 배송, 차량 경로 탐색, 공장 생산 일정, 병원 근무표 작성은 겉보기엔 서로 다른 일 같지만, 계산 방식으로 보면 모두 같은 종류의 문제다. 여러 조건을 만족하면서 가장 효율적인 답을 찾아야 하는 ‘정수선형계획법(ILP)’ 문제다. 조정 가능한 값(변수)이 정수 단위로 정해지고, 반드시 지켜야 할 조건(제약조건)이 여럿 붙는 형태를 말한다.

핵심은 조건 하나만 어겨도 그 계획은 무용지물이 된다는 점이다. 택배 배송을 예로 들면, 단순히 배송 시간을 줄이는 것만이 목표가 아니다. 차량 적재량을 넘기지 않아야 하고, 기사의 근로시간을 지켜야 하며, 모든 배송지를 빠짐없이 방문해야 한다. 아무리 빠른 경로를 짜도 이 중 하나라도 위반하면 현실에서는 쓸 수 없다.

이 문제가 어려운 근본적인 이유는 규모가 커질수록 따져봐야 할 경우의 수가 폭발적으로 늘어난다는 데 있다. 변수가 조금만 많아져도 가능한 조합이 천문학적으로 증가해, 모든 경우를 다 계산해 최적의 답을 찾는 것이 현실적으로 불가능해진다. 그래서 실무에서는 완벽한 최적해를 구하기보다, 조건을 만족하는 ‘쓸 만한 답’을 빠르게 찾는 방식이 널리 쓰여 왔다.

기존 AI 방식의 한계가 바로 이 지점에 있었다. 최근에는 신경망으로 답을 직접 예측하는 기술이 여럿 나왔지만, 예측한 답의 일부만 내놓고 나머지는 여전히 Gurobi나 SCIP 같은 외부 솔버가 떠맡는 구조였다. 신경망의 예측이 부정확하면 실행 가능성이 확보되지 않는 문제가 반복됐고, 값의 범위가 넓은 정수 변수는 제대로 다루지 못하는 한계도 있었다.

연구팀은 문제의 우선순위를 바꿔서 접근했다. ‘가장 좋은 계획’을 찾기 전에 ‘실제로 사용할 수 있는 계획’을 먼저 찾도록 AI를 설계한 것이다. 김민수 교수는 “현실에서는 가장 좋은 답보다 실제로 실행할 수 있는 계획이 더 중요하다”고 말했다. 최적화의 첫 단추인 ‘실행 가능성 확보’를 AI가 스스로 해내는 것을 목표로 삼은 셈이다.

정답을 맞히기보다 고쳐나간다

RL-SPH의 작동 방식은 사람이 계획을 다듬는 과정과 닮았다. 처음부터 완벽한 정답을 한 번에 예측하는 대신, 현재의 계획을 단계적으로 수정해 나간다. 인원 수나 차량 수, 생산량처럼 조정 가능한 값을 하나씩 바꾸면서 위반된 조건을 해결하고, 그 결과를 학습해 점점 더 나은 계획을 만들어간다. 사람이 일정표를 짤 때 어긋난 부분을 하나씩 고쳐가는 것과 비슷하다.

여기에 ‘2단계 탐색’ 전략을 적용했다. 1단계에서는 납기일, 설비 용량, 작업 인력 등 모든 조건을 만족하는 실행 가능한 계획을 먼저 찾는다. 2단계에서는 그 상태를 유지하면서 생산비와 시간을 줄여 나간다. 먼저 ‘지킬 수 있는 답’을 확보한 뒤 그 안에서 품질을 높이는 순서다. 연구팀은 이 보상 설계 아래에서 잘 학습된 AI가 유한한 탐색 안에 반드시 실행 가능한 답에 도달한다는 것을 수학적으로 증명했다. ‘경험적으로 잘 되더라’에 그치지 않고 ‘왜 되는지’를 이론으로 뒷받침한 것이다.

계산 효율을 높이기 위한 장치도 더했다. 변수와 제약조건 사이의 관계를 학습하는 새로운 AI 모델 ‘ILP-GT’를 설계했고, 문제 해결에 가장 효과적인 변수부터 우선 수정하는 ‘실행 가능성 인식 탐색 전략’을 적용했다. 매 단계에서 전체 변수를 다 보는 대신 위반된 조건에 자주 등장하는 일부 변수만 골라 집중함으로써, 살펴야 할 범위를 크게 줄였다. 시험 준비를 할 때 강조된 부분에 집중하는 것과 같은 방식이다.

성능 검증 결과는 뚜렷했다. 대표적인 5종의 벤치마크(성능 측정 시험)에서 RL-SPH는 모든 문제의 실행 가능한 답을 100% 찾아냈고, 값의 범위가 넓은 정수 변수가 포함된 더 복잡한 문제에서도 같은 성능을 유지했다. 기존 기술과 비교하면 최적해와의 차이를 나타내는 ‘프라이멀 갭’이 평균 28.6배 개선됐고, 처음으로 실행 가능한 계획을 찾는 시간도 평균 2.5배 빨라졌다. 최신 AI 기술들과의 비교에서도 RL-SPH만이 모든 벤치마크에서 실행 가능한 답을 100% 찾아냈으며, 학습 시간은 평균 30분으로 기존 기술보다 14.7배 빨랐다.

범용성과 속도도 확인됐다. 산업계와 학계에서 널리 쓰는 국제 최적화 벤치마크(MIPLIB)에서, 학습에 쓴 것보다 최대 67배 큰 문제는 물론 학습 과정에서 한 번도 접하지 못한 새로운 형태의 문제에서도 안정적으로 답을 찾아냈다. 특히 무작위 초기화 버전은 2초 이내에 첫 실행 가능한 답을 찾아, 실시간에 가까운 의사결정이 필요한 환경에 적합할 것으로 연구팀은 전망했다. 김민수 교수는 “앞으로 물류와 제조, 반도체 생산, 인력 운영 등 다양한 산업 현장에서 AI 기반 의사결정을 구현하는 핵심 기술이 될 것”이라고 말했다. 연구팀은 최종적으로 외부 솔버 없이도 최적해에 가까운 답을 스스로 찾는 완전한 독립형 AI 솔버로 발전시키는 것을 목표로 삼고 있다.