Helpful Information Sharing for Partially Informed Planning Agents

1 Introduction

An agent, or actor, tasked with reaching a goal, may have only partial information about its surroundings and limited sensors to acquire new information. In situations where safety constraints are in place and failures are to be avoided, the lack of information may paralyze the actor, which might fail to reach its goal even when the goal would be achievable with more information. In a collaborative multi-agent setting, another agent, the helper, may possess information that could make it possible for the actor to achieve its goal. At the same time, the communication bandwidth between the actor and the helper might be limited, forcing the helper to choose which information to transfer to the actor. We explore the question of Helpful Information Sharing (HIS) that aims at determining the minimal information the helper needs to share with the actor to guarantee its goal is achievable.

HIS is relevant to a broad variety of applications in which one may seek to minimize communication because it is expensive, unreliable, or prone to interception. Consider, for example, underwater autonomous operations with squads of robots (e.g. Camilli et al. 2019). Communication is typically highly constrained in these missions. Underwater, the communication bandwidth is limited, hence the members of the squad need to decide carefully what information to pass to each other. Resurfacing facilitates communication, but this option can only be used sparsely as it consumes resources that could be devoted to performing the mission. Also in this case, it is crucial that the agents exchange only information that is vital to reach the goal. Similar challenges would be faced by a human operator involved in the mission. Consider a controller on a surface vehicle tasked with assisting the robots in reaching their goals. Exploiting a different point of view and a different set of instruments, the controller might gain useful information to help the squad. However, being the bandwidth of the communication channel limited and sporadic, the operator needs to cautiously select which information to transmit and also decide which UAVs in the team to assist.

We formalize HIS as a two-agent setting. The actor uses a partially informed planner that computes a plan to achieve the goal by using its knowledge and available sensors. The helper is assumed to have additional information about the environment, as well as knowledge of the actor, its goal, and the approach the actor takes for planning and acting. The helper's objective is to find minimal information to share with the actor so that it can achieve its goal.

HIS is challenging because there may be a large number of possible choices in regard to what information to share, and evaluating the effect of each information sharing option may be costly. To mitigate this challenge, we offer novel compilations from the two-agent HIS problem to a single-agent planning problem, which includes both information-sharing actions and actions in the environment. After providing guarantees of the optimality of our approach, we discuss how our solution can be applied to additional settings. In particular, we show how our approach can be used in single-agent settings in which the actor needs to decide which information to acquire (e.g., by deciding which sensors to deploy), in settings with alternative performance guarantees, and in other sequential decision-making under uncertainty settings, in which information may be costly or limited.

We test our approaches on a set of standard benchmarks as well as a novel benchmark of an Escape Room that we developed. Our experiments demonstrate the power of our strategy in solving a variety of HIS problems.

1.1 Running Example

