A Decision-Theoretic Planner with Dynamic Compound Reconfiguration for Distributed Real-Time Applications

John S. Kinnebrew, Nishanth Shankaran, Gautam Biswas, Douglas C. SchmidtAAAI 2006

Introduction

Large-scale Distributed Real-Time and Embedded (DRE) systems, such as NASA’s proposed "sensor webs," represent a significant challenge in modern autonomous systems. These networks involve hundreds of interconnected sensors and satellites that must coordinate dynamically to achieve complex mission goals, such as tracking environmental phenomena or managing disaster response. This paper introduces a hybrid architecture designed to manage these systems by combining a novel "anytime" planner, known as the Spreading Activation Partial Order Planner (SA-POP), with a robust resource management framework called the Resource Allocation and Control Engine (RACE).

Problem Statement

Managing DRE systems is notoriously difficult due to two primary factors: environmental uncertainty and combinatorial complexity. Mission priorities and environmental conditions change constantly, requiring the system to adapt in real-time. Furthermore, the task of determining the optimal sequence of actions while simultaneously assigning those actions to specific hardware nodes creates a "combinatorial explosion" that traditional AI planners struggle to resolve. Conventional approaches often attempt to solve high-level task planning and low-level hardware scheduling concurrently, leading to computational bottlenecks that are unacceptable in real-time environments.

Methodology

The authors propose a "separation of concerns" strategy, decoupling the logical planning from the physical resource allocation. This is achieved through two integrated components:

SA-POP: The Decision-Theoretic Planner

SA-POP serves as the high-level "brain" of the system. It utilizes a spreading activation network where utility (the importance of a goal) propagates backward from objectives, and probability (the likelihood of success) propagates forward from preconditions. By calculating the expected utility of various tasks, the planner can prioritize actions effectively.

Key features of SA-POP include:

  • Anytime Algorithm: SA-POP is designed to be interruptible, meaning it can provide the best-found plan at any moment. This is critical for real-time systems that cannot wait for an exhaustive search to complete.
  • Operational Strings: The output of SA-POP is an "operational string"—a high-level blueprint detailing tasks, their dependencies, and specific timing requirements without being bogged down by hardware-specific details.

RACE: The Resource Allocation and Control Engine

RACE acts as the system's "manager." It receives the operational string from SA-POP and handles the deployment of software components onto specific hardware nodes. RACE is responsible for monitoring performance and maintaining Quality of Service (QoS). If a node fails or resources become overtaxed, RACE can attempt local remediation or signal SA-POP to trigger a "plan repair," creating a dynamic feedback loop between the physical and logical layers.

Key Insights

  • Decoupling Logic and Physicality: By separating the logic of the plan (SA-POP) from the physical allocation (RACE), the search space for both algorithms remains manageable. SA-POP ensures a task is feasible, while RACE ensures it is executed efficiently.
  • Mathematical Grounding: The use of spreading activation allows the system to balance mission value against the probability of success in a mathematically rigorous way.
  • Heuristic-Driven Scheduling: SA-POP employs domain-specific heuristics for DRE environments, such as prioritizing data flow conditions. This allows the system to detect potential resource violations, like data bottlenecks, early in the planning phase.

Results and Discussion

The primary contribution of this work is architectural. The authors demonstrate that a hierarchical approach yields a scalable architecture capable of handling planning and allocation problems that are otherwise computationally intractable. The "anytime" nature of the planner ensures that the system remains responsive, providing a viable plan even under tight temporal constraints.

While the paper establishes a strong conceptual framework, it notes certain limitations. At the time of publication, the full integration of SA-POP’s planning with RACE’s control algorithms was ongoing. Additionally, the paper focuses on architectural logic rather than empirical benchmarking; future work is required to provide quantitative data regarding latency and success rates in live deployments.

Conclusion

The integration of SA-POP and RACE provides a promising path forward for the management of complex, distributed real-time systems. By utilizing a decision-theoretic approach and a decoupled architecture, the system can adapt to high levels of uncertainty while maintaining operational efficiency. Future research will focus on refining the feedback mechanisms between the middleware and the planner to ensure rapid plan repair in high-stakes environments.

Summary updated

BibTeX
@inproceedings{kinnebrew2006decision,
  author = {John S. Kinnebrew and Nishanth Shankaran and Gautam Biswas and Douglas C. Schmidt},
  title = {{A Decision-Theoretic Planner with Dynamic Compound Reconfiguration for Distributed Real-Time Applications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure