bounded by $\mathrm{poly}(n_{k})$. This also implies that $V$ runs in
$\mathrm{poly}(n_{k})$ time as well, which completes the analysis of the
$\S_{2}\BPP$ verifier $V$.

##### Derandomization of the $\S_{2}\BPP$ verifier $V$ into the desired
$\S_{2}\P$ verifier $V_{A}$.

Finally, we use the underlying proof technique of $\S_{2}\BPP=\S_{2}\P$
[Can96, RS98] to derandomize $V$ into a deterministic $\S_{2}\P$ verifier
$V_{A}$ that outputs $z$.

By repeating $V$ $\mathrm{poly}(n_{k})$ times and outputs the majority among
all the outputs, we can obtain a new $\S_{2}\BPP$ verifier $\widetilde{V}$
such that

  * •

There exists $\omega\in\\{0,1\\}^{n_{k+1}}$ such that for every
$\pi\in\\{0,1\\}^{n_{k+1}}$, we have

$\Pr[\widetilde{V}(1^{n_{k}},\omega,\pi)=z]\geq
1-2^{-n_{k}}\qquad\text{and}\qquad\Pr[\widetilde{V}(1^{n_{k}},\pi,\omega)=z]\geq
1-2^{-n_{k}}.$ (2)

Let $\ell=\mathrm{poly}(n_{k})$ be an upper bound on the number of random
coins used by $\widetilde{V}$. We also let
$m:=\mathrm{poly}(\ell,n_{k+1})\leq\mathrm{poly}(n_{k})$ and use
$\widetilde{V}(1^{n_{k}},\pi_{1},\pi_{2};r)$ to denote the output of
$\widetilde{V}$ given randomness $r$. Now, we define $V_{A}$ as follows: It
takes two vectors
$\vec{\pi}_{1},\vec{\pi}_{2}\in\\{0,1\\}^{n_{k+1}}\times\left(\\{0,1\\}^{\ell}\right)^{m}$
as proofs. For $\vec{\pi}_{1}=(\alpha,u_{1},u_{2},\dotsc,u_{m})$ and
$\vec{\pi}_{2}=(\beta,v_{1},v_{2},\dotsc,v_{m})$, $V_{A}$ outputs the majority
of the multi-set

$\\{\widetilde{V}(1^{n_{k}},\alpha,\beta;u_{i}\oplus
v_{j})\\}_{(i,j)\in[m]^{2}},$

where $u_{i}\oplus v_{j}$ denotes the bit-wise XOR of $u_{i}$ and $v_{j}$ (if
no strings occur more than $m^{2}/2$ times in the set above, then $V_{A}$
simply outputs $\bot$).

We will show there exists $\vec{\omega}=(\gamma,r_{1},\dotsc,r_{m})$ such that
for every
$\vec{\pi}\in\\{0,1\\}^{n_{k+1}}\times\left(\\{0,1\\}^{\ell}\right)^{m}$,

$\Pr[V_{A}(1^{n_{k}},\vec{\omega},\vec{\pi})=z]\quad\text{and}\quad\Pr[V_{A}(1^{n_{k}},\vec{\pi},\vec{\omega})=z].$

We first claim that there exist $r_{1},\dotsc,r_{m}\in\\{0,1\\}^{\ell}$ such
that for every $u\in\\{0,1\\}^{\ell}$ and for every
$\pi\in\\{0,1\\}^{n_{k+1}}$, it holds that (1) for at least a $2/3$ fraction
of $i\in[m]$, we have $\widetilde{V}(1^{n_{k}},\omega,\pi;r_{i}\oplus u)=z$
and (2) for at least a $2/3$ fraction of $i\in[m]$, we have
$\widetilde{V}(1^{n_{k}},\pi,\omega;r_{i}\oplus u)=z$.

To see this, for every fixed $u\in\\{0,1\\}^{\ell}$ and
$\pi\in\\{0,1\\}^{n_{k+1}}$, by a simple Chernoff bound, the probability, over
$m$ independently uniformly drawn $r_{1},\dotsc,r_{m}$, that more than a $1/3$
fraction of $i\in[m]$ satisfies
$\widetilde{V}(1^{n_{k}},\omega,\pi;r_{i}\oplus u)\neq z$ is at most
$2^{-\Omega(m)}$, and the same probability upper bound holds for the
corresponding case of $\widetilde{V}(1^{n_{k}},\pi,\omega;r_{i}\oplus u)\neq
z$ as well. Our claim then just follows from a simple union bound over all
$u\in\\{0,1\\}^{\ell}$ and $\pi\in\\{0,1\\}^{n_{k+1}}$.

Now, let $\gamma$ be the proof $\omega$ such that the condition (2) holds. We
simply set $\vec{\omega}=(\gamma,r_{1},\dotsc,r_{m})$. From our choice of
$\gamma$ and $r_{1},\dotsc,r_{m}$, it then follows that for every
$v_{1},\dotsc,v_{m}\in\\{0,1\\}^{\ell}$ and $\pi\in\\{0,1\\}^{n_{k+1}}$, at
least a $2/3$ fraction of $\widetilde{V}(1^{n_{k}},\gamma,\pi;r_{i}\oplus
v_{j})$ equals $z$, and similarly for
$\widetilde{V}(1^{n_{k}},\pi,\gamma;r_{i}\oplus v_{j})$. This completes the
proof.

##### Wrapping up.

Finally, we generalize $A$ and $V_{A}$ to work on all inputs $1^{n}$. On input
$1^{n}$, $V_{A}$ calculates the largest $\ell$ such that $n^{(\ell)}\leq n$,
and also calculates the largest ${k^{\prime}}$ such that
$n_{k^{\prime}}^{(\ell)}\leq n$. If $n_{k^{\prime}}^{(\ell)}\neq n$, then
$V_{A}$ immediately outputs $\bot$ and halts. Otherwise, $V_{A}$ receives an
advice bit indicating whether $k^{\prime}=k^{(\ell)}$, where $k^{(\ell)}$ is
the largest integer such that
$f_{k^{(\ell)}}^{(\ell)}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{k}^{(\ell)}}[C_{n_{k}^{(\ell)}}])$.
If this is the case, then $V_{A}$ runs the verification procedure above;
otherwise, it immediately outputs $\bot$ and halts. It is easy to see that
$V_{A}$ runs in $\mathrm{poly}(n)$ time, and is an infinitely-often single-
valued $\mathsf{F}\S_{2}\P$ algorithm solving the range avoidance problem of
$\\{C_{n}\\}$. ∎

Moreover, observe that in the proof of 5.5, all considered input lengths (the
$n^{(\ell)}_{i}$) are indeed powers of $2$. So we indeed have the following
slightly stronger result.

######  Corollary 5.9.

Let $\\{C_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}\\}_{n\in\mathbb{N}}$ be a
$\P$-uniform family of circuits. There is a single-valued $\mathsf{F}\S_{2}\P$
algorithm $A$ with one bit of advice such that for infinitely many
$r\in\mathbb{N}$, letting $n=2^{r}$, $A(1^{n})$ outputs
$y_{n}\in\\{0,1\\}^{2n}\setminus\mathrm{Range}(C_{n})$.

We need the following reduction from Korten which reduces solving range
avoidance with one-bit stretch to solving range avoidance with doubling
stretch.

######  Lemma 5.10 ([Kor21, Lemma 3]).

Let $n\in\mathbb{N}$. There is a polynomial time algorithm $A$ and an
$\FP^{\NP}$ algorithm $B$ such that the following hold:

  1. 1.

Given a circuit $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$, $A(C)$ outputs a
circuit $D\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$.

  2. 2.

Given any $y\in\\{0,1\\}^{2n}\setminus\mathrm{Range}(D)$, $B(C,y)$ outputs a
string $z\in\\{0,1\\}^{n+1}\setminus\mathrm{Range}(C)$.

The following corollary then follows by combining 5.10 and Theorem 2.3.

######  Corollary 5.11.

Let $\\{C_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}\\}_{n\in\mathbb{N}}$ be a
$\P$-uniform family of circuits. There is a single-valued $\mathsf{F}\S_{2}\P$
algorithm $A$ with one bit of advice such that for infinitely many
$r\in\mathbb{N}$, letting $n=2^{r}$, $A(1^{n})$ outputs
$y_{n}\in\\{0,1\\}^{n+1}\setminus\mathrm{Range}(C_{n})$.

The following corollary follows from 2.4 and 5.11.

######  Corollary 5.12.

$\S_{2}\E/_{1}\not\subset\SIZE[2^{n}/n]$.

Finally, we also note that by letting $C_{n}$ be a universal Turing machine
mapping $n$ bits to $n+1$ bits in $\mathrm{poly}(n)$ time, we have the
following strong lower bounds for $\S_{2}\E/_{1}$ against non-uniform time
complexity classes with maximum advice.

######  Corollary 5.13.

For every $\alpha(n)\geq\omega(1)$ and any constant $k\geq 1$,
$\S_{2}\E/_{1}\not\subset\mathsf{TIME}[2^{kn}]/_{2^{n}-\alpha(n)}$.

From 5.6 and noting that the derandomization of $\S_{2}\BPP$ verifier $V$ to
$\S_{2}\P$ verifier $A_{V}$ also relativizes, we can see that all the results
above relativize as well.