A robot is tasked with reaching a destination in a simplified indoor environment. The robot maintains an occupancy map where each cell is marked as 'free' (traversable), 'occupied' (non-traversable), or 'unknown' (the robot doesn't know whether or not the cell is traversable). Initially, all cells are marked as 'unknown'. The map is updated dynamically as the robot gains more information. For simplicity, the world is static, so the value of each cell can only change from 'unknown' to 'occupied' or 'free' throughout execution. The robot can move in one of the four cardinal directions and is assumed to be able to localize itself and know which cell it occupies. It has a sensor that allows it to detect when an adjacent cell is occupied, but the sensor does not indicate which specific cell is occupied. If a robot tries to move into an occupied cell, it may get stuck without the possibility of recovering. Therefore, if the robot's sensors indicate the presence of a nearby obstacle, the robot will only move to an adjacent cell if it can infer that it is free and will backtrack otherwise (based on the Wumpus domain by [Russell and Norvig, 2016]).

Example 1. Figure 1a depicts a simple roomwith a single entry point and a goal destination G. Cells with obstacles (e.g., cell (B, 3)) are marked by flames that emit signals, depicted as smoke waves. Such a signal indicates to the robot the existence of an obstacle in one or more adjacent cells. Figure 1c depicts the robot's initial belief, which corresponds to its initial knowledge. Since the robot does not sense a nearby obstacle, it knows that the two adjacent cells are free (the green cells in the figure). If the robot is willing to follow a plan that is not guaranteed to succeed and replan its behavior if needed, it will compute a plan based on the assumption that some cells are free. As shown in Figure 1b and the corresponding robot belief in Figure 1d, without additional information, the robot will backtrack to a cell it knows is free every time it senses an obstacle. In this case, the robot will abort execution of its task after examining all possible paths.

In Figure 2a, we show a minimal set of informationsharing interventions that guarantee that a replanning agent can achieve its goal. In this case, an optimal solution is for the helper to reveal that cells (A, 4) and (D, 5) are free (the cells marked blue are those whose true value is revealed). Figure 2c shows the robot's initial belief. The path that successfully leads the robot to its goal after the additional information is provided is depicted in Figure 2b, and Figure 2d shows the robot's path along with information that is acquired during execution. Note that this information-sharing intervention is minimal in terms of the number of information items shared. In order to guarantee that a minimal cost plan is achievable, more information needs to be revealed.

2 Planning Under Partial Observability

We follow Bonet and Geffner [2011; 2014] in modeling a partially informed actor.

Definition 1 (Planning Under Partial Observability). A planning under partial observability (PPO) problem is a tuple P = ⟨F,A, I,G,O⟩ where F is a set of fluent symbols, A is a set of deterministic actions, I is a set of clauses over F-literals (referred to as facts) defining the initial situation, G is a set of F-literals defining the goal condition, and O represents the agent sensor model.

An action a ∈ A has a set prec(a) of F-literals as preconditions, and a set eff (a) of conditional effects C → L, where C is a set of F-literals and L is an F-literal. The sensor model O is a set of observations o ∈ O represented as pairs (C, L), where C is a set of F-literals, and L is a positive fluent indicating that the value of L is observable when C is true. Each observation o = (C, L) can be conceived as a sensor on the value of L that is activated when C is true. A state s is a truth valuation over the fluents F ('true' or 'false'). For an agent, the value of a fluent may be known or unknown. A fluent is hidden if its true value is unknown. A belief b is a non-empty collection of states that the agent deems as possible, which we assume always includes the actual state. For unknown fluents, states for both values are included in the belief until one of the values is refuted. A formula F holds in b if it holds for every state s ∈ b.

An action a is applicable in b if the preconditions of a hold in b, and the successor belief b′ is the set of states that result from applying a to each state s in b. When an observation o = (C, L) is activated, the successor belief is the set of states in b that agree on L (i.e., the set of states where fluent L has the sensed value). The initial belief is the set of states that satisfy I, and the goal belief is the set of those that satisfy G. A formula is invariant if it is true in each possible initial state and remains true in any state reachable from it. A PPO problem is simple if the non-unary clauses in I are all invariant, and no hidden fluent appears in the body of a conditional effect. We hereon assume our PPO problems are simple.

A history is a sequence of actions and beliefs h = b0, a0, b1, a1, . . . , bn, an, bn+1, such that action ai is applicable in belief bi. The cost of history h, denoted Ca(h), is the accumulated cost of the performed actions (equivalent to the path length when action cost is uniform): Ca(h) = ΣiC(ai). Each history corresponds to a path π = a0, a1, . . . , an, which is the sequence of actions the agent performs. A path is a plan if the agent performing the path reaches a goal belief.

We are interested in bridging the gap between what is achievable in the environment and what can be accomplished by a partially informed agent. Given a PPO problem P, we let SP be the set of possible world states in P. Similarly, the set BP is the set of possible beliefs in P, and b0 is the initial belief. We refer to a path as executable in the environment if it is executable in the real-world state. An executable plan is an executable path that achieves the goal.

Definition 2 (Executable Path). Given a PPO problem P and state s ∈ SP, a path π = ⟨a0, a1, . . . , an⟩ is executable in s if a0 is applicable in s and, for any 0 < i ≤ n, ai is applicable in ai-1(. . . (a0(s))).

Definition 3 (Executable Plan). Given a PPO problem P and a state s ∈ SP, a path π = ⟨a0, a1, . . . , an⟩ is an executable plan in s if it is an executable path in s and an(. . . (a0(s))) satisfies G.

The above definitions account for what an agent (with full information) can achieve in the environment. To account for what is achievable with limited information and sensing capabilities, we define a PO-executable path and POexecutable plan below.

Definition 4 (PO-executable Path). Given a PPO problem P and belief b ∈ BP, a path π = ⟨a0, a1, . . . , an⟩ is a POexecutable path in b if a0 is applicable in b and, for any 0 < i ≤ n, ai is applicable in ai-1(. . . (a0(b))).

Definition 5 (PO-executable Plan). Given a PPO problem P and belief b ∈ BP, a plan π = ⟨a0, a1, . . . , an⟩ is a POexecutable plan in b if it is a PO-executable path in b and an(. . . (a0(b))) satisfies G.

Note that, since the actor is partially informed, there is a difference between goal states, in which the goal is achieved, and goal beliefs, in which the actor knows the goal has been achieved. It's easy to show that, since an action is applicable in a belief only if it is applicable in every state in the belief (including the actual state), every PO-executable plan is a plan that is guaranteed to be executable in the actual state. Our objective is to find an efficient way to make sure that at least one executable plan is PO-executable by the actor. Since we assume our conservative actor only performs actions it knows the outcome of, the set of executable plans that can be sequentially applied to achieve the goal subsumes the set of PO-executable plans.

Two issues need to be addressed when planning with incomplete information: belief tracking and planning. Belief tracking considers the task of keeping track of the agent's belief as it operates in the environment and collects new information [Geffner and Bonet, 2013]. In the worst case, the computation of the belief states is exponential in the number of state variables. In this work, we focus on understanding which information is needed by a partially informed planner and assume its belief tracking is sound and complete.

There are two main approaches to planning under partial information, offline and online [Brafman and Shani, 2014], and a variety of approaches of these two types have been developed for PPO planning. A common technique for online planning is replanning [Zelinsky, 1992], where an agent finds a plan for its current state based on some simplification of its planning problem and on assumptions it makes about unknown variables. The agent then executes a prefix of the plan until discrepancies between the plan and the information acquired during the execution emerge and require replanning. Our focus here is on providing relevant information to a partially informed replanning agent; we are agnostic to the approach it uses for planning as long as it complies with our assumption that the agent is conservative.

3 Helpful Information-Sharing (HIS)

We consider a two-agent setting where the first agent, the actor, is a partially informed replanning agent that uses a PPO problem to decide how to act to achieve its goal. The second agent, the helper, has access to the actor's planning model and additional information in the form of facts (i.e. Fliterals), which it knows are true and can be shared with the actor. For convenience, we indicate the set of facts over F as LF. We assume that each fact f ∈ LF is revealed and added separately to the actor's knowledge. We refer to each revelation as an information-sharing intervention.

Definition 6 (Information-Sharing Intervention). Given PPO problem P = ⟨F,A, I,G,O⟩ and fact f ∈ LF, information-sharing intervention δf adds f to I, δf(I) = I ∪ {f}.

We assume that the set of facts known to the actor is subsumed by the set known to the helper, but the helper is not necessarily fully informed (in Example 1, it may be aware of only a subset of the blocked cells). The helper uses its knowledge, which may include both invariant and non-invariant facts, and knowledge of the actor to find a minimal set of facts to reveal to the actor to guarantee it can achieve its goal.

Specifically, HIS consists of the helper finding a minimal set of facts to reveal to the partially informed actor to guarantee that it can execute at least one executable plan despite its partial knowledge. Given the set ∆ of informationsharing interventions the helper can perform (i.e., the facts it can reveal), we let P ∆ 0 represent the model that results from applying the set of interventions ∆ ⊆ ∆ to P0 such that P0

and P ∆ 0 are equivalent except for IP ∆ 0 = IP0 ∪LF(∆), where LF(∆) is the set of facts in ∆. Also, given a PPO problem P, we let Πe(P) and Πpoe(P) represent the executable plans in the initial state of P and the PO-executable plans in the initial belief of P, respectively. We seek to find a minimum set of facts to reveal offline to the actor to guarantee that, if an executable plan in the initial state of P0 exists, then a POexecutable plan in the initial belief of P ∆ 0 also exists.

Definition 7 (HIS). Given an actor's initial model P0 = ⟨F,A, I,G,O⟩ and an intervention set ∆, the problem that HIS aims to solve is as follows:

We note that if there is no solution to the HIS problem, that does not necessarily entail there is no way for the actor to achieve the goal based on its sensors. It may mean that the helper cannot provide an offline guarantee that there is a plan that will succeed based on the information it possesses.

For the sake of simplicity, we assume that the cost of communication is uniform among all facts that can be revealed. Extending this approach to non-uniform cost settings is straightforward and requires minimizing the total cost of communication instead of the number of facts that are revealed. In addition, recall that our actor is a replanning agent that can only make assumptions about unknown facts that can be discovered by using one of its sensors, i.e. facts f ∈ L in some sensor (C,L) ∈ O. The actor can make new assumptions and replan if one of its previous assumptions is refuted. Since we are interested in minimizing communication, it is wasteful to reveal facts that can be sensed by the actor. The solution to HIS will, therefore, include only facts that hinder goal achievement and cannot be acquired by the actor.

Example 1 (continued). It is redundant to reveal to the actor that cell (A,3) is 'free' since the actor can infer this when its sensors indicate no signal at adjacent cells. In contrast, its sensors are insufficient to guarantee that cell (A,4) is free given the signal detected at cell (A,3). An optimal HIS solution for this case is depicted in Figure 2.

4 Finding Optimal Solutions for HIS

We propose two approaches to seek optimal solutions to HIS.

4.1 Lazy Breadth-First Search

A baseline approach for solving HIS is to perform a breadthfirst search (BFS) in the space of interventions, computing the actor's cost to goal at each node (in the case of nonuniform communication cost, a Dijkstra search can be applied instead). The root node is the initial model P0 (and empty intervention set), and the operators (edges) are the interventions δ ∈ ∆ that make transitions between models. The value of each node and the corresponding intervention set ∆ represent whether the goal is reachable, i.e. whether Πpoe(P ∆ 0 ) ̸= ∅. The search explores intervention sets of increasing size, using a closed list to avoid the computation of pre-computed sets. To find a solution that complies with Equation 1, the search halts if a solution is found or if there are no more nodes to explore and returns the shortest path (smallest intervention set) to a node that achieves the optimal value. This approach is guaranteed to find an optimal solution but does not scale to large problems.

To increase efficiency over the exhaustive approach, we suggest Lazy Breadth-First Search (Lazy-BFS), which avoids the need to compute the value of nodes that are guaranteed not to represent optimal solutions. The structure of the search tree is similar to the one described for BFS. The novelty is that, instead of fully evaluating each node, we use a lazy approach to node evaluation; when a node is expanded during the search, we map it to a relaxed intervention set, which is guaranteed to overestimate the value of the node. We compute the exact value of the node only if the value for its relaxed set achieves the objective. Computational savings are achieved by storing the values of the relaxed sets and reusing them for future nodes that are mapped to the same relaxed set. To achieve a relaxation of the examined intervention set, we exploit the parameterized representation of our informationsharing interventions and use parameterized padding [Keren et al., 2017], which associates each intervention set to a superset that includes all interventions that share the same value of one or more of its parameters. A full description of LazyBFS is given in the appendix 1 .

4.2 The Tka Translation

To increase efficiency, we transform HIS into a planning problem, which can be solved to obtain an optimal solution to the original HIS problem by using a single call to an offthe-shelf classical optimal planner. Our approach is an extension of the Tk translation of Bonet and Geffner [2011], which finds a plan for a partially informed agent [Bonet and Geffner, 2014]. At the core of the Tk translation is the substitution of each fluent L in the original problem with a pair of fluents KL and K¬L, representing whether L is known to be true or false, respectively [Albore et al., 2009; Palacios and Geffner, 2009]. Each original action is transformed into an equivalent action that replaces the use of every literal to the need to know its value. The agent can make assumptions about observations it can perform during execution and infer new information based on sensory input. This representation captures the underlying planning problem at the knowledge level [Petrick and Bacchus, 2002; Bonet and Geffner, 2014], accounting for the exploratory behavior of a partially informed agent. By using the Tk translation, the actor can follow a planning under optimism approach: it makes the most convenient assumptions about the values of hidden variables and replans its behavior if an assumption is refuted during execution.

We extend Tk by encoding the helper's knowledge into the actor's problem description and by allowing the actor to select which information it needs to acquire to reach the goal. Importantly, this approach will exhibit which information is necessary to reveal to the agent since it will not be able to acquire or deduce this information on its own.

1 Appendix: https://github.com/sarah-keren/HIS-IJCAI-23

Our translation, denoted as Tka, takes as input the actor's planning problem as well as the helper's possible information-sharing options. In addition to execution, assumption, and ramification actions, which appeared in Tk, Tka also includes knowledge acquisition actions A′ka , which are modeled as part of the planning problem and represent the sharing of information by the helper. We also add a cost function, which we use to guarantee that an optimal solution to the translation minimizes communication cost.

Definition 8 (Tka Translation). For any HIS problem M = ⟨P0,∆⟩, Tka(M) = ⟨F ′ , I ′ ,G′ ,A′ , C ′ ⟩ is the fully observable planning problem where

• F ′ = {KL,K¬L : L ∈ F}
• I ′ = {KL : L ∈ I}
• G′ = {KL : L ∈ G}
• A′ = A′exe ∪ A′ram ∪ A′as ∪ A′ka where
• A′exe includes all actions a ∈ A, but with each precondition L replaced by KL, and each conditional effect C → L replaced by KC → KL and ¬K¬C → ¬K¬L.
• A′ram = {aram| for invariants ¬C∨L in I} where
• prec(aram) = {KC} and
• eff (aram) = {KL}
• A′as = A′+ as ∪A′- as where
• A′+ as = {a(C,L)|o = (C,L) ∈ O,L ∈ L∆} where
• prec(a(C,L)) = {KC, ¬KL, ¬K¬L,L} and eff (a(C,L)) = {KL})
• A′- as = {a(C,¬L)|o = (C,L) ∈ O, ¬L ∈ L∆} where

In the definition above, F ′ , I ′ and G′ are the same as in the Tk translation. The key difference is in the definition of A′ and the addition of the cost function C ′ . Tka includes an action in A′ka for every fact in L∆ that is known by the helper and that can be shared with the actor. In addition, instead of allowing the planner to make any assumption that is part of the actor's sensor model, in Tka, we only allow making assumptions that are known to be true by the helper. This is because Tka takes the point of view of the helper, which uses the translation to find facts to reveal to the actor that are guaranteed not to be refuted during execution and that ensure the goal is achievable by the actor.

A solution π′ to the Tka translation is a sequence of actions in A′ , which includes execution actions (A′exe ), ramification actions (A′ram), assumptions (A′as ) and knowledge acquisition actions (A′ka ). The solution to the HIS problem is the set Πka(π′ ) of knowledge acquisition actions in π′ , which represents the information the helper should share with the actor to guarantee goal reachability. We denote the sequence of execution action in π′ as Πexe(π′ ).

4.3 Theoretical Analysis

We start our formal analysis of the Tka translation by showing that the output of the translation is a valid solution for HIS, i.e., it finds a set of facts to share with the actor to guarantee the goal is achievable. Then, we provide conditions under which the set is minimal. All proofs are in the appendix. We first show that, under the assumption that the actor's belief tracking is sound and complete, at every execution step, the belief of the actor in the original model M is subsumed by the belief in the translated problem Tka(M).

