Safe POMDP Online Planning among Dynamic Agents via Adaptive Conformal Prediction
Shili Sheng Pian Yu David Parker Marta Kwiatkowska Lu Feng

Highly Squeezed States in Ring Resonators:

Beyond the Undepleted Pump Approximation
    J. E. Sipe
    April 29, 2024
====================================================================================







Online planning for partially observable Markov decision processes (POMDPs) provides efficient techniques for robot decision-making under uncertainty. However, existing methods fall short of preventing safety violations in dynamic environments. This work presents a novel safe POMDP online planning approach that offers probabilistic safety guarantees amidst environments populated by multiple dynamic agents. Our approach utilizes data-driven trajectory prediction models of dynamic agents and applies Adaptive Conformal Prediction (ACP) for assessing the uncertainties in these predictions. Leveraging the obtained ACP-based trajectory predictions, our approach constructs safety shields on-the-fly to prevent unsafe actions within POMDP online planning. Through experimental evaluation in various dynamic environments using real-world pedestrian trajectory data, the proposed approach has been shown to effectively maintain probabilistic safety guarantees while accommodating up to hundreds of dynamic agents.




§ INTRODUCTION
  


The partially observable Markov decision process (POMDP) framework is a general model for robot decision-making under uncertainty <cit.>, which finds application in various robotic tasks, such as autonomous driving <cit.> and human-robot collaboration <cit.>. 
Significant progress in POMDP online planning, which interleaves policy computation and execution, has been made to overcome computational challenges. 
For instance, the widely adopted Partially Observable Monte Carlo Planning (POMCP) algorithm <cit.> enhances scalability through Monte Carlo sampling and simulation.

For many safety-critical robotic applications, computing POMDP policies that satisfy safety requirements is crucial. 
Existing methods for safe POMDP online planning often represent safety requirements as cost or chance constraints, aiming to maximize expected returns while reducing cumulative costs or failure probabilities <cit.>. 
However, these methods cannot guarantee complete prevention of safety violations.
In our previous work <cit.>, we integrated POMCP with safety shields to ensure that, with probability one, goal states are reached and unsafe states are avoided. 
But these shielding methods are limited to static obstacles and fall short in dynamic environments.

To tackle this limitation, in this work we investigate safe POMDP online planning for a robotic agent travelling among multiple unknown dynamic agents, such as pedestrians or other robots. 
We consider a safety constraint, which specifies that the minimum distance from the robotic agent to any of the dynamic agents should exceed a predefined safety buffer. 
The goal is to develop a safe POMDP online planning method that computes an optimal policy maximizing the expected return while ensuring that the probability of satisfying the safety constraint exceeds a certain threshold.

This work addresses several key challenges. 
The first is the modeling of dynamic agents. We use data-driven trajectory models to predict the movements of these agents and apply Adaptive Conformal Prediction (ACP) to assess the uncertainties in these predictions, as per <cit.>.
The second challenge involves the construction of safety shields that avert collisions with dynamic agents. 
To this end, we propose a novel algorithm that dynamically constructs safety shields to accommodate the ACP-estimated regions of dynamic agents.
The third challenge is integrating safety shields into POMDP online planning. 
We enhance the POMCP algorithm with safety shields by evaluating the safety of each action during the Monte Carlo sampling and simulation process.


To the best of our knowledge, this is the first safe POMDP online planning approach that offers probabilistic safety guarantees in environments with dynamic agents.
We evaluate the proposed approach through computational experiments in various dynamic environments, utilizing real-world pedestrian trajectory data.







 §.§ Related Work
  
Safe POMDP online planning
Prior studies have explored different methods for incorporating safety constraints into online planning with POMDPs.
Online algorithms for constrained POMDPs apply cost (or chance) constraints to limit expected cumulative costs (or failure probability); however, they do not guarantee the avoidance of constraint violations <cit.>. 
An online method introduced in <cit.> synthesizes a partial conditional plan for POMDPs with a focus on safe reachability, aiming for specific probability thresholds to reach goals or avoid static obstacles.
Additionally, a rule-based shielding method presented in <cit.> generates shields by learning parameters for expert-defined rule sets. 
In our previous work <cit.>, we devised shields to preemptively prevent actions that could breach almost-sure reach-avoid specifications and incorporated these shields into the POMCP algorithm to ensure safe online planning for POMDPs. 
However, these methods primarily focus on circumventing static obstacles and are not directly applicable to safe planning in dynamic environments. 




Planning among dynamic agents
Substantial research has been conducted in the field of robotic planning involving dynamic agents, such as pedestrians. 
Some works treat these dynamic agents as static obstacles, adapting to changes through online replanning <cit.>. 
Other approaches make simple assumptions about the dynamics of these agents; for example, they may assume that pedestrians move at a constant velocity <cit.>. 
There are also more sophisticated methods that model the intentions of dynamic agents. 
For instance, PORCA <cit.> is a POMDP-based planning method that accounts for complex models of pedestrians' intentions and interactions.
Additionally, data-driven trajectory predictors have seen extensive use in existing works (e.g., <cit.>).
However, numerous data-driven prediction techniques, such as Long Short-Term Memory (LSTM), often lack mechanisms to convey uncertainty in their predictions, potentially resulting in decisions that compromise safety.
In this work, we adopt LSTM-based trajectory predictors and enhance them by incorporating uncertainty estimation through conformal prediction.



Planning with conformal prediction
Conformal prediction offers techniques for estimating statistically rigorous uncertainty sets for predictive models, such as neural networks, without making assumptions about the underlying distributions or models <cit.>. Adaptive Conformal Prediction (ACP) extends these techniques to estimate prediction regions for time series data <cit.>. Recently, there has been a surge in integrating conformal prediction, including its adaptive variant, into planning frameworks to accommodate the uncertainty in predicted trajectories. For example, Model Predictive Control (MPC) based methods have been developed for safe planning in dynamic environments, which incorporate (adaptive) conformal prediction regions of the predicted trajectories of dynamic agents as constraints within the MPC framework <cit.>.

Furthermore, conformal prediction has been applied to quantify the uncertainty in trajectory predictions derived from diffusion dynamics models, aiding in planning and offline reinforcement learning applications <cit.>. Additionally, a hierarchical conformal natural language planning approach has been proposed to tackle motion planning challenges for mobile robots, particularly for tasks with temporal and logical constraints <cit.>. In the realm of large language models, conformal prediction has been leveraged to provide statistical guarantees on the completion of robot tasks, enhancing the reliability of language model-based planners <cit.>.

In this work, we adopt the ACP-based trajectory predictor proposed in <cit.> and develop a safe POMDP online planning method that constructs shields on-the-fly incorporating ACP regions of dynamic agents.








§ PROBLEM FORMULATION
  



POMDP model
We model the dynamics of a robotic agent as a POMDP, denoted as a tuple =(S, A, O, T, R, Z, γ),
where S, A and O are (finite) sets of states, actions, and observations, respectively;
T: S × A × S → [0,1] is the probabilistic transition function;
R: S × A → is the reward function;
Z: S × A × O → [0,1] is the observation function; 
and γ∈ [0,1] is the discount factor.
At each timestep t, the state s_t ∈ S transitions to a successor state s_t+1∈ S with probability T(s_t, a_t, s_t+1) = (s_t+1| s_t,a_t) given an agent's action a_t ∈ A; the agent receives a reward R(s_t, a_t), and makes an observation o_t+1∈ O about state s_t+1 with probability Z(s_t+1, a_t, o_t+1)=(o_t+1| s_t+1, a_t). 

Given the partial observability of POMDP states, the agent maintains a history of actions and observations, denoted by h_t=a_0, o_1, …, a_t-1, o_t.
A belief state represents the posterior probability distribution over states conditioned on the history, denoted by b_t(s) = (s_t=s | h_t) for s ∈ S. 
Let b_0 denote the initial belief state, representing a distribution over the POMDP's initial states. 
Let B denote the set of belief states of POMDP . 
The belief support of a belief state b ∈ B is defined as (b) := { s  ∈ S | b(s) > 0 }, which is a set of states with positive belief.

The set of belief supports of POMDP  is defined as S_B:={Θ⊆ S |∀ s, s' ∈Θ, (s) = (s')}, 
where : S → 2^O is a function representing the set of possible observations for a state. 



A POMDP policy, denoted by π: B → A, is a mapping from belief states to actions. 
At timestep t, executing a policy π involves selecting an action a_t = π(b_t) based on the current belief state b_t, and subsequently updating to belief state b_t+1 after observing o_t+1 according to Bayes' rule:

    b_t+1(s')=Z(s', a_t, o_t+1) ∑_s ∈ S T(s, a_t, s')b_t(s)/η(o_t+1| b,a)

where η(o_t+1| b,a) is a normalizing constant representing the prior probability of observing o_t+1.


Let R(b_t, a_t):= ∑_s ∈ S R(s,a_t)b_t(s) denote the expected immediate reward of taking action a_t in belief state b_t. 
The expected return from following policy π starting at initial belief state b_0 is defined as:

    V^π(b_0) := 𝔼_π [∑_t=0^∞γ^t R(b_t, π(b_t))  |  b_0].





Dynamic agents
Consider a robotic agent operating in an environment with N dynamic agents whose trajectories are a priori unknown. 
Let X_t := (X_t,1, …, X_t,N) denote the joint agent state at timestep t, where X_t,i represents the state of the i-th dynamic agent. 
Assume the agents' trajectories adhere to an unknown distribution .
Let X := (X_0, X_1, …) ∼ be a random trajectory sampled from this distribution.
We represent the safety constraint, which requires the minimum distance from the robotic agent to any of the N dynamic agents to exceed a safety buffer ϵ∈ℝ^+, through the following Lipschitz continuous constraint function:

    c(s_t, X_t) := min_i ∈{1,…, N}s_t - X_t,i - ϵ.


Given a belief state b_t of the POMDP , we compute the probability of b_t satisfying the safety constraint by summing over the probabilities b_t(s) for all states s ∈(b_t) that meet the condition c(s, X_t) ≥ 0, denoted as:

    ρ(b_t, X_t) := ∑_s ∈(b_t) b_t(s) ·_{c(s, X_t) ≥ 0}.


We define the expected average probability of satisfying the safety constraint across all potential POMDP executions initiated from the initial belief state b_0 under a policy π as:

    ϕ^π(b_0) := 𝔼_π [lim_T→∞1/T∑_t=0^T-1ρ(b_t, X_t)  |  b_0, X_t ∼].



Problem
Given a POMDP model  for a robotic agent with initial belief state b_0, unknown random trajectories X ∼ of N dynamic agents, and a failure rate δ∈ (0,1), the objective is to compute an optimal POMDP policy π^* that maximizes the expected return V^π(b_0) while ensuring that the expected average probability of satisfying the safety constraint is at least 1-δ, denoted by ϕ^π(b_0) ≥ 1 - δ.




§ PRELIMINARIES
  
To tackle the problem under consideration, we propose a safe online planning approach for POMDPs that accounts for the uncertainty of dynamic agents' predicted trajectories. The key idea is as follows. Initially, we convert the probabilistic safety constraint concerning dynamic agents, i.e., ϕ^π(b_0) ≥ 1 - δ, into an equivalent almost-sure safety constraint. This conversion is facilitated through Adaptive Conformal Prediction (ACP), a technique capable of adaptively quantifying the uncertainty of trajectory predictors and generating prediction regions with predefined probability thresholds. Subsequently, safety shields are constructed
to accommodate the previously computed prediction regions of the dynamic agents, and they are integrated into the Partially Observable Monte Carlo Planning (POMCP) algorithm for online planning. 

We now present the essential preliminaries on ACP for trajectory prediction in sec:acp, and the POMCP algorithm for online planning in sec:pomcp.





 §.§ ACP-based Trajectory Prediction
 

Assume there exists a trajectory predictor capable of making predictions about the future trajectories of dynamic agents for a finite horizon H based on their past trajectories. Though our proposed approach is agnostic to the prediction method, we employ an LSTM model as the trajectory predictor in this work and make no additional assumptions about the trajectory distribution 𝒟. 
To consider the uncertainty of predicted trajectories, which could influence the satisfaction of safety constraints, we compute ACP regions using the method described in <cit.>.

Let (X̂_t^1, …, X̂_t^H) represent the predicted trajectory of dynamic agents' future states starting at timestep t and extending to the prediction horizon H, 
where X̂_t^τ:= (X̂_t,1^τ, …, X̂_t,N^τ) is the predicted joint state of N agents made at timestep t for horizon τ∈{1, …, H}. 
However, we cannot evaluate the prediction error for future states since the ground truths (X_t + 1,…, X_t + H) are unknown at timestep t.
We adopt the concept of time-lagged nonconformity score as defined in <cit.>, which quantifies the τ step-ahead prediction error made τ timesteps ago, denoted by β_t^τ:= X_t - X̂_t - τ^τ.

For each prediction horizon τ∈{1, …, H}, we calculate an ACP region β_t^τ≤ C_t^τ based on (β_t-K^τ, …, β_t-1^τ) with a sliding window of size K, ensuring (β_t^τ≤ C_t^τ) ≥ 1-δ, where δ∈ (0,1) denotes a failure probability. The value of C_t^τ is determined by identifying the ⌈(K+1)(1-λ^τ_t)⌉^th smallest value among (β_t-K^τ,…,β_t-1^τ), with the parameter λ^τ_t updated recursively as follows:

    λ_t^τ:= λ_t-1^τ + α(δ - _{C_t-1^τ < β_t-1^τ})

where α∈ (0,1) is the learning rate and λ_0^1∈ (0,1) is a constant for the initial value. 







Consider a robot navigating in a gridworld with one dynamic agent (a pedestrian) as shown in fig:example. 
Let ⟨ x,y⟩ denote a two-dimensional position in the gridworld. 
At timestep t, the dynamic agent's (joint) state is X_t=(⟨ 16.702, 9.726 ⟩).
A trajectory predictor with the prediction horizon H=2 yields one-step and two-step ahead predictions as 
X̂_t^1=(⟨ 17.334, 9.711 ⟩) and X̂_t^2=(⟨17.947, 9.743⟩), respectively.
We compute the time-lagged nonconformity score β_t^1 = X_t-X̂_t-1^1=0.068,
where X̂_t-1^1 = (⟨ 16.650, 9.682 ⟩) is the prediction about state X_t made one timestep ago at t-1. 

Next we compute the ACP region C_t+1^1 to ensure (β_t+1^1≤ C_t+1^1) ≥ 1-δ such that 
the prediction error β_t+1^1 = X_t+1-X̂_t^1 is bounded with the failure probability δ = 0.05. 
Let the size of sliding window be K=30 and the learning rate α=0.0008.
Suppose C_t^1 = 0.736 and λ_t^1=0.0495. 
We have λ_t+1^1 = λ_t^1 + α(δ - _{C_t^1 < β_t^1}) = 0.04954.
We determine the value of C_t+1^1 by finding the ⌈(K+1)(1-λ^1_t+1)⌉^th, which is the 30^th smallest value among (β_t-29^1,…,β_t^1). This process yields C_t+1^1=0.736. 
Similarly, the ACP region to bound the prediction error β_t+2^2 = X_t+2-X̂_t^2 is computed as C_t+2^2=1.329. 

The obtained ACP regions are plotted as red circles in fig:example, centered at X̂_t^1 and X̂_t^2, with radii C_t+1^1 and C_t+2^2, respectively.





 §.§ Partially Observable Monte-Carlo Planning
 

We employ the Partially Observable Monte Carlo Planning (POMCP) algorithm <cit.>, a popular method for POMDP online planning that interleaves the policy computation and execution. 
Each timestep t starts with the POMCP algorithm deploying Monte Carlo tree search <cit.> to navigate a search tree. The root node of this tree is (h_t)=⟨(h_t), (h_t), (h_t)⟩. Here, (h_t) counts how often the history h_t has been visited, (h_t) calculates the expected return from all simulations starting at h_t, and (h_t) contains particles representing POMDP states that estimate the belief state b_t. The algorithm iterates through four main steps:

(1) Selection: A state s is selected at random from the particle set (h_t).
(2) Expansion: Upon reaching a leaf node (h), it introduces new child nodes for every action a ∈ A, expressed as (ha)= ⟨_𝑖𝑛𝑖𝑡(ha), _𝑖𝑛𝑖𝑡(ha), ∅⟩.
(3) Simulation: If (h) is a non-leaf node, an action a is selected to maximize (ha) + c √(log(h)/(ha)) using the upper confidence bound (UCB) to balance exploration and exploitation. In leaf nodes, a is selected based on a predefined rollout policy like uniform random selection. Then, the next state s' is simulated using a black-box simulator (s',o,r) ∼(s,a) and added to (hao). This process runs until reaching a predetermined depth.
(4) Backpropagation: After simulation, the search tree nodes are updated with new data from the path.

