물류·생산·근무표 제약조건 스스로 해결…5종 벤치마크 실행가능해 100% 확보
계획 탐색 2.5배 빨라지고 학습시간 최대 34배 단축…산업 현장 AI 의사결정 기대

택배 배송부터 공장 생산 일정, 병원 근무표까지 현실의 복잡한 조건을 반영해 인공지능(AI)이 스스로 실행 가능한 계획을 만드는 기술이 개발됐습니다.

KAIST 전산학부 김민수 교수 연구팀은 외부 전문 최적화 프로그램(솔버, Solver)의 도움 없이 AI가 현실의 여러 제약조건을 충족하는 계획을 만들도록 학습하는 강화학습 기술 'RL-SPH'를 개발했습니다.

물류 배송이나 차량 경로, 공장 생산 일정, 병원 근무표 등은 여러 조건을 동시에 충족하면서 효율적인 계획을 찾아야 하는 대표적인 정수 선형계획 문제입니다.

택배 배송의 경우 이동 시간을 줄이는 것뿐 아니라 차량 적재량과 기사 근로시간을 지키고 모든 배송지를 빠짐없이 방문해야 실제 계획으로 활용할 수 있습니다.

하지만 기존 AI는 비용이나 시간을 줄인 계획을 만들더라도 적재량이나 근로시간 같은 현실적인 조건을 위반하는 경우가 많았습니다.

이 때문에 최종 단계에서는 'Gurobi'나 'SCIP' 같은 전문 솔버를 이용해 오류를 수정해야 했습니다.

연구팀이 개발한 RL-SPH는 처음부터 완성된 정답을 예측하는 대신 현재 계획을 단계적으로 수정하면서 실행 가능한 답을 찾아가는 방식입니다.

인원과 차량 수, 생산량 등 조정할 수 있는 변수를 하나씩 바꾸면서 제약조건을 해결하고, 그 결과를 학습해 점진적으로 계획의 완성도를 높여 나갑니다.

특히 가장 효율적인 계획을 곧바로 찾기보다 현실에서 실제 사용할 수 있는 계획을 먼저 확보하도록 설계했습니다.

공장 생산계획을 예로 들면 납기일과 설비 용량, 작업 인력 등 필수 조건을 먼저 모두 충족한 뒤 이를 유지하면서 생산비와 시간을 줄여나가는 방식입니다.

이를 위해 모든 제약조건을 만족해 실제 사용할 수 있는 '실행가능해'를 먼저 찾고 이후 비용과 시간을 줄이는 2단계 탐색 전략을 적용했습니다.

연구팀은 변수와 제약조건의 관계를 학습하는 새로운 AI 모델 'ILP-GT'와 문제 해결에 효과적인 변수부터 수정하는 탐색 전략도 적용해 계산 효율을 높였습니다.

대표적인 5종의 벤치마크를 이용해 성능을 평가한 결과, RL-SPH는 모든 문제에서 실행 가능한 계획을 찾는 데 100% 성공했습니다.

최적해와의 차이를 나타내는 '프라이멀 갭'은 기존 기술보다 평균 28.6배 개선됐고, 탐색 과정의 품질과 속도를 평가하는 '프라이멀 인터그럴'도 2.6배 향상됐습니다.

처음으로 실행 가능한 계획을 찾는 데 걸리는 시간은 평균 2.5배 빨라졌습니다.

PAS와 DDIM, DiffILO 등 최신 AI 기술과 비교했을 때도 RL-SPH만 모든 벤치마크에서 실행 가능한 계획을 100% 찾아냈습니다.

학습시간은 평균 30분으로 기존 기술보다 14.7배, 최근 비지도학습(정답을 미리 알려주지 않고 데이터에서 스스로 규칙을 찾는 AI 학습 방식) 기반 기술과 비교해서는 약 34배 빨랐습니다.

국제 최적화 벤치마크인 MIPLIB 평가에서도 기존보다 최대 67배 큰 문제와 학습 과정에서 접하지 않았던 새로운 형태의 문제에서 실행 가능한 계획을 안정적으로 찾아냈습니다.

김민수 교수는 "현실에서는 가장 좋은 답보다 실제로 실행할 수 있는 계획이 더 중요하다"며 "전문 최적화 프로그램의 도움 없이 AI가 스스로 실행 가능한 계획을 만들 수 있음을 보여준 성과"라며 앞으로"물류와 제조, 반도체 생산, 인력 운영 등 다양한 산업 현장에서 AI 기반 의사결정을 구현하는 핵심 기술로 활용될 것"으로 기대했습니다.

KAIST 전산학부 이태훈 박사과정이 제1저자로 참여한 이번 연구 결과는 지난달 열린 세계적 권위의 '국제 기계학습 학회(ICML)'에서 발표됐습니다.