Safe Explicable Planning

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 20:07:52

Abstract: Human expectations stem from their knowledge about the others and the world. Where human-AI interaction is concerned, such knowledge may be inconsistent with the ground truth, resulting in the AI agent not meeting its expectations and degraded team performance. Explicable planning was previously introduced as a novel planning approach to reconciling human expectations and the agent’s optimal behavior for more interpretable decision-making. One critical issue that remains unaddressed is safety in explicable planning since it can lead to explicable behaviors that are unsafe. We propose Safe Explicable Planning (SEP) to extend the prior work to support the specification of a safety bound. The objective of SEP is to search for behaviors that are close to the human’s expectations while satisfying the bound on the agent’s return, the safety criterion chosen in this work. We show that the problem generalizes the consideration of multiple objectives to multiple models and our formulation introduces a Pareto set. Under such a formulation, we propose a novel exact method that returns the Pareto set of safe explicable policies, a more efficient greedy method that returns one of the Pareto optimal policies, and approximate solutions for them based on the aggregation of states to further scalability. Formal proofs are provided to validate the desired theoretical properties of the exact and greedy methods. We evaluate our methods both in simulation and with physical robot experiments. Results confirm the validity and efficacy of our methods for safe explicable planning.

Main paper: 
 introduction: 
 The capabilities of AI agents have advanced rapidly in recent years, to the extent that they are no longer confined to a space of their own but deployed in environments surrounded by humans. Examples of such agents include Starship's food delivery robots, Amazon's Astro -a household robot, Bear Robotics' hospitality robots, Waymo's autonomous driving cars, and many others. As these agents further develop, they are expected to integrate into our daily lives and become our partners. In such situations, it is required for them to behave as in human-human collaboration where one of the critical aspects is for behaviors to align with others' expectations.Existing work that considers human expectation in decision-making is referred to as explicable planning (Zhang et al. 2017; Kulkarni et al. 2016; Hanni and Zhang 2021) .It is assumed that the humans generate their expectations of an agent's behavior based on their understanding of the agent and the world (M H R ), which may differ from the 45 ground truth (the agent's model or M R ) (see Fig. 1(b) ). In the original formulation, the objective is to search for a plan that maximizes its similarity to the human's expected plan, as measured by a new explicability metric, while simultaneously minimizing a plan cost metric via a linearly 50 weighted sum of the two metrics. To handle stochastic domains, (Gong and Zhang 2022 ) optimizes a similar objective under Markov Decision Process (MDP) in a learning setting. An important limitation of these existing approaches is that they do not bound the suboptimality of the solution 55 under the ground-truth model (i.e., M R ). This is due to the fact that the trade-off between cost and explicability metrics (at different scales) relies on a hyper-parameter, referred to as the reconciliation factor by (Zhang et al. 2017 ). Consequently, generating an explicable behavior may result in 60 over-compromising the cost in the ground-truth model, resulting in unsafe behaviors. 1 Intuitively, a solution to such a problem would be to extend explicable planning by incorporating a bound on the cost in the ground-truth model.Let us further illustrate the need for safe explicable plan-65 ning (SEP) via a motivating scenario. Consider a human user working beside a robot manipulator. The robot is required to hand over a box to the human by placing it at either location 'A' or 'B', as depicted in Fig. 1 (a). Location 'A' is closer to the human but can lead to the robot tipping over a water cup with a small probability. When the cup is empty, the cost from tipping over the cup can be safely ignored. In such a case, the desired behavior would be for the robot to place the box at 'A' to better align with the human's expectation due to its proximity. However, when the cup is nonempty, the desired behavior is to place the box at 'B' to avoid tipping over the cup since it can introduce a hazard of electric shock and a significant cost under the robot's model (M H R ). The difference, however, is so subtle that it may not be obvious from the human's perspective (based on the human's model M H R ). The result could be the robot performing "explicably" to conform with the human's expectation under both cases using explicable planning, leading to a safety risk. In SEP, due to the bound on the cost in the robot's model, the robot would never choose the unsafe behavior.We make the following assumptions in developing our approach to SEP to focus on the planning challenges. First, we assume the agent has access to both M R and M H R as in many prior works on explicable planning (Kulkarni et al. 2016; Hanni and Zhang 2021) and explainable decisionmaking (Chakraborti et al. 2019) , in general. The human's model M H R may be obtained via learning from human feedback (e.g., (Christiano et al. 2017; Ibarz et al. 2018; Holmes et al. 2004; Juba and Stern 2022) ). Second, we assume the human is a rational observer: expectations of the agent are generated by computing the optimal behavior under the human's model (M H R ). It also reduces the maximization of the explicability of a behavior to the maximization of its return under M H R (when modeled as an MDP). The assumption of human rationality is a common simplification in cognitive science (Baker, Saxe, and Tenenbaum 2011) and AI.We formulate SEP under MDPs. First, we define the objective as maximizing the expected return in M H R subject to a constraint on M R specified by the bound δ. This problem formulation generalizes the consideration of multiple objec-105 tives (Marler and Arora 2004) to include multiple domain models. The solution is a Pareto set of policies for which exact solvers are generally intractable. We first develop an action pruning technique that significantly reduces the policy space. Then, we introduce a novel tree search method that efficiently searches through the remaining policies to identify the Pareto set. We formally prove that such a search method is sound and complete. In case any policy from the Pareto set is sufficient, we further introduce a greedy search method. Finally, we create approximate solutions for both search methods via state aggregation to scale them to complex domains. For evaluation, we investigate our methods on several domains in simulation and with physical robot experiments to demonstrate their efficacy for SEP. In addition, we analyze the benefits of our pruning techniques via ablation 120 studies to validate their effectiveness.There has been a growing interest in explainable decisionmaking to develop AI agents whose behaviors are explain-able to humans (Chakraborti et al. 2019; Chakraborti, Sreedharan, and Kambhampati 2020; Fox, Long, and Magazzeni 2017) . We may broadly classify methods in this area into two classes: those that generate behaviors that are more interpretable (implicitly explainable) and those that communicate to explain behaviors (explicitly explainable). Our work belongs to the former. Researchers have approached implicit explainable decision-making from various but related perspectives; generating behaviors that are considered legible (Dragan and Srinivasa 2013) , predictable (Dragan and Srinivasa 2013), transparent (MacNally et al. 2018) , explicable (Zhang et al. 2017) , etc. A review of their relationships is provided by (Chakraborti et al. 2019) . Our work extends explicable planning by addressing an important gap in applying such methods to the real world.Our problem formulation of safe explicable planning (SEP) has close connections to the constrainedcriterion-based formulation in safe reinforcement learning (RL) (Garcıa and Fernández 2015) that inherently models the problem as a Constrained MDP (CMDP) (Altman 2021) . Generally, safety is encoded by constraining the expected cost under some cost function given in addition to the agent's reward function. In our work, we encode safety by directly constraining the expected return under the agent's reward function. We assume that safety is correlated to the expected return in the agent's model under the intuition that unsafe behaviors would result in low returns. Our formulation can easily consider a CMDP problem by aligning the two models and imposing the safety constraint on a separate cost function (i.e., substituting the robot's reward function in the constraint with the cost function).A unique challenge in formulating SEP under CMDP is the presence of two separate MDP models. More specifically, apart from the models having two different reward functions, we consider a slightly general setting that allows the two models to have different domain dynamics and discount factors as well. Such a general setting makes existing solution methods for CMDP inapplicable. For example, consider the linear programming (LP) based solution for CMDP (Altman 1994) . The LP objective is defined by an occupation measure, for different state action pairs, which depends on the transition model and the discount factor. When the models are different, applying the LP solution to SEP would result in a different occupation measure being used in the objective from that used in the constraints and it is not straightforward to solve for these two sets of variables. Similar arguments can be made about the other solution methods.The objective considered in SEP is also related to Multi-Objective Markov Decision Processes (MOMDP) (Wakuta and Togawa 1998) , in the sense that SEP considers both the expected return of the agent's reward and the human's belief of the agent's reward. Since MOMDPs consider multiple objectives under the same MDP model, the solutions proposed (refer to the review paper by (Roijers et al. 2013 )) aim to optimize a vector of expected returns from multiple objectives to obtain a Pareto set of solutions or obtain a single solution by considering a linear scalarization of objectives. When the models are different, applying MOMDP techniques would result in multiple vectors (one for each model) of expected returns from multiple objectives. Optimizing these vectors simultaneously is substantially more challenging than optimizing a single vector in MOMDPs since they are computed from different models. While general studies in MOMDP do not consider constraints, a specific study by (Wray, Zilberstein, and Mouaddib 2015) considers constraint specifications for multiple objectives with a lexicographic ordering which has close connections to our work and has inspired the action pruning technique described in this paper. However, in addition to the limitation above, the solution does not guarantee the optimality of the policy found.There exists prior work that considers multiple MDPs (Singh and Cohn 1997; Russell and Zimdars 2003; Buchholz and Scheftelowitsch 2019) which primarily focus on finding a policy that maximizes the combined or weighted expected return from all reward functions, essentially reducing it to a single objective optimization problem. Even though these methods may appear comparable to ours, they can result in a policy that violates the safety bound or has low quality in the human's model. Such an issue is due to the fact that these methods do not explicitly consider safety bounds, which we address in our work.In safe explicable planning, there are two models at play: M R and M H R . We formulate these models as discrete Markov Decision Processes (MDPs). An MDP is represented by a tuple M = ⟨S, A, T , R, γ⟩ where S is a set of states, A is a set of actions, T (s ′ |s, a) is a transition function, R is a reward function, and γ is a discount factor. We assume M R and M H R share the same state and action spaces but have different transition functions, reward functions, and discount factors. This is reasonable when the human and AI agent cohabit the workspace and share certain understanding of the environment. Relaxing such an assumption incurs separate technical challenges (e.g., hierarchical models) that will be deferred to future work. Hence, the ground-truth or agent's model M R is represented by the tuple M R = ⟨S, A, T R , R R , γ R ⟩ where T R is the true transition function or domain dynamics, R R is the engineered reward function, and γ R is the engineered discount factor. The human's understanding or belief about the agent's model  and γ H R is the belief about γ R . We work with the set of all stationary deterministic policies Π, given by ∀π ∈ Π, π : S → A. An optimal agent's policy maximizes the (expected) return in the agent's model and is given by πM H R is repre- sented by the tuple M H R = ⟨S, A, T H R , R H R , γ H R ⟩ where T H R is the human's belief about T R , R H R is the belief about R R ,* = arg max π E π T R [ ∞ t=0 γ t R r R (t)].We define a safe behavior as any behavior with a return within a bound of the optimal agent's return. Similar criteria have been used in safe RL (Garcıa and Fernández 2015; Moldovan and Abbeel 2012) . More formally, a policy π is considered safe if its return satisfies the following condition:EQUATIONwhere δ ∈ (0, 1] is the designer-specified safety bound.Since execution may start from any state, we require such a condition to hold true under any state. It also implies that the condition would hold from any step during execution. 240 These are desirable features of safety critical systems.In prior work on explicable planning, the objective has been to maximize a weighted sum of the return in the agent's model and an explicability metric. For example, such a metric has been defined via plan distances (Kulkarni et al. 2016) 245 in deterministic domains and KL divergence between trajectory distributions (Gong and Zhang 2022) in stochastic domains. In our work, we define the explicability metric simply as the return from the human's model M H R . Given that the human uses M H R to generate expectations, this assumes ra-250 tional human observer: the higher the return in the human's model, the more expected the policy is. Definition 1. Safe Explicable Planning (SEP), given byP E = ⟨M R , M HR , δ⟩, is the problem to search for a policy that maximizes the return in M H R subject to a constraint 255 on the return in M R under any state, or more formally:π * E = arg max π E π T H R ∞ t=0 γ H R t r H R (t) subject to E π T R ∞ t=0 γ t R r R (t) ≥ δE π * T R ∞ t=0 γ t R r R (t) . (2)Requiring the constraint above to hold under any state introduces a Pareto set of optimal policies where no policies in this set are strictly dominated by any policy. Briefly, a policy π 1 strictly dominates another policy π 2 if its state val-260 ues are no smaller in any state, and larger in at least one state. More formally, denote such a relationship asπ 1 ≻ π 2 , which holds if ∀s ∈ S [V π1 M H R (s) ≥ V π2 M H R (s)] ∧ ∃s ′ ∈ S [V π1 M H R (s ′ ) > V π2 M H R (s ′ )]. The Pareto set Π *E is then given by:EQUATIONwhereΠ δ = {π∈Π| ∀s∈S [V π M R (s)≥δV π * M R (s)]}is the set 265 of policies that satisfy the safety bound.In this section, we motivate and discuss our solution methods for SEP. Given the large policy space to search for, we first discuss a technique to cut the policy space. Since any 270 policy in Π δ may be in the Pareto set, we are required to expand all policies in Π δ . We propose an exact method that almost expands only those policies in Π δ to determine the Pareto set Π * E . A greedy method that only expands a subset of policies in Π δ and returns a single policy in Π * E is then dis-275 cussed. Finally, we propose approximate solutions via state aggregation using handcrafted features to condition similar states to choose the same actions to further scalability. Complete proofs are provided in the supplemental materials.Even though the set of Π δ cannot be obtained directly from the entire policy space Π, we aim to cut the policy space based on the safety constraint to produce a subset of policies in Π, referred to as Π. The challenge here is to ensure that Π ⊇ Π δ (see Fig. 2(a) ).We achieve this by pruning sub-optimal actions for every state that are guaranteed to violate the constraint. More specifically, let A(s) be the set of all actions that are available in state s. The set of actions after pruning is given by:A(s)={a ∈ A(s)|Q π * M R (s, a)≥δ max a ′ ∈A(s) Q π * M R (s, a ′ )}.(4) The policy space after action pruning for all states is Π.Our action pruning technique is inspired by (Wray, Zilberstein, and Mouaddib 2015; Pineda, Wray, and Zilberstein 2015) . To provide a worst-case guarantee (where all states choose actions as far as possible from the optimal after a) under M R , the authors used 4), resulting in a different set of policies, referred to as Π η . Their pruning condition is more stringent than ours and may result in pruning state-actions that belong to policies satisfying the constraint in Eqn (2). Consequently, the guarantee that Π η ⊇ Π δ is lost there (see Fig. 2(a) ).1 -(1 -γ)(1 -δ) instead of δ in Eqn. (Lemma 1. The set of policies after action pruning based on Eqn. ( 4) is a superset of the set of policies that satisfy the constraint in Eqn. (2), i.e., Π ⊇ Π δ .Proof Sketch: To prove this result, we show that an action pruned by any state per Eqn. ( 4) is guaranteed to introduce policies that do not satisfy the constraint in Eqn. ( 2) under at least one state. We show that the expected return of choosing a pruned action in that state and then following the optimal policy thereafter does not satisfy the constraint. Hence, any policy that chooses the pruned action for that state cannot satisfy the constraint either.To determine Π * E , intuitively, we can evaluate every policy in Π. However, this would be impractical and proves to be unnecessary. A better idea is to enable further pruning in Π by expanding policies in certain order that facilitates pruning. We consider two options here. First, we can start from the optimal policy in the human's model and apply policy ascent in the agent's model to improve it until the bound is satisfied. Alternatively, we can start from the agent's optimal policy and apply policy descent in the agent's model and identify better policies in the human's model until the bound is violated. Since the first search strategy can lead to missed policies in Π * E , we choose the latter option in our work. In tree search, we start from an optimal policy in M R , denoted by π * , as the root node. The benefit of doing so is that, first, we already know that π * satisfies the bound under the agent's model since it is the optimal policy under M R . Second, we can leverage the known state values V π * M R to expand policies that have lower state values than that of the parent node recursively. Since this is the opposite of policy improvement, we refer to it as policy descent. More formally, all descendants of a policy π under single-action policy updates in PDT can be obtained by replacing π(s) under any 335 s ′ T R (s, a, s ′ )V π M R (s ′ ) ≤ s ′ T R (s, π(s), s ′ )V π M R (s ′ ).(5) Once a branch reaches a policy whose state values no longer satisfy the bound under M R (any state suffices), it is pruned as illustrated in Fig. 2(b ). The search continues until all branches are pruned and the set of non-dominated policies under M H R are maintained. The algorithm is presented 340 in Alg. 1, which we refer to as PDT+ (action pruning). Next, we formally show that such a process returns Π E = Π * E . Lemma 2. Let π and π ′ be two deterministic policies that differ by only a single action in some state i.e.,∃s i ∈ S [π ′ (s i ) ̸ = π(s i )] ∧ ∀s j ∈ S \ {s i } [π ′ (s j ) = π(s j )] and 345 satisfy Q π M R (s i , π ′ (s i )) ≤ V π M R (s i ).Then, policy π ′ is a descendant of π in PDT, i.e., policy π ′ is no better than π, or more formally,∀s ∈ S [V π ′ M R (s) ≤ V π M R (s)].Proof Sketch: This is an extension of the policy improvement theorem (Sutton and Barto 2018) but in the opposite 350 direction (hence referred to as a policy descent step). We first introduce a temporary non-stationary policy π ′ 1 that chooses an action as per π ′ under the initial state and follows π thereafter. We can show that the return of π ′ 1 is no better than that of π. We can repeat such a pattern to update π ′ 1 for the next 355 state and so on, resulting in π ′ at the end.Similarly, we can show that a special case of the policy improvement theorem holds when a single action is updated (referred to as a policy ascent step).Theorem 1. PDT+ returns all Pareto optimal policies in Π * E . 360 Proof Sketch: To prove this, we show that there exists a policy descent path from any optimal policy (denoted by π * ) in M R (i.e., the root node in PDT) to any Pareto optimal policy (denoted by π * E ) in Π * E by induction. When π * E differs from π * in only 1 action, π * E must be one of the direct descendants 365 of π * in PDT as π * is optimal in M R based on the search Algorithm 1: PDT+Input: M R , M H R , δ V * M R ← ValueIteration(M R ); retrieve π * Compute A(s), ∀s ∈ S; Initialize Π E ← ∅; fringe.push(π * ); while fringe ̸ = ∅ do π ← fringe.pop(); for a in A(s), s ∈ S do if Eqn. (5) is satisfied then π ′ ← Modify(π, π(s) = a); if ∀s ∈ S [V π ′ M R (s) ≥ δV π * M R (s)] then fringe.push(π ′ ); if nonDominated(π ′ , Π E , M H R ) then Π E .update(π ′ );return Π E process. Hence, π * E will be expanded by PDT. Assume any policy that differs from π * in k actions are expanded. When π * E differs from π * in k + 1 actions, we show that there must exist a policy π that differs from π * in k out of the k + 1 ac-370 tions (hence differing from π * E in 1 action) and (by Lem. 2) is no worse than π * E under M R via proof by contradiction. Consequently, π * E must be a descendant of π in PDT. Since π is expanded under our inductive assumption, π * E will be expanded. Then by Lem. 1, the conclusion holds.In certain situations, it may be unnecessary to compute Π * E : any policy in the set would suffice. To this end, we introduce a greedy method that only searches through a subset of Π δ , making it more computationally efficient than PDT.Similar to PDT, we start with π * at the root node. However, unlike in PDT where we expand policies that have a lower state values under M R via single-action policy updates, we expand only a single policy that has higher values under M H R than its parent node via multi-action policy updates (see Fig. 2(b) ). More formally, only one descendant of policy π is expanded in PAG, which is obtained by replacing π(s) under each state s with an action a that satisfies the following condition (similar to a policy improvement step):EQUATIONwhere each such state-action update is checked against the constraint in Eqn. (2) (under M R ) incrementally and incorporated only if the constraint is not violated, resulting in a multi-action policy update for V πM H R .In PAG, we maintain a single candidate policy π E as opposed to a set in PDT. The current policy π E is updated to its descendant π ′ if at least one of the state-action updates is incorporated. This process is repeated until π E remains unchanged. The algorithm, referred to as PAG+ (action pruning), is presented in Alg. 2. Theorem 2. PAG+ returns a policy in the Pareto set Π * E .Proof Sketch: The PAG search process stops when it can no longer improve or find a policy that is equivalent in values Algorithm 2: PAG+Input: M R , M H R , δ V * M R ← ValueIteration(M R ); retrieve π * Compute A(s), ∀s ∈ S; Initialize π E ← π * ; changed ← true; while changed do V π E M H R ← PolicyEvaluation(π E , M H R ) changed ← f alse for a in A(s), s ∈ S do if Eqn. (6) is satisfied then π ′ ← Modify(π E , π E (s) = a); if ∀s ∈ S[V π ′ M R (s) ≥ δV π * M R (s)] then Update π E ← π ′ changed ← true return π E to π E under M HR while satisfying the safety constraint. This translates to that there does not exist a state-action update that implements a policy ascent step under the constraint. However, if π E / ∈ Π * E , there must exist another policy π ∈ Π * E that dominates π E , which contradicts with the fact that no policy ascent step exists. Then by Lem. 1, π E ∈ Π * E .In the worst case, the number of policies that PDT+ and PAG+ must search through is in the order of | Π|, which is still exponential. Hence, it would be challenging to directly apply these methods to complex domains. Approximate solutions are needed. However, since the search is over the policy space, typical methods for function-approximating state value functions to search for optimal policies (Sỳkora 2008; Abel, Hershkowitz, and Littman 2016; Abel et al. 2018; Ferrer-Mestres et al. 2020) do not apply here. We aim to design an approximate solution that can reduce the unique number of policies to be searched for. Inspired by function approximation, one idea is to reduce the state space by aggregating states that are alike in terms of action selection. The likeness of states can be measured by domain dependent features. We can condition states from the same clusters to choose the same actions under any policy with either model, effectively reducing the state space size and thus the number of policies. More formally, such a process introduces a mapping Φ : S K → S, a one-to-many mapping from clusters to states and K is the number of clusters. Both PDT and PAG can work with the aggregated state space (i.e., clusters) by considering S K as the new state space.Under the assumption that the states in any aggregated state are "correlated" under any given policy for action selection, the same guarantees of optimality, completeness, and constraint satisfaction hold. Such a situation may occur, for example, when two states are topologically equivalent such that a reasonable policy should always choose the same action under these states. It would be interesting to study when such states are introduced, as well as the impact on the theoretical guarantees when such an assumption does not hold or hold only approximately. From such a per-spective, our approximation method is analogous to function approximation under Q-learning.We evaluate our methods under various domains in simulation and with physical robot experiments. The objective of our evaluations is threefold. First, we compare safe explicable behaviors with optimal behaviors to validate the effectiveness of our approach. Second, since the solution to SEP requires searching for the optimal policy in the feasible policy space in a brute-force manner to obtain the Pareto set, we analyze the efficiency of the proposed methods and compare with baselines (BF & BF+) that brute-force the policy search. Note that our comparisons are against the brute force methods because all prior studies discussed in the related work section are limited in terms of the consideration of multiple models or safety bounds (refer to related work).We also analyze the benefits of our approximate solutions with more complex domains and the action pruning technique in ablation studies for each proposed method. Third, we evaluate with physical robot experiments to show the applicability of our approach to real-world scenarios. By our naming convention, we append '+' to a method name to indicate the incorporation of our action pruning technique, such that the policy space is reduced to Π; a method whose name is without '+' must deal with the original policy space, or Π (see Fig. 2(a) ). All evaluations were run on a MacBook Pro (16 GB, 3.1 GHz Dual-Core Intel Core i5). Details of the domain descriptions and implementation are in the supplemental materials.Bound Selection: In our approach, the bound (δ) is assumed to be specified by the designer based on experience. However, it can often be approximated based on the domain. For example, consider one of the cliff worlds in Fig. 5 (see below). The return of the optimal trajectory under the agent's model is 94 (i.e., moving along the edge of the cliff to the goal) and the return of the trajectory with the longest detour (i.e., staying as far away from the edge as possible) without falling off the cliff is 90, when ignoring any discount. Since unsafe behaviors should be captured by the agent's (groundtruth) model and result in much lower return than the detour, the safety bound can be set at 90/94 = 0.957 and then adjusted. More analyses will be deferred to future work.Policy Selection: To select from the Pareto set Π * E , we can rely on user preferences. Alternatively, domain-specific scores may be introduced to assist with the selection. For example, higher scores may be given to policies that appear "simpler". Example scores are discussed when applicable.The agent is required to navigate alongside the edge of a cliff to reach the goal (see Figs. 4 and 5 ). The ground-truth model (M R ) is that the agent can travel alongside the edge without slipping off the cliff. The human's belief (M H R ) is that the agent may slip off from the edge with some probability, and the terrain closer to the cliff is more uneven and hence more difficult to traverse. For both worlds, the reward functions 4(a ) and 4(b), respectively, for the larger domain. We created a small 4 × 5 domain (CS) for the exact methods and a large 500 4×100 domain (CL) for approximate solutions. To apply approximate solutions to CL, the states were aggregated based on features such as distance to the cliff, agent's position in the grid (e.g., along the edge or at the ends). For CL, we aggregated all non-terminal states into 10 clusters and retained 505 the terminal states as is.δ BF BF+ PDT PDT+ |Π * E | PAG PAG+ # # # RT # RT # RT # RT 1.2) Wumpus World (W): The agent is required to exit a 5×5 cave while collecting gold coins on its way out and avoiding encounters with the wumpus (i.e., staying in the same location) (see Fig. 3 ). The wumpus always chooses moves to-510 wards the agent. Collecting each gold coin gives a reward of +30. The game terminates if the agent encounters the wumpus (-100) or if it exits the cave (+100). In the ground-truth model (M R ), the agent's actions are deterministic while the wumpus's actions are stochastic. The human's belief M H R is 515 that the actions of both agents are stochastic. Under such a belief, the human would consider it dangerous for the agent to come close to the wumpus. For approximate solutions, the non-terminal states were aggregated into 15 clusters based on features such as the relative direction of the wumpus from 520 agent and collection status of the gold coins.Results. 1) Performance Comparison: Tab. 1 shows the runtime (except for BF and BF+ due to the large number of policies) and number of policies expanded (or evaluated) by each method under the three simulation domains. The first 525 set of results is obtained with the small cliff world (CS) domain with 16 non-terminal states and 4 actions available in each state, resulting in |Π| = 4 16 policies. The second set of results is obtained with the large cliff world (CL) with 301 non-terminal states and 4 actions available in each state, 530 resulting in |Π| = 4 301 policies. Applying state aggregation with 10 clusters results in 4 10 policies. The third set of results is obtained with the wumpus world (W) with 2116 We can observe that action pruning reduces the policy space and thereby the number of policies expanded by BF+, PDT+, and PAG+ as compared to those by BF, PDT, and 540 PAG, respectively. The expansion order of policies in PDTs results in considerable additional pruning compared to BF+. With or without action pruning, PAGs expand fewer policies than PDTs since they only need to return a single policy. Lastly, while the number of policies expanded in PDTs increases (for lower δ), it is interesting to note that PAGs sometimes expand fewer policies due to their greedy nature.(a) τ (π * M R ) (b) τ (π * M H R ) (c) τ (π * E ) | PDT+ (d) τ (π * E ) | PAG+2) Behavior Comparison in Cliff Worlds: The results of the cliff worlds are shown in Figs. 5 (CS) and 4 (CL). Both the small and large domains introduce similar behaviors: 550 shown only in the large domain, the optimal behavior in the agent's model takes the shortest path (Fig. 4(a) ) whereas the human's expectation is to stay as far away from the cliff as possible (Fig. 4(b) ). For SEP, Fig. 5 shows all the three policies in the Pareto set obtained given δ = 0.90 in the small domain. Fig. 4(c) shows the most likely trajectories resulting from 2/3 policies in the Pareto set obtained given δ = 0.95 in the large domain using the approximate solution. In general, we observe that the safe explicable policies result in trajectories that steer the agent away but not too far from the cliff 560 to satisfy the bound while aligning with the human's expectation. In cliff worlds, to choose from Π * E , we assign higher scores to policies producing simpler behaviors (e.g., fewer turns), it led to choosing the policy producing the green trajectory in Fig. 4(c ) and the policy in Fig. 5(a) . PAGs, on the other hand, computed different policies in Π * E (see figures). 3) Behavior Comparison in Wumpus World: The results are shown in Fig. 3 . Under the optimal behavior in the agent's model (M R ), the agent collected both coins while staying within the proximity of the wumpus before exiting, 570 as shown in Fig. 3(a) . The human's expectation (under M H R ) is that the agent avoids getting close to the wumpus and collecting a single coin before exiting, as shown in Fig. 3(b) . When applying SEP under the bound δ = 0.90, PDT+ returns a large Pareto set (see Tab. 1). To select from Π * E , we 575 score policies based on the average distance from the wumpus throughout the most likely trajectory. Fig. 3(c) shows the trajectory obtained from the policy with the highest score in Π * E : the agent managed to collect both coins while maintaining a cautious distance from the wumpus while taking a longer path, which is more explicable than the optimal agent's behavior in Fig. 3 (a) and simultaneously more efficient than the human's expection in Fig. 3(b) . Fig. 3(d) shows the behavior obtained by PAG+, which also maintains a cautious distance from the wumpus for the most part.Robot Assistant Domain. We implemented a scenario similar to the motivating example where a Kinova MOVO robot is assisting a human user with setting up the dining table (Fig. 6 ). The robot is required to fetch a napkin for the user from another table. The user does not fully understand the kinematic constraints of the robot arms and hence expects the robot to reach any location within its arm's length. Hence, the human's expectation is for the robot to place the napkin next to the plate (close to her). In the robot's model, however, movement of the arms is restricted by a vase on the table such that placing the napkin close to the user may tip over the vase containing water, resulting in a safety risk. Therefore, the robot's optimal behavior is to place the napkin next to the vase, which is further away from the user. This experiment was run in a discretized setting where the state space was specified by the following variables: location of the robot, location of the napkin, and location of the vase. For any transition between the discrete states, the robot trajectories were generated a priori using Move It. More specifically, M H R specifies that the robot can access any location on the dining table irrespective of its location or the vase's position whereas M R properly captures the influences from these factors. Our aim is to demonstrate that a robot running SEP would choose a costlier policy under M R to be explicable to the human user while ensuring safety.Results. The safe explicable behaviors from the results of the robot experiment are shown in Fig. 6 . The optimal behavior under M R involved two steps where the robot picked up the napkin and placed it on the table next to the vase and away from the user (see appendix B in supplemental materials). We then ran SEP with two different bounds that resulted in two different safe explicable behaviors. When the bound was δ = 0.85 (Fig. 6(a) ), the robot picked up the napkin, moved its entire body to be closer to the user so that it was no longer obstructed by the vase, before placing the napkin next to the plate. When the bound was set to δ = 0.80 (Fig. 6(b )), the robot first pushed the vase aside so that it was no longer obstructing its arm movements before picking up the napkin and placing it next to the plate.EQUATIONEQUATIONIn this paper, we introduced the problem of Safe Explicable Planning (SEP), which significantly extends explicable planning to support a safety bound. To focus on the planning challenges of introducing safety in explicable planning, we assume the human belief model M H R is known. We provide references to existing literature where a similar assumption is made. When M H R is unknown, it can be learned by querying human subjects, to learn a reward function such as the approaches discussed in the survey paper (Wirth et al. 2017 ) and to learn domain dynamics such as the approach by (Zhuo 2015) . We defer the consideration of other forms of M H R (such as hierarchical models) or learning M H R for future work. It is worth noting that the problem of SEP can be formulated as a CMDP problem under the special case where T R = T H R and γ R = γ H R , in planning (Altman 2021) or learning (Achiam et al. 2017) setting.In our work, we assume that safety is correlated to the expected return in the agent's model under the intuition that unsafe behaviors would result in low returns. Thus, imposing a lower bound on the return prevents unsafe behaviors. Such a safety definition is based on the constrained criterion. We aim to extend it to consider other safety formulations such as the worst-case criterion etc. outlined in (Garcıa and Fernández 2015) in the future. It would also be interesting to study how our value function-based criterion can be compared with or potentially equated to a state-machine-based criterion such as that studied by (Hunt et al. 2021) . For example, prior work has studied how LTL constraints can be approximately considered by shaping the reward function (Camacho et al. 2019; Li, Vasile, and Belta 2017) . Fur- ther, the safety bound in our work is domain-specific as the criticality of safety is different in different scenarios and can be specified by the designer. We discuss how the safety bound was determined for the experimental evaluations and 660 will more systematically address it in future work.Our problem formulation generalizes the consideration of objectives from multiple models and the solution is a Pareto set of policies. We proposed an action pruning technique to reduce the search space, an exact method that returns the 665 Pareto set, and a greedy method that returns a single policy. Existing literature in MOMDP shows that finding exact Pareto solutions for complex problems is intractable. To scale to complex domains, we further discussed approximate solutions by clustering states that are alike in terms of action 670 selection. Since SEP requires searching the policy space, the methods proposed (exact and approximate) are still susceptible to policy explosion in large domains. The aggregationbased approximation proposed is preliminary work toward finding approximate safe explicable policies. We defer the 675 study of generalized and more efficient approximation techniques to solve SEP in the future.An underlying assumption here is that safety is negatively correlated with the cost metric. Other forms of safety criteria, such as behavior deviation, will be considered in future work. 
 
 Appendix:  


Decision: This paper is recommended to be accepted; we encourage the authors to consider the comments made by reviewers to ensure the best possible camera-ready version is submitted.

Reviews: review: strength_weakness: strength_weakness: 1. Assumption of Human Rationality and Other Human Factors:
While acknowledged as limitation, the paper assumes that humans interacting with the AI system will behave rationally. This assumption is a potential weakness because human behavior can be influenced by a range of factors and may not always be predictable, or even rational. In real-world settings, this could affect the performance and reliability of the proposed SEP model. Additionally, the paper does not consider other critical human factors, such as trust, that can impact the efficacy and applicability of SEP. For example, if the system's actions are not only explicable but also demonstrably safe, it may enhance user trust. Conversely, a lack of clear safety protocols could erode trust, even if the system's actions are explicable.

2. Scalability in Complex Environments:
While the paper addresses scalability through state aggregation, it may face challenges in more complex or dynamic environments where the state space can become significantly large. This raises concerns about the practical applicability of SEP in such scenarios and its ability to maintain computational efficiency and accuracy. As such, this question should be explored.

3. Evaluation in Limited Contexts and Generalizability:
Although the paper includes simulations and physical robot experiments, these are conducted in relatively controlled or limited contexts. Therefore, the results may not generalize. Different contexts or types of human-robot interactions could present unique challenges not accounted for in the current experiments, potentially affecting the broader applicability of the SEP approach.
questions: questions: 1) How does the assumption of human rationality in your model affect its applicability and reliability in real-world scenarios, where human behavior can be unpredictable or non-rational?

