韓国科学技術院（KAIST）は8月3日、キム・ミンス氏（KAIST電算学部教授）の研究チームが、現実の制約条件を満たす計画をAIが自律的に導く強化学習技術「RL-SPH」を開発したと発表した。物流配送や生産計画などの整数線形計画法（ILP）で評価した結果、全ベンチマークで実行可能解を見つけたとしている。

物流配送、車両経路探索、工場の生産スケジュール、病院の勤務表作成といった業務では、複数の制約を守りながら効率的な計画を立てる必要がある。こうした問題はILPとして定式化されることが多い。例えば宅配では、車両の積載量や配達員の労働時間を満たさなければ、計画として成立しない。

KAISTによると、従来のAIはコストや時間の面で優れた計画を提示できても、積載量や労働時間などの制約に違反するケースがあった。このため、AIが出した計画を専門の最適化プログラムで修正する必要があったという。

今回のRL-SPHは、最初から正解を予測するのではなく、現在の計画を段階的に修正していく手法を採用した。最適解を直ちに求めるのではなく、まず現場で実行できる計画を見つけることを優先する設計だ。

具体的には、すべての制約を満たす実行可能解を先に探索し、その条件を維持したままコストと時間を削減する2段階の探索戦略を導入した。あわせて、変数と制約条件の関係を学習するAIモデル「ILP-GT」と、有効な変数から優先的に修正する探索戦略も組み合わせた。

5種類のベンチマークでRL-SPHを評価した結果、すべての問題で実行可能な計画を見つけた。一般整数変数を含む複雑な問題でも、実行可能解の発見率は100%だった。

既存技術と比べると、最適解との差を示すプライマルギャップは平均28.6倍改善した。探索過程の品質と速度を示すプライマルインテグラルは2.6倍改善し、最初の実行可能計画を見つけるまでの時間も平均2.5倍短縮した。

PAS、DDIM、DiffILOなどの最新AI技術と比較しても、全ベンチマークで実行可能な計画を100%見つけたのはRL-SPHだけだった。学習時間は平均30分で、既存技術比で14.7倍、教師なし学習ベースの技術比で約34倍高速だったという。

国際最適化ベンチマークのMIPLIBによる評価では、従来手法より最大67倍大きい問題や、学習時に扱っていない新しい形式の問題でも実行可能な計画を見つけた。

キム氏は「現実では最良の答えよりも、実際に実行できる計画が重要だ」とコメント。「物流、製造、半導体生産、人員運用など多様な産業現場で、AIベースの意思決定を実装する中核技術になることを期待している」と述べた。

この研究には、電算学部のイ・テフン氏（博士課程）が筆頭著者として参加し、キム氏が責任著者を務めた。研究成果は7月に開催された国際機械学習学会（ICML）で発表された。