RELIC: Revealed Principles for Learning Interpretable Composable Skills in Multi-Agent Planning
Summary
Introduces RELIC, a framework for learning interpretable and composable skills in multi-agent planning via revealed principles, enabling privacy-preserving coordination and cross-agent skill transfer without sharing code.
View Cached Full Text
Cached at: 07/21/26, 06:40 AM
# Revealed Principles for Learning Interpretable Composable Skills in Multi-Agent Planning
Source: [https://arxiv.org/html/2607.16745](https://arxiv.org/html/2607.16745)
Bui Dinh PhamDuong Quoc ChinhDao Van TungTran Cong DaoHuynh Thi Thanh Binh
###### Abstract
Multi\-agent planning becomes substantially harder when agents must improve specialized decision\-making skills while keeping their internal implementations private\. This regime arises when agents are developed independently, expose different interfaces and capabilities, and must nevertheless coordinate without sharing executable policies\. Prior research has largely assumed centralized optimization, shared policy access, or common skill representations, making it poorly suited to privacy\-constrained cooperation\. We introduce RELIC, a framework for learning interpretable and composable skills via revealed principles\. Each agent refines its own programmatic skill through private LLM\-guided search, while a trusted orchestrator evaluates proposed updates solely through team\-level performance\. Successful behaviors are not broadcast as code; instead, they are abstracted into portable principles that other agents can instantiate within their own interfaces and recombine with local strategies\. This separates coordination from implementation sharing, enabling cross\-agent transfer under heterogeneous skill signatures\. RELIC thus introduces a new paradigm for privacy\-preserving skill learning and coordination in multi\-agent planning\.
Machine Learning, ICML
## 1Introduction
Large language models \(LLMs\) are increasingly used as search and synthesis engines for automated planning\. Recent work has shown that LLMs can generate executable policies or planning programs, refine symbolic planning models, and support long\-horizon decision making through reusable skills\(Silveret al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib11); Lianget al\.,[2023](https://arxiv.org/html/2607.16745#bib.bib12); Oswaldet al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib10); Mahdaviet al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib9)\)\. In parallel, a growing line of work studies skill discovery and skill libraries, where LLMs or offline data are used to acquire reusable behaviors that can later be retrieved, adapted, or composed\(Zhanget al\.,[2023](https://arxiv.org/html/2607.16745#bib.bib2); Zhuet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib4); Wanget al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib5); Alzubiet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib6); Liet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib7)\)\. These directions have established that LLMs are effective at producing structured planning artifacts and reusable skills\.
However, most existing approaches assume that planning knowledge is improved in a centralized form: a shared planner, a common symbolic model, or a globally accessible skill repository\. This assumption is limiting for multi\-agent planning settings in which different agents expose different decision interfaces, specialize in different roles, and must still improve as a team\. In such settings, the key challenge is not merely to optimize each skill independently, but to discover*transferable coordination structure*: what aspects of a successful local policy can be abstracted, communicated, and re\-instantiated by another agent with a different interface and role\.
We study multi\-agent planning problems in which each agent is represented by its own programmatic decision skill, implemented as an interpretable function with an agent\-specific signature\. The agents must improve jointly as a team, yet candidate updates are evaluated only through overall team performance\. This creates a coupled search problem: a local change should be retained only if it improves coordination at the team level, while any useful behavioral structure should remain transferable across agents with different interfaces\.
We introduceRELIC\(REvealed Principles forLearningInterpretableComposable Skills\), a framework for learning in this setting\. Each agent performs LLM\-guided search over revisions of its own skill program, while a trusted orchestrator evaluates candidate updates under the current team and maintains the best joint solution\. Rather than transferring successful skills directly as implementations,RELICdistills them into*revealed principles*: compact descriptions of strategies or coordination patterns that can be re\-instantiated under another agent’s local signature\. This separates local program optimization from cross\-agent transfer, allowing coordination structure to be reused without requiring a common implementation space\. Concretely,RELICcombines private per\-agent program search, a shared public tree of revealed principles, and operators for principle instantiation and reflection\.
This perspective differs from prior multi\-agent LLM systems that focus on communication protocols, centralized planning, or retrieval from pre\-existing skill libraries\(Liet al\.,[2025](https://arxiv.org/html/2607.16745#bib.bib3); Yanget al\.,[2025](https://arxiv.org/html/2607.16745#bib.bib8); Liet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib7)\)\. Our goal is instead to learn transferable coordination principles jointly with the underlying skills, under heterogeneous agent interfaces and team\-level supervision\. This makesRELICwell suited to teams of independently specialized agents that must develop interoperable behavior\.
This work makes three contributions\. First, we formulate a new setting for multi\-agent planning: learning interoperable programmatic skills under heterogeneous agent interfaces and team\-level evaluation\. Second, we proposeRELIC, a framework that combines private skill search with principle\-mediated transfer to learn interpretable and composable behaviors\. Third, across diverse multi\-agent planning domains, we show thatRELICimproves both team performance and cross\-agent skill reuse over competitive baselines\.
## 2Preliminary
### 2\.1Problem Formulation
We study cooperative multi\-agent planning with heterogeneous programmatic skills\. A team consists ofNNagents indexed byi∈\[N\]i\\in\[N\]\. Each agentiireceives local inputs from𝒳i\\mathcal\{X\}\_\{i\}, outputs actions in𝒜i\\mathcal\{A\}\_\{i\}, and acts through a decision skillπi:𝒳i→𝒜i\\pi\_\{i\}:\\mathcal\{X\}\_\{i\}\\to\\mathcal\{A\}\_\{i\}, implemented as an interpretable executable program with an agent\-specific function signature\. The input spaces𝒳i\\mathcal\{X\}\_\{i\}may differ across agents, reflecting heterogeneous roles and information access\.
We consider a stream of batchesb=1,…,Bb=1,\\dots,B\. At batchbb, task instances are drawn from a distribution𝒟b\\mathcal\{D\}\_\{b\}\. Let𝝅=\(π1,…,πN\)\\boldsymbol\{\\pi\}=\(\\pi\_\{1\},\\dots,\\pi\_\{N\}\)denote the team of skills\. The team objective at batchbbis
Jb\(𝝅\)=𝔼ξ∼𝒟b\[R\(ξ;𝝅\)\],J\_\{b\}\(\\boldsymbol\{\\pi\}\)=\\mathbb\{E\}\_\{\\xi\\sim\\mathcal\{D\}\_\{b\}\}\\bigl\[R\(\\xi;\\boldsymbol\{\\pi\}\)\\bigr\],\(1\)whereR\(ξ;𝝅\)R\(\\xi;\\boldsymbol\{\\pi\}\)is the cooperative return obtained by executing the team on instanceξ\\xi\. In practice,JbJ\_\{b\}is estimated on a finite batchℬb=\{ξm\(b\)\}m=1Mb\\mathcal\{B\}\_\{b\}=\\\{\\xi\_\{m\}^\{\(b\)\}\\\}\_\{m=1\}^\{M\_\{b\}\}as
J^b\(𝝅\)=1Mb∑m=1MbR\(ξm\(b\);𝝅\)\.\\widehat\{J\}\_\{b\}\(\\boldsymbol\{\\pi\}\)=\\frac\{1\}\{M\_\{b\}\}\\sum\_\{m=1\}^\{M\_\{b\}\}R\(\\xi\_\{m\}^\{\(b\)\};\\boldsymbol\{\\pi\}\)\.\(2\)Our goal is to improve team performance over the task stream while preserving decentralized execution: agents act through local interfaces, and skill updates are evaluated only by their team\-level impact\.
### 2\.2LLM\-Guided Program Tree Search
RELIC builds on LLM\-guided program search methods such as MCTS\-AHD\(Zhenget al\.,[2025](https://arxiv.org/html/2607.16745#bib.bib16)\)and MOTIF\(Kietet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib13)\), which represent search directly in code space\. For each agentii, we maintain a search tree𝒯i\\mathcal\{T\}\_\{i\}whose nodes are candidate skill programs\. The root node contains a seed skill, and each child node is obtained by applying an LLM\-guided editing operator to its parent program\.
Each node stores a candidate skillπ\\pi, together with standard tree\-search statistics such as visit countN\(π\)N\(\\pi\)and value estimateQ\(π\)Q\(\\pi\)\. Node selection follows an upper\-confidence criterion; for a child nodeπ′\\pi^\{\\prime\}of parentπ\\pi,
UCT\(π′\)=Q\(π′\)\+clnN\(π\)N\(π′\),\\mathrm\{UCT\}\(\\pi^\{\\prime\}\)=Q\(\\pi^\{\\prime\}\)\+c\\sqrt\{\\frac\{\\ln N\(\\pi\)\}\{N\(\\pi^\{\\prime\}\)\}\},\(3\)wherec\>0c\>0is an exploration constant\. This representation is well suited to RELIC because each search state remains an interpretable executable skill, while LLM operators can revise code in structured ways rather than regenerate policies from scratch\.
Figure 1:Overview of the RELIC framework, illustrating the main components and information flow of the proposed method\.
## 3Methodology
RELIC maintains a current best team𝝅¯b=\(π¯1,b,…,π¯N,b\)\\bar\{\\boldsymbol\{\\pi\}\}\_\{b\}=\(\\bar\{\\pi\}\_\{1,b\},\\dots,\\bar\{\\pi\}\_\{N,b\}\)at batchbb, where eachπ¯i,b\\bar\{\\pi\}\_\{i,b\}is an executable skill program for agentii\. The method alternates between private search over program revisions and public updates of transferable principles\.
### 3\.1Batch\-Level Training Loop
Letℬb=\{ξm\(b\)\}m=1Mb\\mathcal\{B\}\_\{b\}=\\\{\\xi\_\{m\}^\{\(b\)\}\\\}\_\{m=1\}^\{M\_\{b\}\}be the current batch\. To reduce myopic updates under the non\-stationary task stream, RELIC trains on a mixed batch
ℬ~b=ℬb∪⋃t∈ℛb𝒮t,\\widetilde\{\\mathcal\{B\}\}\_\{b\}=\\mathcal\{B\}\_\{b\}\\cup\\bigcup\_\{t\\in\\mathcal\{R\}\_\{b\}\}\\mathcal\{S\}\_\{t\},\(4\)whereℛb⊆\{1,…,b−1\}\\mathcal\{R\}\_\{b\}\\subseteq\\\{1,\\dots,b\-1\\\}indexes replay batches and𝒮t⊆ℬt\\mathcal\{S\}\_\{t\}\\subseteq\\mathcal\{B\}\_\{t\}is a small replay sample\. All candidate revisions at batchbbare scored onℬ~b\\widetilde\{\\mathcal\{B\}\}\_\{b\}\.
The orchestrator evaluates only team\-level performance\. For any team𝝅=\(π1,…,πN\)\\boldsymbol\{\\pi\}=\(\\pi\_\{1\},\\dots,\\pi\_\{N\}\), its empirical utility onℬ~b\\widetilde\{\\mathcal\{B\}\}\_\{b\}is
J^b\(𝝅\)=1\|ℬ~b\|∑ξ∈ℬ~bR\(ξ;𝝅\)\.\\widehat\{J\}\_\{b\}\(\\boldsymbol\{\\pi\}\)=\\frac\{1\}\{\|\\widetilde\{\\mathcal\{B\}\}\_\{b\}\|\}\\sum\_\{\\xi\\in\\widetilde\{\\mathcal\{B\}\}\_\{b\}\}R\(\\xi;\\boldsymbol\{\\pi\}\)\.\(5\)At each batch, RELIC executes
𝝅¯b→private search𝝅¯b′→principle update\(𝝅¯b\+1,𝒫b\+1\),\\bar\{\\boldsymbol\{\\pi\}\}\_\{b\}\\;\\xrightarrow\{\\text\{private search\}\}\\;\\bar\{\\boldsymbol\{\\pi\}\}^\{\\prime\}\_\{b\}\\;\\xrightarrow\{\\text\{principle update\}\}\\;\(\\bar\{\\boldsymbol\{\\pi\}\}\_\{b\+1\},\\mathcal\{P\}\_\{b\+1\}\),where𝒫b\\mathcal\{P\}\_\{b\}denotes the public principle tree\. The first phase updates executable skills; the second phase updates transferable textual principles\.
### 3\.2Private Program Search
Each agentiimaintains a private tree𝒯i,b=\(𝒱i,b,ℰi,b\)\\mathcal\{T\}\_\{i,b\}=\(\\mathcal\{V\}\_\{i,b\},\\mathcal\{E\}\_\{i,b\}\)\. Each nodev∈𝒱i,bv\\in\\mathcal\{V\}\_\{i,b\}stores a candidate skillπ\(v\)\\pi\(v\), a visit countN\(v\)N\(v\), a node valueQ\(v\)Q\(v\), and operator\-specific statistics\{Nop\(v,o\),Qop\(v,o\)\}o∈𝒪\\\{N\_\{\\mathrm\{op\}\}\(v,o\),Q\_\{\\mathrm\{op\}\}\(v,o\)\\\}\_\{o\\in\\mathcal\{O\}\}, where𝒪=\{L,B,R\}\\mathcal\{O\}=\\\{\\textsf\{L\},\\textsf\{B\},\\textsf\{R\}\\\}\. The root node contains the seed skill, and each child corresponds to one LLM\-generated revision of its parent\.
#### Node and operator selection\.
For agentii, RELIC descends its private tree by repeatedly selecting, from a current nodeuu, the childvvmaximizing
Unode\(v;u\)=Q\(v\)\+cnodelnN\(u\)N\(v\)\.U\_\{\\mathrm\{node\}\}\(v;u\)=Q\(v\)\+c\_\{\\mathrm\{node\}\}\\sqrt\{\\frac\{\\ln N\(u\)\}\{N\(v\)\}\}\.\(6\)This recursion terminates at an expansion nodevv, where RELIC chooses an operatoro∈𝒪o\\in\\mathcal\{O\}according to
Uop\(o;v\)=Qop\(v,o\)\+copln∑o′∈𝒪Nop\(v,o′\)Nop\(v,o\)\.U\_\{\\mathrm\{op\}\}\(o;v\)=Q\_\{\\mathrm\{op\}\}\(v,o\)\+c\_\{\\mathrm\{op\}\}\\sqrt\{\\frac\{\\ln\\sum\_\{o^\{\\prime\}\\in\\mathcal\{O\}\}N\_\{\\mathrm\{op\}\}\(v,o^\{\\prime\}\)\}\{N\_\{\\mathrm\{op\}\}\(v,o\)\}\}\.\(7\)Thus, RELIC makes two coupled decisions at each search step: which existing revision to build on, and which type of edit to apply next\.
#### Candidate generation and scoring\.
Letvvbe the selected node in agentii’s tree\. The chosen operatorooprompts the LLM to produce a revised program
π~i∼pθ\(⋅∣π\(v\),o,𝒞i,b\),\\tilde\{\\pi\}\_\{i\}\\sim p\_\{\\theta\}\\\!\\left\(\\,\\cdot\\mid\\pi\(v\),\\,o,\\,\\mathcal\{C\}\_\{i,b\}\\right\),\(8\)where𝒞i,b\\mathcal\{C\}\_\{i,b\}is the operator\-specific context \(e\.g\., function signature, revealed principle, or reflection summary\)\. The orchestrator evaluatesπ~i\\tilde\{\\pi\}\_\{i\}by replacing only agentii’s incumbent skill:
Δb\(π~i\)=J^b\(π¯1,b,…,π~i,…,π¯N,b\)−J^b\(𝝅¯b\)\.\\Delta\_\{b\}\(\\tilde\{\\pi\}\_\{i\}\)=\\widehat\{J\}\_\{b\}\(\\bar\{\\pi\}\_\{1,b\},\\dots,\\tilde\{\\pi\}\_\{i\},\\dots,\\bar\{\\pi\}\_\{N,b\}\)\-\\widehat\{J\}\_\{b\}\(\\bar\{\\boldsymbol\{\\pi\}\}\_\{b\}\)\.\(9\)A new childv′v^\{\\prime\}withπ\(v′\)=π~i\\pi\(v^\{\\prime\}\)=\\tilde\{\\pi\}\_\{i\}is then added to𝒯i,b\\mathcal\{T\}\_\{i,b\}, with node value
Q\(v′\)=Δb\(π~i\)\.Q\(v^\{\\prime\}\)=\\Delta\_\{b\}\(\\tilde\{\\pi\}\_\{i\}\)\.\(10\)The operator statistics at the expanded nodevvare updated by
Nop\(v,o\)\\displaystyle N\_\{\\mathrm\{op\}\}\(v,o\)←Nop\(v,o\)\+1,\\displaystyle\\leftarrow N\_\{\\mathrm\{op\}\}\(v,o\)\+1,\(11\)Qop\(v,o\)\\displaystyle Q\_\{\\mathrm\{op\}\}\(v,o\)←Qop\(v,o\)\+Δb\(π~i\)−Qop\(v,o\)Nop\(v,o\)\.\\displaystyle\\leftarrow Q\_\{\\mathrm\{op\}\}\(v,o\)\+\\frac\{\\Delta\_\{b\}\(\\tilde\{\\pi\}\_\{i\}\)\-Q\_\{\\mathrm\{op\}\}\(v,o\)\}\{N\_\{\\mathrm\{op\}\}\(v,o\)\}\.\(12\)IfΔb\(π~i\)\\Delta\_\{b\}\(\\tilde\{\\pi\}\_\{i\}\)exceeds the score of agentii’s incumbent best node, the orchestrator updatesπ¯i,b←π~i\\bar\{\\pi\}\_\{i,b\}\\leftarrow\\tilde\{\\pi\}\_\{i\}\. At the beginning of each new batch, RELIC re\-evaluates previously successful nodes onℬ~b\\widetilde\{\\mathcal\{B\}\}\_\{b\}and resetsπ¯i,b\\bar\{\\pi\}\_\{i,b\}to the highest\-scoring validated node\.
#### Operators\.
The three operators differ only in the context𝒞i,b\\mathcal\{C\}\_\{i,b\}\.L\(*Lift*\) instantiates a revealed principleρ∈𝒜i,brev\\rho\\in\\mathcal\{A\}^\{\\mathrm\{rev\}\}\_\{i,b\}under agentii’s local signature,
𝒞i,bL=\(π\(v\),ρ,σi\),\\mathcal\{C\}^\{\\textsf\{L\}\}\_\{i,b\}=\\bigl\(\\pi\(v\),\\rho,\\sigma\_\{i\}\\bigr\),\(13\)whereσi\\sigma\_\{i\}is agentii’s function signature\.B\(*Bridge*\) conditions on a public principlep∈𝒫bp\\in\\mathcal\{P\}\_\{b\},
𝒞i,bB=\(π\(v\),ρ\(p\),σi\)\.\\mathcal\{C\}^\{\\textsf\{B\}\}\_\{i,b\}=\\bigl\(\\pi\(v\),\\rho\(p\),\\sigma\_\{i\}\\bigr\)\.\(14\)R\(*Reflect*\) uses a reflection summarygi,b\(π\(v\)\)g\_\{i,b\}\(\\pi\(v\)\)produced by the orchestrator:
𝒞i,bR=\(π\(v\),gi,b\(π\(v\)\),σi\)\.\\mathcal\{C\}^\{\\textsf\{R\}\}\_\{i,b\}=\\bigl\(\\pi\(v\),g\_\{i,b\}\(\\pi\(v\)\),\\sigma\_\{i\}\\bigr\)\.\(15\)Heregi,b\(π\)g\_\{i,b\}\(\\pi\)is computed by comparing the full team\(π¯1,b,…,π,…,π¯N,b\)\(\\bar\{\\pi\}\_\{1,b\},\\dots,\\pi,\\dots,\\bar\{\\pi\}\_\{N,b\}\)against the subset team𝝅¯b,−i\\bar\{\\boldsymbol\{\\pi\}\}\_\{b,\-i\}, which removes agentiientirely from the rollout\. ThusRis driven by where agentiiis decisive versus redundant on the batch\.
### 3\.3Revealed Principles and Public Tree
RELIC transfers behavior through*revealed principles*, i\.e\., short textual abstractions of successful skills\. It maintains two principle memories: a local archive𝒜i,brev\\mathcal\{A\}^\{\\mathrm\{rev\}\}\_\{i,b\}for each agentii, and a shared public tree𝒫b\\mathcal\{P\}\_\{b\}\. Each public nodep∈𝒫bp\\in\\mathcal\{P\}\_\{b\}stores a principle textρ\(p\)\\rho\(p\), a typeτ\(p\)\\tau\(p\), a contributorκ\(p\)\\kappa\(p\), a visit countN\(p\)N\(p\), and a cumulative endorsementE\(p\)E\(p\)\.
Table 1:Comparison of methods on Multi\-Agent Path Planning and Multi\-Agent Scheduling benchmarks over 5 runs\.MethodVariantMulti\-Agent Path PlanningMulti\-Agent SchedulingPrize Collection\(↑\\uparrow\)Area Reconnaissance\(↑\\uparrow\)Dynamic Servicing\(↑\\uparrow\)Job Dispatch\(↓\\downarrow\)Skilled Tasks\(↓\\downarrow\)Flow Shop\(↑\\uparrow\)508050805080508050805080HumanGS33\.9054\.6541\.6467\.6718\.3734\.722782\.536434\.27237\.68860\.5359\.5565\.85CCEA33\.9054\.6541\.8968\.0418\.3135\.402782\.536434\.27237\.68860\.5359\.5565\.85HHS33\.9054\.6541\.5867\.7818\.3135\.132812\.976537\.88238\.00860\.6659\.4565\.50HAOS33\.9054\.6541\.6467\.6718\.3734\.722812\.976537\.88237\.97858\.8459\.5565\.85RL\-IS38\.1362\.2240\.4767\.3826\.0448\.003709\.009409\.83236\.44853\.4061\.9574\.65LLMMOTIF38\.0461\.4142\.4370\.8532\.9963\.662780\.926543\.09255\.74938\.1261\.4570\.30RELIC38\.0461\.4642\.6471\.0737\.6585\.482770\.956411\.59231\.72840\.5766\.0081\.40
#### Distill, reveal, and cross\-distill\.
Let𝒮i,b⊆𝒱i,b\\mathcal\{S\}\_\{i,b\}\\subseteq\\mathcal\{V\}\_\{i,b\}be the set of agent\-iiprivate nodes created at batchbbwith positive gain:
𝒮i,b=\{v∈𝒱i,b:Δb\(π\(v\)\)\>0\}\.\\mathcal\{S\}\_\{i,b\}=\\\{v\\in\\mathcal\{V\}\_\{i,b\}:\\Delta\_\{b\}\(\\pi\(v\)\)\>0\\\}\.\(16\)RELIC distills at most one public principle from the strongest such node,
vi,b⋆=argmaxv∈𝒮i,bΔb\(π\(v\)\)\.v\_\{i,b\}^\{\\star\}=\\arg\\max\_\{v\\in\\mathcal\{S\}\_\{i,b\}\}\\Delta\_\{b\}\(\\pi\(v\)\)\.\(17\)Applying an LLM distillation mapDiD\_\{i\}yields
\(τ,ρ\)=Di\(π\(vi,b⋆\),Δb\(π\(vi,b⋆\)\),𝒫b\),\(\\tau,\\rho\)=D\_\{i\}\\\!\\left\(\\pi\(v\_\{i,b\}^\{\\star\}\),\\Delta\_\{b\}\(\\pi\(v\_\{i,b\}^\{\\star\}\)\),\\mathcal\{P\}\_\{b\}\\right\),\(18\)which is inserted into𝒫b\\mathcal\{P\}\_\{b\}\. In parallel, the orchestrator abstracts each incumbent skill into a revealed principleρ^i,b=Ai\(π¯i,b\),\\hat\{\\rho\}\_\{i,b\}=A\_\{i\}\(\\bar\{\\pi\}\_\{i,b\}\),and broadcastsρ^i,b\\hat\{\\rho\}\_\{i,b\}to every other agent’s local archive𝒜j,brev\\mathcal\{A\}^\{\\mathrm\{rev\}\}\_\{j,b\},j≠ij\\neq i\. Finally, each agent may cross\-distill additional public principles from its own incumbent skill and the set\{ρ^j,b:j≠i\}\\\{\\hat\{\\rho\}\_\{j,b\}:j\\neq i\\\}\.
#### Public\-tree retrieval and endorsement\.
WhenBis invoked by agentii, RELIC selects a public principle contributed by another agent using
Upub\(p\)=E\(p\)N\(p\)\+cpubln∑q∈𝒫bN\(q\)N\(p\),κ\(p\)≠i\.U\_\{\\mathrm\{pub\}\}\(p\)\\\!=\\\!\\frac\{E\(p\)\}\{N\(p\)\}\\\!\+c\_\{\\mathrm\{pub\}\}\\sqrt\{\\frac\{\\ln\\\!\\sum\_\{q\\in\\mathcal\{P\}\_\{b\}\}\\\!\\\!N\(q\)\}\{N\(p\)\}\},\\\!\\\!\\\!\\\!\\quad\\kappa\(p\)\\neq i\.\(19\)If a Bridge\-derived revision that referencesppachieves positive gainΔb\>0\\Delta\_\{b\}\>0, RELIC updates
E\(p\)←E\(p\)\+Δb,N\(p\)←N\(p\)\+1\.E\(p\)\\leftarrow E\(p\)\+\\Delta\_\{b\},\\qquad N\(p\)\\leftarrow N\(p\)\+1\.\(20\)Principles with repeatedly positive downstream impact therefore become easier to retrieve, while low\-endorsement leaf nodes are periodically pruned\. The public tree thus stores transferable coordination structure, whereas the private trees store executable implementations\.
Figure 2:RELIC behavior convergence during training\.
## 4Experiments
#### Baselines\.
We compare RELIC against six baselines\.GSperforms exhaustive grid search over handcrafted role\-specific heuristics for agentsA,B,CA,B,C\.HHS\(Cowlinget al\.,[2001](https://arxiv.org/html/2607.16745#bib.bib31)\)is a contextual selection hyper\-heuristic over the same candidate set\.CCEA\(Potter and Jong,[2000](https://arxiv.org/html/2607.16745#bib.bib32)\)applies cooperative coevolution, with one species per agent and weighted mixtures of heuristic components as individuals\.HAOS\(Peiet al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib33)\)uses a learned gate to switch between offline and online hyper\-heuristic selectors\.RL\-ISis an RL\-based hyper\-heuristic, adapted from DRLH\(Kallestadet al\.,[2023](https://arxiv.org/html/2607.16745#bib.bib34)\), that trains an instance\-level policy for each agent to choose among candidate heuristics\. We also compare toMOTIF\(Kietet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib13)\), the closest LLM\-based baseline: although many methods search over code with LLMs, MOTIF is the only one we found that can optimize multiple functions with heterogeneous signatures\.
Table[1](https://arxiv.org/html/2607.16745#S3.T1)summarizes the main comparison\. Among the baselines, all methods other thanRELICare trained in a centralized offline regime: GS, HHS, CCEA, and MOTIF operate on the full training set, while HAOS and RL\-IS use batches but still revisit a fixed offline dataset over multiple epochs rather than adapting to a non\-stationary stream\. By contrast,RELICrefines skills in a decentralized manner at the agent level while handling streaming batches under centralized orchestration\. Figure[2](https://arxiv.org/html/2607.16745#S3.F2)shows the convergence behavior ofRELIC, in which the companies, although trained privately, contribute nearly equally\.
## References
- S\. Alzubi, N\. Provenzano, J\. Bingham, W\. Chen, and T\. Vu \(2026\)Evoskill: automated skill discovery for multi\-agent systems\.arXiv preprint arXiv:2603\.02766\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
- I\. Chao, B\. L\. Golden, and E\. A\. Wasil \(1996\)The team orienteering problem\.European Journal of Operational Research88\(3\),pp\. 464–474\.External Links:ISSN 0377\-2217,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/0377-2217%2894%2900289-4),[Link](https://www.sciencedirect.com/science/article/pii/0377221794002894)Cited by:[§B\.1](https://arxiv.org/html/2607.16745#A2.SS1.SSS0.Px1.p1.3)\.
- ChentongChen, M\. Zhong, J\. Shi, J\. Sun, and Y\. Fan \(2026\)HiFo\-prompt: prompting with hindsight and foresight for LLM\-based automatic heuristic design\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=imSLzfZ6av)Cited by:[§A\.1](https://arxiv.org/html/2607.16745#A1.SS1.p2.1)\.
- P\. Cowling, G\. Kendall, and E\. Soubeiga \(2001\)A hyperheuristic approach to scheduling a sales summit\.InPractice and Theory of Automated Timetabling III,E\. Burke and W\. Erben \(Eds\.\),Berlin, Heidelberg,pp\. 176–190\.External Links:ISBN 978\-3\-540\-44629\-3Cited by:[§4](https://arxiv.org/html/2607.16745#S4.SS0.SSS0.Px1.p1.1)\.
- M\. Fırat and C\. A\. Hurkens \(2012\)An improved mip\-based approach for a multi\-skill workforce scheduling problem\.J\. of Scheduling15\(3\),pp\. 363–380\.External Links:ISSN 1094\-6136,[Link](https://doi.org/10.1007/s10951-011-0245-x),[Document](https://dx.doi.org/10.1007/s10951-011-0245-x)Cited by:[§B\.2](https://arxiv.org/html/2607.16745#A2.SS2.SSS0.Px2.p1.7)\.
- W\. Huang, F\. Xia, T\. Xiao, H\. Chan, J\. Liang, P\. Florence, A\. Zeng, J\. J\. R\. Tompson, I\. Mordatch, Y\. Chebotar, P\. Sermanet, N\. Brown, T\. Jackson, L\. Luu, S\. Levine, K\. Hausman, and B\. A\. Ichter \(2022\)InnerMonologue: embodied reasoning through planning with language models\.Note:CoRL 2022 \(to appear\)External Links:[Link](https://innermonologue.github.io/)Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p2.1)\.
- b\. ichter, A\. Brohan, Y\. Chebotar, C\. Finn, K\. Hausman, A\. Herzog, D\. Ho, J\. Ibarz, A\. Irpan, E\. Jang, R\. Julian, D\. Kalashnikov, S\. Levine, Y\. Lu, C\. Parada, K\. Rao, P\. Sermanet, A\. T\. Toshev, V\. Vanhoucke, F\. Xia, T\. Xiao, P\. Xu, M\. Yan, N\. Brown, M\. Ahn, O\. Cortes, N\. Sievers, C\. Tan, S\. Xu, D\. Reyes, J\. Rettinghouse, J\. Quiambao, P\. Pastor, L\. Luu, K\. Lee, Y\. Kuang, S\. Jesmonth, N\. J\. Joshi, K\. Jeffrey, R\. J\. Ruano, J\. Hsu, K\. Gopalakrishnan, B\. David, A\. Zeng, and C\. K\. Fu \(2023\)Do as i can, not as i say: grounding language in robotic affordances\.InProceedings of The 6th Conference on Robot Learning,K\. Liu, D\. Kulic, and J\. Ichnowski \(Eds\.\),Proceedings of Machine Learning Research, Vol\.205,pp\. 287–318\.External Links:[Link](https://proceedings.mlr.press/v205/ichter23a.html)Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p2.1)\.
- Y\. Jiang, Q\. Chao, Y\. Chen, X\. Li, S\. Liu, and G\. Cong \(2024\)UrbanLLM: autonomous urban activity planning and management with large language models\.InFindings of the Association for Computational Linguistics: EMNLP 2024,Y\. Al\-Onaizan, M\. Bansal, and Y\. Chen \(Eds\.\),Miami, Florida, USA,pp\. 1810–1825\.External Links:[Link](https://aclanthology.org/2024.findings-emnlp.98/),[Document](https://dx.doi.org/10.18653/v1/2024.findings-emnlp.98)Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p1.1)\.
- D\. Ju, S\. Jiang, A\. Cohen, A\. Foss, S\. Mitts, A\. Zharmagambetov, B\. Amos, X\. Li, J\. T\. Kao, M\. Fazel\-Zarandi, and Y\. Tian \(2024\)To the globe \(TTG\): towards language\-driven guaranteed travel planning\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: System Demonstrations,D\. I\. Hernandez Farias, T\. Hope, and M\. Li \(Eds\.\),Miami, Florida, USA,pp\. 240–249\.External Links:[Link](https://aclanthology.org/2024.emnlp-demo.25/),[Document](https://dx.doi.org/10.18653/v1/2024.emnlp-demo.25)Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p1.1)\.
- I\. Kacem, N\. Souayah, and M\. Haouari \(2012\)Branch\-and\-bound algorithm for total weighted tardinessminimization on parallel machines under release dates assumptions\.RAIRO \- Operations Research46\(2\),pp\. 125–147\.External Links:[Document](https://dx.doi.org/10.1051/ro/2012010)Cited by:[§B\.2](https://arxiv.org/html/2607.16745#A2.SS2.SSS0.Px1.p1.7)\.
- J\. Kallestad, R\. Hasibi, A\. Hemmati, and K\. Sörensen \(2023\)A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems\.European Journal of Operational Research309\(1\),pp\. 446–468\.External Links:ISSN 0377\-2217,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.ejor.2023.01.017),[Link](https://www.sciencedirect.com/science/article/pii/S037722172300036X)Cited by:[§4](https://arxiv.org/html/2607.16745#S4.SS0.SSS0.Px1.p1.1)\.
- N\. V\. T\. Kiet, T\. Dao, C\. D\. Tran, and H\. T\. T\. Binh \(2026\)MOTIF: multi\-strategy optimization via turn\-based interactive framework\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 37000–37008\.Cited by:[§A\.1](https://arxiv.org/html/2607.16745#A1.SS1.p2.1),[§2\.2](https://arxiv.org/html/2607.16745#S2.SS2.p1.2),[§4](https://arxiv.org/html/2607.16745#S4.SS0.SSS0.Px1.p1.1)\.
- E\. Kirac, A\. B\. Milburn, and R\. Gedik \(2025\)The dynamic team orienteering problem\.European Journal of Operational Research324\(1\),pp\. 22–39\.External Links:ISSN 0377\-2217,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.ejor.2025.01.009),[Link](https://www.sciencedirect.com/science/article/pii/S0377221725000347)Cited by:[§B\.1](https://arxiv.org/html/2607.16745#A2.SS1.SSS0.Px3.p1.3)\.
- G\. J\. Kyparisis and C\. Koulamas \(2001\)A note on weighted completion time minimization in a flexible flow shop\.Operations Research Letters29\(1\),pp\. 5–11\.External Links:ISSN 0167\-6377,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/S0167-6377%2801%2900072-4),[Link](https://www.sciencedirect.com/science/article/pii/S0167637701000724)Cited by:[§B\.2](https://arxiv.org/html/2607.16745#A2.SS2.SSS0.Px3.p1.7)\.
- D\. Li, Z\. Li, H\. Du, X\. Wu, S\. Gui, Y\. Kuang, and L\. Sun \(2026\)Graph of skills: dependency\-aware structural retrieval for massive agent skills\.arXiv preprint arXiv:2604\.05333\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1),[§1](https://arxiv.org/html/2607.16745#S1.p5.1)\.
- Z\. Li, W\. Zhao, and J\. Pajarinen \(2025\)Cooperative multi\-agent planning with adaptive skill synthesis\.arXiv preprint arXiv:2502\.10148\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p5.1)\.
- J\. Liang, W\. Huang, F\. Xia, P\. Xu, K\. Hausman, B\. Ichter, P\. Florence, and A\. Zeng \(2023\)Code as policies: language model programs for embodied control\.In2023 IEEE International conference on robotics and automation \(ICRA\),pp\. 9493–9500\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
- F\. Liu, Y\. Liu, Q\. Zhang, T\. Xialiang, and M\. Yuan \(2026\)Eoh\-s: evolution of heuristic set using llms for automated heuristic design\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 37090–37098\.Cited by:[§A\.1](https://arxiv.org/html/2607.16745#A1.SS1.p2.1)\.
- F\. Liu, T\. Xialiang, M\. Yuan, X\. Lin, F\. Luo, Z\. Wang, Z\. Lu, and Q\. Zhang \(2024\)Evolution of heuristics: towards efficient automatic algorithm design using large language model\.InInternational Conference on Machine Learning,pp\. 32201–32223\.Cited by:[§A\.1](https://arxiv.org/html/2607.16745#A1.SS1.p1.1)\.
- Y\. Liu, L\. Palmieri, S\. Koch, I\. Georgievski, and M\. Aiello \(2025\)Delta: decomposed efficient long\-term robot task planning using large language models\.In2025 IEEE International Conference on Robotics and Automation \(ICRA\),pp\. 10995–11001\.Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p2.1)\.
- S\. Mahdavi, R\. Aoki, K\. Tang, and Y\. Cao \(2024\)Leveraging environment interaction for automated pddl translation and planning with large language models\.Advances in Neural Information Processing Systems37,pp\. 38960–39008\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
- J\. Oswald, K\. Srinivas, H\. Kokel, J\. Lee, M\. Katz, and S\. Sohrabi \(2024\)Large language models as planning domain generators\.In34th International Conference on Automated Planning and Scheduling,External Links:[Link](https://openreview.net/forum?id=C88wQIv0aJ)Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
- J\. Pei, J\. Liu, and Y\. Mei \(2024\)Learning from offline and online experiences: a hybrid adaptive operator selection framework\.InProceedings of the genetic and evolutionary computation conference,pp\. 1017–1025\.Cited by:[§4](https://arxiv.org/html/2607.16745#S4.SS0.SSS0.Px1.p1.1)\.
- M\. A\. Potter and K\. A\. D\. Jong \(2000\)Cooperative coevolution: an architecture for evolving coadapted subcomponents\.Evolutionary Computation8\(1\),pp\. 1–29\.External Links:[Document](https://dx.doi.org/10.1162/106365600568086)Cited by:[§4](https://arxiv.org/html/2607.16745#S4.SS0.SSS0.Px1.p1.1)\.
- T\. Silver, S\. Dan, K\. Srinivas, J\. B\. Tenenbaum, L\. Kaelbling, and M\. Katz \(2024\)Generalized planning in pddl domains with pretrained large language models\.InProceedings of the AAAI conference on artificial intelligence,Vol\.38,pp\. 20256–20264\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
- A\. Singh, A\. Krause, C\. Guestrin, and W\. J\. Kaiser \(2009\)Efficient informative sensing using multiple robots\.Journal of Artificial Intelligence Research34,pp\. 707–755\.Cited by:[§B\.1](https://arxiv.org/html/2607.16745#A2.SS1.SSS0.Px2.p1.1)\.
- I\. Singh, V\. Blukis, A\. Mousavian, A\. Goyal, D\. Xu, J\. Tremblay, D\. Fox, J\. Thomason, and A\. Garg \(2023\)ProgPrompt: generating situated robot task plans using large language models\.In2023 IEEE International Conference on Robotics and Automation \(ICRA\),pp\. 11523–11530\.Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p2.1)\.
- Y\. Tang, Z\. Wang, A\. Qu, Y\. Yan, Z\. Wu, D\. Zhuang, J\. Kai, K\. Hou, X\. Guo, J\. Zhao, Z\. Zhao, and W\. Ma \(2024\)ItiNera: integrating spatial optimization with large language models for open\-domain urban itinerary planning\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track,F\. Dernoncourt, D\. Preoţiuc\-Pietro, and A\. Shimorina \(Eds\.\),Miami, Florida, US,pp\. 1413–1432\.External Links:[Link](https://aclanthology.org/2024.emnlp-industry.104/),[Document](https://dx.doi.org/10.18653/v1/2024.emnlp-industry.104)Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p1.1)\.
- C\. Wang, Z\. Yu, X\. Xie, W\. Yao, R\. Fang, S\. Qiao, K\. Cao, G\. Zheng, X\. Qi, P\. Zhang,et al\.\(2026\)SkillX: automatically constructing skill knowledge bases for agents\.arXiv preprint arXiv:2604\.04804\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
- Y\. Yang, H\. Chai, S\. Shao, Y\. Song, S\. Qi, R\. Rui, and W\. Zhang \(2025\)AgentNet: decentralized evolutionary coordination for LLM\-based multi\-agent systems\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=tXqLxHlb8Z)Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p5.1)\.
- H\. Ye, J\. Wang, Z\. Cao, F\. Berto, C\. Hua, H\. Kim, J\. Park, and G\. Song \(2024\)Reevo: large language models as hyper\-heuristics with reflective evolution\.Advances in neural information processing systems37,pp\. 43571–43608\.Cited by:[§A\.1](https://arxiv.org/html/2607.16745#A1.SS1.p1.1)\.
- J\. Zhang, J\. Zhang, K\. Pertsch, Z\. Liu, X\. Ren, M\. Chang, S\. Sun, and J\. J\. Lim \(2023\)Bootstrap your own skills: learning to solve new tasks with large language model guidance\.InConference on Robot Learning,pp\. 302–325\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
- X\. Zhang, Y\. Ding, Y\. Hayamizu, Z\. Altaweel, Y\. Zhu, Y\. Zhu, P\. Stone, C\. Paxton, and S\. Zhang \(2025\)LLM\-grop: visually grounded robot task and motion planning with large language models\.The International Journal of Robotics Research,pp\. 02783649251378196\.Cited by:[§A\.2](https://arxiv.org/html/2607.16745#A1.SS2.p2.1)\.
- Z\. Zheng, Z\. Xie, Z\. Wang, and B\. Hooi \(2025\)Monte carlo tree search for comprehensive exploration in llm\-based automatic heuristic design\.InInternational Conference on Machine Learning,pp\. 78338–78373\.Cited by:[§A\.1](https://arxiv.org/html/2607.16745#A1.SS1.p1.1),[§2\.2](https://arxiv.org/html/2607.16745#S2.SS2.p1.2)\.
- C\. Zhu, M\. Vanniasinghe, J\. Chen, and C\. Lee \(2026\)Offline discovery of interpretable skills from multi\-task trajectories\.arXiv preprint arXiv:2602\.01018\.Cited by:[§1](https://arxiv.org/html/2607.16745#S1.p1.1)\.
Appendix: Supplementary Material
RELIC: Revealed Principles for Learning Interpretable Composable Skills in Multi\-Agent Planning
## Appendix ARelated Works
We briefly review the most relevant research threads surrounding our setting, with particular emphasis on LLM\-based heuristic construction, reusable skill learning, and decentralized cooperation\. This discussion clarifies the gap addressed by RELIC: interoperable skill discovery across independently trained agents under limited information sharing\.
### A\.1LLMs for Automated Heuristic Design
Recent work has shown that large language models \(LLMs\) can serve as powerful search operators for*automated heuristic design*\(AHD\), where the goal is to discover high\-quality algorithmic components with minimal human intervention\. A representative line of work is EoH\(Liuet al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib15)\), which combines evolutionary search with LLM\-based generation of both high\-level heuristic ideas and executable code, demonstrating that natural\-language “thoughts” can be treated as evolving search objects alongside programs\. ReEvo\(Yeet al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib14)\)further develops this direction by framing LLMs as reflective hyper\-heuristics, using iterative self\-reflection and evolutionary improvement to generate stronger heuristics and meta\-heuristics across optimization tasks\. Moving beyond population\-based evolution, MCTS\-AHD\(Zhenget al\.,[2025](https://arxiv.org/html/2607.16745#bib.bib16)\)replaces greedy population updates with Monte Carlo Tree Search, preserving a richer search history and enabling more comprehensive exploration of the heuristic space\.
More recent work expands the design space beyond a single heuristic\. MOTIF\(Kietet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib13)\)formulates automated solver design as a*multi\-strategy*optimization problem, where multiple interdependent components are improved through a turn\-based interactive framework between LLM agents\. EoH\-S\(Liuet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib17)\)shifts the objective from discovering one universal heuristic to constructing a*complementary heuristic set*, aiming for stronger robustness across heterogeneous instances and distributions\. HiFo\-Prompt\(ChentongChenet al\.,[2026](https://arxiv.org/html/2607.16745#bib.bib18)\)introduces hindsight and foresight mechanisms to guide LLM\-based AHD, explicitly controlling the exploration–exploitation trade\-off while accumulating reusable design principles over time\. Overall, these methods primarily focus on centralized heuristic or component search\. In contrast, RELIC studies*cooperative planning*under decomposition, where multiple agents improve private decision functions separately while exchanging only abstract principles through a shared public structure\.
### A\.2LLMs for Planning Optimization
A related line of work uses LLMs for*automated planning and optimization*in domains such as routing, itinerary generation, urban operations, and robot task planning\. One common paradigm is to use LLMs as an interface between natural\-language requests and downstream optimization modules\. For example, TTG\(Juet al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib23)\)translates user requests into symbolic constraints and then invokes a mixed\-integer optimization solver to produce guaranteed travel plans\. ItiNera\(Tanget al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib24)\)similarly combines LLM\-based request understanding with explicit spatial optimization for open\-domain urban itinerary planning\. At a broader systems level, UrbanLLM\(Jianget al\.,[2024](https://arxiv.org/html/2607.16745#bib.bib25)\)studies LLMs as decision\-making agents for urban activity planning and management, covering planning problems with realistic operational structure and constraints\. These works show that LLMs are useful not only for language understanding, but also for generating structured optimization inputs and coordinating solver\-based planning pipelines\.
Another closely related direction focuses on*robotic planning*, where LLMs are combined with symbolic actions, affordances, or motion feasibility constraints\. SayCan\(ichteret al\.,[2023](https://arxiv.org/html/2607.16745#bib.bib26)\)grounds language\-model action selection using robot affordances, enabling long\-horizon execution of high\-level tasks on real robots\. Inner Monologue\(Huanget al\.,[2022](https://arxiv.org/html/2607.16745#bib.bib27)\)extends this idea by incorporating environment feedback and re\-planning during execution\. ProgPrompt\(Singhet al\.,[2023](https://arxiv.org/html/2607.16745#bib.bib28)\)represents robot plans as executable program\-like prompts, improving situated task planning under explicit action and object vocabularies\. More recent systems push further toward hierarchical and embodied planning: DELTA\(Liuet al\.,[2025](https://arxiv.org/html/2607.16745#bib.bib29)\)decomposes long\-horizon robot tasks before invoking automated planners, while LLM\-GROP\(Zhanget al\.,[2025](https://arxiv.org/html/2607.16745#bib.bib30)\)integrates visual grounding with task\-and\-motion planning for mobile manipulation\. Compared with these approaches, RELIC is not aimed at directly producing a single plan for one instance\. Instead, it learns and improves reusable*planning decision functions*for cooperative multi\-agent optimization, with private local search and restricted information sharing through distilled public principles\.
## Appendix BProblems & Algorithms
This appendix presents the six benchmark optimization problems considered in this work\. They are organized into two families\. The first family,*multi\-agent path planning*, concerns teams of mobile agents that must coordinate their movements on a metric graph under limited travel budgets\. These models are directly relevant to applications such as persistent monitoring, environmental reconnaissance, search\-and\-rescue, and field servicing\. The second family,*multi\-agent scheduling*, concerns decentralized dispatching over multiple resources or processing stages, where each agent controls a local decision rule while performance is evaluated through a global system\-level objective\. Such settings arise naturally in manufacturing, service operations, warehouse control, and heterogeneous human–robot teamwork\.
Throughout this appendix, the set of agents is denoted by
𝒦=\{A,B,C\}\.\\mathcal\{K\}=\\\{A,B,C\\\}\.Each agent controls one local decision function\. The resulting problems are cooperative: actions are selected locally, but the objective is defined at the team level\.
### B\.1Multi\-Agent Path Planning
The first family considers cooperative routing on a metric graph\. Let
G=\(𝒱,ℰ\),𝒱=\{0,1,…,N\},G=\(\\mathcal\{V\},\\mathcal\{E\}\),\\qquad\\mathcal\{V\}=\\\{0,1,\\dots,N\\\},where node0is a common depot and each edge\(i,j\)∈ℰ\(i,j\)\\in\\mathcal\{E\}has metric travel costℓij≥0\\ell\_\{ij\}\\geq 0, induced by Euclidean coordinates\. Each agentk∈𝒦k\\in\\mathcal\{K\}starts from the depot and must execute a route whose total travel cost does not exceed a budgetB\>0B\>0\. The three problems differ in the reward structure associated with visiting nodes\.
#### Multi\-Agent Prize Collection\.
This problem is also known as the*Team Orienteering Problem*\(Chaoet al\.,[1996](https://arxiv.org/html/2607.16745#bib.bib35)\)\. Each non\-depot nodei∈𝒱∖\{0\}i\\in\\mathcal\{V\}\\setminus\\\{0\\\}carries a prizeqi≥0q\_\{i\}\\geq 0\. For each agentk∈𝒦k\\in\\mathcal\{K\}, let
Pk=\(vk,0,vk,1,…,vk,Tk\)P\_\{k\}=\(v\_\{k,0\},v\_\{k,1\},\\dots,v\_\{k,T\_\{k\}\}\)denote its route, with
vk,0=0,vk,Tk=0,v\_\{k,0\}=0,\\qquad v\_\{k,T\_\{k\}\}=0,and with the budget constraint
∑t=1Tkℓvk,t−1,vk,t≤B,∀k∈𝒦\.\\sum\_\{t=1\}^\{T\_\{k\}\}\\ell\_\{v\_\{k,t\-1\},v\_\{k,t\}\}\\leq B,\\qquad\\forall k\\in\\mathcal\{K\}\.Each prize can be collected at most once by the team\. Define the binary variable
yi=\{1,if nodeiis visited by at least one agent,0,otherwise,i∈𝒱∖\{0\}\.y\_\{i\}=\\begin\{cases\}1,&\\text\{if node \}i\\text\{ is visited by at least one agent\},\\\\ 0,&\\text\{otherwise\},\\end\{cases\}\\qquad i\\in\\mathcal\{V\}\\setminus\\\{0\\\}\.The problem can then be written as
max\(Pk\)k∈𝒦,y∑i∈𝒱∖\{0\}qiyi\\max\_\{\(P\_\{k\}\)\_\{k\\in\\mathcal\{K\}\},\\,y\}\\;\\sum\_\{i\\in\\mathcal\{V\}\\setminus\\\{0\\\}\}q\_\{i\}y\_\{i\}subject to
yi≤∑k∈𝒦∑t=1Tk−1𝟏\{vk,t=i\},∀i∈𝒱∖\{0\},y\_\{i\}\\leq\\sum\_\{k\\in\\mathcal\{K\}\}\\sum\_\{t=1\}^\{T\_\{k\}\-1\}\\mathbf\{1\}\\\{v\_\{k,t\}=i\\\},\\qquad\\forall i\\in\\mathcal\{V\}\\setminus\\\{0\\\},yi∈\{0,1\},∀i∈𝒱∖\{0\},y\_\{i\}\\in\\\{0,1\\\},\\qquad\\forall i\\in\\mathcal\{V\}\\setminus\\\{0\\\},together with the route\-budget constraints above\. The objective is to maximize the total prize collected by the team under decentralized routing\.
#### Multi\-Agent Area Reconnaissance\.
This problem is studied in the context of multi\-robot reconnaissance and information gathering\(Singhet al\.,[2009](https://arxiv.org/html/2607.16745#bib.bib36)\)\. Here, node visits generate*information gain*rather than direct reward\. Each nodei∈𝒱∖\{0\}i\\in\\mathcal\{V\}\\setminus\\\{0\\\}initially carries unit uncertainty, whereas the depot has zero uncertainty:
ui\(0\)=\{0,i=0,1,i∈𝒱∖\{0\}\.u\_\{i\}^\{\(0\)\}=\\begin\{cases\}0,&i=0,\\\\ 1,&i\\in\\mathcal\{V\}\\setminus\\\{0\\\}\.\\end\{cases\}Letσ\>0\\sigma\>0be a correlation parameter and define the spatial correlation kernel
ρij=exp\(−ℓij22σ2\),∀i,j∈𝒱\.\\rho\_\{ij\}=\\exp\\\!\\left\(\-\\frac\{\\ell\_\{ij\}^\{2\}\}\{2\\sigma^\{2\}\}\\right\),\\qquad\\forall i,j\\in\\mathcal\{V\}\.If the set of non\-depot nodes scanned by the team at decision epochttis denoted by𝒮\(t\)⊆𝒱∖\{0\}\\mathcal\{S\}^\{\(t\)\}\\subseteq\\mathcal\{V\}\\setminus\\\{0\\\}, then the residual uncertainty evolves according to
uj\(t\+1\)=uj\(t\)∏s∈𝒮\(t\)\(1−ρsj\),∀j∈𝒱,u\_\{j\}^\{\(t\+1\)\}=u\_\{j\}^\{\(t\)\}\\prod\_\{s\\in\\mathcal\{S\}^\{\(t\)\}\}\(1\-\\rho\_\{sj\}\),\\qquad\\forall j\\in\\mathcal\{V\},followed by the convention
u0\(t\+1\)=0,us\(t\+1\)=0∀s∈𝒮\(t\)\.u\_\{0\}^\{\(t\+1\)\}=0,\\qquad u\_\{s\}^\{\(t\+1\)\}=0\\quad\\forall s\\in\\mathcal\{S\}^\{\(t\)\}\.Thus, scanning a node reduces uncertainty not only at the scanned location, but also in nearby regions through a Gaussian spillover mechanism\.
LetPkP\_\{k\}denote the route of agentkk, with the same route feasibility condition
∑t=1Tkℓvk,t−1,vk,t≤B,∀k∈𝒦\.\\sum\_\{t=1\}^\{T\_\{k\}\}\\ell\_\{v\_\{k,t\-1\},v\_\{k,t\}\}\\leq B,\\qquad\\forall k\\in\\mathcal\{K\}\.The objective is to minimize the final residual uncertainty, equivalently to maximize the total uncertainty reduction:
min\(Pk\)k∈𝒦∑i∈𝒱ui\(T\)⟺max\(Pk\)k∈𝒦∑i∈𝒱\(ui\(0\)−ui\(T\)\),\\min\_\{\(P\_\{k\}\)\_\{k\\in\\mathcal\{K\}\}\}\\;\\sum\_\{i\\in\\mathcal\{V\}\}u\_\{i\}^\{\(T\)\}\\qquad\\Longleftrightarrow\\qquad\\max\_\{\(P\_\{k\}\)\_\{k\\in\\mathcal\{K\}\}\}\\;\\sum\_\{i\\in\\mathcal\{V\}\}\\Bigl\(u\_\{i\}^\{\(0\)\}\-u\_\{i\}^\{\(T\)\}\\Bigr\),whereTTdenotes the terminal decision epoch\. The practical significance of this model lies in coordinated sensing and surveillance, where redundant scans are undesirable and spatially complementary coverage is essential\.
#### Multi\-Agent Dynamic Servicing\.
This problem studies cooperative routing under stochastic, time\-sensitive demand\(Kiracet al\.,[2025](https://arxiv.org/html/2607.16745#bib.bib37)\)\. For each non\-depot nodei∈𝒱∖\{0\}i\\in\\mathcal\{V\}\\setminus\\\{0\\\}, service requests arrive over discrete time according to a stochastic process with intensity parameterλi\\lambda\_\{i\}\. A realized requestρ\\rhois characterized by:
iρ∈𝒱∖\{0\}\(location\),τρ∈ℤ≥0\(arrival time\),i\_\{\\rho\}\\in\\mathcal\{V\}\\setminus\\\{0\\\}\\quad\\text\{\(location\)\},\\qquad\\tau\_\{\\rho\}\\in\\mathbb\{Z\}\_\{\\geq 0\}\\quad\\text\{\(arrival time\)\},wρ\>0\(service value\),δρ∈ℤ\>0\(deadline horizon\)\.w\_\{\\rho\}\>0\\quad\\text\{\(service value\)\},\\qquad\\delta\_\{\\rho\}\\in\\mathbb\{Z\}\_\{\>0\}\\quad\\text\{\(deadline horizon\)\}\.A request is active over the time window
t∈\[τρ,τρ\+δρ\]\.t\\in\[\\tau\_\{\\rho\},\\tau\_\{\\rho\}\+\\delta\_\{\\rho\}\]\.In the benchmark generator, request values are drawn from node\-dependent exponential distributions and deadlines are sampled from a finite discrete range\.
A feasible team policy must jointly determine the routes of the agents and the requests to be served\. Letzρ∈\{0,1\}z\_\{\\rho\}\\in\\\{0,1\\\}indicate whether requestρ\\rhois served before expiration\. If agentkkarrives at nodeiρi\_\{\\rho\}during the active interval of requestρ\\rho, then that request may be served\. Since at most one request is served per arrival event, the realized service variables must satisfy node\-time capacity constraints induced by the selected routes\.
The objective is to maximize the expected total serviced value:
maxπ𝔼\[∑ρwρzρ\],\\max\_\{\\pi\}\\;\\mathbb\{E\}\\\!\\left\[\\sum\_\{\\rho\}w\_\{\\rho\}z\_\{\\rho\}\\right\],whereπ=\(πk\)k∈𝒦\\pi=\(\\pi\_\{k\}\)\_\{k\\in\\mathcal\{K\}\}denotes a collection of decentralized causal policies, and the expectation is taken over the request\-arrival process\. Route feasibility must still hold for every agent:
∑t=1Tkℓvk,t−1,vk,t≤B,∀k∈𝒦\.\\sum\_\{t=1\}^\{T\_\{k\}\}\\ell\_\{v\_\{k,t\-1\},v\_\{k,t\}\}\\leq B,\\qquad\\forall k\\in\\mathcal\{K\}\.This formulation captures online fleet coordination in settings such as maintenance dispatch, emergency response, and on\-demand field service, where requests are spatially distributed, stochastic, and perishable\.
### B\.2Multi\-Agent Scheduling
The second family concerns decentralized scheduling under asynchronous decision epochs\. Each agent controls a local resource and repeatedly chooses which available job or task to process next\. The team objective depends on the global interaction of these local dispatching decisions through release times, due dates, processing times, skill heterogeneity, and precedence constraints\.
#### Multi\-Agent Job Dispatch\.
This benchmark follows parallel\-machine job dispatch under weighted tardiness objectives\(Kacemet al\.,[2012](https://arxiv.org/html/2607.16745#bib.bib38)\)\. Consider a set of jobs
𝒥=\{1,…,N\}\\mathcal\{J\}=\\\{1,\\dots,N\\\}and a set of identical parallel machines
ℳ=\{1,2,3\},\\mathcal\{M\}=\\\{1,2,3\\\},with one machine controlled by each agent in𝒦\\mathcal\{K\}\. Each jobj∈𝒥j\\in\\mathcal\{J\}has release timerjr\_\{j\}, processing timepjp\_\{j\}, due datedjd\_\{j\}, and weightωj≥0\\omega\_\{j\}\\geq 0\. Each job must be assigned to exactly one machine and processed non\-preemptively\.
Letxjm∈\{0,1\}x\_\{jm\}\\in\\\{0,1\\\}indicate whether jobjjis assigned to machinemm, letSjS\_\{j\}be its start time, and letCjC\_\{j\}be its completion time\. The weighted tardiness of jobjjis
Tj=max\{0,Cj−dj\}\.T\_\{j\}=\\max\\\{0,C\_\{j\}\-d\_\{j\}\\\}\.A standard mixed\-integer formulation is
minx,S,C,π∑j∈𝒥ωjTj\\min\_\{x,S,C,\\pi\}\\;\\sum\_\{j\\in\\mathcal\{J\}\}\\omega\_\{j\}T\_\{j\}subject to
∑m∈ℳxjm=1,∀j∈𝒥,\\sum\_\{m\\in\\mathcal\{M\}\}x\_\{jm\}=1,\\qquad\\forall j\\in\\mathcal\{J\},Sj≥rj,Cj=Sj\+pj,∀j∈𝒥,S\_\{j\}\\geq r\_\{j\},\\qquad C\_\{j\}=S\_\{j\}\+p\_\{j\},\\qquad\\forall j\\in\\mathcal\{J\},and disjunctive no\-overlap constraints on each machine\. For all distincti,j∈𝒥i,j\\in\\mathcal\{J\}and allm∈ℳm\\in\\mathcal\{M\}, letπijm∈\{0,1\}\\pi\_\{ijm\}\\in\\\{0,1\\\}indicate whether jobiiprecedes jobjjon machinemm\. Then
Si\+pi≤Sj\+M\(1−πijm\)\+M\(2−xim−xjm\),S\_\{i\}\+p\_\{i\}\\leq S\_\{j\}\+M\(1\-\\pi\_\{ijm\}\)\+M\(2\-x\_\{im\}\-x\_\{jm\}\),Sj\+pj≤Si\+Mπijm\+M\(2−xim−xjm\),S\_\{j\}\+p\_\{j\}\\leq S\_\{i\}\+M\\pi\_\{ijm\}\+M\(2\-x\_\{im\}\-x\_\{jm\}\),whereMMis a sufficiently large constant\. The objective is therefore to minimize total weighted tardiness\.
From an operational viewpoint, this problem is solved online: whenever machinemmbecomes idle at timett, its controller selects one released and unassigned job from the available pool
𝒜\(t\)=\{j∈𝒥:rj≤t,jnot yet assigned\}\.\\mathcal\{A\}\(t\)=\\\{j\\in\\mathcal\{J\}:r\_\{j\}\\leq t,\\;j\\text\{ not yet assigned\}\\\}\.This corresponds to decentralized dispatching in deadline\-sensitive production or service environments\.
#### Multi\-Agent Skilled Tasks\.
This benchmark follows heterogeneous task scheduling with category\-dependent agent efficiency\(Fırat and Hurkens,[2012](https://arxiv.org/html/2607.16745#bib.bib39)\)\. Let
𝒥=\{1,…,N\}\\mathcal\{J\}=\\\{1,\\dots,N\\\}be the set of tasks and let
𝒞=\{1,…,S\}\\mathcal\{C\}=\\\{1,\\dots,S\\\}be the set of skill categories\. Each taskj∈𝒥j\\in\\mathcal\{J\}is associated with:
rj\(release time\),cj∈𝒞\(category\),r\_\{j\}\\quad\\text\{\(release time\)\},\\qquad c\_\{j\}\\in\\mathcal\{C\}\\quad\\text\{\(category\)\},pj\>0\(nominal processing requirement\),vj\>0\(value\),dj\(deadline\)\.p\_\{j\}\>0\\quad\\text\{\(nominal processing requirement\)\},\\qquad v\_\{j\}\>0\\quad\\text\{\(value\)\},\\qquad d\_\{j\}\\quad\\text\{\(deadline\)\}\.Each agentk∈𝒦k\\in\\mathcal\{K\}possesses a skill matrix entryαks\>0\\alpha\_\{ks\}\>0for categorys∈𝒞s\\in\\mathcal\{C\}\. If taskjjis executed by agentkk, then its effective processing time becomes
p~jk=pjαk,cj\.\\widetilde\{p\}\_\{jk\}=\\frac\{p\_\{j\}\}\{\\alpha\_\{k,c\_\{j\}\}\}\.
Letxjk∈\{0,1\}x\_\{jk\}\\in\\\{0,1\\\}indicate assignment of taskjjto agentkk, letSjS\_\{j\}andCjC\_\{j\}denote its start and completion times, and letzj∈\{0,1\}z\_\{j\}\\in\\\{0,1\\\}indicate whether the task is completed on time\. A natural formulation is
maxx,S,C,z,π∑j∈𝒥vjzj\\max\_\{x,S,C,z,\\pi\}\\;\\sum\_\{j\\in\\mathcal\{J\}\}v\_\{j\}z\_\{j\}subject to
∑k∈𝒦xjk≤1,∀j∈𝒥,\\sum\_\{k\\in\\mathcal\{K\}\}x\_\{jk\}\\leq 1,\\qquad\\forall j\\in\\mathcal\{J\},Sj≥rj,∀j∈𝒥,S\_\{j\}\\geq r\_\{j\},\\qquad\\forall j\\in\\mathcal\{J\},Cj≥Sj\+p~jk−M\(1−xjk\),∀j∈𝒥,∀k∈𝒦,C\_\{j\}\\geq S\_\{j\}\+\\widetilde\{p\}\_\{jk\}\-M\(1\-x\_\{jk\}\),\\qquad\\forall j\\in\\mathcal\{J\},\\;\\forall k\\in\\mathcal\{K\},Cj≤dj\+M\(1−zj\),∀j∈𝒥,C\_\{j\}\\leq d\_\{j\}\+M\(1\-z\_\{j\}\),\\qquad\\forall j\\in\\mathcal\{J\},together with no\-overlap constraints on each agent\. For all distincti,j∈𝒥i,j\\in\\mathcal\{J\}and allk∈𝒦k\\in\\mathcal\{K\}, withπijk∈\{0,1\}\\pi\_\{ijk\}\\in\\\{0,1\\\},
Si\+p~ik≤Sj\+M\(1−πijk\)\+M\(2−xik−xjk\),S\_\{i\}\+\\widetilde\{p\}\_\{ik\}\\leq S\_\{j\}\+M\(1\-\\pi\_\{ijk\}\)\+M\(2\-x\_\{ik\}\-x\_\{jk\}\),Sj\+p~jk≤Si\+Mπijk\+M\(2−xik−xjk\)\.S\_\{j\}\+\\widetilde\{p\}\_\{jk\}\\leq S\_\{i\}\+M\\pi\_\{ijk\}\+M\(2\-x\_\{ik\}\-x\_\{jk\}\)\.The objective is to maximize the total value of tasks completed no later than their deadlines\. This formulation is particularly relevant to specialist teams, where the same task may be easy for one agent but difficult for another\.
#### Multi\-Agent Flow Shop\.
This benchmark follows three\-stage flow\-shop scheduling under weighted completion objectives\(Kyparisis and Koulamas,[2001](https://arxiv.org/html/2607.16745#bib.bib40)\)\. The benchmark is a three\-stage flow shop\. Let
𝒥=\{1,…,N\}\\mathcal\{J\}=\\\{1,\\dots,N\\\}be the job set and let
𝒮=\{1,2,3\}\\mathcal\{S\}=\\\{1,2,3\\\}be the ordered set of processing stages\. Stages∈𝒮s\\in\\mathcal\{S\}is controlled by one agent in𝒦\\mathcal\{K\}\. Each jobj∈𝒥j\\in\\mathcal\{J\}has release timerjr\_\{j\}, stage\-specific processing timespj1,pj2,pj3p\_\{j1\},p\_\{j2\},p\_\{j3\}, and weightωj≥0\\omega\_\{j\}\\geq 0\. Every job must visit the stages in the fixed order
1→2→3\.1\\rightarrow 2\\rightarrow 3\.
LetSjsS\_\{js\}andCjsC\_\{js\}denote the start and completion times of jobjjat stagess\. The objective is to minimize the total weighted completion time at the final stage:
minS,C,π∑j∈𝒥ωjCj3\.\\min\_\{S,C,\\pi\}\\;\\sum\_\{j\\in\\mathcal\{J\}\}\\omega\_\{j\}C\_\{j3\}\.The formulation is subject to release\-time and technological precedence constraints:
Sj1≥rj,Cjs=Sjs\+pjs,∀j∈𝒥,s∈𝒮,S\_\{j1\}\\geq r\_\{j\},\\qquad C\_\{js\}=S\_\{js\}\+p\_\{js\},\\qquad\\forall j\\in\\mathcal\{J\},\\;s\\in\\mathcal\{S\},Sj,s\+1≥Cjs,∀j∈𝒥,s=1,2\.S\_\{j,s\+1\}\\geq C\_\{js\},\\qquad\\forall j\\in\\mathcal\{J\},\\;s=1,2\.Machine\-capacity constraints must hold at each stage\. For all distincti,j∈𝒥i,j\\in\\mathcal\{J\}and alls∈𝒮s\\in\\mathcal\{S\}, letπijs∈\{0,1\}\\pi\_\{ijs\}\\in\\\{0,1\\\}indicate whether jobiiprecedes jobjjon stagess\. Then
Sis\+pis≤Sjs\+M\(1−πijs\),S\_\{is\}\+p\_\{is\}\\leq S\_\{js\}\+M\(1\-\\pi\_\{ijs\}\),Sjs\+pjs≤Sis\+Mπijs\.S\_\{js\}\+p\_\{js\}\\leq S\_\{is\}\+M\\pi\_\{ijs\}\.The objective thus penalizes late completion of high\-weight jobs at the end of the production line\.
In decentralized online form, whenever stagessbecomes available at timett, its controller selects a job from the current admissible buffer
ℬs\(t\)=\{j∈𝒥:jobjhas completed stages−1,is ready att,and has not yet started stages\},\\mathcal\{B\}\_\{s\}\(t\)=\\\{j\\in\\mathcal\{J\}:\\text\{job \}j\\text\{ has completed stage \}s\-1,\\;\\text\{is ready at \}t,\\;\\text\{and has not yet started stage \}s\\\},with the convention that stage11uses release timesrjr\_\{j\}as readiness times\. This benchmark therefore captures local dispatching inside a multistage production system with strict precedence structure and globally coupled performance\.
## Appendix CExperimental Settings
#### Evaluation protocol\.
We evaluate all methods on the six benchmark problems described in the previous section\. Each problem uses the same three\-agent setup, with one local decision function per agent\. For every problem, training consists of a stream of five batches with1010instances per batch\. The training size is smaller than the test size: the three path\-planning problems are trained on instances withN=40N=40nodes, the job\-dispatch and skilled\-task problems are trained on instances withN=30N=30, and the flow\-shop problem is trained on instances withN=25N=25\. Evaluation is conducted on two larger held\-out test sets withN∈\{50,80\}N\\in\\\{50,80\\\}, each containing2020instances\.
RELIC processes the training stream sequentially in batch order\. In contrast, all non\-LLM baselines are trained in a centralized regime\. GS, HHS, and CCEA operate on the aggregated offline training set; HAOS and RL\-IS retain the batch decomposition but still train offline over multiple passes through the full stream rather than adapting in a single pass\. For the heuristic\-based baselines, the candidate primitive set is the same handcrafted role\-specific pool used throughout the repository\. For MOTIF, we match the problem interfaces, seed initialization, and search budget to those of RELIC to ensure a fair comparison\.
#### RELIC configuration\.
Unless otherwise stated, all RELIC experiments use the default configuration in the released implementation\. We usegpt\-4o\-minias the underlying LLM backbone with sampling temperature1\.01\.0\. At each training batch, every agent performs1010private search iterations, yielding5×3×10=1505\\times 3\\times 10=150private program\-expansion steps per run\. The private search tree uses maximum depth88, replay size22, and equal exploration constants for node, operator, and public\-principle selection\.
#### Agent roles and function signatures\.
Across all benchmarks, the three agents follow the same high\-level role decomposition\. AgentAAis a myopic local decision maker: it observes only its own state and the currently available options\. AgentBBis teammate\-aware: it receives limited runtime information about other agents, such as current positions, busy times, or local states\. AgentCCis global\-planning oriented: it receives a denser system\-level representation, such as full remaining\-value vectors, machine\-load vectors, or pipeline state\. This design creates heterogeneous skill signatures even within the same cooperative task\. RELIC must therefore learn interoperable behavior across agents whose executable functions expose different arguments and information\.
Listing 1:Function signatures for the three multi\-agent path\-planning benchmarks\.1
2defselect\_next\_A\(current:int,unvisited\_prizes:dict,
3dist\_mat:np\.ndarray,
4budget\_left:float\)\-\>int:\.\.\.
5
6defselect\_next\_B\(my\_state:dict,teammate\_positions:list,
7graph:dict,
8budget\_left:float\)\-\>int:\.\.\.
9
10defselect\_next\_C\(current:int,dist\_row:np\.ndarray,
11remaining\_prizes:np\.ndarray,
12remaining\_budget:float\)\-\>int:\.\.\.
13
14
15
16defselect\_next\_A\(current:int,uncertainty\_dict:dict,
17dist\_mat:np\.ndarray,
18budget\_left:float\)\-\>int:\.\.\.
19
20defselect\_next\_B\(my\_state:dict,teammate\_positions:list,
21graph:dict,
22budget\_left:float\)\-\>int:\.\.\.
23
24defselect\_next\_C\(current:int,dist\_row:np\.ndarray,
25uncertainty\_vector:np\.ndarray,
26remaining\_budget:float\)\-\>int:\.\.\.
27
28
29
30defselect\_next\_A\(current:int,request\_dict:dict,
31dist\_mat:np\.ndarray,
32budget\_left:float\)\-\>int:\.\.\.
33
34defselect\_next\_B\(my\_state:dict,teammate\_positions:list,
35graph:dict,
36budget\_left:float\)\-\>int:\.\.\.
37
38defselect\_next\_C\(current:int,dist\_row:np\.ndarray,
39value\_vector:np\.ndarray,
40deadline\_vector:np\.ndarray,
41remaining\_budget:float\)\-\>int:\.\.\.
Listing 2:Function signatures for the three multi\-agent scheduling benchmarks\.1
2defselect\_next\_A\(my\_busy\_until:float,t\_now:float,
3job\_pool:dict,
4p\_mine:float\)\-\>int:\.\.\.
5
6defselect\_next\_B\(my\_busy\_until:float,
7teammate\_busy\_until:list,
8job\_pool:dict,
9t\_now:float\)\-\>int:\.\.\.
10
11defselect\_next\_C\(busy\_vector:np\.ndarray,
12job\_ids:np\.ndarray,
13job\_features:np\.ndarray,
14t\_now:float\)\-\>int:\.\.\.
15
16
17
18defselect\_next\_A\(my\_skills:np\.ndarray,
19my\_busy\_until:float,
20task\_pool:dict,
21t\_now:float\)\-\>int:\.\.\.
22
23defselect\_next\_B\(my\_state:dict,teammate\_states:list,
24task\_pool:dict,
25t\_now:float\)\-\>int:\.\.\.
26
27defselect\_next\_C\(skill\_matrix:np\.ndarray,
28busy\_vector:np\.ndarray,
29task\_features:np\.ndarray,
30t\_now:float\)\-\>int:\.\.\.
31
32
33
34defselect\_next\_A\(my\_buffer:dict,
35my\_busy\_until:float,
36t\_now:float,
37dummy:float\)\-\>int:\.\.\.
38
39defselect\_next\_B\(my\_buffer:dict,
40upstream\_busy:float,
41downstream\_buf\_size:int,
42my\_busy\_until:float\)\-\>int:\.\.\.
43
44defselect\_next\_C\(my\_buffer:dict,
45pipeline\_state:np\.ndarray,
46job\_table:np\.ndarray,
47t\_now:float\)\-\>int:\.\.\.
## Appendix DExamples of Generated Outputs
The following functions were discovered for the Multi\-Agent Path Planning: Prize Collections problem\.
Listing 3:Policy for company A\.1importnumpyasnp
2
3defselect\_next\_A\(current:int,unvisited\_prizes:dict,dist\_mat:np\.ndarray,budget\_left:float\)\-\>int:
4"""
5EnhancedstrategyforCompanyA:incorporatepotentialimpactsofteammates’positions
6ondecision\-makingwhileweighingimmediaterewardsandoptions\.
7
8Args:
9current:currentnodeidofmyrobot\.
10unvisited\_prizes:\{node\_id:prize\}fornodesnotyetcollectedbyanyone\.
11dist\_mat:\(N,N\)distancematrix\.
12budget\_left:remainingtravelbudgetforthisrobot\.
13"""
14best\_node=0
15best\_ratio=\-1\.0
16
17fornode,prizeinunvisited\_prizes\.items\(\):
18ifnode==current:
19continue
20
21
22cost\_to\_node=dist\_mat\[current,node\]
23cost\_back\_to\_depot=dist\_mat\[node,0\]
24total\_cost=cost\_to\_node\+cost\_back\_to\_depot
25
26iftotal\_cost\>budget\_left:
27continue
28
29
30effective\_cost=total\_cost\-cost\_back\_to\_depot
31adjusted\_ratio=\(prize/\(effective\_cost\+1e\-9\)\)ifeffective\_cost\>0else0
32
33
34fornext\_node,next\_prizeinunvisited\_prizes\.items\(\):
35ifnext\_node==nodeornext\_node==current:
36continue
37
38cost\_to\_next=dist\_mat\[node,next\_node\]
39cost\_back\_from\_next=dist\_mat\[next\_node,0\]
40total\_with\_next=total\_cost\-cost\_back\_to\_depot\+cost\_to\_next\+cost\_back\_from\_next
41
42iftotal\_with\_next<=budget\_left:
43effective\_next\_cost=cost\_to\_node\+cost\_to\_next
44adjusted\_next\_ratio=\(next\_prize/\(effective\_next\_cost\+1e\-9\)\)ifeffective\_next\_cost\>0else0
45
46
47adjusted\_ratio\+=adjusted\_next\_ratio\*\(1\.0\-\(cost\_to\_next/\(budget\_left\+1e\-9\)\)\)
48
49
50ifadjusted\_ratio\>best\_ratio:
51best\_ratio=adjusted\_ratio
52best\_node=node
53
54returnbest\_node
Listing 4:Policy for company B\.1importnumpyasnp
2
3defselect\_next\_B\(my\_state:dict,teammate\_positions:list,graph:dict,budget\_left:float\)\-\>int:
4current=my\_state\["current"\]
5dist\_mat=graph\["dist\_mat"\]
6nodes=graph\["nodes"\]
7
8best\_node=0
9best\_score=\-float\("inf"\)
10
11potential\_nodes=\[\]
12
13
14for\(node\_id,\_x,\_y,prize\)innodes:
15ifnode\_id==currentorprize<=0:
16continue
17
18cost=dist\_mat\[current,node\_id\]\+dist\_mat\[node\_id,0\]
19ifcost<=budget\_left:
20my\_dist=dist\_mat\[current,node\_id\]
21teammate\_dist=min\(dist\_mat\[tp,node\_id\]fortpinteammate\_positions\)ifteammate\_positionselsefloat\("inf"\)
22
23score=prize\-0\.1\*my\_dist\+0\.1\*\(teammate\_dist\-my\_dist\)
24
25ifteammate\_dist\>my\_dist:
26potential\_nodes\.append\(\(node\_id,score\)\)
27
28ifscore\>best\_score:
29best\_score=score
30best\_node=node\_id
31
32
33ifpotential\_nodes:
34best\_exploration=max\(potential\_nodes,key=lambdax:x\[1\]\)\[0\]
35returnbest\_exploration
36
37returnbest\_nodeifbest\_node\!=0else0
Listing 5:Policy for company C\.1importnumpyasnp
2
3defselect\_next\_C\(current:int,dist\_row:np\.ndarray,remaining\_prizes:np\.ndarray,remaining\_budget:float\)\-\>int:
4"""
5Global\-planningforCompanyC:balancebetweenleveragingstrongcoverageandexploringuncollectednodes\.
6
7Args:
8current:currentnodeidofmyrobot\.
9dist\_row:\(N,\)float\.dist\_row\[j\]=distancefrom‘current‘toj\.
10dist\_row\[0\]isthedistancefromcurrentbacktodepot\.
11remaining\_prizes:\(N,\)float\.Prizestillavailableateachnode
12\(0ifalreadycollectedbyanyrobot\)\.Depotentryis0\.
13remaining\_budget:remainingtravelbudgetforthisrobot\.
14
15Returns:
16Thenextnodeidtotarget,or0toreturntodepot\.
17"""
18n=len\(remaining\_prizes\)
19dist\_to\_depot=dist\_row\[0\]
20
21
22best\_node=0
23best\_score=\-float\("inf"\)
24
25
26forjinrange\(1,n\):
27ifremaining\_prizes\[j\]\>0anddist\_row\[j\]\+dist\_to\_depot<=remaining\_budget:
28
29score=remaining\_prizes\[j\]/\(dist\_row\[j\]\+1e\-6\)
30
31
32ifremaining\_budget\-dist\_row\[j\]\>0:
33forkinrange\(1,n\):
34ifk\!=jandremaining\_prizes\[k\]\>0:
35potential\_cost=dist\_row\[k\]\+dist\_to\_depot
36ifdist\_row\[j\]\+potential\_cost<=remaining\_budget:
37score\+=remaining\_prizes\[k\]/\(potential\_cost\+1e\-6\)
38
39
40ifscore\>best\_score:
41best\_score=score
42best\_node=j
43
44returnbest\_node
The following functions were discovered for the Multi\-Agent Scheduling: Skilled Tasks problem\.
Listing 6:Policy for company A\.1importnumpyasnp
2
3defselect\_next\_A\(my\_skills:np\.ndarray,my\_busy\_until:float,task\_pool:dict,t\_now:float\)\-\>int:
4"""
5Selectsthebesttaskfromthetaskpoolbasedonskillefficiency,value\-to\-timeratio,andurgency\.
6
7Args:
8my\_skills:\(S,\)myskillvector\.
9my\_busy\_until:equalst\_nowwhenthisiscalled\.
10task\_pool:\{task\_id:\(category,p,v,d\)\}\.
11t\_now:currenttime\.
12"""
13ifnottask\_pool:
14return\-1
15
16best\_task=\-1
17best\_ratio=\-1\.0
18best\_priority=float\(’inf’\)
19
20max\_skill\_cat=np\.argmax\(my\_skills\)
21
22fortid,\(cat,p,v,d\)intask\_pool\.items\(\):
23s=max\(float\(my\_skills\[int\(cat\)\]\),1e\-6\)
24eff\_p=p/s
25finish=t\_now\+eff\_p
26
27iffinish\>d\+1e\-9:
28continue
29
30ratio=v/\(eff\_p\+1e\-6\)
31urgency=max\(d\-finish,0\)
32priority=eff\_p\+urgency
33
34
35ifcat==max\_skill\_cat:
36if\(ratio\>best\_ratio\)or\(ratio==best\_ratioandpriority<best\_priority\):
37best\_ratio=ratio
38best\_priority=priority
39best\_task=tid
40
41else:
42iffinish<d:
43
44if\(eff\_p<2\*np\.min\(list\(task\_pool\.values\(\)\),axis=0\)\[1\]\):
45if\(ratio\>best\_ratio\)or\(ratio==best\_ratioandpriority<best\_priority\):
46best\_ratio=ratio
47best\_priority=priority
48best\_task=tid
49
50returnbest\_task
Listing 7:Policy for company B\.1importnumpyasnp
2
3defselect\_next\_B\(my\_state:dict,teammate\_states:list,task\_pool:dict,t\_now:float\)\-\>int:
4"""
5ComparativeadvantageskillforCompanyBwithcooperationprinciple\.
6
7Args:
8my\_state:\{"skills":\(S,\)np\.ndarray,"busy\_until":float\}\.
9teammate\_states:listofdictswiththesamekeysforeachteammate\.
10task\_pool:\{task\_id:\(category,p,v,d\)\}\.
11t\_now:currenttime\.
12"""
13ifnottask\_pool:
14return\-1
15
16my\_skills=my\_state\["skills"\]
17best\_task=\-1
18best\_value\_ratio=\-float\("inf"\)
19
20fortid,\(cat,p,v,d\)intask\_pool\.items\(\):
21cat=int\(cat\)
22my\_skill=float\(my\_skills\[cat\]\)
23
24
25ifmy\_skill<=1e\-6:
26continue
27eff\_time=p/my\_skill
28finish\_time=t\_now\+eff\_time
29iffinish\_time\>d:
30continue
31
32
33teammate\_skills=\[float\(ts\["skills"\]\[cat\]\)fortsinteammate\_statesifnp\.isfinite\(ts\["busy\_until"\]\)\]
34best\_teammate\_skill=max\(teammate\_skills,default=0\.0\)
35teammate\_busy\_until=max\(\(ts\["busy\_until"\]fortsinteammate\_statesifts\["skills"\]\[cat\]\>my\_skill\),default=np\.inf\)
36
37
38ifteammate\_busy\_until<finish\_timeandbest\_teammate\_skill\>my\_skill:
39continue
40
41
42value\_ratio=v/\(eff\_time\+1e\-6\)
43
44
45ifvalue\_ratio\>best\_value\_ratio:
46best\_value\_ratio=value\_ratio
47best\_task=tid
48
49returnbest\_task
Listing 8:Policy for company C\.1importnumpyasnp
2
3defselect\_next\_C\(
4skill\_matrix:np\.ndarray,
5busy\_vector:np\.ndarray,
6task\_features:np\.ndarray,
7t\_now:float,
8\)\-\>int:
9iftask\_features\.shape\[0\]==0:
10return\-1
11
12K=skill\_matrix\.shape\[0\]
13ids=task\_features\[:,0\]\.astype\(np\.int64\)
14cats=task\_features\[:,1\]\.astype\(np\.int64\)
15ps=task\_features\[:,2\]
16vs=task\_features\[:,3\]
17ds=task\_features\[:,4\]
18
19my\_idx=np\.where\(np\.isclose\(busy\_vector,t\_now,atol=1e\-6\)\)\[0\]
20ifmy\_idx\.size==0:
21my\_idx=np\.where\(np\.isfinite\(busy\_vector\)\)\[0\]\[0\]
22else:
23my\_idx=my\_idx\[0\]
24
25my\_skills=skill\_matrix\[my\_idx\]
26must\_do\_tasks=\[\]
27possible\_tasks=\[\]
28
29foriinrange\(len\(ids\)\):
30cat=int\(cats\[i\]\)
31my\_skill=max\(float\(my\_skills\[cat\]\),1e\-6\)
32eff\_time\_mine=float\(ps\[i\]\)/my\_skill
33
34ift\_now\+eff\_time\_mine<=float\(ds\[i\]\)\+1e\-9:
35alt\_times=\[\]
36forkinrange\(K\):
37ifk\!=my\_idxandnp\.isfinite\(busy\_vector\[k\]\):
38alt\_skill=max\(float\(skill\_matrix\[k,cat\]\),1e\-6\)
39start\_time=max\(float\(busy\_vector\[k\]\),t\_now\)
40alt\_eff\_time=float\(ps\[i\]\)/alt\_skill
41finish\_time=start\_time\+alt\_eff\_time
42iffinish\_time<=float\(ds\[i\]\)\+1e\-9:
43alt\_times\.append\(alt\_eff\_time\+\(start\_time\-t\_now\)\)
44
45alt\_eff=min\(alt\_times\)ifalt\_timeselsefloat\("inf"\)
46
47ifalt\_eff\>eff\_time\_mine:
48must\_do\_tasks\.append\(\(eff\_time\_mine,ids\[i\],vs\[i\]\)\)
49else:
50possible\_tasks\.append\(\(eff\_time\_mine,ids\[i\],vs\[i\]\)\)
51
52
53ifmust\_do\_tasks:
54best\_task=max\(must\_do\_tasks,key=lambdax:\(x\[2\]/\(x\[0\]\+1e\-6\)\)\)\[1\]
55returnbest\_task
56
57
58ifpossible\_tasks:
59option\_task=max\(possible\_tasks,key=lambdax:\(x\[2\]/\(x\[0\]\+1e\-6\)\)\)
60all\_other\_potential\_tasks=\(task\_features\[:,2\]\>0\)&\(ds\>t\_now\)
61ifnp\.any\(all\_other\_potential\_tasks\):
62min\_time\_until\_next=np\.min\(ps\[all\_other\_potential\_tasks\]/my\_skills\[cats\[all\_other\_potential\_tasks\]\.astype\(int\)\]\)
63ifmin\_time\_until\_next<option\_task\[0\]:
64return\-1
65
66
67returnoption\_task\[1\]ifoption\_task\[0\]<min\_time\_until\_nextelse\-1
68
69return\-1Similar Articles
Relic: From Multi-Agent Collaboration to Persistent Organizational Capability
Relic introduces a framework that converts recurring multi-agent collaboration failures into organization-owned executable protocols, enhancing persistent organizational capability and performance in software workloads through experimental validation.
Skill2Real: Agentic Skill Learning for Zero-Shot Sim-to-Real Robot Manipulation
Skill2Real introduces an agentic skill learning framework using a Proposer-Verifier-Governor loop that learns executable robot skills in simulation via a shared API and transfers them zero-shot to real-world manipulation without fine-tuning, achieving strong success rates on LIBERO benchmarks and real-robot tasks.
Agent Priors-guided Policy Learning
This paper introduces Agent Priors-guided Policy Learning (APPL), a framework where construction and runtime agents use structural priors—describing what a behavior depends on—as an interface between skill learning and skill composition, improving out-of-distribution skill generalization on MetaWorld and long-horizon ManiSkill tasks.
@dair_ai: // Evolving Meta-Skill for Multi-Agent Systems // Can a multi-agent system get better at orchestration without touching…
Skill-MAS introduces a method for evolving meta-skills in multi-agent systems to improve orchestration without modifying model weights, achieving transferable performance gains across tasks and LLMs.
Consilience: Conformally Calibrated Communication Control for Hidden-Profile Multi-Agent Reasoning
This paper proposes Consilience, an inference-time orchestration framework for multi-agent LLM systems that provides conformally calibrated communication control to improve decision accuracy and efficiency in hidden-profile reasoning tasks.