###  5.4 Infinitely Often Single-Valued $\mathsf{F}\S_{2}\P$ Algorithm for
Arbitrary Input Range Avoidance

Theorem 5.7 and 5.11 only give single-valued $\mathsf{F}\S_{2}\P$ algorithms
for solving range avoidance for $\P$-uniform families of circuits. Applying
Korten’s reduction [Kor21], we show that it can be strengthened into a single-
valued infinitely-often $\mathsf{F}\S_{2}\P$ algorithm solving range avoidance
given an arbitrary input circuit.

We need the following reduction from [Kor21].

######  Lemma 5.14 ([Kor21, Theorem 7]).

There is an $\FP^{\NP}$ algorithm $A_{\mathsf{Korten}}$ satisfying the
following:

  1. 1.

$A_{\mathsf{Korten}}$ takes an $s$-size circuit
$C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ and a truth table
$f\in\\{0,1\\}^{2^{m}}$ such that $2^{m}\geq s^{3}$ and $n\leq s$ as input.

  2. 2.

If the circuit complexity of $f$ is at least $c_{1}\cdot m\cdot s$ for a
sufficiently large universal constant $c_{1}\in\mathbb{N}$, then
$A_{\mathsf{Korten}}(C,f)$ outputs a string
$y\in\\{0,1\\}^{n+1}\setminus\mathrm{Range}(C)$.

######  Theorem 5.15.

There is a single-valued $\mathsf{F}\S_{2}\P$ algorithm $A$ with one bit of
advice such that for infinitely many $s\in\mathbb{N}$, for all $s$-size
circuits $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ where $n\leq s$, $A(C)$
outputs $y_{C}\in\\{0,1\\}^{n+1}\setminus\mathrm{Range}(C)$.

###### Proof Sketch.

By 5.11, there is a single-valued $\mathsf{F}\S_{2}\P$ algorithm $W$ with one
bit of advice such that for infinitely many $n\in\mathbb{N}$, $W(1^{2^{n}})$
outputs a string $f_{n}\in\\{0,1\\}^{2^{n}}$ with $\SIZE(f_{n})\geq 2^{n}/n$.

Now we construct our single-valued $\mathsf{F}\S_{2}\P$ algorithm $A$ with one
bit of advice as follows: given an $s$-size circuit
$C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ with $n\leq s$ as input; let
$m=\lceil\log s^{3}\rceil$ and $f_{m}=W(1^{2^{m}})$; output
$A_{\mathsf{Korten}}(C,f_{m})$. It follows from Theorem 2.3 that $A$ is a
single-valued $\mathsf{F}\S_{2}\P$ algorithm with one bit of advice (the
advice of $A$ is given to $W$). ∎

Finally, $\S_{2}\P\subseteq\ZPP^{\NP}$ [Cai07] implies that every single-
valued $\mathsf{F}\S_{2}\P$ algorithm can also be implemented as a single-
valued $\mathsf{F}\ZPP^{\NP}$ algorithm with polynomial overhead. Therefore,
the above theorem also implies an infinitely often $\mathsf{F}\ZPP^{\NP}$
algorithm for range avoidance.

Reminder of Theorem 1.5. There is a single-valued $\mathsf{F}\ZPP^{\NP}$
algorithm $A$ with one bit of advice such that for infinitely many
$s\in\mathbb{N}$, for all $s$-size circuits
$C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ where $n\leq s$, $A(C)$ outputs
$y_{C}\in\\{0,1\\}^{n+1}\setminus\mathrm{Range}(C)$. That is, for all those
$s$, there is a string $y_{C}\in\\{0,1\\}^{n+1}\setminus\mathrm{Range}(C)$
such that $A(C)$ either outputs $y_{C}$ or $\bot$, and the probability (over
the inner randomness of $A$) that $A(C)$ outputs $y_{C}$ is at least $2/3$.

## Acknowledgments

Part of the work was done when all authors were participating in the Meta-
Complexity program at the Simons Institute. Lijie Chen is supported by a
Miller Research Fellowship. Shuichi Hirahara is supported by JST, PRESTO Grant
Number JPMJPR2024, Japan. Hanlin Ren received support from DIMACS through
grant number CCF-1836666 from the National Science Foundation. We thank Oliver
Korten, Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam, Roei Tell, and Ryan
Williams for helpful discussions. We also want to thank Jiatu Li, Igor C.
Oliveira, and Roei Tell for comments on an early draft of the paper.

## References

  * [Aar06] Scott Aaronson.  Oracles are subtle but not malicious.  In CCC, pages 340–354. IEEE Computer Society, 2006.  doi:10.1109/CCC.2006.32.
  * [AB09] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach.  Cambridge University Press, 2009.
  * [AKS04] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  PRIMES is in $\P$.  Annals of Mathematics, 160(2):781–793, 2004.  doi:10.4007/annals.2004.160.781.
  * [BCG+96] Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, and Christino Tamon.  Oracles and queries that are sufficient for exact learning.  J. Comput. Syst. Sci., 52(3):421–433, 1996.  doi:10.1006/jcss.1996.0032.
  * [BFL91] László Babai, Lance Fortnow, and Carsten Lund.  Non-deterministic exponential time has two-prover interactive protocols.  Computational Complexity, 1:3–40, 1991.  doi:10.1007/BF01200056.
  * [BFNW93] László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson.  $\BPP$ has subexponential time simulations unless ${\sf EXPTIME}$ has publishable proofs.  Computational Complexity, 3:307–318, 1993.  doi:10.1007/BF01275486.
  * [BFT98] Harry Buhrman, Lance Fortnow, and Thomas Thierauf.  Nonrelativizing separations.  In CCC, pages 8–12, 1998.  doi:10.1109/CCC.1998.694585.
  * [BLS85] Ronald V. Book, Timothy J. Long, and Alan L. Selman.  Qualitative relativizations of complexity classes.  J. Comput. Syst. Sci., 30(3):395–413, 1985.  doi:10.1016/0022-0000(85)90053-4.
  * [BS06] Joshua Buresh-Oppenheim and Rahul Santhanam.  Making hard problems harder.  In CCC, pages 73–87. IEEE Computer Society, 2006.  doi:10.1109/CCC.2006.26.
  * [Cai07] Jin-yi Cai.  $\S_{2}^{p}\subseteq\ZPP^{\NP}$.  J. Comput. Syst. Sci., 73(1):25–35, 2007.  doi:10.1016/j.jcss.2003.07.015.
  * [Can96] Ran Canetti.  More on $\BPP$ and the polynomial-time hierarchy.  Inf. Process. Lett., 57(5):237–241, 1996.  doi:10.1016/0020-0190(96)00016-6.
  * [CCHO05] Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, and Mitsunori Ogihara.  Competing provers yield improved Karp–Lipton collapse results.  Inf. Comput., 198(1):1–23, 2005.  doi:10.1016/j.ic.2005.01.002.
  * [CLO+23] Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam.  Polynomial-time pseudodeterministic construction of primes.  In FOCS, 2023.  To appear.  doi:10.48550/arXiv.2305.15140.
  * [CMMW19] Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams.  Relations and equivalences between circuit lower bounds and Karp–Lipton theorems.  In CCC, volume 137 of LIPIcs, pages 30:1–30:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.CCC.2019.30.
  * [CT21a] Lijie Chen and Roei Tell.  Hardness vs randomness, revised: Uniform, non-black-box, and instance-wise.  In FOCS, pages 125–136, 2021.  doi:10.1109/FOCS52979.2021.00021.
  * [CT21b] Lijie Chen and Roei Tell.  Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost.  In STOC, pages 283–291, 2021.  doi:10.1145/3406325.3451059.
  * [CZ19] Eshan Chattopadhyay and David Zuckerman.  Explicit two-source extractors and resilient functions.  Annals of Mathematics, 189(3):653–705, 2019.  doi:10.4007/annals.2019.189.3.1.
  * [Erd59] Paul Erdős.  Graph theory and probability.  Canadian Journal of Mathematics, 11:34–38, 1959.  doi:10.4153/CJM-1959-003-9.
  * [FHOS93] Stephen A. Fenner, Steven Homer, Mitsunori Ogiwara, and Alan L. Selman.  On using oracles that compute values.  In STACS, volume 665 of Lecture Notes in Computer Science, pages 398–407. Springer, 1993.  doi:10.1007/3-540-56503-5\\_40.
  * [FM05] Gudmund Skovbjerg Frandsen and Peter Bro Miltersen.  Reviewing bounds on the circuit size of the hardest functions.  Information Processing Letters, 95(2):354–357, 2005.  doi:10.1016/j.ipl.2005.03.009.
  * [GG11] Eran Gat and Shafi Goldwasser.  Probabilistic search algorithms with unique answers and their cryptographic applications.  Electron. Colloquium Comput. Complex., TR11-136, 2011.  URL: https://eccc.weizmann.ac.il/report/2011/136.
  * [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali.  How to construct random functions.  Journal of the ACM, 33(4):792–807, 1986.  doi:10.1145/6490.6503.
  * [GGNS23] Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi.  Range avoidance for constant depth circuits: Hardness and algorithms.  In APPROX/RANDOM, volume 275 of LIPIcs, pages 65:1–65:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.APPROX/RANDOM.2023.65.
  * [GLW22] Venkatesan Guruswami, Xin Lyu, and Xiuhan Wang.  Range avoidance for low-depth circuits and connections to pseudorandomness.  In APPROX/RANDOM, volume 245 of LIPIcs, pages 20:1–20:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.APPROX/RANDOM.2022.20.
  * [Gol08] Oded Goldreich.  Computational complexity: a conceptual perspective.  Cambridge University Press, 2008.  doi:10.1017/CBO9780511804106.
  * [GS92] Peter Gemmell and Madhu Sudan.  Highly resilient correctors for polynomials.  Inf. Process. Lett., 43(4):169–174, 1992.  doi:10.1016/0020-0190(92)90195-2.
  * [Hir15] Shuichi Hirahara.  Identifying an honest $\EXP^{\NP}$ oracle among many.  In CCC, volume 33 of LIPIcs, pages 244–263. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.  doi:10.4230/LIPIcs.CCC.2015.244.
  * [HLR23] Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren.  Bounded relativization.  In CCC, volume 264 of LIPIcs, pages 6:1–6:45. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.CCC.2023.6.
  * [HNOS96] Lane A. Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, and Alan L. Selman.  Computing solutions uniquely collapses the polynomial hierarchy.  SIAM J. Comput., 25(4):697–708, 1996.  doi:10.1137/S0097539794268315.
  * [IKV18] Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich.  The power of natural properties as oracles.  In CCC, volume 102 of LIPIcs, pages 7:1–7:20, 2018.  doi:10.4230/LIPIcs.CCC.2018.7.
  * [IKW02] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson.  In search of an easy witness: exponential time vs. probabilistic polynomial time.  J. Comput. Syst. Sci., 65(4):672–694, 2002.  doi:10.1016/S0022-0000(02)00024-7.
  * [IW97] Russell Impagliazzo and Avi Wigderson.  $\P=\BPP$ if $\E$ requires exponential circuits: Derandomizing the XOR lemma.  In STOC, pages 220–229. ACM, 1997.  doi:10.1145/258533.258590.
  * [Jeř04] Emil Jeřábek.  Dual weak pigeonhole principle, Boolean complexity, and derandomization.  Ann. Pure Appl. Log., 129(1-3):1–37, 2004.  doi:10.1016/j.apal.2003.12.003.
  * [Kan82] Ravi Kannan.  Circuit-size lower bounds and non-reducibility to sparse sets.  Inf. Control., 55(1-3):40–56, 1982.  doi:10.1016/S0019-9958(82)90382-5.
  * [KC00] Valentine Kabanets and Jin-Yi Cai.  Circuit minimization problem.  In STOC, pages 73–79, 2000.  doi:10.1145/335305.335314.
  * [KKMP21] Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos Papadimitriou.  Total functions in the polynomial hierarchy.  In ITCS, volume 185 of LIPIcs, pages 44:1–44:18, 2021.  doi:10.4230/LIPIcs.ITCS.2021.44.
  * [KL80] Richard M. Karp and Richard J. Lipton.  Some connections between nonuniform and uniform complexity classes.  In STOC, pages 302–309, 1980.  doi:10.1145/800141.804678.
  * [Kor21] Oliver Korten.  The hardest explicit construction.  In FOCS, pages 433–444. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00051.
  * [Kra01] Jan Krajíček.  Tautologies from pseudo-random generators.  Bull. Symb. Log., 7(2):197–212, 2001.  doi:10.2307/2687774.
  * [Kre88] Mark W. Krentel.  The complexity of optimization problems.  J. Comput. Syst. Sci., 36(3):490–509, 1988.  doi:10.1016/0022-0000(88)90039-6.
  * [KvM02] Adam R. Klivans and Dieter van Melkebeek.  Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses.  SIAM J. Comput., 31(5):1501–1526, 2002.  doi:10.1137/S0097539700389652.
  * [KW98] Johannes Köbler and Osamu Watanabe.  New collapse consequences of $\NP$ having small circuits.  SIAM J. Comput., 28(1):311–324, 1998.  doi:10.1137/S0097539795296206.
  * [LFKN92] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan.  Algebraic methods for interactive proof systems.  Journal of the ACM, 39(4):859–868, 1992.  doi:10.1145/146585.146605.
  * [Li23] Xin Li.  Two source extractors for asymptotically optimal entropy, and (many) more.  In FOCS, 2023.  To appear.  doi:10.48550/arXiv.2303.06802.
  * [Lup58] Oleg B Lupanov.  On the synthesis of switching circuits.  Doklady Akademii Nauk SSSR, 119(1):23–26, 1958.
  * [MVW99] Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe.  Super-polynomial versus half-exponential circuit size in the exponential hierarchy.  In COCOON, volume 1627 of Lecture Notes in Computer Science, pages 210–220. Springer, 1999.  doi:10.1007/3-540-48686-0\\_21.
  * [NW94] Noam Nisan and Avi Wigderson.  Hardness vs randomness.  Journal of Computer and System Sciences, 49(2):149–167, 1994.  doi:10.1016/S0022-0000(05)80043-1.
  * [RS98] Alexander Russell and Ravi Sundaram.  Symmetric alternation captures $\BPP$.  Comput. Complex., 7(2):152–162, 1998.  doi:10.1007/s000370050007.
  * [RSW22] Hanlin Ren, Rahul Santhanam, and Zhikun Wang.  On the range avoidance problem for circuits.  In FOCS, pages 640–650. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00067.
  * [San09] Rahul Santhanam.  Circuit lower bounds for Merlin–Arthur classes.  SIAM J. Comput., 39(3):1038–1061, 2009.  doi:10.1137/070702680.
  * [Sel94] Alan L. Selman.  A taxonomy of complexity classes of functions.  J. Comput. Syst. Sci., 48(2):357–381, 1994.  doi:10.1016/S0022-0000(05)80009-1.
  * [Sha49] Claude E. Shannon.  The synthesis of two-terminal switching circuits.  Bell System technical journal, 28(1):59–98, 1949.  doi:10.1002/j.1538-7305.1949.tb03624.x.
  * [Sud95] Madhu Sudan.  Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, volume 1001 of Lecture Notes in Computer Science.  Springer, 1995.  doi:10.1007/3-540-60615-7.
  * [Val77] Leslie G. Valiant.  Graph-theoretic arguments in low-level complexity.  In MFCS, volume 53 of Lecture Notes in Computer Science, pages 162–176, 1977.  doi:10.1007/3-540-08353-7\\_135.
  * [Vin05] N. V. Vinodchandran.  A note on the circuit complexity of $\PP$.  Theor. Comput. Sci., 347(1-2):415–418, 2005.  doi:10.1016/j.tcs.2005.07.032.
  * [VW23] Nikhil Vyas and Ryan Williams.  On oracles and algorithmic methods for proving lower bounds.  In ITCS, volume 251 of LIPIcs, pages 99:1–99:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi:10.4230/LIPIcs.ITCS.2023.99.


# Partial Disclosure of Private Dependencies in Privacy Preserving Planning

Rotem Lev Lehman1 Guy Shani1&Roni Stern1,2 1Software and Information Systems
Engineering, Ben Gurion University of the Negev, Be’er Sheva, Israel
2Palo Alto Research Center, Palo Alto, CA, USA<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In collaborative privacy preserving planning (cppp), a group of agents jointly
creates a plan to achieve a set of goals while preserving each others’
privacy. During planning, agents often reveal the private dependencies between
their public actions to other agents, that is, which public action facilitates
the preconditions of another public action. Previous work in cppp does not
limit the disclosure of such dependencies. In this paper, we explicitly limit
the amount of disclosed dependencies, allowing agents to publish only a part
of their private dependencies. We investigate different strategies for
deciding which dependencies to publish, and how they affect the ability to
find solutions. We evaluate the ability of two solvers — distribute forward
search and centralized planning based on a single-agent projection – to
produce plans under this constraint. Experiments over standard cppp domains
show that the proposed dependency-sharing strategies enable generating plans
while sharing only a small fraction of all private dependencies.

##  1 Introduction

Designing autonomous agents that act collaboratively to achieve a common set
of goals has been a major goal for Artificial Intelligence research for many
years. _Collaborative Privacy-Preserving Planning_ (cppp) is a multi-agent
planning task in which agents need to achieve a common set of goals without
revealing certain private information (Brafman and Domshlak, 2008). In
particular, in cppp an individual agent may have a set of private facts and
actions that it does not share with the other agents. cppp has important
motivating examples, such as planning for organizations that outsource some of
their tasks, and has recently received considerable attention from the
academic community Nissim and Brafman (2014); Brafman (2015); Torreño et al.
(2017); Tozicka et al. (2017); Maliah et al. (2018); Caspari et al. (2020).

There are two common approaches to cppp: _single search_ and _two-level
search_. Single search solvers run a joint forward search Nissim and Brafman
(2014); Štolba and Komenda (2017) where agents that apply public actions send
the resulting state to other agents that continue the forward search. Two-
level search solvers create a public plan skeleton that is shared by all
agents, and then each agent extends it locally with private actions Maliah et
al. (2015).

In either case, the agents either indirectly or explicitly publish
_dependencies_ between the public actions. For example, in a multiagent Mars
Rover scenario, the need to take a camera from a base station before sending
an image, incurs a private dependency between these public actions. In both
single search and a two-level approach some private dependencies are revealed
during planning. Maliah et al. (2016b) compute and publish all such private
dependencies in the form of artificial facts. This allows the agents to
jointly create and publish a _projection_ of the problem that contains all the
public facts, public actions, and published artificial facts that capture
private dependencies. Such a projection can be used to construct heuristics
for single search cppp algorithms such as mafs. In two-level search solvers,
this projection can be used to generate the public plan, defining the public
plan to be a solution to the problem defined by the projection.

In many cases, however, the agents can construct a plan requiring only a small
portion of the private dependencies. It may be preferable to reveal only a
part of the dependencies, intuitively reducing the amount of disclosed private
information. This raises the challenge of how to choose which private
dependencies to share and which not to. We suggest 4 different heuristic
methods for deciding which dependencies should be published first. We provide
experiments on standard benchmarks from the cppp literature. Our results show
that in many domains using our heuristics allows computing a plan while
publishing only a small portion of the private dependencies. We also analyze
the makespan cost of the plans, showing that for some domains publishing fewer
dependencies does not increase the plan cost significantly.

##  2 Background

An ma-strips problem (Brafman and Domshlak, 2013) is a tuple $\langle
P,\\{A_{i}\\}_{i=1}^{k},I,G\rangle$ where:

  * •

$k$ is the number of agents.

  * •

$P$ is a finite set of primitive propositions (facts).

  * •

$A_{i}$ is the set of actions agent $i$ can perform.

  * •

$I$ is the start state.

  * •

$G$ is the goal condition.

Each action $a=\langle pre(a),\mathit{eff}(a)\rangle$ is defined by its
preconditions ($pre(a)$), and effects ($\mathit{eff}(a)$). Preconditions and
effects are conjunctions of primitive propositions and literals, respectively.
A state is a truth assignment over $P$. $G$ is a conjunction of facts. $a(s)$
denotes the result of applying action $a$ to state $s$. A plan
$\pi=(a_{1},\ldots,a_{k})$ is a solution to a planning task iff $G\subseteq
a_{k}(\ldots(a_{1}(I)\ldots)$.

Privacy-preserving ma-strips extends ma-strips by defining sets of variables
and actions as private, known only to a single agent. $private_{i}(P)$ and
$private_{i}(A_{i})$ denote the variables and actions, respectively, that are
private to agent $i$. $public(P)$ is the set of public facts in $P$.
$public_{i}(A_{i})$, the complement of $private_{i}(A_{i})$ w.r.t. $A_{i}$, is
the set of public actions of agent $i$. Some preconditions and effects of
public actions may be private, and the action obtained by removing these
private elements is called its public projection, and it is known to other
agents. When a public action is executed, all agents are aware of the
execution, and view the public effects of the action. The goals can be public,
but can also be private to a single agent. An agent is aware only of its local
view of the problem, that is, its private actions and facts, its public
actions, the public facts, and the public projection of the actions of all
other agents. That is, for public actions of other agents, the agent’s local
view contains only the public preconditions and effects of these actions.

Figure 1: The rovers domain, with 2 base stations $b_{1}$ and $b_{2}$, and 2
rovers, $r_{1}$ and $r_{2}$, collaborating to take measurements of a rock.

In a Rovers example (Figure 1), 2 Mars Rovers collaborate to explore Mars
rocks. The Rovers need to perform sensor measurements on rocks, and, due to
limited carriage capacity, can only carry 2 sensors at a time. Unused sensors
are stored in base stations, and can be taken and returned to the base
stations as needed. The public facts in this problem are the sensors located
in bases, and the current condition of the target rock. The public actions are
taking and returning sensors to the base stations, putting collected rock
samples at the base stations, and performing various examination actions on
rocks, such as taking an image, mining a mineral, or collecting a sample. The
sensors held by a rover and its position are private, and the private actions
are movement actions.

###  2.1 Privacy Models

An algorithm is privacy-preserving, if it provably does not “reveal private
information”. Much of the research on privacy-preserving planning considered
revealing private information only if the information is explicitly
communicated to another agent. For example, if an agent publishes during
planning that it intends to drive rover $r_{1}$ from the base $base_{1}$ to
the rock $rock_{1}$, then clearly the agent has revealed the existence of
$r_{1}$, as well as an ability to achieve the private fact (at $r_{1}$
$rock_{1}$), breaking the privacy constraint. However, if the agent only
publishes that it can achieve a private fact with the obfuscated name $p$,
then it is unclear what private information has been revealed. Thus, some
privacy-preserving MA-STRIPS planners are built on obfuscating the private
information they publish by applying some cryptographic tool (Luis and
Borrajo, 2014; Borrajo and Fernandez, 2015).

Brafman (2015) shows that the above form of privacy is weak, in the sense that
there is no well-formed constraint on what other agents can infer from the
information available to them. For example, if the public plan consists of
agent $i$ taking a camera and the take action requires a rover to be present
at the base that contains the camera, then all agents now know that $i$
controls at least one rover. Brafman considered a stronger form of privacy,
where a fact or a specific value of a fact is strongly private if other agents
cannot deduce its existence from the available information.

By “deducing the existence” of a private fact, we mean that regardless of the
reasoning power of the agents, they cannot infer the existence of a strongly
private fact from the available information. The information available to an
agent is (1) its local view of the problem, (2) the messages between the
agents during planning, and (3) the sequence of public actions (of all agents)
in the resulting plan. A multi-agent planning algorithm is said to be strongly
privacy preserving if the only information that agents can deduce, following
the execution of the algorithm, is information that is implied by the public
projection, their local view, and the public part of the solution (Brafman,
2015).

While appealing, achieving such a strong form of privacy may be difficult. In
fact, only two algorithms proven so far have this strict form of privacy:
Secure mafs (Brafman, 2015) and two special variants of PSM (Tozicka et al.,
2017). Even these algorithms preserve this form of privacy only under
restrictive conditions. For example, secure mafs was shown to preserves strong
privacy in a short list of specific domains (logistics, satellites, rovers),
having unit action cost and when the heuristic function ignores the private
state.

Thus, using more informed heuristics, such as the dependencies preserving
projection heuristic (Maliah et al., 2016c) that we discuss later in the
article, may violate the strong privacy of Secure MAFS. The current planners
that preserve strong privacy are either inefficient or incomplete (Tozicka et
al., 2017; Stolba et al., 2016). Inefficiency in this context is that for any
ma-strips problem, all public solutions to all local views must be computed
before a solution is returned. Tozicka et al. (2017) suggested considering
cases where an algorithm maintains strong privacy for a class of problems.

Researchers have offered other definitions of privacy aside from the two
extreme cases of weak and strong privacy. Maliah et al. (2016a) suggest that
an agent should only be aware of neighboring agents that modify a subset-
private fact that the agent uses as precondition or effect. An algorithm
preserves agent privacy if no agent can infer the existence of another agent
with which it does not share subset-private facts.

Alternatively, Maliah et al. (2016c) suggest that agents may be aware of the
types of objects that other agents manipulate, but not of their cardinality.
In the rovers example, even though all agents may be aware that rovers carry
tools between the base and the rocks, they should not be aware of the number
of rovers, or the amount of tools in the rovers’ storage. An algorithm
preserves cardinality privacy if no agent can infer the number of private
objects controlled by another agent. In our running example, no agent should
know whether $agent_{1}$ controls 1 or 2 rovers.

Finally, instead of designing binary privacy criteria, one can consider more
refined privacy metrics, that quantify the amount of leaked information
(Štolba et al., 2018). For example, in distributed search (Maheswaran et al.,
2006) one often quantifies information loss using the entropy over the
possible state space. In that case, it may be possible for an application
designer to sacrifice some privacy in favor of efficiency, such as the ability
to scale up to larger problems. The trade-off between privacy loss and
efficiency is also studied in our paper, where privacy loss is quantified by
the amount of revealed private dependencies and efficiency is measured by
coverage and plan cost.

###  2.2 Algorithmic Approaches

We provide here a brief background on the two main approaches for cppp:
_single search_ and _two-level search_. Single search algorithms for cppp work
by running a distributed forward search algorithm in which each agent searches
for a plan using its own action space, and agents informs other agents of
advancements in the search process by sending and receiving the states they
have reached. mafs (Nissim and Brafman, 2014) is a well-known example of a
single-search algorithm for cppp. In mafs each agent runs a best-first forward
search to reach the goal and maintains its own open list of states. In every
iteration, each agent chooses a state in its open list to expand, generates
all its children, and adds them to its open list (avoiding duplicates).
Whenever an agent expands a state that was generated by applying a public
action, it also broadcasts this state to all other agents. When an agent
receives a broadcasted state, it adds that state to its open list. For
example, in Figure 1, when agent $1$ puts down the camera at base $b_{2}$, it
broadcasts this state to all other agents. Agent $2$ can now use this state to
pick up the camera and take a photo of a rock. To preserve privacy, the
private part of a state is obfuscated when broadcasting it by replacing the
private facts with an index. Only the broadcasting agent knows how to map this
index to the corresponding private facts. Once the goal is reached, the agent
achieving the goal informs all others.

Two-level search algorithms for cppp work by computing a public plan, known as
a coordination scheme (Nissim and Brafman, 2014; Brafman and Domshlak, 2013;
Torreno et al., 2014), and then have each agent independently extend the
public plan into a complete plan by adding private actions. In this extension
each agent attempts to achieve the preconditions of its own public actions in
the public plan. The Dependency Projection Planner (DPP) (Maliah et al., 2018)
is an example of a two-level search algorithm. In DPP, the agents compute
together a single agent projection of the cppp problem that captures the
dependencies between public actions. This projection, referred to as the _DP
projection_ , captures for each agent which public actions facilitate the
execution of other public actions of that agent. In our running example, such
a dependency exists, e.g., for agent $1$ between picking up a camera at base
$b_{1}$ and taking a photo of the rock. These dependencies are computed using
limited regression from the precondition of a public action to the effects of
other public actions. One can compute a public plan over the projection using
a standard classical planner. The projection is incomplete, and hence the
generated public plan may not be extended to a complete plan.

##  3 Partial Disclosure of Private Dependencies

We now present the main contribution of this paper — reducing the amount of
disclosed private dependencies and hence, the amount of disclosed information.
In this paper, we discuss this in the context of two state-of-the-art methods:
mafs Nissim and Brafman (2014) and DPP Maliah et al. (2018). We first describe
our methods in the context of DPP, and then discuss their application to mafs.

DPP works by generating a DP projection that is shared between all agents. For
ease of exposition, we describe a brief and slightly modified version of the
DP projection. We say that a public action $a$ facilitates the achievement of
a private fact $f$, if (1) $f$ is an effect of $a$, or (2) there exists a
sequence of private actions $a_{1},...,a_{k}$ such that: $f$ is an effect of
$a_{k}$, each $a_{i}$ takes as precondition an effect of some $a_{j}$ s.t.
$j<i$, and $a_{1}$ takes as precondition an effect of $a$.

######  Definition 1 (Private Dependency).

An action $a$ is said to have a private dependency if it has a private fact
$f$ as a precondition such that one of the following hold: (1) there is
another public action $a^{\prime}$ that facilitates achieving $f$, (2) $f$ is
either true in the start state or can be achieved from it by only applying
private actions.

In the rovers example take-image$(rover_{1},rock_{1})$ has a private
dependency because it has a private precondition
holding$(rover_{1},camera_{1})$ that the public action
take$(rover_{1},camera_{1},base_{1})$ facilitates to achieve.

The agents jointly create a projection of the public problem, containing all
the public facts, and a projected version of the public actions. For each
public action $a_{i}$ that requires a private precondition $f_{j}$, we create
an artificial public fact $f^{i}_{j}$. The projected public version of $a$
requires $f^{i}_{j}$ as precondition. For each action $a^{\prime}$ of the
agent that facilitates the achievement of the private $f_{j}$, the agent
publishes $f^{i}_{j}$ as an effect of $a^{\prime}$, thus publishing the
private dependency of $a$ on $a^{\prime}$, although the way that $f_{j}$ is
achieved remains obscured.

For a public action $a_{1}$ of an agent $i$ we add to the projection a public
artificial fact $f_{a_{1}}$, signifying that $a_{1}$ was executed. If $a_{1}$
facilitates the achievement of a private precondition of an action $a_{2}$ of
$i$, then the projected $a_{2}$ will have $f_{a_{1}}$ as precondition. These
artificial facts $f_{a}$ capture private dependencies between public actions.

In DPP Maliah et al. (2016b), the agents compute and publish all their private
dependencies. In this work, we limit the number of private dependencies of
each agent is allowed to publish to $k$, where $k$ is a parameter.
Technically, each agent publishes all the artificial preconditions of all
public actions, as well as $k$ artificial effects of public actions. All
public preconditions are published to avoid an over optimistic projection,
where agents believe that they can execute public actions with no previous
requirements.

In mafs Nissim and Brafman (2014), each agent decides which dependencies it is
willing to disclose, but it does not publish them. Instead, these dependencies
are considered in mafs when it generates states and when it computes heuristic
values for a state. A state is only expanded if it does not reveal a
dependency that is not disclosed, and it only considers published dependencies
when computing heuristics for states. Further details on how mafs considers
the disclosed set of dependencies is given in section 3.3.

Figure 2: Local perspective of agent 1 private dependencies in the Rovers
domain. Each node $n$ is marked with a unique identifier colored red.
$r_{1}=rover_{1},c_{1}=camera_{1},b_{i}=base_{i},md_{1}=mineral\\_detector_{1}$

###  3.1 Ranking Published Dependencies

We now discuss how to choose which $k$ private dependencies to share. We
suggest 4 different methods for selecting which dependencies to publish first.
We take an iterative approach — all agents publish one artificial effect of
one public action at each iteration. Our methods assign a heuristic score to
each dependency. The artificial effect with the highest score is published at
each iteration. If the public projection cannot be solved, all agents
recompute the heuristic scores, and publish a second artificial effect of a
public action, and so forth. Hence, at each iteration an agent recomputes the
scores, given the effects it has published thus far.

To better illustrate our methods, Figure 2 shows the local perspective of the
private dependencies of agent 1 in the Rovers domain. Black nodes in the first
and third columns represent public actions, purple nodes in the fourth column
represent public facts, and blue nodes in the second column denote artificial
facts that capture private dependencies between public actions. The public
actions on the first column generate the artificial facts while the public
actions on the third column require them as preconditions, and generate the
public facts. Our methods always publish one of the black edges in the graph,
between a public action and an artificial fact that it can generate. The blue
and purple edges (artificial preconditions and public effects) are always
known.

Our first method, which we denote $m_{1}$, publishes artificial effects that
are used as preconditions in as many public actions as possible. Initially the
score of an artificial effect is set to the out-degree of the artificial fact.
In the example in Figure 2, we can publish either the effect of $n_{1}$, or
the effect of $n_{2}$, representing taking the camera from either base, as it
supplies a precondition for 3 public actions ($n_{10}$, $n_{11}$, $n_{12}$).
Let us assume that the effect of $n_{1}$ was published first.

We want to avoid choosing to publish the effect of $n_{2}$ at the next
iteration, encouraging facilitating additional preconditions. We hence
decrease from the score of an edge $\langle n_{i},n_{j}\rangle$ by the number
of incoming edges to the artificial fact $n_{j}$ that were already published.
In our example, at the next step, all unpublished effects have the same
ranking.

The second method, which we denote $m_{2}$, publishes an effect that enables
the achievement of as many public facts as possible, denoted by outgoing
purple edges in Figure 2. An effect enables the achievement of a public fact
$f$ if it is a precondition to an action that achieves $f$. In $m_{2}$ we set
the score of a black edge to the number of paths that lead from the edge to a
public fact (purple node). Again, at each iteration we decrease the score by
number of incoming edges that were published to avoid repeatedly choosing the
same effect. In our example all edges have the same score (3) at the first
iteration. If we again select at the first iteration the effect of $n_{1}$, at
the second iteration we will select either $n_{8}$ or $n_{9}$.

The third method, denoted $m_{3}$, maximizes the amount of public actions that
can be executed. That is, instead of publishing the artificial fact that
provides a precondition for several actions, we publish the artificial fact
that enables as many public actions as possible. Here, in the first iteration,
publishing the effect of taking the camera from either base ($n_{7}$), or the
effect of clearing the storage of the rover ($n_{9}$), both enable immediately
one public action ($n_{10}$, and $n_{13}$, respectively). If we first select,
again, $n_{1}$, at the next iteration, taking the mineral detector from either
base station (producing $n_{8}$) or clearing the storage (producing $n_{9}$),
both enable one additional action ($n_{11}$ and $n_{13}$ respectively), and
are hence tied.

In this method we also need to balance between enabling new public actions
that have not been available given the already published effects, and enabling
new ways to apply already possible actions, that may result in better plans.
As such, for each action $a$ that is enabled by the published effect, we
discount its score by $\frac{1}{c_{a}+1}$ where $c_{a}$ is the number of times
that $a$ was enabled by previously published facts. Hence, at the first time
that an action is enabled, it provides a score of 1, at the second time, a
score of $\frac{1}{2}$, and so forth.

The last method, denoted $m_{4}$, is similar to $m_{3}$, but focuses not on
the public actions, but on the public effects. That is, we publish an effect
that enables achieving as many public facts (purple nodes) as possible. Again,
we discount the score of a public fact by $\frac{1}{c_{f}+1}$ where $c_{f}$ is
the number of times that public fact $f$ was enabled by previously published
facts. In this method, again any incoming edge to $n_{7}$ and $n_{9}$ are tied
in the first iteration. In the second iteration, however, if we again select
$n_{1}$ first, taking the mineral detector (producing $n_{8}$) has a better
score, because it enables the mineral drilling action ($n_{11}$), that has 2
public effects $n_{15}$, and $n_{14}$ that was already obtained, and hence a
score of $1\frac{1}{2}$.

###  3.2 The Implications of Adding Dependencies

A DP projection $\Pi$ is a single-agent problem. Let $plans(\Pi)$, $opt(\Pi)$,
and $states(\Pi)$ be the set of plans for $\Pi$, the cost of an optimal plan
for $\Pi$, and the number of reachable states in $\Pi$, respectively. For two
DP projections $\Pi$ and $\Pi^{\prime}$ of the same problem, we say that
$\Pi^{\prime}$ _subsumes_ $\Pi$, denote by $\Pi\subseteq\Pi^{\prime}$, iff the
set of private dependencies shared by $\Pi$ is a subset of the set of private
dependencies shared by $\Pi^{\prime}$.

######  Corollary 1.

For any two DP projections $\Pi$ and $\Pi^{\prime}$ such that
$\Pi\subseteq\Pi^{\prime}$ it holds that: (1) $plans(\Pi)\subseteq
plans(\Pi^{\prime})$, (2) $opt(\Pi^{\prime})\leq opt(\Pi)$, and (3)
$states(\Pi)\leq states(\Pi^{\prime})$.

This observation highlights the tradeoff we face when revealing more private
dependencies. On the one hand, revealing more dependencies has the potential
to solve more problems since more plans are reachable and find lower-cost
solutions. On the other hand, DP projections created by revealing more
dependencies are, in general, harder to solve, since its corresponding state
space is larger. Corollary 1 is directly applicable to all the heuristic
methods described above for choosing which dependencies to share. For all
methods ($m_{1}$, $m_{2}$, $m_{3}$, and $m_{4}$), increasing the number of
dependencies that can be published ($k$) results in a DP projection that
subsumes the DP projection created by publishing fewer dependencies. Indeed,
we observe the aforementioned trade-off in our experimental results.

###  3.3 Partial Disclosure of Dependencies in mafs

In this section, we provide more details on how we implemented partial
disclosure of private dependencies in mafs (Nissim and Brafman, 2014).

1

2 MAFS($r_{i}$)

3 Initialize a set of dependencies $D$ that are not allowed to be revealed

4 Insert $I$ into open list

5 while  _solution not found_ do

6 foreach message $m$ call process-message($m$)

7 $s\leftarrow$ extract-min(open list)

8 expand($s$)

9

10

11 process-message($m=\langle s,g_{j}(s),h_{j}(s)\rangle$)

12

13 if  _$s$ is not in open or closed list $\vee$ $g_{i}(s)>g_{j}(s)$ _ then

14 add $s$ to open list and calculate $h_{i}(s)$

15 $g_{i}(s)\leftarrow g_{j}(s)$

16 $h_{i}(s)\leftarrow max(h_{i}(s),h_{j}(s))$

17

18 expand($s$)

19 move $s$ to closed list

20 if  _$s$ is a goal state_ then

21 broadcast $s,g_{i}(s),h_{i}(s)$ to all agents

22 return $s$ as the solution

23 $a\leftarrow$ the action that generated $s$

24 if  _$a$ is a public action_ then

25 $a^{\prime}\leftarrow$ the public action preceding $a$

26 if  _$\langle a^{\prime},a\rangle\notin D$_ then

27 send $s$ to all relevant agents

28 else

29 return // stop expansion of s

30 apply $r_{i}$’s successor operators to $s$

31 foreach  _successors $s^{\prime}$_ do

32 compute $h_{i}(s^{\prime})$

33 if  _$s^{\prime}$ is not in closed list or $h_{i}(s^{\prime})$ has
improved_ then

34 add $s^{\prime}$ to open list

35

Algorithm 1 MAFS for agent $r_{i}$

An agent running mafs (Algorithm 1) searches its own local space. Whenever
agent $i$ executes a public action it broadcasts a message $m=\langle
a_{p},s_{p},idx_{1},...,idx_{n}\rangle$ containing the executed public action
$a_{p}$, the resulting public state $s_{p}$ to all other agents, with a
private state index $idx_{k}$ for every agent $k$. Agent $i$ can now continue
searching from that state. If, in the same search path, agent $i$ executes
another public action it will send a new message $m^{\prime}=\langle
a^{\prime}_{p},s^{\prime}_{p},idx_{1},...,idx_{n}\rangle$. The private state
indexes in $m^{\prime}$ for all agents, except $i$ are identical to the
indexes in $m$.

An agent $j$ that receives both messages $m$ and $m^{\prime}$ can compare them
and identify that only the public state, and the state index for $i$, have
changed. Thus, agent $j$ can know that message $m^{\prime}$ contains a state
that was generated in the same search path after $m$. This may reveal to agent
$j$ a private dependency of agent $i$ between $a_{p}$ and $a^{\prime}_{p}$.

To limit the private dependencies that are revealed in mafs, each agent must
initially decide on which dependencies it does not reveal (Line 1 in Algorithm
1). Then, whenever the situation above occurs, if there is a dependency for
agent $i$ between $a_{p}$ and $a^{\prime}_{p}$ that it does not wish to
disclose, it will not broadcast $m^{\prime}$ (Line 1 in Algorithm 1). Agent
$i$ will not continue searching from the state that $m^{\prime}$ represents,
because even if we find a plan that uses that state, the final plan will leak
the dependency we did not wish to disclose. This modification — limiting the
broadcasted states — allows mafs to perform a joint search disclosing only
some dependencies.

One can also envision an iterative method, where initially, all agents attempt
solving without revealing any dependencies. If the agents are unable to
produce a solution, each agent reveals one dependency, and so forth. To avoid
repeated expansions, each agent can save the unbroadcasted states mapped by
the undisclosed dependency which was the reason that the state was not
broadcasted. When revealing a new dependency, the agent can publish all the
states that were not previously published due to the newly unrevealed
dependency. We leave further exploration of this idea to future research.

Domain | #dep | Joint Projection | MAFS
---|---|---|---
$m_{1}$ | $m_{2}$ | $m_{3}$ | $m_{4}$ | $m_{1}$ | $m_{2}$ | $m_{3}$ | $m_{4}$
$\\#C$ | $M_{D}\%$ | $\\#C$ | $M_{D}\%$ | $\\#C$ | $M_{D}\%$ | $\\#C$ | $M_{D}\%$ | $\\#C$ | $M_{D}\%$ | $\\#C$ | $M_{D}\%$ | $\\#C$ | $M_{D}\%$ | $\\#C$ | $M_{D}\%$
BlocksWorld | 1225 | 19 | 53% | 19 | 53% | 19 | 62% | 19 | 62% | 14 | 69% | 14 | 69% | 14 | 69% | 14 | 69%
Depot | 6753 | 20 | 35% | 20 | 45% | 20 | 40% | 20 | 40% | 20 | 70% | 20 | 70% | 20 | 75% | 20 | 75%
Driverlog | 5060 | 19 | 8% | 18 | 13% | 19 | 38% | 18 | 32% | 18 | 17% | 18 | 17% | 18 | 50% | 18 | 50%
Elevators | 6245 | 20 | 20% | 20 | 20% | 20 | 5% | 20 | 60% | 20 | 51% | 20 | 51% | 20 | 13% | 20 | 60%
Logistics | 150 | 21 | 10% | 21 | 15% | 21 | 10% | 21 | 15% | 20 | 10% | 20 | 15% | 20 | 10% | 20 | 15%
Rovers | 42155 | 20 | 5% | 20 | 5% | 19 | 11% | 17 | 17% | 20 | 5% | 20 | 5% | 19 | 11% | 17 | 17%
ZenoTravel | 1320 | 17 | 25% | 16 | 4% | 18 | 55% | 18 | 5% | 18 | 85% | 17 | 4% | 17 | 4% | 18 | 5%

Table 1:  Coverage and disclosed dependencies for the projection method and
mafs. #dep is the maximal amount of dependencies for a problem in the domain.
$\\#C$ is the coverage for each heuristic $m_{1},...,m_{4}$. $M_{D}\%$ is the
percentage of the minimal amount of disclosed dependencies that allows solving
the most problems. The heuristic with the minimal $M_{D}\%$ for each domain is
in bold.

(a) Elevators, max dep = 6245

(b) Blocksworld, max dep = 1225

(c) Depot, max dep = 6753

(d) Rovers, max dep = 42155

(e) Logistics, max dep = 150

(f) Driverlog, max dep = 5060

(g) ZenoTravel, max dep = 1320

(h) Legend.

Figure 3: # of solved problems for each amount of published dependencies in
the Joint projection method.

(a) Elevators, max dep = 6245

(b) Blocksworld, max dep = 1225

(c) Depot, max dep = 6753

(d) Rovers, max dep = 42155

(e) Logistics, max dep = 150

(f) Driverlog, max dep = 5060

(g) ZenoTravel, max dep = 1320

(h) Legend.

Figure 4: # of solved problems for each amount of published dependencies in
the mafs method.

(a) Elevators

(b) BlocksWorld

(c) Depot

(d) Rovers

(e) Logistics

(f) Driverlog

(g) ZenoTravel

Figure 5: Single agent dependency graphs for all domains. All of the
dependencies graphs are drawn for the easiest problem of the domain. Each
dependencies graph has the same layers as described previously. The size of
the nodes in the first and second layers, is their _out-degree_ , and the size
of the nodes in the third and fourth layers is their _in-degree_. There is
also a special action that is a dummy-init-action in each domain, that action
is at the bottom of the first actions layer. The dummy-init-action does not
appear in Logistics and ZenoTravel, because it does not have any dependency
with another public action in these domains.

##  4 Empirical Analysis

We now evaluate our methods using standard benchmarks Štolba et al. (2015).
For each problem in each domain, we ran the projection-based solver Maliah et
al. (2016b) and the revised mafs, both with a growing number of revealed
dependencies. We denote the first as “joint projection” and the latter as
“mafs”. The methods were implemented in C# and run on a Windows machine with
an i7-8700 3.20GHz CPU with 6 cores, and 16 GB of RAM.

In every experiment, we started without disclosing any private dependencies
and run the chosen solver, recording whether it was able to solve the problem
and, if so, the resulting plan makespan cost. We repeat this process,
disclosing new private dependencies, running the solver, and recording the
same statistics. Then, we compute the average solution cost and the number of
solved problems under a timeout of 5 minutes. This value is referred to as
_coverage_.

#### Coverage Results

Table 1 shows the coverage results for the different solvers using the
different heuristics $m_{1}$, $m_{2}$, $m_{3}$, and $m_{4}$. As can be seen,
$m_{3}$, maximizing the number of public actions that can be executed,
performs the best for Elevators, for both joint projection and mafs solvers by
an order of magnitude. In BlocksWorld with the joint projection solver,
$m_{3}$ and $m_{4}$ perform worse than $m_{1}$ and $m_{2}$, but it is only
because of a single problem that was solved faster by $m_{1}$ and $m_{2}$. The
rest of the problems required less dependencies by $m_{3}$ and $m_{4}$, as can
be seen in figure 3(b). In Driverlog, $m_{3}$ performs worse than $m_{1}$. In
this domain, 16 problems were solved with exactly the same amount of
dependencies for all heuristics. The last 3 problems required more
dependencies in $m_{3}$ than in $m_{1}$. In Logistics and ZenoTravel, all
methods performed the same (except of one difficult problem). In Rovers,
$m_{4}$ performs the worst, and all other methods perform almost the same
(again, except of one problem). In general, mafs is slightly worse than the
projection, and requires more dependencies in order to solve the problems.

Figure 3 shows the number of problems that were solved on each domain given
the number of revealed dependencies by each agent in the projection-based
solver. For each problem, we also computed a “Hindsight value”, which is the
number of private dependencies used by the plan that was generated when all
dependencies are known. The hindsight is a baseline for comparison, indicating
how many private dependencies are enough to find a solution. The hindsight may
not be optimal, and it may be possible to provide a solution with fewer
dependencies. We also report a method that randomly decides which dependency
to disclose, averaged over 10 runs.

Domain | M | Joint projection | MAFS
---|---|---|---
Min | Max | Min. dep | Max. dep | Imp. | Min | Max | Min. dep | Max. dep | Imp.
BlocksWorld | m1 | 48.95 | 111.75 | 92.10 | 55.15 | 45.39% | 29.33 | 30.93 | 30.07 | 30.20 | 1.93%
m2 | 51.15 | 95.65 | 79.50 | 55.15 | 36.25% | 29.33 | 30.93 | 30.07 | 30.20 | 1.93%
m3 | 47.35 | 99.65 | 83.20 | 50.10 | 43.05% | 28.57 | 31.64 | 29.57 | 30.64 | 2.98%
m4 | 47.65 | 97.95 | 81.60 | 50.10 | 42.61% | 28.57 | 31.64 | 29.57 | 30.64 | 2.98%
Depot | m1 | 21.35 | 29.50 | 28.75 | 21.55 | 21.61% | 21.15 | 21.70 | 21.25 | 21.55 | 1.13%
m2 | 21.35 | 29.45 | 28.40 | 21.55 | 19.73% | 21.15 | 21.65 | 21.20 | 21.55 | 0.71%
m3 | 21.45 | 28.90 | 28.45 | 21.55 | 19.18% | 21.25 | 21.65 | 21.30 | 21.55 | 0.71%
m4 | 21.45 | 29.05 | 28.60 | 21.55 | 20.26% | 21.25 | 21.65 | 21.30 | 21.55 | 0.71%
Driverlog | m1 | 28.89 | 63.63 | 61.42 | 29.32 | 32.82% | 21.11 | 23.56 | 22.39 | 22.67 | 6.48%
m2 | 22.22 | 43.61 | 41.28 | 22.67 | 30.10% | 21.61 | 23.50 | 22.61 | 22.67 | 5.91%
m3 | 39.21 | 58.63 | 57.00 | 39.47 | 23.98% | 21.17 | 23.39 | 22.17 | 22.67 | 5.91%
m4 | 22.44 | 46.33 | 44.61 | 22.67 | 28.31% | 21.17 | 23.39 | 22.06 | 22.67 | 5.55%
Elevators | m1 | 33.50 | 53.10 | 37.45 | 46.90 | 10.67% | 37.25 | 61.75 | 39.90 | 55.70 | 6.88%
m2 | 33.55 | 54.45 | 39.15 | 46.90 | 16.08% | 39.35 | 61.40 | 42.65 | 55.70 | 9.67%
m3 | 33.00 | 51.25 | 38.35 | 46.90 | 13.38% | 33.60 | 58.90 | 36.10 | 55.70 | 6.36%
m4 | 34.75 | 51.75 | 38.35 | 46.90 | 10.20% | 37.55 | 60.50 | 40.90 | 55.70 | 9.19%
Logistics | m1 | 25.05 | 31.29 | 27.24 | 29.24 | 6.40% | 25.15 | 31.95 | 27.85 | 29.35 | 8.04%
m2 | 25.05 | 31.29 | 26.81 | 29.24 | 5.33% | 25.15 | 31.95 | 27.35 | 29.35 | 6.75%
m3 | 25.00 | 31.24 | 27.24 | 29.24 | 6.62% | 25.15 | 31.95 | 27.85 | 29.35 | 8.07%
m4 | 25.00 | 31.24 | 26.81 | 29.24 | 5.55% | 25.15 | 31.95 | 27.35 | 29.35 | 6.79%
Rovers | m1 | 49.50 | 53.00 | 52.40 | 50.25 | 6.07% | 57.50 | 62.30 | 61.45 | 58.35 | 8.12%
m2 | 50.25 | 51.50 | 51.50 | 50.25 | 3.28% | 58.25 | 60.40 | 60.40 | 58.35 | 4.99%
m3 | 51.74 | 68.42 | 67.58 | 52.84 | 22.68% | 60.26 | 83.05 | 82.00 | 62.37 | 26.83%
m4 | 51.53 | 64.35 | 63.35 | 52.53 | 18.26% | 58.00 | 77.41 | 77.41 | 58.41 | 24.41%
ZenoTravel | m1 | 45.12 | 56.12 | 47.59 | 54.41 | 9.32% | 52.44 | 63.11 | 55.00 | 61.28 | 8.96%
m2 | 37.31 | 50.63 | 39.81 | 48.81 | 9.81% | 44.06 | 56.53 | 46.65 | 54.59 | 9.39%
m3 | 51.83 | 62.83 | 54.61 | 60.72 | 8.69% | 45.24 | 56.71 | 47.94 | 54.59 | 9.06%
m4 | 51.83 | 62.83 | 54.61 | 60.72 | 8.69% | 52.33 | 63.39 | 55.11 | 61.28 | 8.69%
Average | m1 | 36.05 | 56.91 | 49.56 | 40.97 | 18.90% | 34.85 | 42.19 | 36.84 | 39.87 | 5.93%
m2 | 34.41 | 50.94 | 43.78 | 39.22 | 17.23% | 34.13 | 40.91 | 35.85 | 38.91 | 5.62%
m3 | 38.51 | 57.27 | 50.92 | 42.98 | 19.66% | 33.61 | 43.90 | 38.13 | 39.55 | 8.56%
m4 | 36.38 | 54.79 | 48.28 | 40.53 | 19.13% | 34.86 | 44.28 | 39.10 | 39.94 | 8.33%
Table 2: Averaged plan makespan cost over all of solved problems for each
domain. Min denotes the average minimal cost over all solved problems. Max
denotes the average maximal cost. Min. dep denotes the cost when solved with
the minimal amount of disclosed dependencies. Max. dep denotes the cost when
solved with the maximal amount of disclosed dependencies. Imp. denotes
improvement between the first time that the problem was solved to the best
achieved solution. The lowest improvement, and hence best initial plan, is in
bold.

$m_{3}$, which prioritizes enabling additional public actions, performs the
best in all domains. The rest of the methods vary in their performance. On
Blocksworld, e.g., $m_{4}$, that prioritizes achieving additional public
facts, is the best together with $m_{3}$, but on Elevators and Rovers $m_{4}$
performs the worst. On Elevators, arguably the domain with the highest amount
of required collaboration, differences between methods are most pronounced. On
Depot, random dependencies have identical performance as the heuristics,
except for 2 problems, where the random selection did not identify needed
dependencies.

Figure 5 shows agent’s dependency graphs (Section 3.1). In BlocksWorld and
Elevators, $m_{3}$ performs the best due to an artificial effect that is
precondition to many actions, manifesting as a larger blue node in Figure 5.
$m_{1}$ and $m_{2}$ reveal this artificial effect numerous times, instead of
other useful effects, while $m_{3}$ reveals this effect once, and publishes
other effects to achieve more actions.

$m_{4}$ performs very well on BlocksWorld but poorly on Elevators and Rovers.
This is because BlocksWorld has some public facts that are easier to achieve,
as they are achieved by many actions (denoted by larger purple nodes). $m_{4}$
avoids publishing additional ways to achieve these facts, and can hence allow
achieving other useful public facts. In the other domains, most public facts
have almost the same number of actions that can achieve them. $m_{4}$ cannot
distinguish between these dependencies. Hence, an analysis of the agent’s
dependency graph can reveal whether $m_{3}$ or $m_{4}$ can be more useful.
$m_{4}$ performs better under diverse in-degree for the purple nodes, while
$m_{3}$ performs better given a uniform in-degree.

On Depot all methods perform much worse than the hindsight, and very similar
to the random solver, leaving much room for improvement. Looking at the
dependency graph (Figure 5(c)), for each public fact (purple node) there is a
very small number of paths to it. Hence, practically every dependency seems
equally important to all heuristics, yet many of them are not useful for
achieving the goal.

An interesting phenomenon occur in, e.g., BlocksWorld and Rovers, where some
problems are solved when not all dependencies are available, but cannot be
solved when more dependencies are published. This is because the projection
method may produce a public plan that cannot be extended into a complete plan,
and we did not backtrack. Our methods were often able to publish dependencies
that resulted in plans that could be extended. Later, additional dependencies
confused the planner to choose plans that could not be extended.

Figure 4 shows the number of problems that were solved on each domain given
the number of revealed dependencies by each agent using mafs. As in the
projection-based solver, $m_{3}$ seems to be the best here in all the domains.
In mafs, for Elevators the difference between the heuristic methods is most
pronounced. mafs performed worse than the projection method in our
experiments, but in BlocksWorld the results are very poor, as mafs timed out
on many problems. This happened because the projection method was better at
identifying plans with very little agent collaboration, while mafs tended to
identify plans here with significantly more collaboration.

#### Plan Cost Results

Finally, we consider the makespan cost of the generated public plan.
Dependencies affect not just solvability but also cost. Even when a plan could
be obtained without revealing any dependency, better plans may be obtained by
collaboration, revealing some dependencies. Thus, agents may trade off some
privacy for increased efficiency.

Table 2 shows the results of the following averaged factors: (1) Min. cost,
(2) Max. cost, (3) Min. dep. cost — the solution cost for a plan found with
the least amount of revealed dependencies, and (4) Max. dep. cost – the
solution cost for a plan that was found with the maximal amount of
dependencies revealed. The “Improvement” column shows the percentage of the
minimal cost out of the Min. dep. cost $(\frac{Min.\,dep.\,cost-
Min.\,cost}{Min.\,dep.\,cost}*100\%)$. That is, how much cost can be reduced
by revealing more dependencies. On average, the improvement is only about 20%
for the different methods in the joint projection planner, and only 10% in
mafs. This means that the solution obtained with the least amount of revealed
dependencies was almost as good as the best solution that was found when we
revealed additional dependencies.

However, the impact of sharing private dependencies on solution cost varies
significantly per domain. For example, in the joint projection solver, in
BlocksWorld, the improvement is about 40%. This is because every problem can
be solved by a single agent doing all the work. However, if the agents work
jointly, they distribute the actions to provide a better makespan. Also, in
most cases, there was almost no difference between the different heuristics
($m_{1-4}$) with respect to the solution cost. This shows that our heuristics
are better geared towards solvability, not makespan. We leave heuristics
oriented towards reducing costs to future research.

The improvement made by mafs is less than the improvement made by the joint
projection solver. This is because mafs prefers plans with more collaboration.

##  5 Conclusion and Future Work

In this work we suggest methods for publishing only a part of the private
dependencies between public actions of agents. We provide experimental results
on both the joint projection method that uses all private dependencies to
compute a public plan, and mafs, modified to broadcast states only if they do
not reveal a forbidden dependency. We show that in many cases a public plan
can be computed with only a small portion of the dependencies, and that our
heuristic methods rapidly find a good subset to share for both the joint
projection method and mafs. We provide experiments over standard benchmark
domains, comparing the coverage of our methods, as well as the cost of the
found plans.

Future work should analyze the privacy leakage, with respect to the revealed
transition systems Stolba et al. (2019) in the context of using the shared
dependencies in current solvers. It is also worthwhile to assign importance
values to different dependencies, where each dependency has an intrinsic value
that needs to be considered.

## Acknowledgements

This work is partially funded by ISF grant # 210/17 to Roni Stern and by ISF
grant # 1210/18 to Guy Shani.

## References

  * Borrajo and Fernandez [2015] Daniel Borrajo and Susana Fernandez.  MAPR and CMAP.  In CoDMAP-15, 2015.
  * Brafman and Domshlak [2008] Ronen I Brafman and Carmel Domshlak.  From one to many: Planning for loosely coupled multi-agent systems.  In ICAPS, pages 28–35, 2008.
  * Brafman and Domshlak [2013] Ronen I. Brafman and Carmel Domshlak.  On the complexity of planning for agent teams and its implications for single agent planning.  Artificial Intelligence, 198:52–71, 2013.
  * Brafman [2015] Ronen I. Brafman.  A privacy preserving algorithm for multi-agent planning and search.  In IJCAI, pages 1530–1536, 2015.
  * Caspari et al. [2020] Patrick Caspari, Robert Mattmuller, and Tim Schulte.  A framework to prove strong privacy in multi-agent planning.  In Distributed and Multi-Agent Planning (DMAP) workshop at ICAPS, 2020.
  * Luis and Borrajo [2014] Nerea Luis and Daniel Borrajo.  Plan merging by reuse for multi-agent planning.  In DMAP–ICAPS, 2014.
  * Maheswaran et al. [2006] Rajiv T Maheswaran, Jonathan P Pearce, Emma Bowring, Pradeep Varakantham, and Milind Tambe.  Privacy loss in distributed constraint reasoning: A quantitative framework for analysis and its applications.  JAAMAS, 13(1):27–60, 2006.
  * Maliah et al. [2015] Shlomi Maliah, Guy Shani, and Roni Stern.  Privacy preserving pattern databases.  In DMAP–ICAPS, volume 15, pages 9–17, 2015.
  * Maliah et al. [2016a] Shlomi Maliah, Ronen I Brafman, and Guy Shani.  Increased privacy with reduced communication and computation in multi-agent planning.  In DMAP–ICAPS, volume 16, pages 106–112, 2016.
  * Maliah et al. [2016b] Shlomi Maliah, Guy Shani, and Roni Stern.  Stronger privacy preserving projections for multi-agent planning.  In the International Conference on Automated Planning and Scheduling (ICAPS), pages 221–229, 2016.
  * Maliah et al. [2016c] Shlomi Maliah, Guy Shani, and Roni Stern.  Stronger privacy preserving projections for multi-agent planning.  In ICAPS, pages 221–229, 2016.
  * Maliah et al. [2018] Shlomi Maliah, Guy Shani, and Roni Stern.  Action dependencies in privacy-preserving multi-agent planning.  Autonomous Agents and Multi-Agent Systems, 32(6):779–821, 2018\.
  * Nissim and Brafman [2014] Raz Nissim and Ronen I. Brafman.  Distributed heuristic forward search for multi-agent planning.  JAIR, 51:293–332, 2014.
  * Štolba and Komenda [2017] Michal Štolba and Antonín Komenda.  The madla planner: Multi-agent planning by combination of distributed and local heuristic search.  Artificial Intelligence, 252:175–210, 2017.
  * Štolba et al. [2015] Michal Štolba, Antonın Komenda, and Daniel L Kovacs.  Competition of distributed and multiagent planners (codmap).  The International Planning Competition (WIPC-15), page 24, 2015\.
  * Stolba et al. [2016] Michal Stolba, Jan Tozicka, and Antonín Komenda.  Secure multi-agent planning algorithms.  In ECAI, pages 1714–1715, 2016.
  * Štolba et al. [2018] Michal Štolba, Jan Tožička, and Antonín Komenda.  Quantifying privacy leakage in multi-agent planning.  TOIT, 18(3):28, 2018.
  * Stolba et al. [2019] Michal Stolba, Daniel Fiser, and Antonín Komenda.  Privacy leakage of search-based multi-agent planning algorithms.  In J. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, and Siddharth Srivastava, editors, Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ICAPS 2018, Berkeley, CA, USA, July 11-15, 2019, pages 482–490. AAAI Press, 2019.
  * Torreno et al. [2014] Alejandro Torreno, Eva Onaindia, and Oscar Sapena.  FMAP: Distributed cooperative multi-agent planning.  Applied Intelligence, 41(2):606–626, 2014.
  * Torreño et al. [2017] Alejandro Torreño, Eva Onaindia, Antonín Komenda, and Michal Štolba.  Cooperative multi-agent planning: A survey.  ACM Computing Surveys, 50(6):1–32, 2017.
  * Tozicka et al. [2017] Jan Tozicka, Michal Štolba, and Antonín Komenda.  The limits of strong privacy preserving multi-agent planning.  In ICAPS, 2017.