💻 computer science

Generating Local Shields for Decentralised Partially Observable Markov Decision Processes

This paper introduces a method for generating local safety shields in communication-free Decentralised Partially Observable Markov Decision Processes by compiling a shield process algebra into a global Mealy machine and projecting it onto local belief-based automata, thereby enabling agents to filter unsafe actions without requiring shared global state or memoryless filters.

Original authors: Haoran Yang (University of Oxford), Nobuko Yoshida (University of Oxford)

Published 2026-04-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haoran Yang (University of Oxford), Nobuko Yoshida (University of Oxford)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy intersection where several drivers (agents) are trying to reach their destinations. The problem? They can't talk to each other, and they can't see the whole map—each driver only sees a small circle around their own car. If they all just guess what to do, they might crash into each other or get stuck in a gridlock where no one can move.

This paper introduces a clever solution: Local Shields. Think of these as "smart traffic lights" or "safety coaches" that live inside each driver's car. They don't control the car, but they whisper, "Hey, don't turn left right now, that's dangerous," or "You're good to go forward."

Here is a breakdown of how this works, using simple analogies:

1. The Problem: Blind Drivers in a Fog

In the world of multi-agent systems (like robots or self-driving cars), things get tricky when:

No Communication: The agents can't call each other to say, "I'm turning left!"
Partial Observation: They only see a tiny slice of the world.
The "Joint Action" Trap: Even if Agent A decides to move forward, the result depends on what Agent B does. If Agent B moves sideways at the same time, they might crash. Since Agent A doesn't know what B will do, it's hard to guarantee safety.

Existing safety systems usually require a "God's eye view" (a central computer seeing everything) or very simple rules that don't account for history. This paper says, "We can do better without a central boss."

2. The Solution: The "Shield Process" (The Recipe Book)

The authors created a new language (a "process algebra") to write down a Recipe for Safety.

Imagine writing a story: "First, everyone stays in their starting spots. Then, Agent A moves down while Agent B moves right. Then, they both move forward..."
This story isn't just a plan; it's a Guardian Angel. It defines a sequence of "safe states" that the group must pass through to reach their goal without crashing.

3. The Pipeline: From Story to Action

The paper describes a three-step machine that turns this safety story into a working tool for each agent:

Step 1: The Storybook (Process Automaton)
The computer takes the safety story and turns it into a flowchart. This flowchart tracks where the group should be in the grand scheme of things.
- Analogy: It's like a conductor's score for an orchestra, showing exactly when each instrument should play.
Step 2: The Global Coach (Global Mealy Machine)
The computer builds a "Master Coach" that knows the whole map. It looks at the current state of the world and says, "Okay, based on our safety story, the group can do these specific combinations of moves."
- Analogy: This is the coach standing on a hill seeing the whole field, telling the team, "If you do X and you do Y, we are safe."
Step 3: The Local Whisper (Local Mealy Machines)
This is the magic trick. The Master Coach can't talk to the agents directly because they are blind. So, the computer creates a personalized version of the coach for each agent.
- Since Agent A can only see a small circle, the computer asks: "Given that Agent A sees X, what are all the possible things the rest of the world could be doing?"
- It creates a "belief state" (a guess of the possibilities) and filters the Master Coach's advice.
- Analogy: Imagine Agent A is wearing blinders. The Local Shield looks at what Agent A can see, calculates all the possible scenarios that fit that view, and then says: "In all those possible scenarios, turning left is safe. But turning right might cause a crash in one of them, so I'm blocking it."

4. The Result: Safe and Efficient

The authors tested this with a "Multi-Agent Path Finding" game (robots moving on a grid to reach targets).

Without Shields: The robots crashed constantly or got stuck.
With Old Shields: They were super safe but too cautious. They often just stood still because the rules were too strict.
With This New System:
- Zero Collisions: The robots never crashed.
- High Success: They actually reached their targets much faster than the overly cautious robots.
- Adaptability: The system worked even when the robots had very limited vision (like the "Blind Agents" example where they couldn't see anything but their own cell).

Why This Matters

This is like giving every driver in a foggy city a personal safety coach that knows the traffic laws and the likely behavior of others, without needing a central traffic control tower. It allows complex groups of robots (or software agents) to work together safely, even when they can't talk and can't see the whole picture.

In short: They turned a complex safety rulebook into a set of personalized, real-time "do's and don'ts" for each agent, ensuring they never crash, even in the dark.

1. Problem Statement

The paper addresses the critical safety challenge in Multi-Agent Systems (MAS) operating under Decentralised Partially Observable Markov Decision Processes (Dec-POMDPs).

The Core Issue: In Dec-POMDPs, agents act based solely on local observations without communication or access to a shared global state. Consequently, an individual agent's locally chosen action does not uniquely determine the resulting joint action. This makes it difficult to guarantee safety (e.g., avoiding collisions or deadlocks) because an agent cannot predict the actions of others.
Limitations of Existing Solutions:
- Centralised Assumptions: Many existing shielding techniques assume access to a global state, which is unavailable in communication-free settings.
- Memoryless Filters: Current local filters often lack memory, failing to utilize interaction history to infer the global state.
- Rigidity: Automated synthesis (e.g., from LTL) often results in overly conservative shields that restrict valid actions unnecessarily.
- Information Gap: Standard methods struggle to handle the informational complexity where local views are only fragments of the global state.

2. Methodology

The authors propose a novel pipeline that bridges the gap between high-level global safety specifications and executable local safety filters (shields) without requiring communication.

A. Shield Process Algebra

The authors introduce a process algebra to specify safe global behavior. The syntax includes:

Guarded Choice ( $P_1 \parallel_g P_2$ ): The process behaves as $P_1$ if the current state is in guard set $g$ , otherwise $P_2$ .
Recursion ( $\mu X.P$ ): Allows for infinite behaviors and loops.
State Assertions ($Sh.P$): Asserts that the next state must lie within a safe set $Sh$ before continuing as $P$ .
Termination: idle (success) and fail (failure).

B. The Compilation Pipeline

The core contribution is a three-step compilation pipeline that transforms a high-level process specification into local Mealy machines:

Process Automaton Construction:
The shield process is translated into a deterministic Process Automaton ( $A_P$ ). This automaton tracks the progress of the safety specification (e.g., which safe state sequence is currently being executed).
Global Shield Mealy Machine Synthesis:
A Global Mealy Machine ( $G$ ) is constructed.
- Input: Global Dec-POMDP states ( $S$ ).
- Output: A set of safe joint actions ( $\prod 2^{A_i}$ ).
- Logic: The machine combines the current global state with the current state of the Process Automaton. It computes safe joint actions by intersecting possible transitions with the process constraints. A deterministic decomposition function ($Dec$) maps joint action sets to individual agent action sets.
Local Shield Projection (Belief-State Construction):
Since agents cannot see the global state, the global Mealy machine is projected into Local Mealy Machines ( $L_i$ ) for each agent.
- State Representation: The state of a local machine is a belief set (a subset of global Mealy states) consistent with the agent's current local observation.
- Transition: When an agent observes $o_i$ , the belief set is updated by filtering global states consistent with $o_i$ and simulating transitions.
- Output: The local output is the intersection of the safe action sets of all global states in the current belief set. If the intersection is empty (or leads to fail), the output is $\perp$ (shield failure).

C. Implementation

Language: The pipeline is implemented in Rust.
Verification: Integrated with PRISM (Probabilistic Symbolic Model Checker) to compute best- and worst-case safety probabilities without fixing a specific agent policy.

3. Key Contributions

Shield Process Algebra: A formalism with guarded choice and recursion specifically designed for communication-free, partially observable settings.
Compilation Pipeline: A novel method to synthesize local Mealy shields from global process specifications. It handles partial observability by using belief-state subsets, allowing agents to make safe decisions based on limited information.
Rust Implementation & PRISM Integration: A working toolchain that allows for the analysis of safety probabilities (lower/upper bounds) independent of the agents' learning policies.

4. Case Study and Results

The authors evaluated the pipeline using a Multi-Agent Path Finding (MAPF) problem on grids with varying sizes ( $3\times3$ to $5\times5$ ) and agent counts ( $n=2, 3$ ).

Experimental Setup

Baselines: Unshielded random policies and Q-learning policies.
Shield Variants:
- $P_1$ (Conservative): Keeps agents in safe states but often forces them to stay stationary, leading to low task completion.
- $P_2$ (Optimized): Minimizes action loss by avoiding unnecessary intersections in the branch structure, allowing more movement while maintaining safety.

Key Findings

Safety: Both shielded variants ( $P_1$ and $P_2$ ) achieved 0% collision rates across all configurations, whereas the unshielded baseline had high collision rates (up to 98.6%).
Performance (Reachability):
- $P_2$ significantly outperformed $P_1$ . While $P_1$ was too conservative (often resulting in <10% success rate), $P_2$ allowed agents to reach targets in 90%+ of trials (e.g., 0.929 for $4\times4$ grid, $n=2$ ).
- Observation Radius ( $R$ ): Larger observation radii improved $P_2$ 's performance by enabling more precise belief updates.
Learned Policies: When applied to Q-learning agents:
- Shields enforced zero collisions regardless of the underlying policy.
- Agents trained with $P_2$ achieved the highest success rates, proving that the shield does not hinder learning but rather guides it safely.
- Agents trained with $P_1$ performed poorly, confirming that over-conservative shielding restricts the agent's ability to learn effective paths.

5. Significance

This work provides a rigorous theoretical and practical framework for ensuring safety in decentralised, communication-free multi-agent systems.

Overcoming Partial Observability: It demonstrates that safety can be guaranteed even when agents have no global view, provided a global safety specification exists and is compiled correctly into local belief-based filters.
Expressiveness vs. Conservatism: The process algebra allows for nuanced specifications that are less conservative than standard DFA-based synthesis, striking a better balance between safety and task performance.
Policy Independence: The approach works as a "pre-posed" filter, meaning it can be applied to any underlying policy (random, learned, or hand-crafted) without retraining the agents, making it highly applicable to real-world safety-critical systems.

In conclusion, the paper successfully bridges the gap between formal global safety specifications and decentralized execution, offering a scalable solution to prevent collisions and deadlocks in complex multi-agent environments.