The planning phase at timestep t concludes once a target number of these iterations has occurred or a time limit is reached. The agent then takes the best action a_t = _a(h_ta), receives a new observation o_t+1, and proceeds to the next step, constructing a search tree from the new root node (h_ta_to_t+1).
POMCP is effective because it mitigates the curse of dimensionality through state sampling and the curse of history via history sampling with a black-box simulator.  




§ APPROACH
  


We develop a novel approach that constructs safety shields on-the-fly using ACP-based trajectory predictions for dynamic agents, and shields unsafe actions in POMDP online planning. We first define safety shields in sec:shield, present an algorithm for on-the-fly shield construction in sec:construct, describe the shielding method for safe online planning in sec:safe-pomcp, and analyze the correctness and complexity of the proposed approach in sec:correct.






 §.§ ACP-induced Safety Shield
 

Given a τ-step ahead prediction X̂_t^τ made at timestep t for the dynamic agents' future state, and its corresponding ACP region C_t+τ^τ computed as per sec:acp, we define the safety constraint using the Lipschitz continuous function described in eqn:safety as follows:

    c(s_t+τ, X̂_t^τ) ≥ L · C_t+τ^τ

where L>0 is the Lipschitz constant and τ∈{1, …, H} with the prediction horizon H. 

Denote by F_t^τ := {s ∈ S | c(s, X̂_t^τ) < L · C_t+τ^τ} the τ-step ahead prediction region of X̂_t^τ made at timestep t. It follows from <cit.> that Pr(X_t+τ∈ F_t^τ ) ≥ 1-δ, ∀τ∈{1, …, H}, where X_t+τ is the true state of the dynamic agents at timestep t+τ. By ensuring that the prediction regions {F_t^τ}_τ∈{1, …, H} are avoided almost-surely (i.e., with probability 1) at every timestep t, it becomes possible to achieve the desired probabilistic safety guarantee, i.e.,  ϕ^π(b_0) ≥ 1 - δ, with regards to the dynamic agents.


