Fast Re-routing Using Machine Learning
Abstract
Abstract: Fast re-routing using machine learning Approved for Public ReleaseTra,ffic engineering (TE) problems have traditionally been solved by methods from classicaloptimization, including integer linear progra,mming (ILP). Although the solution quality is good, someproblem instances take multiple seconds to compute. Navy network planners wo,uld like solutions tosome of these problems, specifically re-routing problems, computed in less than 1 second. Furthermore,future pr,oblem instances are expected to be much larger; network planners would like to keep TErunning times low, possibly growing linearly o,r better with problem size.This proposal develops a new approach to re-routing solutions to traffic engineering problems. Our ideain, the proposed work is to learn heuristics to solve an entire class of problem instances using a neuralmodel and cached solutions. We, accomplish this goal with a mix of machine learning and traditionaloptimization methods. ML-based heuristics have potential running, time that scale linearly with problemsize, as compared to traditional methods that have at least quadratic time [2]. In particular,, we plan tocombine innovations in graph neural networks with efficient reinforcement learning to develop fastsolutions that can lear,n from a library of previous problems.Our goal is to deliver new algorithms that provide TE solutions 3-10x faster than current stat,e-of-the-artmethods. Faster solutions will enable software controlled networks to respond quickly to changesinherent in tactical sit,uations to provide accurate and timely information to units, warfighting groups,and fleets.Our team includes researchers from Boeing, Research & Technology and Stanford University. Withexpertise in optimization and machine learning, and significant experience both,on the practical andtheoretical aspects of routing problems, we believe we have the best R&D team to tackle this problem.The propose,d effort directly supports the Navy?s Information Warfare vision by developingcomputational technology that directly enhances end-to,-end connectivity and quality-of-service formission-critical information exchange.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Oct 06, 2022
- Source ID
- N000142212825
Entities
People
- Madeleine Udell
Organizations
- Office of Naval Research
- Stanford University
- United States Navy