Iterative Message Passing for Hierarchical Planning & Scheduling

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).