2) Can you elaborate on the performance and scalability of the SEP methods in more complex environments? Are there limitations to the current state aggregation approach in these contexts?

3) Is there a trade-off between ensuring safety and maintaining high levels of explicability in the SEP model? How do safety constraints influence the agent's behavior from a human perspective?
strength_weakness: strength_weakness: 1) The experimental results are limited to 3 fairly small synthetic problems and a small robot problem.  Two of the synthetic problems are identical in structure.

2) Your results do not show the difference in reward between the PDT(+) and PAG(+) policies.  This is important!

3) You never compare your techniques with/without different levels of state aggregation. 

4) State aggregation appears essential for even moderate sized problems, and so far, this is a manual process.

5) In the Cliff problems, the agent model has a lower assessment of risk for walking next to the cliff than the user.  I was expecting the opposite (like in the robot problem).  I think you would get much more interesting behavior if there was varying risk at different places along the cliff, the users expectation was to walk along the cliff, and the SEP policy deviates away from the riskiest portions of the cliff depending on the safety bound. 

6)  Related work: There is a close connection between the problem of SEP and OverSubscription Planning (OP).  In OP, different goals have different rewards, and there are resource limitations.  As a result, one is trying to optimize reward while remaining within the resource bounds.  The planning problem can be either stochastic or not.   There is also work on risk bounded planning done by Brian Williams and probably others.
questions: questions: 1) Please comment on the difference in reward between PDT+ and PAG+ policies

2) It seems like there is a potential to guide the PDT and PAG search by focusing on those states where the user and agent optimal policies  are significantly different in action choice, but the user's action still satisfies the safety bound.  This can perhaps be seen as a way of measuring user "regret".  Please comment on the extent to which you already take advantage of this in your existing search.

3) Along the same lines, low regret in states could potentially be used as a basis for selection of states to aggregate.

4) In most cases, I don't think you care about the Pareto frontier, only in the optimal user policy still satisfying the safety constraint.  You can compute the optimal reward for the user, given the reduced policy space.  This would give you a bound on what could be attained.  If you find a policy "close enough" to this bound you could stop the search.  This would provide you with a search procedure that finds a bounded optimal policy subject to the safety constraints.  Seems worth considering as an intermediate between PDT and PAG.  Please comment.
strength_weakness: strength_weakness: Although it is elaborated how SEP differs from MOMDP and why the latter might not be ideal to tackle the problem, I feel that there might have been an empirical comparison with it (brute force policy search as a baseline might be a bit naive).
questions: questions: 1. Although explicit explainability is out of scope of the paper, I wonder how easy/hard is to make resulting policies (and decisions) explainable to humans ? 
2. Can the methods be easily extended to consider multiple humans with different models ?

====
Thank you for your response !