Lemma 1. Given a HIS problem M = ⟨P0,∆⟩, and a solution π′ to Tka(M), we let bi and b′i represent the actor's belief directly before applying action ai in Πexe(π′ ) in M and Tka(M), respectively. If the actor's belief tracking is sound and complete, then for any i, bi ⊆ b′i .

We will now show that the solution produced by the translation represents a valid solution to the HIS problem.

Theorem 1. For a HIS problem M = ⟨P0,∆⟩, assuming belief tracking is sound and complete, there exists a solution to Tka(M) if and only if there is a solution to M.

Corollary 1. For a HIS problem M = ⟨P0,∆⟩ and a solution π′ of Tka(M), Πexe(π′ ) is a PO-executable plan of M.

The intuition behind the proofs is that the translation represents all possible behaviors of the PPO actor because it captures all possible changes that can be applied to the actual state as well as the agent's belief. Also, based on Lemma 1, we know that the solution to the translation is applicable in the original PPO problem, and therefore it represents a POexecutable plan.

So far, we have shown that the Tka translation reveals a set of interventions that guarantee the goal is achievable. We now specify conditions that guarantee the solution minimizes communication cost. This is achieved by manipulating the cost function so that a single information-acquisition action is more costly than all other actions. This computational artifice is used to guarantee the conditions under which the translation will find the minimal set of facts to reveal to achieve the objective and does not correspond to actual cost.