We have X̂_t^1=(⟨ 17.334, 9.711 ⟩) and C_t^1 = 0.736 from eg:acp.
Let the Lipschitz constant be L=1 and the safety buffer ϵ=2.
Suppose the robot's actual state at timestep t+1 is s_t+1=(18,4). 
We have c(s_t+1, X̂_t^1) = s_t+1 - X̂_t^1 - ϵ = 3.7497 ≥ C_t^1.
Thus, the safety constraint is satisfied. 



In <cit.>, it was demonstrated that, for enforcing almost-sure safety specifications, belief probabilities are irrelevant and only the belief support is important. Inspired by this observation, we define a winning belief support and winning regions for a given horizon h, which are used for shielding unsafe actions during online planning.

We say that a POMDP policy π is winning from belief state b_t for a finite horizon h ≤  H iff every state in the belief supports (b_t+j) for j ∈{0, …, h} of all possible executions under the policy π satisfies the safety constraint of eqn:safety-acp.

A belief state b ∈ B is considered winning for a horizon h if there exists an h-step horizon winning policy π originating from b, and the belief support, denoted as (b), is termed a winning belief support for the horizon h. 
A set of belief supports, denoted by W ⊆ S_B, is termed a winning region for an h-step horizon if every belief support Θ∈ W is winning for the horizon h. 
In the special case when h=0, we say that W is a winning region with a zero-step horizon iff all states belonging to each belief support (b) ∈ W satisfy the safety constraint of eqn:safety-acp.


To enforce safety, we can define a safety shield, denoted by ξ: Θ→ 2^A, which restricts actions to those leading solely to successor belief supports within the winning region W. 





 §.§ Computing Winning Regions for Shields
 





We present alg:wr for computing a set of winning regions, denoted by {W_t^τ}_τ=1^H, to construct safety shields on-the-fly at timestep t, where each winning region W_t^τ has a winning horizon of H-τ.


First, given a winning belief state b_t, we compute the set of belief supports of the POMDP  that are reachable within H steps, denoted by S_B^b_t,H⊆ S_B. 

Next, we construct the reachable fragment of a belief-support transition system (BSTS) for the POMDP , 
denoted by a tuple _B^b_t,H = {S_B^b_t,H× Q, s̅_B^b_t, H, A, T_B^b_t, H}, 
where the state space is the product of S_B^b_t,H and a time counter Q = {0,1,…,H},
the initial state is s̅_B^b_t, H = ⟨(b_t),0 ⟩,
the set of actions A are the same as in the POMDP ,
and the transition function is given by 
T_B^b_t, H(⟨Θ,q ⟩, a) = ⟨Θ',q+1 ⟩ if  
Θ' ∈{⋃_s∈Θ{s' ∈ S | T(s,a,s')>0  and  o ∈(s')}| o ∈ O }. The transition function T_B^b_t, H is constructed as follows. Given a belief support Θ∈ S_B^b_t,H, a timestep q∈ Q, and an action a, our initial step involves calculating the set of all potential successor states from Θ and a. This is accomplished by determining the set of all possible successor states from each state s∈Θ and then taking the union of these sets. 
Following that, we reorganize these states into a set of belief supports based on the principle that   states within a belief support share the same observation. Finally, the timestep is increased by 1.
Let (⟨Θ, q ⟩, a) := {Θ' | T_B^b_t, H(⟨Θ,q ⟩, a) = ⟨Θ',q+1 ⟩} denote the set of all possible successor belief supports.

Given a set of dynamic agents' predicted states {X̂_t^τ}_τ=1^H and ACP regions {C_t+τ^τ}_τ=1^H, we compute all possible POMDP states where the safety constraint could be violated, denoted as 
F_t^τ := {s ∈ S | c(s, X̂_t^τ) < L · C_t+τ^τ}.
The set of unsafe states in the BSTS _B^b_t,H is defined as 
Ψ_t := {⟨Θ, q ⟩∈ S_B^b_t,H× Q |∃ s ∈Θ such that  s ∈ F_t^q}.

