SBIR-STTR Award

Courses of action (COA) for United States Air Force operations have traditionally been developed by a team of expert planners, based on their combined experiences and proven rules of thumb. While today’s manual COA creation processes were successful for counter-insurgency missions in Afghanistan and Iraq, they cannot scale to support tomorrow’s complex and Joint operations against near-peer adversaries. In this STTR, Caliola Engineering and the University of Southern California (USC) will jointly develop a theoretically well-founded framework for modeling and solving hierarchical heterogeneous planning and scheduling problems. Our technical approach builds on iterative message passing algorithms (MPA), which generalize Judea Pearl’s belief propagation algorithm to graphical models with cycles. Our technical approach is inspired by a flurry of recent results on the use of message passing algorithms to approximate solutions to combinatorial optimization problems. In Phase I, we will draw on results from the information theory literature to develop formal methods for connecting MPA-based solutions to constituent sub-problems into a comprehensive architecture for solving complex planning and scheduling problems. In Phase II, we will demonstrate our framework as part of a software tool that automates Air Tasking Order (ATO) development from a Master Air Attack Plan (MAAP).

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.