Message Passing Algorithms for Hierarchical Planning & Scheduling

In this STTR, Caliola and the University of Southern California (USC) are jointly exploring the application of message passing algorithms (MPA) to solve complex combinatorial optimization problems. In Phase I, we demonstrated for the first time that MPA-based solvers for multiple problems can be connected in a comprehensive architecture to solve a hierarchical planning problem that arises in air tasking order production. In the proposed Phase II effort, we plan to fully develop and release an open-source software suite for MPA-based optimization that is tuned to tackle hierarchical planning and scheduling problems that are too complex to be handled by traditional, monolithic solvers such as Google’s OR-Tools. We call our toolkit BP-OPT to emphasize its use of belief propagation. In Phase II, we will also integrate BP-OPT with Caliola’s AssuredConf product to solve an important emerging satellite communications beam assignment and antenna configuration problem. AssuredConf is an automated planning tool that we are developing to support Operation Plan development at the Combatant Commands. A major theme of our proposed work is the cross-pollination of MPA-based techniques from digital receiver design to combinatorial optimization. The Phase II effort will be led by Caliola’s Chief Scientist, Dr. Tom Halford. His doctoral work at USC established fundamental performance versus complexity tradeoffs for MPAs. At Caliola, he leads an interdisciplinary team that is developing planners for the next generation of Navy modems and Air Force weapons data links. The USC team will be led by Prof. Keith Chugg. He has made significant contributions to the development of iterative MPA-based solutions for digital receiver design, both at USC and at TrellisWare, where he is Chief Scientist. Recently, Prof. Chugg has turned his focus to machine learning, leveraging techniques from digital receiver design to accelerate model training.