We compute a set of winning regions {W_t^τ}_τ=1^H recursively in a backward manner.
Let W_t^H be the set of reachable belief supports Θ∈ S_B^b_t, H, excluding those that result in unsafe states where ⟨Θ, H ⟩∈Ψ_t.
Starting from τ=H-1, we add a reachable belief support Θ∈ S_B^b_t, H to the winning region W_t^τ only if both of the following two conditions hold:
(C1) ⟨Θ, τ⟩ does not belong to the unsafe set Ψ_t;
and (C2) there exists an action a ∈ A that leads solely to winning successor belief supports (⟨Θ, τ⟩, a) ⊆ W_t^τ+1 from Θ in the BSTS _B^b_t,H.


Following previous examples, we compute the set of unsafe POMDP states for a one-step prediction at timestep t as 
F_t^1 = {s ∈ S | c(s, X̂_t^1) < C_t+1^1}. 
These states are represented as the yellow shadow in fig:example. 
Similarly, for a two-step prediction at timestep t, we compute the set of unsafe states as 
F_t^2 = {s ∈ S | c(s, X̂_t^2) < C_t+2^2}. 
The winning region W_t^2 is identified as the set of belief supports S_B^b_t, 2 that can be reached from b_t within two steps, while excluding those that contain any unsafe states from F_t^2.
We say that W_t^2 has a zero-step winning horizon, because we do not evaluate the safety of actions leading to states beyond the prediction horizon H=2. 
The one-step horizon winning region W_t^1 is identified as the set of reachable belief supports that do not contain unsafe states from F_t^1 and can lead solely to successor belief supports in W_t^2.





 §.§ Safe Online Planning via Shielding
  

alg:shield illustrates the proposed safe POMDP online planning approach. 
At each planning step t, it first predicts dynamic agents' trajectories {X̂_t^τ}_τ=1^H and computes ACP regions {C_t+τ^τ}_τ=1^H as described in sec:acp.
Then, alg:wr is applied to compute a set of winning regions {W_t^τ}_τ=1^H for the safety shield. 

In Line 5, the procedure 𝗌𝗁𝗂𝖾𝗅𝖽𝖯𝖮𝖬𝖢𝖯 is called, integrating shields with the POMCP algorithm (see sec:pomcp), which navigates a search tree whose root node is (h_t). 
During the simulation phase of the POMCP algorithm, when an action a ∈ A is selected (either by the UCB rule or during rollout) for the history h_t+τ-1, with τ∈{1, …, H}, and a black-box simulator generates (s',o,r) ∼(s,a), the procedure checks if the particle set (h_t+τ-1ao) ∪{s'} belongs to the winning region W_t^τ. 
If the resulting particle set is not a winning belief support, the branch of the tree starting from node (h_t+τ-1a) is pruned, effectively shielding action a at node (h_t+τ-1).
If the simulation depth exceeds H, no shield is applied to actions selected for any history beyond h_t+H. 

When the POMCP planning concludes at timestep t, the best action a_t is selected from the set of allowed actions at node (h_t) as the one that achieves the maximum value of (h_ta).
We set the policy π^* with π^*(b_t)=a_t. 
The agent executes a_t, receives an observation o_t+1 and updates the belief state b_t+1 for the next step. 










