배송계획·인력배치도 척척…AI가 현실조건 따져 실행계획 짠다

(대전=뉴스1) 김종서 기자 = 택배 배송과 공장 생산계획, 병원 근무표 등 앞으로는 인공지능(AI)이 현실의 모든 조건을 고려해 '실제로 실행 가능한 계획'을 스스로 만드는 시대가 열릴 전망이다.

한국과학기술원(KAIST)은 전산학부 김민수 교수 연구팀이 외부의 전문 최적화 프로그램 없이도 AI가 스스로 실행 가능한 계획을 만들도록 학습하는 강화학습 기술 'RL-SPH'를 개발했다고 3일 밝혔다.

물류 배송과 차량 경로 탐색, 공장 생산 일정, 병원 근무표 작성은 모두 여러 조건을 만족하면서 가장 효율적인 계획을 찾는 대표적인 정수선형계획법(ILP)이 중요하다. 예를 들어 택배 배송은 배송 시간을 줄이는 것뿐 아니라 차량 적재량과 기사 근로시간을 지키고 모든 배송지를 빠짐없이 방문해야 한다. 조건 하나만 어겨도 아무리 빠른 경로라도 실제로 사용할 수 없다.

기존 AI는 비용이 적게 드는 계획을 제안하더라도 차량 적재량이나 근로시간 같은 현실의 조건을 위반하는 경우가 많아 AI만으로는 완전한 해결이 어려웠다.

연구팀이 개발한 RL-SPH는 처음부터 정답을 예측하는 대신 사람이 계획을 하나씩 고쳐 나가듯 현재 계획을 단계적으로 수정한다. 인원 및 차량 수, 생산량 등 변수를 하나씩 바꾸며 반드시 지켜야 하는 제약조건을 해결하고 그 결과를 학습해 점점 더 나은 계획을 만들어간다.

특히 연구팀은 '가장 좋은 계획'보다 '실제로 사용할 수 있는 계획'을 먼저 찾도록 AI를 설계했다. 이를 위해 먼저 모든 제약조건을 만족해 실제 사용할 수 있는 계획을 찾고, 이후 비용과 시간을 줄이는 2단계 탐색 전략을 적용했다.

또 변수와 제약조건의 관계를 학습하는 새로운 AI 모델 'ILP-GT'와, 문제 해결에 가장 효과적인 변수부터 우선 수정하는 실행가능성 인식 탐색 전략을 적용해 계산 효율도 크게 높였다.

연구팀은 대표적인 5종의 벤치마크에서 RL-SPH를 평가한 결과 모든 문제에서 100%의 실행가능한 값을 찾는데 성공했다. 일반 정수 변수가 포함된 더 복잡한 문제에서도 같은 성능을 유지했다.

기존 기술과 비교하면 최적화 차이를 나타내는 프라이멀 갭은 평균 28.6배, 탐색 과정 전체의 품질과 속도를 평가하는 프라이멀 인터그럴은 2.6배 개선됐다. 처음으로 실행 가능한 계획을 찾는 시간도 평균 2.5배 빨라졌다.

최신 AI 기술과 비교한 결과에서도 RL-SPH만이 모든 벤치마크에서 실행 가능한 계획을 100% 찾아냈다. 학습 시간도 평균 30분으로 기존 기술보다 14.7배, 최근 비지도학습 기반 기술보다 약 34배 빨랐다.

특히 산업계와 학계에서 널리 사용하는 국제 최적화 벤치마크 'MIPLIB'에서도 높은 범용성을 입증했다. 기존보다 최대 67배 큰 문제는 물론, 학습 과정에서 한 번도 접하지 못한 새로운 형태의 문제에서도 실행 가능한 계획을 안정적으로 찾아냈다.

김 교수는 "현실에서는 가장 좋은 답보다 실제로 실행할 수 있는 계획이 더 중요하다"며 "물류와 제조, 반도체 생산, 인력 운영 등 다양한 산업 현장에서 AI 기반 의사결정을 구현하는 핵심 기술이 될 것으로 기대한다"고 말했다.

연구팀은 외부 솔버 없이도 최적해에 가까운 해를 스스로 찾는 완전한 독립형 AI 솔버로의 발전을 목표로 더 큰 규모의 문제에도 안정적으로 대응할 수 있는 확장성 향상 연구를 이어갈 계획이다.

KAIST 전산학부 이태훈 박사과정이 제1 저자로 참여한 이번 연구 결과는 기계학습 국제 학술대회 '국제 기계학습 학회(ICML)’에서 발표됐다.

jongseo12@news1.kr