{"id":"c1564d6a-6c7e-40af-89bc-7fffa6bda98b","arxiv_id":"2411.16134","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"MARVEL uses graph attention policies and entropy-guided exploration to let robot teams reroute in real time when road passability is uncertain, improving team on-time arrival probability in simulations and a two-robot maze.","lead":"Robots navigating road networks with unknown blockages usually commit to fixed routes and cannot adapt when a road turns out to be blocked. MARVEL is a learning-based method that lets a team of robots test risky edges and share observations, improving the probability that the whole team arrives on time.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Undisclosed online expert with potential privileged access makes the no-prior-knowledge claim and the reported gains unverifiable; the expert is never defined, ablations do not remove it, and Algorithm 1 omits the imitation loss.","rationale":"The reader's weakest assumption identifies the same core issue: the training expert is undefined and may use privileged information. I agree with that and add a second, compounding observation: the paper describes an imitation loss L in Section IV-C but Algorithm 1 omits it, so the actual training objective is ambiguous. This is the most load-bearing concern because the entire empirical superiority claim depends on the learned policy being the source of the gains; if the expert is a strong oracle, the 'no prior knowledge' claim is misleading and the baseline comparison is unfair. The concern is concrete and testable: removing the expert supervision and benchmarking the expert itself would settle whether the learned GAT contributes independently. Because these issues are addressable via revision and code inspection, the conditional acceptance verdict remains appropriate rather than outright rejection.","tokens_in":11713,"tokens_out":6915,"duration_ms":67105,"concrete_test":"Specify the expert (e.g., RAO* or DDP with access to true traversal probabilities) and compute its SOTA probability on the same test OD pairs; then train MARVEL with the expert component removed (pure Eq. (21) policy gradient, no cross-entropy to prior solutions) and compare SOTA probabilities. If the expert's SOTA exceeds MARVEL's, or if MARVEL without expert drops materially (say more than 3 percentage points), the reported gains depend on the undisclosed expert and the no-prior-knowledge claim must be weakened. Also inspect the released code to verify the expert is not invoked during evaluation.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim is that MARVEL 'enables real-time planning and rerouting' without prior knowledge of edge passability and 'consistently outperforms' baselines on team on-time arrival probability. The load-bearing condition is that the reported SOTA gains come from the learned GAT policy rather than from the undisclosed 'online expert' used in training (Section IV-C). The paper states that 'a centralized controller' computes 'the prior optimal solution for each state' and that the model is trained by imitating this expert via cross-entropy loss, but it never defines the expert, its inputs, or its computational cost. If the expert uses true traversal probabilities or a strong CTP solver, then MARVEL is a distillation of an oracle: the 'no prior knowledge' property holds only at inference, and the comparison against baselines (which are given the true probabilities) may partly measure the expert, not the learned policy. Furthermore, Section IV-C describes an imitation loss L, but Algorithm 1 uses only the policy gradient of Eq. (21) and never mentions L or the expert; this internal inconsistency makes it impossible to tell what was actually trained. Without the expert's specification and an ablation that removes it, the central claim is not falsifiable.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MARVEL, a learning-based approach for multi-robot navigation in uncertain topological networks, where edge traversability is unknown until a robot reaches the edge's starting node. The problem is formulated as a POMDP with a team objective combining weighted on-time arrival probabilities and an information-entropy exploration bonus. The method combines a dynamic graph embedding step, a Graph Attention Network (GAT) policy, and an 'online expert' that provides supervision during training. The authors report that MARVEL outperforms several single-agent CTP and reliable-path-finding baselines on four standard transportation networks, and they include a physical experiment with two Pioneer 3-DX robots in a maze with an uncertain edge. The paper also provides an ablation study and a link to public source code.","tokens_in":12011,"tokens_out":2842,"duration_ms":29142,"significance":"If the central claims hold, MARVEL is a meaningful step toward multi-robot coordination under topological uncertainty, particularly because it operates at inference without prior knowledge of edge passability and can adapt routes in real time based on observations from teammates. The inclusion of real-robot experiments and a publicly available code repository is commendable and increases the paper's reproducibility. The ablation study provides useful evidence about the contributions of the attention mechanism and the entropy term. However, the credibility of the main empirical result hinges on the specification of the 'online expert' used for training, which is currently undefined, and on the absence of error bars and multi-agent baselines in the comparisons. These issues must be addressed before the performance claims can be considered fully supported.","major_comments":[{"comment":"The training procedure is not fully specified. The text states that 'a centralized controller' computes 'the prior optimal solution for each state' and that the model is trained by imitating the expert via a cross-entropy loss L, but Algorithm 1 only uses the policy gradient of Eq. (21) and never mentions L or the expert. This internal inconsistency makes it impossible to determine what was actually trained. Please define the expert precisely, including its inputs, its optimization objective, whether it has access to true traversal probabilities or other privileged information, and its computational cost. Also, reconcile Algorithm 1 with the described imitation loss, or explain how the cross-entropy loss enters the gradient in Eq. (21). Without this information, the 'no prior knowledge' claim at inference and the reported superiority over baselines may partly reflect the expert's performance rather than the learned policy.","section":"Section IV-C and Algorithm 1"},{"comment":"The central claim that MARVEL 'consistently outperforms' baselines is supported only by aggregate bar charts with no error bars, confidence intervals, or significance tests. Since on-time arrival probabilities are estimated from 10,000 simulations per OD pair, the variability across random seeds and across OD pairs should be reported. Please add standard deviations, box plots, or statistical significance tests (e.g., paired tests across the same OD pairs) to substantiate the comparisons.","section":"Section V-D, Fig. 4"},{"comment":"All baselines are single-agent algorithms evaluated independently for each agent; there is no multi-agent coordination baseline (e.g., a MA-CTP method, a multi-agent pathfinding variant, or a centralized greedy planner). The paper's central narrative emphasizes team collaboration and 'collective intelligence,' but without a multi-agent baseline it is unclear whether the gains come from coordination or simply from the GAT policy's representational power. Please add a multi-agent baseline or an ablation with independent (non-coordinated) policies to isolate the effect of coordination.","section":"Section V-D, Baselines"},{"comment":"The derivation of the policy gradient is not mathematically self-consistent. In Eq. (16), the SOTA probability appears as a weighting factor inside the expectation, but Eq. (17) replaces it with a sigmoid of the travel time against the budget, which is not derived. Moreover, Eq. (19) defines ΔH as a sum over explored edges, but the objective in Eq. (1) includes the graph entropy H(G) as a global term, not a trajectory-dependent one. Please clarify the relationship between the objective and the gradient estimators, and provide a clean derivation or cite the relevant variational policy gradient theorem appropriately.","section":"Equations (16)-(21)"}],"minor_comments":[{"comment":"In the text after Eq. (4), the information entropy H is defined in Eq. (4), but the sentence in Section III-C says 'H is defined in Eq. (5)', which is actually the normalized adjacency matrix. Please correct the cross-reference.","section":"Section III-C"},{"comment":"The statement 'for ∀i ∈ E' should likely be 'for ∀i ∈ V' or 'for all vertices i', since attention coefficients are computed over vertices and their neighbors. Please fix the notation.","section":"Section IV-B"},{"comment":"The description 'sampled from a Gaussian distribution with rejection' is vague. Please specify the exact truncation/rejection procedure, including the minimum bound and whether the rejection is independent across edges.","section":"Section V-A.1"},{"comment":"Algorithm 1 outputs 'at = SoftMax(πθ)', but Section IV-B states that during testing the action is selected as the edge with maximum probability. Please clarify whether the algorithm outputs a distribution or a deterministic action, and align the pseudocode with the text.","section":"Algorithm 1"},{"comment":"The POMDP formulation is presented as two tuples but does not explicitly define the state space, observation space, transition function, or reward function. Please provide a formal POMDP definition with these components, or state clearly how they map to the tuple notation.","section":"Section III-A"}],"recommendation":"major_revision","confidential_remarks":"The central idea is interesting and the physical demonstration is a positive feature, but the undefined 'online expert' is a serious verifiability issue that needs to be resolved before publication. In addition to the technical revisions, I recommend that the editor ask the authors to verify that the public GitHub repository actually contains the full training code, including the expert and the imitation loss, and to report the exact hyperparameters and compute budget for the expert. The absence of a multi-agent baseline weakens the novelty claim; a comparison with a simple coordinated baseline (e.g., centralized greedy with shared observations) would strengthen the paper considerably."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this paper assembles a genuinely new combination — multi-agent Canadian traveller problem with a team-level on-time arrival objective, adaptive graph embeddings, entropy-guided exploration, and GAT policies — and shows consistent-looking gains over single-agent baselines on four standard networks plus a two-robot physical demo. The integration is useful and the authors are honest that each piece is known. I think it deserves referee time, but the training pipeline has a black box that needs to be opened before the results can be interpreted.\n\nWhat's new: no prior work I know of combines team SOTA with heterogeneous task weights and learned exploration in CTP. The adaptive embedding (Dijkstra-weighted chains instead of random walks) is a reasonable fix for the gradient dilution they identify. The ablation study is a plus; removing self-attention drops SOTA from 63% to 40%, and removing the cross-entropy loss slows convergence, which is informative.\n\nThe soft spots are real and load-bearing. Section IV-C says a centralized controller computes the \"prior optimal solution for each state\" and the model is trained by imitating it via cross-entropy loss L, but Algorithm 1 never mentions L, the expert, or the imitation loss. The expert's definition, inputs, and cost are absent. If that expert uses true traversal probabilities, then the \"no prior knowledge\" claim applies only at inference and the comparison against baselines that do receive true probabilities may partly measure the expert. That's not a fatal flaw — distilling an oracle is a legitimate method — but it has to be disclosed and ablated. Right now it's not falsifiable from the paper. The missing multi-agent baseline is less concerning because few exist, but error bars on Fig. 4 and Table I would help; some of the reported differences look small (e.g., 62% vs 63% for no cross-entropy).\n\nThe POMDP formalism is sketched, not complete — the reward and observation structure isn't pinned down. And the physical demo is illustrative, not a statistical evaluation, which is fine.\n\nBottom line: the paper is worth a serious referee. The central idea is sound and the experiments point in the right direction, but the expert must be specified and ablated, and the training loss must match the algorithm listing. If those are fixed, this is a solid contribution to CTP/MAPF literature. I'd send it to review with the expectation of major revision.","headline":"A useful new combination for multi-agent CTP that deserves review once the undisclosed training expert is specified and ablated.","tokens_in":12509,"tokens_out":1588,"would_cite":false,"duration_ms":15598,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph-attention policy lets robot teams reroute as uncertain roads are revealed.","keywords":["multi-robot navigation","Canadian traveller problem","Graph Attention Networks","POMDP","on-time arrival probability","adaptive graph embedding","multi-agent reinforcement learning","uncertain topological networks"],"falsifier":"Run the centralized expert on the same test networks and compare its team on-time arrival probability with MARVEL's; if MARVEL does not match or beat the expert, the reported superiority may be inherited from the expert rather than learned. Then retrain MARVEL using training labels generated by a solver with access only to information the robots actually possess; if team on-time arrival probability drops sharply, the claimed no-prior-knowledge capability fails.","tokens_in":11538,"feed_emoji":"🤖","tokens_out":5678,"duration_ms":52143,"temperature":0.7,"pith_summary":"This paper tries to establish that a team of robots can navigate road networks with unknown edge passability by learning to plan and reroute as information is revealed, without needing prior traversal probabilities at deployment. It reformulates the problem as a partially observable Markov decision process whose objective is the weighted on-time arrival probability of the whole team minus the information entropy of the explored graph. The proposed MARVEL pipeline uses cost-weighted shortest-path chains to embed graph nodes, a graph attention network to pick the next edge, and an online expert to supply training labels for faster convergence. If the claim holds, multi-robot systems can balance individual punctuality against team-level exploration in emergencies, time-critical deliveries, and other settings where road conditions change unexpectedly.","feed_headline":"Graph-attention policy reroutes robot teams when roads fail","feed_subtitle":"A team-trained policy probes uncertain edges so lower-priority robots can sacrifice punctuality for the team's on-time odds.","key_machinery":"The machinery is a three-part pipeline: (i) a dynamic adaptive graph embedding that replaces random walks with Dijkstra shortest-path chains weighted by edge costs and appends origin-destination positions, so node features reflect navigation value rather than raw topology; (ii) a multi-head Graph Attention Network policy that computes attention coefficients over neighbouring nodes and turns dot-product similarities into edge-selection probabilities; and (iii) an online expert-augmented policy gradient whose objective is the team's weighted stochastic on-time-arrival probability minus the information entropy of explored edges. The entropy term is the exploration lever: it rewards a robot for resolving uncertainty in edges whose passability would change teammates' decisions, while the cross-entropy loss against the expert's prior solutions accelerates convergence.","core_discovery":"MARVEL's central claim is that a team of robots, each with its own origin, destination, time budget, and task priority, can maximize the weighted on-time arrival probability of the whole team even when edge passability is unknown until a robot reaches one end of the edge. The key is to treat the evolving explored graph as a partially observable state, embed it with cost-weighted shortest-path chains rather than random walks, and select next edges with a Graph Attention Network whose self-attention weights shift as conditions are revealed. Training is guided by an online expert that supplies prior optimal solutions, and the objective subtracts the graph's information entropy from the team's success probability, which makes lower-priority robots sacrifice punctuality to probe uncertain edges when that probing helps the team. The paper reports that MARVEL outperforms three reliable-shortest-path baselines and three Canadian-traveller-problem solvers on four standard transportation networks in team on-time arrival probability, and that the behavior transfers to two physical robots in a maze.","pith_inferences":["A natural extension the paper does not test: the entropy-driven exploration bonus could be added to single-agent CTP solvers as a curiosity reward, where it should improve information gain without needing a second robot.","Because the expert labels come from a centralized controller at training time only, the 'no prior knowledge' claim is about inference; a stricter test would train MARVEL with labels from a solver that sees only what robots observe, which would separate the learned policy's contribution from the expert's.","The POMDP formulation is generic enough to cover last-mile delivery or emergency response, but only if the time budgets and traversal distributions in those settings resemble the truncated Gaussian costs used here; that transfer is an open question."],"forward_implications":["If MARVEL's claim is correct, robots can be sent into an unfamiliar network with no passability prior and still adapt their routes online as edges are revealed.","The mechanism implies a principled division of labor: low-priority robots absorb punctuality loss to probe uncertain edges, and the team's overall weighted success probability rises.","The reported results across four networks of different sizes suggest one trained policy can generalize to new topological maps without per-network retraining.","Physical maze experiments with two robots show the learned exploration-and-reroute behavior survives on real hardware."],"supporting_citations":[{"why":"Supplies the robust Canadian traveller problem formulation and the RAO* baseline that MARVEL must beat.","marker":"[1]"},{"why":"Supplies the Practical Q-learning baseline for minimizing delay probability.","marker":"[2]"},{"why":"Defines the Canadian traveller problem that MARVEL extends to multi-agent teams.","marker":"[8]"},{"why":"Motivates the use of graph attention networks for route selection in large-scale road networks.","marker":"[25]"},{"why":"Provides the skip-gram embedding method that MARVEL adapts to road-network nodes.","marker":"[28]"},{"why":"Provides the four canonical transportation networks used for benchmark experiments.","marker":"[32]"},{"why":"Supplies the Fourth-Moment Approach baseline for reliable shortest paths.","marker":"[33]"},{"why":"Supplies the Decreasing Order-of-Time baseline for most reliable routes.","marker":"[34]"},{"why":"Supplies the reliable path search baseline for maximizing on-time arrival probability.","marker":"[35]"},{"why":"Supplies the Dual Dynamic Programming baseline for the mean-standard-deviation CTP.","marker":"[36]"}],"fun_headline_variants":["Graph attention lets robot teams probe uncertain roads","Multi-robot navigation learns to adapt to unknown road conditions","Team robot routing with graph attention beats uncertain networks","Graph attention tackles uncertain topologies for robot teams"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the centralized controller used in training can compute a genuinely optimal prior solution for every state a robot visits, and that imitating those labels is what transfers to unseen networks; if that expert relies on privileged traversal probabilities or is a weak solver, MARVEL's deployment-time claim is narrower than it appears.","fun_headline_variants_meta":{"raw":{"variants":["Graph attention lets robot teams probe uncertain roads","Multi-robot navigation learns to adapt to unknown road conditions","Team robot routing with graph attention beats uncertain networks","Graph attention tackles uncertain topologies for robot teams"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000188,"raw_usage":{"total_tokens":1353,"prompt_tokens":986,"completion_tokens":367,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":307}},"tokens_in":602,"tokens_out":367,"duration_ms":4099,"temperature":1.0,"reasoning_tokens":307,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:31:55.451345+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the centralized expert on the same test networks and compare its team on-time arrival probability with MARVEL's; if MARVEL does not match or beat the expert, the reported superiority may be inherited from the expert rather than learned. Then retrain MARVEL using training labels generated by a solver with access only to information the robots actually possess; if team on-time arrival probability drops sharply, the claimed no-prior-knowledge capability fails.","supporting_citations":[{"cited_title":"Dual dynamic programming for the mean standard deviation Canadian traveller problem,","cited_arxiv_id":null,"evidence_quote":"Supplies the Dual Dynamic Programming baseline for the mean-standard-deviation CTP."},{"cited_title":"The robust Canadian traveller problem applied to robot routing,","cited_arxiv_id":null,"evidence_quote":"Supplies the robust Canadian traveller problem formulation and the RAO* baseline that MARVEL must beat."},{"cited_title":"Using reinforcement learning to minimize the probability of delay oc- currence in transportation,","cited_arxiv_id":null,"evidence_quote":"Supplies the Practical Q-learning baseline for minimizing delay probability."},{"cited_title":"Shortest paths without a map,","cited_arxiv_id":null,"evidence_quote":"Defines the Canadian traveller problem that MARVEL extends to multi-agent teams."},{"cited_title":"Transportation network test problems,","cited_arxiv_id":null,"evidence_quote":"Provides the four canonical transportation networks used for benchmark experiments."},{"cited_title":"Navigation with time limits in transportation networks: A fourth moment approach,","cited_arxiv_id":null,"evidence_quote":"Supplies the Fourth-Moment Approach baseline for reliable shortest paths."},{"cited_title":"Algorithms for most reliable routes on stochastic and time-dependent networks,","cited_arxiv_id":null,"evidence_quote":"Supplies the Decreasing Order-of-Time baseline for most reliable routes."},{"cited_title":"Most reliable path-finding algorithm for maximizing on-time arrival probability,","cited_arxiv_id":null,"evidence_quote":"Supplies the reliable path search baseline for maximizing on-time arrival probability."}],"review_version":1}