Theorem 2. For any HIS problemM = ⟨P0∆⟩ if

then, for any optimal solution π′∗ to Tka(M), Πka(π′∗ ) represents a minimal set of information-sharing interventions that guarantee the actor can achieve its goal.

5 Tka Extensions

In the HIS setting described above, we have a helper agent that can reveal known facts to the actor. In many real-world settings, the actor itself can choose to perform information acquisition actions but needs to decide which of the possible costly actions to perform. Such actions can correspond to placing or activating sensors in the environment, performing information-gathering actions, or proactively requesting information from other agents. The key difference of such settings is that, as opposed to the two-agent setting described above in which the actual values of the revealed information items are known to the actor, here the actual outcome of the information acquisition actions is not known. To support such settings, we extend our approach by letting the actor itself apply Tka to its planning problem such that ∆ now represents the information the actor can request (e.g., which sensors to deploy). Since the real values of the facts in L∆ are not known, we have knowledge acquisition actions for every possible value of each fact (i.e., for each fact L ∈ L∆, the agent can acquire L or ¬L). Actions for which the agent decides to acquire a specific value are those which represent valuable information acquisition actions.

Our approach can also be used in settings in which the observer may not have enough knowledge to guarantee the actor can accomplish its goal but may be willing to settle for operating under a robustness guarantee, which quantifies the plan's ability to avoid failure. For this purpose, we rely on Keren et al. [2020a], where plan robustness is defined as the number of states in the belief for which the plan is guaranteed to succeed. Thus, we can find a minimal intervention set that yields a solution that complies with a robustness threshold. This is achieved by allowing the solution to include a specified number of assumptions in A′as for which the value is not known (the larger the number, the lower the robustness guarantee).

