AI 스스로 '실행 가능한' 배송·생산 계획 짠다…KAIST, 새 강화학습 기술 개발

택배 배송 경로는 이동 시간만 줄인다고 되는 게 아니다. 차량에 실을 수 있는 짐의 양과 기사의 근로시간, 빠짐없이 방문해야 하는 배송지까지 한꺼번에 맞아떨어져야 하며, 조건 하나만 어긋나도 그 경로는 현장에서 쓸 수 없다. KAIST 전산학부 김민수 교수 연구팀은 이런 현실의 제약조건을 모두 만족하는 계획을 인공지능(AI)이 외부 프로그램의 도움 없이 스스로 만들어내는 강화학습(시행착오를 반복하며 더 나은 선택을 익히는 AI 학습 방식) 기술 'RL-SPH'를 개발했다고 3일 밝혔다.

물류 배송, 공장 생산 일정, 병원 근무표 작성은 모두 여러 조건을 만족하면서 가장 효율적인 방안을 찾아야 하는 정수선형계획법(ILP, 여러 조건을 만족하는 최적의 계획을 찾는 계산 기법) 문제로 분류된다. 기존 AI는 비용이 적은 계획을 내놓아도 차량 적재량이나 근로시간 같은 현실 조건을 어기기 일쑤여서, 구로비·SCIP 같은 전문 최적화 프로그램(솔버)이 막판에 오류를 다시 손봐야 했다.

사람처럼 계획을 단계적으로 고쳐나가는 방식

연구팀이 개발한 RL-SPH는 처음부터 정답을 예측하는 대신 사람이 계획을 하나씩 고쳐나가듯 현재 계획을 단계적으로 수정하는 방식을 쓴다. 인원 수나 차량 수, 생산량처럼 조정 가능한 변수를 하나씩 바꿔가며 반드시 지켜야 하는 제약조건을 해결하고, 그 결과를 학습해 점점 더 나은 계획을 만들어간다. 가장 좋은 계획보다 실제로 쓸 수 있는 계획을 먼저 찾도록 설계한 것이 특징으로, 모든 조건을 만족하는 계획을 먼저 확보한 뒤 그 상태를 유지하면서 비용과 시간을 줄여나가는 2단계 탐색 전략을 적용했다. 변수와 제약조건의 관계를 학습하는 AI 모델 'ILP-GT'와 문제 해결에 가장 효과적인 변수부터 우선 수정하는 탐색 전략도 함께 적용해 계산 효율을 높였다.

벤치마크 100% 성공…연산 속도도 대폭 단축

연구팀이 대표적인 5종 벤치마크로 평가한 결과 RL-SPH는 모든 문제에서 실행 가능한 계획을 100% 찾아냈으며, 더 복잡한 문제에서도 같은 성능을 유지했다. 기존 기술과 비교하면 최적해와의 차이를 나타내는 '프라이멀 갭'은 평균 28.6배, 탐색 과정 전체의 품질과 속도를 보여주는 '프라이멀 인터그럴'은 2.6배 개선됐고, 처음 실행 가능한 계획을 찾는 시간도 평균 2.5배 빨라졌다. 최신 AI 기술들과 비교한 실험에서도 RL-SPH만이 모든 벤치마크에서 실행 가능한 계획을 100% 찾아냈으며, 학습에 걸리는 시간도 평균 30분으로 기존 기술보다 최대 14.7배 단축됐다. 산업계와 학계가 널리 쓰는 국제 최적화 벤치마크에서도 기존보다 최대 67배 큰 문제와 한 번도 접하지 못한 새로운 유형의 문제에서 안정적으로 계획을 찾아내며 범용성을 입증했다.

김민수 교수는 "현실에서는 가장 좋은 답보다 실제로 실행할 수 있는 계획이 더 중요하다"며 "전문 최적화 프로그램의 도움 없이 AI가 스스로 실행 가능한 계획을 만들 수 있음을 보여준 성과로, 앞으로 물류와 제조, 반도체 생산, 인력 운영 등 다양한 산업 현장에서 AI 기반 의사결정을 구현하는 핵심 기술이 될 것"이라고 말했다. 이번 연구는 KAIST 전산학부 이태훈 박사과정이 제1 저자로 참여했으며, 국제 기계학습 학회(ICML)에서 발표됐다.

자료: KAIST