TECH FOCUS AREAS: Autonomy; Artificial Intelligence/Machine Learning TECHNOLOGY AREAS: Information Systems OBJECTIVE: The objective of this topic is to explore the development of a theoretical foundation or model for hierarchical heterogeneous planning and scheduling by which we can reason about autonomous/automated decision-making in multiple different domains while accounting for the hierarchical structure of each domain. This topic will reach companies and universities that can complete research of the foregoing concepts in Phase I schedules. This topic is specifically aimed at the earlier stage basic science and research. DESCRIPTION: The current modus operandi for generating courses of action in military operational scenarios is largely human-derived. An increasingly heterogeneous all-domain (e.g., air, land, sea, cyber, space, electronic warfare) battle space and the resulting warfare complexity presents human decision-makers with an overwhelming amount of data and potential plans. Add to this the inherently hierarchical nature of each domain (e.g. for the air domain, there are wings composed of groups, that are composed of squadrons, that are composed of units) and this gives rise to a unique type of planning and scheduling problem. Indeed, this multi-domain hierarchical planning and scheduling would benefit greatly from automated or autonomous approaches which can model the heterogeneity of the various domains, establish a hierarchical decision-making pipeline within each domain, and explore and optimize over many potential plans and schedules in a short span of time. However, we currently have no means by which to formally reason about such hierarchical heterogeneous planning and scheduling settings. The mathematical modeling of various operational problems lend credence to some theoretical foundation and mathematical model by which to accomplish this. Examples include the Maximum-on-Ground (MOG) parking problem of assigning a set of aircraft to various airfields so as to maximize the packing density of the airfields and how this can be formalized as a Bin Packing problem [1]. This bin packing formulation immediately lets us reason about the complexity of the MOG problem, exact solutions, approximate efficient solutions, heuristics, and interesting extensions to the problem. Similarly, we have seen the problem of air asset scheduling for Air Tasking Orders (ATOs) being modeled using integer programming [2]. Drawing inspiration from such approaches, we seek the development of a theoretical foundation or model for hierarchical heterogeneous planning and scheduling by which we can reason about autonomous/ automated decision-making in multiple different domains while accounting for the hierarchical structure of each domain. Success can be evaluated by comparing the proposed model and solution to the baseline of reasoning over each domain separately and by using naive planning approaches. The heterogeneity of the various domains may be formalized by some abstraction that accounts for domain-specific effects, such as range, mobility, impact, latency, etc. The hierarchical nature of the solution may encapsulate the granularity and delegation of desired effects for a given domain. For example, at the wing level, potential enemy targets may be identified; this information is passed down to the group level, where squadrons are assigned to the different targets; this, in turn, is used to determine the routes and schedules of aircraft at the unit level. The underlying environment within which the agent interacts can take many forms, including purely theoretical models such as Markov Decision Processes (MDPs), performer-developed environments and academic tools like OpenAI Gym and PySC2. The developed concepts need not be specific to military operations. PHASE I: Validate the product-market fit between the proposed solution and the proposed topic and define a clear and immediately actionable plan for running a trial with the proposed solution and the proposed AF customer. This feasibility study should directly address: 1. Clearly identify who the prime (and additional) potential AF end user(s) is and articulate how they would use your solution(s) (i.e., the one who is most likely to be an early adopter, first user, and initial transition partner). 2. Deeply explore the problem or benefit area(s), which are to be addressed by the solution(s) - specifically focusing on how this solution will impact the end user of the solution. 3. Define clear objectives and measurable key results for a potential trial of the proposed solution with the identified Air Force end user(s). 4. Clearly identify any additional specific stakeholders beyond the end user(s) who will be critical to the success of any potential trial. This includes, but is not limited to, program offices, contracting offices, finance offices, information security offices and environmental protection offices. 6. Describe if and how the demonstration can be used by other DoD or governmental customers. 7. Describe technology related development that is required to successfully field the solution. The funds obligated on the resulting Phase I awards are to be used for the sole purpose of conducting a thorough feasibility study using mathematical models, scientific experiments, laboratory studies, commercial research and interviews. PHASE II: Develop, install, integrate and demonstrate a prototype system determined to be the most feasible solution during the Phase I feasibility study. This demonstration should focus specifically on: 1. Evaluating the proposed solution against the objectives and measurable key results as defined in the Phase I feasibility study. 2. Describing in detail how the solution can be scaled to be adopted widely (i.e. how can it be modified for scale). 3. A clear transition path for the proposed solution that takes into account input from all affected stakeholders including but not limited to: end users, engineering, sustainment, contracting, finance, legal, and cyber security. 4. Specific details about how the solution can integrate with other current and potential future solutions. 5. How the solution can be sustainable (i.e. supportability). 6. Clearly identify other specific DoD or governmental customers who want to use the solution. PHASE III DUAL USE APPLICATIONS: The Primary goal of STTR is Phase III. The contractor will pursue commercialization of the various technologies developed in Phase II for transitioning expanded mission capability to a broad range of potential government and civilian users and alternate mission applications. Direct access with end users and government customers will be provided with opportunities to receive Phase III awards for providing the government additional research & development, or direct procurement of products and services developed in coordination with the program. PROPOSAL PREPARATION AND EVALUATION: Please follow the Air Force-specific Phase I instructions under the Department of Defense 21.2 SBIR Broad Agency Announcement and Chart 1 (above) when preparing proposals. Proposals under this topic will have a maximum value of $156,500 SBIR funding and a maximum performance period of five months, including four months technical performance and one month for reporting. Proposals will be evaluated using a two-step process. After proposal receipt, an initial evaluation will be conducted IAW the criteria found in the AF-specific Phase I instructions as previously referenced. Based on the results of that evaluation, Selectable companies will be provided an opportunity to participate in the Air Force Trusted AI Pitch Day, tentatively scheduled for 26-30 July 2021 (possibly virtual). Companies' pitches will be evaluated using the initial proposal evaluation criteria. Selectees will be notified after the event via email. Companies must participate in the pitch event to be considered for award. REFERENCES: 1. De La Vega, W. Fernandez, and George S. Lueker. "Bin packing can be solved within 1+ in linear time." Combinatorica 1.4 (1981): 349-355 2. Rossillon, Kevin Joseph. Optimized air asset scheduling within a Joint Aerospace Operations Center (JAOC). Diss. Massachusetts Institute of Technology, 2015 3. Paquay, C lia, Michael Schyns, and Sabine Limbourg. "A mixed integer programming formulation for the three dimensional bin packing problem deriving from an air cargo application." International Transactions in Operational Research 23.1-2 (2016): 187-213 4. Hoehn, John R. Joint All Domain Command and Control (JADC2). Congressional Research SVC Washington United States, 2020
