Introduction
In multi-agent systems, such as swarms of autonomous drones or robotic teams constructing lunar habitats, coordination is traditionally managed by a centralized leader. This leader is responsible for extracting a plan from a set of possibilities, verifying temporal consistency, and dispatching tasks. However, this centralized approach is inherently brittle. The leader agent often becomes a communication bottleneck and a single point of failure. If the leader's communication link fails or its processor becomes overwhelmed, the entire mission may stall.
Furthermore, real-world plans are rarely static; they are often "contingent" (containing multiple decision points) and "temporally flexible" (tasks have valid time windows rather than fixed start times). Managing these complexities centrally does not scale effectively as the number of agents or the complexity of the mission grows.
Temporal Plan Networks (TPNs)
To address these challenges, the authors utilize Temporal Plan Networks (TPNs). A TPN is a graphical representation of a plan that incorporates both choice and temporal constraints. It allows for the specification of complex behaviors through several fundamental constructs.
As shown in the figure above, TPNs are composed of:
- Activities: Tasks with associated time bounds $[l, u]$.
- Sequences: Tasks that must occur one after another.
- Parallelism: Tasks that can be executed simultaneously.
- Choices: Decision points where one of several paths must be selected.
The D-Kirk Algorithm
The paper introduces Distributed-Kirk (D-Kirk), a distributed algorithm designed to extract and verify plans from TPNs by spreading the computational and communication load across a hierarchy of autonomous agents. The process follows three primary stages:
- TPN Distribution: The system organizes agents into a hierarchical "ad-hoc" network using a leader election algorithm. The TPN is then mapped onto this hierarchy, where each agent becomes responsible for a specific sub-portion of the overall plan.
- Distributed Candidate Generation: Instead of a single agent searching for a valid path through the plan's choices, agents perform a parallel, recursive, depth-first search. They coordinate choices across the hierarchy using a specialized messaging protocol (
findfirst,findnext,ack,fail). - Distributed Consistency Checking: Once a candidate plan is selected, agents must ensure the timing is feasible. D-Kirk employs a distributed Bellman-Ford algorithm to detect "negative weight cycles" in the timing graph. A key innovation is interleaving: agents check sub-plans locally and only propagate results up the hierarchy if the local components are consistent, significantly reducing global overhead.
Key Insights and Results
The transition from centralized to distributed planning yields several critical advantages:
- Structure-Mapping: The hierarchical structure of a complex plan (Mission → Task → Sub-task) naturally maps to the hierarchical network of agents. This allows for "local knowledge" planning, where agents only interact with their immediate supervisors or subordinates.
- Linear Scaling: Empirical evaluations using randomly generated plans (ranging from 1 to 100 nodes) demonstrate that the communication cycles required to find a plan scale roughly linearly with the number of nodes. This is a substantial improvement over the exponential worst-case complexity typical of centralized search problems.
- Robustness: By distributing the "thinking" process, the system becomes less sensitive to individual agent failures or localized communication drops, ensuring more resilient mission execution.
Conclusion and Future Work
D-Kirk effectively eliminates the bottlenecks of centralized planning, enabling robust, real-time coordination in complex environments. Future research directions include optimizing hierarchy formation to be more "plan-aware," integrating real-time execution feedback into the distributed search process, and validating the algorithm on heterogeneous hardware with varying power and processing constraints.
Summary updated