Fast Re-Routing Using Machine Learning
Abstract
Approved for Public ReleaseTraffic engineering (TE) problems have traditionally been solved by methods from classical optimization,,including integer linear programming (ILP). Although the solution quality is good, some problem instances take multiple seconds to c,ompute. Navy network planners would like solutions to some of these problems, specifically re-routing problems, computed in less tha,n 1 second. Furthermore, future problem instances are expected to be much larger; network planners would like to keep TE running tim,es low, possibly growing linearly or better with problem size. This proposal develops a new approach to re-routing solutions to traf,fic engineering problems. Our idea in the proposed work is to learn heuristics to solve an entire class of problem instances using a, neural model and cached solutions. We accomplish this goal with a mix of machine learning and traditional optimization methods. ML,-based heuristics have potential running time that scale linearly with problem size, as compared to traditional methods that have at, least quadratic time [2]. In particular, we plan to combine innovations in graph neural networks with efficient reinforcement learn,ing to develop fast solutions that can learn from a library of previous problems.Our goal is to deliver new algorithms that provide,TE solutions 3-10x faster than current state-of-the-art methods. Faster solutions will enable software-controlled networks to respon,d quickly to changes inherent in tactical situations to provide accurate and timely information to units, warfighting groups, and fl,eets.Our team includes researchers from Boeing Research & Technology and Cornell University. With expertise in optimization and mach,ine learning, and significant experience both on the practical and theoretical aspects of routing problems, we believe we have the b,est R&D team to tackle this problem. The proposed effort directly supports the Navys Information Warfare vision by developing compu,tational technologythat directly enhances end-to-end connectivity and quality-of-service for mission-critical information exchange.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 08, 2022
- Source ID
- N000142212152
Entities
People
- Madeleine Udell
Organizations
- Cornell University
- Office of Naval Research
- United States Navy