You are here

Scheduling Algorithm for Efficient and Effective Predicted Intercept Points (PIPs) for Multiple Targets


OBJECTIVE: Develop a scheduling software algorithm that instantaneously and accurately predicts intercept points (PIPs) between an interceptor and a target for multiple simultaneous and/or staggered threats. 

DESCRIPTION: The AEGIS Combat System (ACS) utilizes the PIP of the interceptor to the target to determine weapons engagement sequencing and scheduling of ACS functions. A PIP is the intersection of two moving or one stationary object by an interceptor(s). Evolving threats, and the prolific manner in which they are used, necessitate the calculation of multiple PIPs to: (1) maintain the highest probability of elimination of a single threat and (2) successfully eliminate multiple threats. Hundreds of data sets comprise a single PIP and the calculation of a PIP requires the use of hundreds of thousands of algorithmic calculations. A scheduling software algorithm is needed that can instantaneously predict numerous simultaneous intercept points to improve scheduling performance of AEGIS Weapons Systems (AWS). Inputs to the scheduling software include data from track managers, weapons, and missile systems. The scheduling algorithm must reliably provide ACS resourcing recommendations utilizing PIPs that account for variations in the type of threats, the number of threats, operational and test environments, and environmental and engagement debris. A solution must not increase any combat system processing time to achieve its primary objective. It will integrate with all elements of the ACS in order to collect the maximum amount of data sets to include in PIP determination, including track managers, weapons, and missile systems. It will also be able to integrate with the Combat System Test Bed (CSTB) using Real-time JAVA programming language to facilitate system evaluation against more advanced and prolific threats. This will enable shortening of testing and certification timelines for new AEGIS baselines as compared to current timelines. This will also help in maintaining or improving product quality through the early detection of deficiencies in the product. The speed and accuracy of the solution must exceed existing ACS performance attributes resonant in the CSTB. The scheduling software algorithm developed under this effort will provide an enhanced capability to address targets in raiding or swarming configurations and provide optimal engagement options to the Sailor. This will increase mission capability and effectiveness against the latest threats. Because of the planned implementation in both operational and testing environments, the software will permit realistic testing of interceptor versus evolving threat types and configurations in a dynamic test environment. The modeling and simulation will provide initial physics-based weapon system testing in an environment that does not require the expenditure of ordnance; thereby reducing test complexities and costs associated with fielding new ACS baselines. The Phase II effort will likely require secure access, and NAVSEA will process the DD254 to support the contractor for personnel and facility certification for secure access. The Phase I effort will not require access to classified information. If need be, data of the same level of complexity as secured data will be provided to support Phase I work. Work produced in Phase II may become classified. Note: The prospective contractor(s) must be U.S. Owned and Operated with no Foreign Influence as defined by DOD 5220.22-M, National Industrial Security Program Operating Manual, unless acceptable mitigating procedures can and have been implemented and approved by the Defense Security Service (DSS). The selected contractor and/or subcontractor must be able to acquire and maintain a secret level facility and Personnel Security Clearances, in order to perform on advanced phases of this contract as set forth by DSS and NAVSEA in order to gain access to classified information pertaining to the national defense of the United States and its allies; this will be an inherent requirement. The selected company will be required to safeguard classified material IAW DoD 5220.22-M during the advance phases of this contract. 

PHASE I: Develop a concept for a scheduling algorithm for PIPs that must show it will feasibly support the operational and test environments identified in the description. Feasibility will be established through comparative evaluation and integration capability into the CSTB environment. The Phase I Option, if awarded, will include the initial design specifications and capabilities description to build a prototype in Phase II. Develop a Phase II plan. 

PHASE II: Based upon the results of Phase I and the Phase II Statement of Work (SOW), develop, deliver, and implement a prototype scheduling algorithm for PIPs into an existing Government-approved modeling and simulation environment such as the AEGIS test bed to validate performance. The prototype must be capable of demonstrating the implementation and integration of the engagement model as described in the description. Prepare a Phase III development plan to transition the technology for Navy use and Program of Record It is probable that the work under this effort will be classified under Phase II (see Description section for details). 

PHASE III: Support PEO IWS 1.0 in transitioning the prototype PIP algorithm to AEGIS use in the baseline testing modernization process. The effort will consist of integrating into a baseline definition, incorporation of the baselines existing and new threat capabilities, validation testing, and combat system certification. 


1: Younas, I. and Aqeel, A. "A Genetic Algorithm for Mid-Air Target Interception." International Journal of Computer Applications (0975 – 8887) Volume 14– No.1, January 2011.

2:  Bentley, J. L. and Ottmann, T. A. "Algorithms for reporting and counting geometric intersections." IEEE Transactions on Computers, 1979.

3:  Chazelle, Bernard and Edelsbrunner, Herbert. "An optimal algorithm for intersecting line segments in the plane." Journal of the ACM, 39 (1): 1–54.

KEYWORDS: Scheduling Software Algorithm; Weapons Engagement Sequencing; Predictive Intercept Points; Predict Numerous Simultaneous Intercept Points; Swarm And Raid Tactics; Scheduling Performance Of AEGIS Combat Systems (ACS) 


Bob Rumbaugh 

(202) 781-4932 

Bryan Metts 

(540) 653-1769 

US Flag An Official Website of the United States Government