Finally, Theorem 2 provides conditions on the cost function under which Tka finds a minimal set of interventions that guarantee goal achievement, thus focusing on settings in which communication is costly. Applying this idea to settings in which execution actions or ramification actions should be minimized is straightforward. Using the cost function, we can impose any ordering by which actions of each type are performed. For example, by creating a strict ordering between execution, information-acquisition, assumptions (on values that are known to be true) and ramification actions, we can find the minimal information that is needed to guarantee an optimal plan is achievable by the partially informed actor.

6 Empirical Evaluation

The objective of the evaluation is to examine our approaches in terms of the computational resources used and their ability to find helpful interventions in a variety of domains.

Dataset. We use seven partially observable planning domains: WUMPUS, TRAIL, COLOR-BALLS, COLORBALLS-E, LOGISTICS, and UNIX [Bonet and Geffner, 2011; Albore et al., 2009]. The adaptation to HIS involves limiting the actor's sensors and specifying the information that can be revealed. We also introduce a new domain, ESCAPE-ROOM, in which the helper seeks a minimal set of clues that guarantee a puzzle is solvable. For each domain, we generated at least 100 benchmarks by randomly selecting the initial state and the set of items that are known to the helper. The Appendix includes a description of all the domains and the complete dataset and code.

Setup. We compare three HIS solution approaches: BFS, Lazy-BFS (Section 4.1), and the Tka transformation (Section 4.2). We use PDDL [McDermott et al., 1998] to specify the domains and the available information-sharing interventions. The BFS approaches are implemented using an adaptation of pyperplan (https://github.com/aibasel/pyperplan) to parse the intervention file and provide the set of applicable information-sharing interventions for each node in the search and the model that results from applying each intervention. While our method is agnostic to the planner used by the actor, we use the K-planner [Bonet and Geffner, 2011] with Fast-Downward [Helmert, 2006] classical planner (FD) and the Lm-cut heuristic [Helmert and Domshlak, 2009].

We run each instance on the three approaches with a time limit of 10 minutes, a memory limit of 2548 MB, and 1000 explored nodes. All evaluations were run on an 11th Gen Intel® Core™ i9-11900F @ 2.50GHz ×16.

We evaluate the following information-sharing settings:

• MININF: HIS setting described in Definition 7 in which the helper reveals a minimal set of facts that guarantees goal achievement.
• OPOP (Section 5): the helper reveals a minimal set of facts that guarantee an optimal plan is PO-executable.
• ROB (Section 5): the helper reveals a minimal set of facts to achieve the required robustness. We examine settings with decreasing robustness guarantees by allowing 1, 2 and 3 assumptions to be made by the agent, denoting them as ROB1, ROB2, and ROB3.

Results. Table 1 compares the computational resources used by BFS, Lazy-BFS and Tka. For each approach and domain, we measure 'sol' as the ratio of solved instances, i.e., instances for which the approach finishes before the allocated time bound is reached (best result is underlined), and 'time' as the average computation time in seconds for instances solved by all methods (best result in bold). For COLOR-BALLS(- EX), we indicate the average computation time for Tka, since BFS and Lazy-BFS fail on all instances.

Results show that for WUMPUS and TRAIL, BFS solved a higher percentage of instances (with lower computation time for Lazy-BFS for all but ESCAPE-ROOM), while Tka solves more instances on the other domains. In addition, Tka substantially reduces computational time for all domains (most notably for the LOGISTICS domain).

An investigation of the instances for which Tka did not complete, but BFS did, reveals instances with large spaces of information-sharing interventions for which the grounded version of the compiled problem exhausted the allocated memory. A direction for future investigation would be to explore ways to prune the space of grounded operators.

In Tables 2 and 3, we present the performance of the extensions of Tka presented in Section 5. Table 2 examines the average number of information-sharing interventions needed to achieve the requirement in MININF and OPOP settings in which the observer has sufficient information for achieving the requirement (which is that some path is PO-executable for MININF and an optimal one is achievable for OPOP). As expected, the average number of information-sharing interventions increases as the requirements are more restrictive, i.e. more (or an equal number of) interventions are needed for OPOP than for MININF. In Table 3, we compare the number of interventions needed to achieve a required level of robustness when the observer does not necessarily have the needed information to guarantee goal achievement, but the actor can make 1 - 3 assumptions. We note that when we compromise robustness (i.e. the agent can make more assumptions), fewer interventions are needed.

7 RelatedWork

The idea that information is malleable has been investigated in a variety of research disciplines, including economics [Kamenica, 2019], business management [Drucker, 2012], politics [Murphy and Shleifer, 2004], and more. We focus on controlling the information of a partially informed planning actor and the effect of additional information on the actor's behavior. Our work is most related to the extensive body of work on selective information revelation in multi-agent AI.

One relevant line of work considers communication in collaborative settings. Kamar et al. [2009] provide a mechanism for reasoning about the utility of communicating information relevant to an agent's plans in a collaborative setting. Similarly, several lines of work [Xuan et al., 2001; Wu et al., 2011; Unhelkar and Shah, 2016; Sarne and Grosz, 2007; Macke et al., 2021] consider limited communication settings and investigate the gain to effective coordination versus communication cost. To address this challenge, a unified framework is created where communication becomes part of the overall agent decision problem. In [Marcotte et al., 2020] a team of robots can share observations to improve team performance, but communication bandwidth is limited. The decision of what to communicate is based on forward simulations and a bandit-based combinatorial optimization algorithm. Our technique is different as it focuses on planning agents, ensuring the helper shares minimal information with the actor so that it can achieve its goal.

Information sharing can also be viewed as a special case of environment design [Zhang et al., 2009], which provides a framework for an interested party to seek an optimal way to modify an environment to maximize some utility. Among the many ways to instantiate the general model, policy teaching [Zhang and Parkes, 2008; Zhang et al., 2009] enables modifying the reward function of a stochastic agent to entice the agent to follow specific policies. We focus here on performing design by controlling the information an agent uses for planning, rather than by reward shaping, and on using information sharing to ensure that the goal is achievable.

Recent work [Shmaryahu et al., 2019; Nguyen et al., 2017; Keren et al., 2020b] provides various comparative criteria for plans and policies for partially informed planning and ways to compute plans that comply with those criteria, i.e., plans that maximize robustness. Specifically, Keren et al. [2020b] offer a translation of the problem to classical planning that accounts for a user-specified level of robustness by associating a corresponding cost to making assumptions. Here, we extend this approach by allowing the actor to 'buy' the information it needs and exploit the cost function to guarantee that the generated solution minimizes communication costs.

8 Conclusion

We presented HIS as the problem of finding a minimal set of information-sharing interventions that guarantee that a partially informed actor can achieve its goal. To find optimal solutions, we offer a variation of BFS and a transformation of HIS to a single-agent planning problem that can be solved using any off-the-shelf classical planner. Our evaluation, based on a set of domains adapted from the literature, shows the computational benefit of our suggested approaches.

Possible extensions include an account of informationsharing settings with stochastic sensor models and faulty communication. Another extension considers the cost of sensor placement in settings in which the helper's knowledge is not sufficient to guarantee the goal is achievable.

Acknowledgements

Sarah Keren acknowledges the support of the Technion Autonomous Systems Program as well as the helpful discussions with Lucy Liu at the preliminary stages of this work.