A technology has been developed that allows AI to create plans that can be executed in the real world on its own, without help from external specialist optimisation programmes.

The Korea Advanced Institute of Science and Technology (KAIST) said on Sunday that a research team led by School of Computing professor Minsoo Kim (김민수) developed a reinforcement-learning technique, RL-SPH, that trains AI to create plans that meet real-world constraints.

KAIST said logistics delivery, vehicle route planning, factory production scheduling and hospital shift rostering are integer linear programming (ILP) problems that require finding efficient plans while meeting multiple conditions. Parcel delivery also cannot be used in the field if vehicle load limits and drivers' working hours are not met.

Existing AI technology sometimes violated real-world conditions such as vehicle load limits or working hours even when it proposed plans that reduced costs or time, KAIST said. This meant specialist optimisation programmes had to correct the plans generated by AI.

RL-SPH works by progressively modifying the current plan rather than predicting the correct answer from the outset. The AI was designed to find a usable plan first, rather than immediately seeking the optimal plan.

It applies a two-stage search strategy that first finds a feasible solution that satisfies all constraints and then reduces costs and time while maintaining those conditions. The team also applied an AI model called ILP-GT that learns relationships between variables and constraints, along with a search strategy that prioritises modifying variables that are effective for solving the problem.

The team evaluated RL-SPH on five types of benchmarks and succeeded in finding feasible plans for all problems. It recorded a 100 percent success rate in finding feasible solutions even in complex problems that included general integer variables.

Compared with existing technologies, the "primal gap," which indicates the difference from the optimal solution, improved by an average of 28.6 times. The "primal integral," which assesses the quality and speed of the search process, improved by 2.6 times. The time to find the first feasible plan was 2.5 times faster on average.

In comparisons with the latest AI technologies including PAS, DDIM and DiffILO, only RL-SPH found feasible plans in all benchmarks with a 100 percent rate. Average training time was 30 minutes, 14.7 times faster than existing technologies and about 34 times faster than methods based on unsupervised learning.

In evaluations on the international optimisation benchmark MIPLIB, it found feasible plans in problems up to 67 times larger than before and in new types of problems it had not encountered during training.

Kim said, "In the real world, a plan that can actually be executed is more important than the best answer," adding, "We expect it will become a core technology for implementing AI-based decision-making in a variety of industrial fields such as logistics and manufacturing, semiconductor production and workforce operations."

The research involved School of Computing doctoral student Taehoon Lee (이태훈) as first author, while Kim served as corresponding author. The results were presented at the International Conference on Machine Learning (ICML) held in July.