[쿠키과학] ‘AI가 택배 배송·생산·근무표 완성’… KAIST, 현실조건 지키는 계획 AI 개발

인공지능(AI)이 외부 최적화 프로그램의 도움 없이 물류 배송과 생산 일정, 인력 배치에 필요한 조건을 모두 지키는 계획을 스스로 만들 수 있게 됐다.

KAIST 전산학부 김민수 교수팀은 복잡한 계획 문제에서 실제로 실행할 수 있는 답을 찾는 강화학습 기술 ‘RL-SPH’를 개발했다.

연구팀은 5개 최적화 벤치마크에서 RL-SPH를 시험해 모든 문제에서 실행가능한 계획을 찾아 기존 기술보다 최적해와의 차이를 평균 28.6배 줄였고, 학습 속도는 14.7배 높였다.

택배 배송과 공장 생산 일정, 병원 근무표 작성에는 많은 조건이 얽혀 있다.

택배 차량은 적재 한도를 지켜야 하고, 기사는 근로시간을 넘기면 안 되며, 모든 배송지를 방문해야 한다.

정수선형계획법(ILP)은 이처럼 여러 조건을 만족하면서 가장 효율적인 답을 찾는다.

기존 AI는 비용이나 이동 시간을 줄이는 계획을 제시해도 현실의 제약조건을 위반하는 경우가 많았다.

실제 사용하려면 구로비(Gurobi)나 SCIP 같은 전문 최적화 프로그램이 오류를 수정해야 했다.

연구팀은 AI가 처음부터 완성된 답을 예측하는 대신 현재 계획을 단계적으로 고치도록 설계했다.

AI는 차량 수와 생산량, 투입 인원처럼 조정할 수 있는 값을 바꾸며 위반한 조건을 줄인다.

RL-SPH는 먼저 모든 조건을 만족하는 계획을 찾고, 이후 비용과 시간을 줄이는 2단계 전략을 사용한다.

연구팀은 가장 효율적인 답보다 현장에서 사용할 수 있는 계획을 먼저 확보하도록 AI를 학습시켰다.

AI는 변수의 허용 범위를 지키고, 제약조건 위반을 줄인 뒤, 마지막으로 비용이나 시간을 개선한다.

연구팀은 이 보상 체계를 적용한 AI가 제한된 탐색 과정 안에서 실행 가능한 답에 도달한다는 사실을 수학적으로 증명했다.

RL-SPH에는 정수선형계획 문제의 구조를 학습하는 그래프 트랜스포머 ‘ILP-GT’도 적용했다.

ILP-GT는 변수와 제약조건의 연결 관계와 멀리 떨어진 변수 사이의 영향까지 분석한다.

연구팀은 위반한 제약조건과 자주 연결되는 변수부터 선택해 수정하는 탐색 전략도 개발했다.

이 방식은 AI가 확인할 범위를 줄여 학습과 계산 속도를 높인다.

성능 평가에서 RL-SPH는 5개 벤치마크 모두에서 실행 가능한 답을 100% 찾아냈고, 값의 범위가 넓은 일반 정수 변수를 포함한 복잡한 문제에서도 같은 성능을 유지했다.

최적해와 현재 답의 차이를 나타내는 프라이멀 갭은 기존 기술보다 평균 28.6배 줄었다.

탐색 과정의 속도와 답의 품질을 함께 평가하는 프라이멀 인터그럴은 2.6배 개선됐다.

처음으로 실행 가능한 계획을 찾는 시간도 평균 2.5배 빨라졌다.

일부 실험에서는 무작위 상태에서 시작해 2초 안에 첫 실행 가능한 답을 찾았다.

PAS와 DDIM, DiffILO 등 기존 AI 최적화 기술과 비교한 결과에서도 RL-SPH만 모든 문제에서 실행 가능한 답을 100% 도출했다.

학습에는 평균 30분이 걸렸다.

이는 비교 대상 기술보다 14.7배 빠르고, 비지도학습 기반 기술보다 약 34배 빠른 수준이다.

RL-SPH는 학습 과정에서 보지 못한 문제와 학습 데이터보다 최대 67배 큰 문제에서도 실행 가능한 답을 찾아냈다.

이 기술은 택배 차량 경로와 공장 생산관리, 반도체 공정 일정, 병원 근무표, 자원 배분, 통신망 설계 등에 활용할 수 있다.

김 교수는 “현실에서는 가장 좋은 답보다 실제로 실행할 수 있는 계획을 확보하는 일이 우선”이라며 “이번 연구는 AI가 외부 최적화 프로그램 없이 스스로 실행 가능한 계획을 만들 수 있다는 사실을 보여줬다”고 말했다.

이번 연구에는 이태훈 KAIST 전산학부 박사과정이 제1저자로,참여했고, 연구결과는 지난달 열린 국제 기계학습 학회(ICML)에서 발표했다.
(논문명: RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs)

이재형 기자 jh@kukinews.com