At timestep t, consider a state s= ⟨ 17,5 ⟩ sampled from the particle set (h_t) at the root node (h_t). During the POMCP simulation, suppose action a=east is chosen for history h_t, and a black-box simulator yields (s',o,r) ∼(s,a) with s' = ⟨ 18,5 ⟩. We then check if (h_tao) ∪{s'} falls within the winning region W_t^1; it does, so the simulation process advances with action a' for history h_tao. Assuming a'=north leads to (s”,o',r') ∼(s',a') with s” = ⟨ 18,7 ⟩, an unsafe state in F_t^2, the updated particle set (h_taoa'o') ∪{s”} falls outside of W_t^2. Therefore, action north is shielded at node (h_tao).








 §.§ Correctness and Complexity
 

Correctness
The correctness of alg:wr is stated in lem:wr and the correctness of alg:shield, with respect to the problem statement in sec:problem, is stated in thm:main. The proofs are given in the appendix. 


The output of alg:wr, denoted by {W_t^τ}_τ=1^H, comprises a set of winning regions, with each W_t^τ representing a winning region for an (H-τ)-step horizon.



Given a POMDP model  for a robotic agent with initial belief state b_0, the unknown random trajectories X∼ of N dynamic agents with a prediction horizon H, and a failure probability δ∈ (0,1), the policy π^* computed by alg:shield achieves the maximal expected return V^π^*(b_0) while ensuring safety, i.e., ϕ^π^*(b_0) ≥ 1 - δ. 



Complexity
There are several components in the complexity analysis of the proposed approach in alg:shield. 
The complexity of predicting dynamic agents' trajectories depends on the underlying prediction model. 
The complexity of computing ACP regions at timestep t is Ø(H· N· K ·log(K)), depending on the prediction horizon H, the number of agents N, and the sliding window size K.
The complexity of alg:wr for computing winning regions to construct shields is bounded by Ø(H · |S_B^b_t,H| · |A|), which depends on the prediction horizon H, the number of H-step reachable belief supports S_B^b_t,H from belief state b_t, and the size of the action set A. 
The overhead of adding shielding to POMCP, specifically checking against safety shields, is bounded by Ø((|A|·|O|)^H) per simulation. 
In practice, the overhead is negligible, as demonstrated by the experimental results in the next section.







§ EXPERIMENTS
  





We implemented the proposed approach and evaluated it through various computational experiments.
All experiments were run on a MacBook Pro machine with 10-core 3.2 GHz Apple M1 processor and 16 GB of memory. 

Environments
We consider three gridworld environments, where the movements of N dynamic agents follow real-world pedestrians trajectories derived from benchmark datasets <cit.>. Specifically, we utilize three datasets: ETH, Hotel, and GC, for which example scenes are illustrated in fig:datasets.
In each gridworld environment, the robot aims to reach a target destination while avoiding pedestrians. The robot can move east, south, west, or north, reaching the adjacent cell with probability 0.1 or one cell further with probability 0.9. The robot has partial observability of the environment due to noisy sensors, such that every four neighboring grid cells in a 2×2 block share the same observation. The reward function is defined as: 1,000 for reaching the destination, -1 per step, and -10 per collision. 

Hyperparameters
Each pedestrian trajectory dataset is split into training, validation, and test sets in a ratio of 16:4:5. 
LSTM models with 64 hidden units are trained for the trajectory prediction with a prediction horizon H=3. 
We set the failure probability δ=0.05 and the safety buffer to be ϵ=0.5 grid. 
The ACP regions are computed with a learning rate α=0.0008.
The POMCP algorithm is set with the following hyperparameters: the number of simulations is 4,096; the simulation depth is 200; and the number of particles sampled from the initial state distribution is 10,000. 

Results
We compare the performance of the proposed approach for safe online planning via ACP-induced shields with two baselines: (i) No Shield, i.e., POMCP without shielding; and (ii) Shielding without ACP, i.e., POMCP with shields that do not account for ACP regions, by modifying the safety constraint in eqn:safety-acp to c(s_t+τ, X̂_t^τ) ≥ 0.

tab:exp shows the results averaging over 100 runs of each method for different environments with varying number N of dynamic agents. 
Across all cases, the proposed approach achieves a better safety rate (i.e., measured by the percentage of time satisfying the safety constraint during a run) than the baselines.
All three methods result in comparable travel times for the robot to reach the destination in the ETH and Hotel environments, while shielding approaches lead to longer travel times when the robot needs to avoid a significantly higher number of pedestrians in the GC environment.
tab:exp also reports the mean and standard deviation of the minimum distance between the robot and pedestrians; the proposed approach is more conservative than the baselines, maintaining a larger minimum distance for safety.

Finally, we observed that shielding does not significantly add to the runtime of online planning. The average computation time for each planning step of POMCP without shields is 0.28 seconds, compared to 0.35 seconds for the proposed approach, incurring an additional 0.07 seconds for constructing winning regions and shielding actions per step.



§ CONCLUSION
  
This work developed a novel shielding approach aimed at ensuring safe POMDP online planning in dynamic environments with multiple unknown dynamic agents. We proposed to leverage ACP for predicting the future trajectories of these dynamic agents. Subsequently, safety shields are computed based on the prediction regions. Finally, we integrated these safety shields into the POMCP algorithm to enable safe POMDP online planning. Experimental results conducted on three benchmark domains, each with varying numbers of dynamic agents, demonstrated that the proposed approach successfully met the safety requirements while adhering to a predefined failure rate.

For future work, we will assess the effectiveness of the proposed approach across diverse POMDP domains and deploy it in real-world robotic tasks. Another important direction is to explore methods for handling continuous POMDPs to enhance scalability and generalization.




IEEEtran


 



The output of alg:wr, denoted by {W_t^τ}_τ=1^H, comprises a set of winning regions, with each W_t^τ representing a winning region for an (H-τ)-step horizon.





We prove the lemma by induction on the increasing horizon of winning regions.

Base case:
By the definition of W_t^H,
for any belief state b_t+H whose belief support (b_t+H) ∈ W_t^H, every state s_t+H∈(b_t+H) satisfies the safety constraint, i.e.,
c(s_t+H, X̂_t^H) ≥ L · C_t+H^H.
Thus, W_t^H is a winning region for zero-step horizon.


Inductive step:
Assume that W_t^τ is the winning region for an (H-τ)-step horizon. By definition, for every belief state b_t+τ whose belief support (b_t+τ) ∈ W_t^τ, there exists an (H-τ)-step horizon winning policy π_t+τ originating from b_t+τ. For every belief state b_t+τ-1 with belief support (b_t+τ-1) ∈ W_t^τ-1, there exists at least one action a_t+τ-1∈ A that leads to a successor belief support state 

    (b_t+τ) ∈(⟨(b_t+τ-1), τ-1 ⟩, a_t+τ-1) ⊆ W_t^τ.

We can augment policy π_t+τ into an (H-τ+1)-step horizon winning policy π_t+τ-1 with π_t+τ-1(b_t+τ-1)=a_t+τ-1. Thus, W_t^τ-1 is the winning region for an (H-τ+1)-step horizon.

Conclusion: By induction, we have proved that alg:wr outputs a set of winning regions {W_t^τ}_τ=1^H, with each W_t^τ having an (H-τ)-step winning horizon.























Given a POMDP model  for a robotic agent with initial belief state b_0, the unknown random trajectories X∼ of N dynamic agents with a prediction horizon H, and a failure probability δ∈ (0,1), the policy π^* computed by alg:shield achieves the maximal expected return V^π^*(b_0) while ensuring safety, i.e., ϕ^π^*(b_0) ≥ 1 - δ. 





Let a_t = π^*(b_t) denote the action selected by the policy π^* at timestep t computed via alg:shield. 
By construction, a_t is a safe action leading solely to successor belief supports within the winning region W_t^1, which, according to lem:wr, has an (H-1)-step winning horizon.
Thus, for each state s_t+1∈(b_t+1), we have 

    c(s_t+1, X̂_t^1) ≥ L · C_t+1^1.

Based on eqn:proof-1 and thanks to Lipschitz continuity of function c, we derive that 

    0    ≤  c(s_t+1, X̂_t^1) - L · C^1_t+1
       ≤ c(s_t+1, X_t+1) + L ·X_t+1 - X̂_t^1 - L · C^1_t+1.

Hence, X_t+1 - X̂_t^1≤ C^1_t+1 is a sufficient condition for c(s_t+1, X_t+1) ≥ 0, that is,

    (c(s_t+1, X_t+1) ≥ 0) | X_t+1 - X̂_t^1 ≤ C_t+1^1) = 1.

Thanks to the law of total probability, we have

    (c(s_t+1, X_t+1) ≥ 0) ≥( X_t+1 - X̂_t^1 ≤ C_t+1^1).
 

With the assistance of Corollary 3 in <cit.>, it can be shown that the ACP regions C_t+1^1 computed as per sec:acp guarantee that

    1/T∑_t=0^T-1( X_t+1 - X̂_t^1 ≤ C_t+1^1) ≥ 1 - δ - p_1

with constant p_1:=λ^1_0 + α/T ·α, where λ^1_0 is the constant initial value in eq:failureupdate and T is the number of times eq:failureupdate is applied. 

Combining eqn1eqn2, we have

    1/T∑_t=0^T-1(c(s_t+1, X_t+1) ≥ 0) ≥ 1 - δ - p_1.


By definition of eqn:prob-safe, we have

    ρ(b_t+1, X_t+1) = ∑_s ∈(b_t+1) b_t+1(s) ·_{c(s, X_t+1) ≥ 0}.

Since eqn3 holds for all s∈ supp(b_t+1), we have

    1/T∑_t=0^T-1ρ(b_t, X_t)
    
    =     1/T∑_t=0^T-1 b_t+1(s) ·(c(s_t+1, X_t+1) ≥ 0)
    ≥    1-δ -p_1.


Since lim_T →∞ p_1=0, we have

    ϕ^π(b_0) = 𝔼_π [lim_T→∞1/T∑_t=0^T-1ρ(b_t, X_t)  |  b_0, X_t ∼] ≥ 1-δ.


Moreover, a_t = π^*(b_t) is selected as the best action that achieves the maximum value of (h_ta), which calculates the expected return from all simulations starting at h_t, among all safe actions enabled at timestep t. 
Thus, given a substantial number of simulations, the expected return V^π^*(b_0) at the initial belief state b_0 is optimal.  

In conclusion, we have proved that the policy π^* computed by alg:shield achieves the maximal expected return V^π^*(b_0) while ensuring safety, i.e., ϕ^π^*(b_0) ≥ 1 - δ. 




