Scheduling Algorithm for Efficient and Effective Predicted Intercept Points (PIPs) for Multiple Targets
Navy SBIR 2018.1 - Topic N181-055
NAVSEA - Mr. Dean Putnam -
Opens: January 8, 2018 - Closes: February 7, 2018 (8:00 PM ET)


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


TECHNOLOGY AREA(S): Battlespace, Electronics, Sensors

ACQUISITION PROGRAM: Program Executive Office Integrated Warfare System (PEO IWS) 1.0 AEGIS Combat Systems

The technology within this topic is restricted under the International Traffic in Arms Regulation (ITAR), 22 CFR Parts 120-130, which controls the export and import of defense-related material and services, including export of sensitive technical data, or the Export Administration Regulation (EAR), 15 CFR Parts 730-774, which controls dual use items. Offerors must disclose any proposed use of foreign nationals (FNs), their country(ies) of origin, the type of visa or work permit possessed, and the statement of work (SOW) tasks intended for accomplishment by the FN(s) in accordance with section 5.4.c.(8) of the Announcement. Offerors are advised foreign nationals proposed to perform on this topic may be restricted due to the technical data under US Export Control Laws.

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 DUAL USE APPLICATIONS: 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): 154.

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)


These Navy Topics are part of the overall DoD 2018.1 SBIR BAA. The DoD issued its 2018.1 BAA SBIR pre-release on November 29, 2017, which opens to receive proposals on January 8, 2018, and closes February 7, 2018 at 8:00 PM ET.

Between November 29, 2017 and January 7, 2018 you may talk directly with the Topic Authors (TPOC) to ask technical questions about the topics. During these dates, their contact information is listed above. For reasons of competitive fairness, direct communication between proposers and topic authors is not allowed starting January 8, 2018
when DoD begins accepting proposals for this BAA.
However, until January 24, 2018, proposers may still submit written questions about solicitation topics through the DoD's SBIR/STTR Interactive Topic Information System (SITIS), in which the questioner and respondent remain anonymous and all questions and answers are posted electronically for general viewing until the solicitation closes. All proposers are advised to monitor SITIS during the Open BAA period for questions and answers and other significant information relevant to their SBIR/STTR topics of interest.

Topics Search Engine: Visit the DoD Topic Search Tool at to find topics by keyword across all DoD Components participating in this BAA.

Proposal Submission: All SBIR/STTR Proposals must be submitted electronically through the DoD SBIR/STTR Electronic Submission Website, as described in the Proposal Preparation and Submission of Proposal sections of the program Announcement.

Help: If you have general questions about DoD SBIR program, please contact the DoD SBIR Help Desk at 800-348-0787 or via email at