AI-Enhanced System Solves Complex Planning Problems Faster
MIT researchers have developed a novel artificial intelligence-enhanced planning system that dramatically reduces the time required to solve complex logistical challenges. The system leverages machine learning to streamline algorithmic solvers, achieving up to a 50% reduction in solve time while also improving the quality of solutions.
The innovative approach addresses the challenge of planning movements in complex environments, such as coordinating commuter trains at busy stations. Traditional algorithmic solvers often struggle with the scale of these problems, leading to lengthy computation times and suboptimal outcomes.
“Often, a dedicated team could spend months or even years designing an algorithm to solve just one of these combinatorial problems. Modern deep learning gives us an opportunity to use new advances to help streamline the design of these algorithms. We can take what we know works well, and use AI to accelerate it,” says Cathy Wu, the Thomas D. and Virginia W. Cabot Career Development Associate Professor in Civil and Environmental Engineering (CEE) and the Institute for Data, Systems, and Society (IDSS) at MIT, and a member of the Laboratory for Information and Decision Systems (LIDS).
The core innovation lies in the system’s ability to learn which parts of a problem remain constant across multiple iterations. By freezing these variables, the system avoids redundant computations, allowing the algorithmic solver to focus on the most critical decisions. This approach, dubbed learning-guided rolling horizon optimization (L-RHO), leads to significant efficiency gains.
To train the machine-learning model, the researchers used a classical algorithmic solver to solve a set of subproblems. The best solutions, characterized by minimal recomputation needs, were then used as training data. Once trained, the model can predict which operations should not be recomputed in new, unseen subproblems.
The researchers tested L-RHO against several baseline solvers, including specialized algorithms and machine learning-only approaches. The results demonstrated a 54% reduction in solve time and up to a 21% improvement in solution quality.
Furthermore, L-RHO proved adaptable to various problem variants, such as those involving factory machine breakdowns or train congestion. The system can also automatically generate new algorithms when objectives change, requiring only a new training dataset.
Beyond train scheduling, the researchers envision applications for L-RHO in various logistical domains, including hospital staff scheduling, airline crew assignments, and task allocation in factories.
