[더테크 이지영 기자] 택배 배송 경로부터 반도체 생산 일정, 병원 근무표까지. 앞으로는 인공지능(AI)이 현실의 다양한 제약조건을 스스로 고려해 실제 실행 가능한 계획을 수립하는 시대가 열릴 전망이다.
KAIST는 전산학부 김민수 교수 연구팀이 외부 최적화 프로그램(솔버·Solver)의 도움 없이도 AI가 스스로 실행 가능한 계획을 생성하는 강화학습 기술 'RL-SPH(Reinforcement Learning-based Start Primal Heuristic)'를 개발했다고 3일 밝혔다.
이번 연구의 핵심은 AI가 비용이 가장 낮은 계획이 아니라 현실에서 바로 실행할 수 있는 계획을 먼저 찾도록 설계했다는 점이다. 연구팀은 이를 통해 물류와 제조, 반도체 생산, 인력 운영 등 다양한 산업 분야에서 활용할 수 있는 AI 기반 의사결정 기술을 구현했다.
현실의 계획 수립은 배송 경로, 생산 일정, 인력 배치처럼 여러 조건을 동시에 만족해야 하는 정수선형계획법(ILP) 문제에 해당한다. 예를 들어 택배 배송은 배송 시간을 최소화하는 것뿐 아니라 차량 적재량과 운전자 근무시간을 지키고 모든 배송지를 빠짐없이 방문해야 한다. 조건 하나라도 충족하지 못하면 실제 운영에는 사용할 수 없다.
기존 AI는 비용을 최소화하는 계획을 제안하더라도 적재량이나 근로시간 같은 현실 제약을 위반하는 경우가 많아 최종적으로 Gurobi나 SCIP 같은 전문 최적화 솔버가 이를 수정해야 했다.
연구팀이 개발한 RL-SPH는 사람이 계획을 수정하듯 현재 계획을 단계적으로 개선하는 방식으로 동작한다. 차량 수나 생산량, 인력 규모 등 변수를 하나씩 조정하면서 제약조건을 만족시키고, 그 결과를 학습해 점차 더 나은 계획을 만들어낸다.
특히 먼저 모든 제약조건을 만족하는 실행 가능한 계획을 찾은 뒤 비용과 시간을 줄여가는 2단계 탐색 전략을 적용했다. 여기에 변수와 제약조건의 관계를 학습하는 AI 모델 'ILP-GT'와 실행 가능성을 높이는 우선 탐색 전략을 결합해 계산 효율도 높였다.
성능 평가 결과는 기존 기술 대비 뚜렷한 개선 효과를 보였다. 연구팀은 대표적인 5개 벤치마크에서 RL-SPH가 모든 문제에 대해 실행 가능한 계획을 100% 도출했다고 밝혔다. 일반 정수 변수가 포함된 복잡한 문제에서도 동일한 성능을 유지했다.
최적해와의 차이를 의미하는 프라이멀 갭(Primal Gap)은 평균 28.6배 개선됐고, 탐색 품질과 속도를 종합적으로 평가하는 프라이멀 인터그럴(Primal Integral)은 2.6배 향상됐다. 처음 실행 가능한 계획을 찾는 시간도 평균 2.5배 단축됐으며, 학습 시간은 평균 30분으로 기존 기술보다 14.7배, 최근 비지도학습 기반 기법보다 약 34배 빠른 성능을 기록했다.
또한 국제 최적화 벤치마크인 MIPLIB에서도 기존보다 최대 67배 큰 문제를 처리했으며, 학습 과정에서 한 번도 경험하지 않은 새로운 유형의 문제에서도 안정적으로 실행 가능한 계획을 생성하는 범용성을 입증했다.
김민수 KAIST 전산학부 교수는 "현실에서는 가장 좋은 답보다 실제로 실행할 수 있는 계획이 더 중요하다"며 "이번 연구는 전문 최적화 프로그램의 도움 없이 AI가 스스로 실행 가능한 계획을 만들 수 있음을 보여준 성과로, 물류와 제조, 반도체 생산, 인력 운영 등 다양한 산업에서 AI 기반 의사결정 기술의 활용 가능성을 높일 것으로 기대한다"고 말했다.
이번 연구는 KAIST 전산학부 이태훈 박사과정이 제1저자로 참여했으며, 김민수 교수가 교신저자를 맡았다. 연구 결과는 지난 7월 열린 세계 최고 권위의 기계학습 국제학술대회 ICML(International Conference on Machine Learning) 2026에서 발표됐다.
