MD Advanced Engagement Planning and Scheduling within a Probabilistic Framefork

This study investigates the use of probabilistic data and probabilistic algorithms in the engagement planning and scheduling (EPS) function of a ballistic missile defense system's C2BMC. EPS is the part of a ballistic missile defense system battle manager that is responsible for deciding how to use the system's resources to defend assets. The data used by EPS is probabilistic, and is highly dependent on the current conditions and uncertainties. By making full use of probabilistic data, EPS can effectively plan engagements against threats that would otherwise leak through, and can plan engagements with higher probability of kill using fewer shots. However, the EPS problem is an NP-hard optimization problem. Recently, randomized approximation algorithms have been used to provide near-optimal solutions to NP-hard problems, with arbitrarily high probability, in polynomial time. Such a probabilistic algorithm for the EPS problem may provide near-optimal EPS solutions in real time. Phase I of the study identified the main issues of the EPS problem, developed a mathematical characterization and a mathematical solution approach, and produced a preliminary algorithmic architecture. The issues involve the uncertainties, actions, constraints, objectives, and heuristics for the EPS problem. The mathematical characterization is in terms of a partially observed Markov decision process, with continuous time and mixed discrete-continuous state space whose objective is to plan and schedule engagements against threat clusters in order to maximize the expected utility of surviving asset value. The mathematical solution approach uses approximate dynamic programming. The transition probabilities up to the time horizon are computed from real-time probabilistic battlespace analysis (PBSA) and threat evaluation data. The transition probabilities from the time horizon to the end of the battle are computed in terms of a stochastic game against a worst-case attacker, using an offline-generated leakage probability function. The search through the solution space for the optimal action is a randomized approximation algorithm based on Markov chain Monte Carlo techniques, guided by heuristic policies. Phase II of the study will implement the algorithmic architecture in Matlab and C++, evaluate the algorithms in TechFinity's ballistic missile defense algorithm testbed, and produce a detailed algorithmic architecture. It will use real-time data from TechFinity's PBSA study - a companion MDA SBIR Phase II. The GMD and KEI POs have endorsed our study, and we intend to develop core and generic capabilities in Probabilistic EPS (PEPS) during the Phase II Basic Contract that can be modified and tailored for GMD and KEI specific issues. We propose an additional Option 1 Contract to address some of the key and generic PEPS issues in Midcourse MD, and an Option 2 Contract to address generic PEPS issues in Boost Phase MD, avoiding specific design issues of GMD and KEI. Our objective is to develop detailed algorithms and tools in a spiral, evolutionary manner for potential insertion into BMDS block upgrades and for use in other domains, focusing on missile/air defense applications in Phase II. We intend to extend our approach to non-DoD government applications and to private sector commercial markets in Phase III.