Profiles, Proxies, and Assumptions: Decentralized, Communications-Resilient Planning, Allocation, and Scheduling

Ugur Kuter, Brian Kettler, Katherine Guo, Martin O. Hofmann, Valerie Champagne, Kurt Lachevet, Jennifer Lautenschlager, Robert P. Goldman, Luis Asencios, Josh HamellAAAI 2019 · DOI

This paper, presented at IAAI-19, introduces LAPLATA (Living Air Operations Planning Triggered by Assessment), a decentralized system designed to manage large-scale military air operations even when communications are severely degraded or "denied" (e.g., due to electronic jamming or natural disasters).

TL;DR

LAPLATA enables decentralized command and control by decoupling high-level mission planning from resource allocation. By using "assumption-based" planning and resource "profiles" to estimate peer capabilities, the system maintains operational momentum in communication-starved environments where centralized systems would fail.

The Challenge: Centralized Failure in Denied Environments

In modern military operations, Command and Control (C2) typically relies on a "centralized control, decentralized execution" model. However, this model has a single point of failure: communication. If an adversary jams communications or a disaster destroys infrastructure, forward-operating nodes lose touch with the central authority.

Existing distributed planning systems often struggle with two primary factors:

  1. Scale: Managing thousands of missions per day is computationally expensive.
  2. Uncertainty: Most systems assume a "closed world" where all information is known. In a contested environment, nodes do not know exactly what their peers are doing or what resources they have left.

If nodes wait for communications to be restored, they miss critical windows of opportunity. LAPLATA aims to provide a resilient architecture that allows independent nodes to plan, coordinate, and execute missions with minimal data exchange.

Methods: Decoupling Planning and Allocation

The authors propose a service-oriented architecture where each C2 node contains two primary engines that work in tandem to maintain operations despite connectivity issues.

Figure 1: The LAPLATA decentralized architecture, showing the interaction between planning (APA) and resource allocation (GAO) within a C2 node.

1. APA (Assumption-based Planning and Adaptation)

Based on the SHOP2 Hierarchical Task Network (HTN) planner, APA generates high-level mission plans (e.g., "strike this target").

  • The Innovation: Instead of waiting for perfect data, APA makes "assumptions" about the world and peer actions.
  • Murphy Counter-planning: It uses a tool called "Murphy" to intentionally try to "break" its own plans by simulating potential failures. If an assumption’s confidence drops too low, the system triggers a "discrepancy" and automatically replans the affected sub-tasks.

2. GAO (Global Asset Optimization)

Once a plan is made, GAO handles the "how"—assigning specific aircraft and munitions to tasks.

  • Resource Profiles: To avoid constant back-and-forth messaging, nodes share "profiles"—histograms representing their resource availability over time.
  • Auction-based Allocation: GAO uses these profiles to "bid" on tasks. If a local node cannot fulfill a task, it uses its knowledge of peer profiles to ask the most likely candidate for help, minimizing network traffic.
  • Schedule Negotiation: If a resource is unavailable at the requested time, GAO suggests an alternative window to APA, creating a feedback loop that converges on a viable schedule.

Key Results and Insights

The system was evaluated using realistic air campaign specifications designed by Subject Matter Experts (SMEs) to stress the architecture across 2 to 4 C2 nodes and hundreds of sorties. Bandwidth was throttled from a high-speed 100Mb/s down to a "dial-up" speed of 56kb/s to simulate extreme jamming.

  • Communication Resilience: The system's scheduling success was nearly identical at 100Mb/s and 56kb/s, proving that it requires very little data to function effectively.
  • Negotiation Boosts Success: Without negotiation between the planner and the allocator, success rates were significantly lower due to timing mismatches. Adding just two rounds of "schedule negotiation" drastically improved the percentage of successfully scheduled tasks.
Figure 5: Impact of negotiation rounds on the percentage of tasks successfully scheduled across multiple experimental runs.
  • Scalability: The time required for strike task generation remained nearly constant regardless of the number of nodes, suggesting the architecture can scale to larger operations.

Limitations and Future Work

While LAPLATA successfully handled 250 targets, the authors aim to scale the algorithms to handle 1,000+ tasks per day. Future work will also focus on "Joint Bidding," allowing assets to team up for complex missions, and improving "explainability" to help human commanders understand the reasoning behind decentralized planning choices.

Summary updated

BibTeX
@inproceedings{kuter2019profiles,
  author = {Ugur Kuter and Brian Kettler and Katherine Guo and Martin O. Hofmann and Valerie Champagne and Kurt Lachevet and Jennifer Lautenschlager and Robert P. Goldman and Luis Asencios and Josh Hamell},
  title = {{Profiles, Proxies, and Assumptions: Decentralized, Communications-Resilient Planning, Allocation, and Scheduling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019504},
}
Figure