Zhifeng Gu, Ying Chen, Rui Jiang, Lei Yi, Bing Wang
原文摘要
Experience from past tasks can help embodied agents perform new tasks, but it may not remain applicable or effective when conditions change. Tasks with different overall goals often share subgoals, providing a basis for cross-task experience transfer. We present EmbodiExp, a framework for constructing outcome-grounded subgoal experiences and composing them in new tasks. Each experience describes how to pursue a subgoal, when the guidance applies, and what outcome must be verified for completion. Verified outcomes from applying one experience can satisfy the conditions for applying another, allowing experiences from different past tasks to be composed online. By examining the actions and observed outcomes at the subgoal level, EmbodiExp retains experience from successful subgoals and uses explicit action failures to identify actions to avoid under specific conditions. Experiments on EmbodiedBench and VIGIL assess cross-task transfer with experiences kept fixed throughout held-out evaluation. EmbodiExp achieves success rates of 68.0% on EB-Habitat and 68.3% on EB-ALFRED, compared with 50.0% and 54.7% for the agent without stored experience.
This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree $λ$ and its edges are subsampled from a common parent Erdős-Rényi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $λ=ω(1)$ with $λ=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $λs\ge(1+ε)\log n$ for a constant $ε>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.