Backend
Collective Tree Exploration with Predictions
arXiv cs.MA0 views
arXiv:2611.17482v1 Announce Type: cross Abstract: We study collective tree exploration with subtree-size predictions. In this problem, a team of $k$ mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex $u$ is discovered, the team receives a prediction $\hat n_u$ of the number of nodes $n_u$ in the subtree rooted at $u$. We provide algorithmic guarantees under two error measures: the maximum error $E=\max_u|\widehat n_u-n_u|$ and the multiplicative distortion $\mu = (\max_u\widehat n_u/n_u)(\max_u n_u/\widehat n_u)$. For the maximum error, we present a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in $O(\text{OPT}+E)$ rounds, where $\text{OPT} = \Theta(n/k+D)$ is the offline benchmark, and we show that there is no deterministic algorithm that admits an $O(\text{OPT})+o(E)$ guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in $\widetilde O(\min\{ \sqrt\mu\log k, \mu\log\log k+\mu^{1.5} \})$, where the $\widetilde O(\cdot)$ may hide logarithmic factors in $\mu$.
Source:https://arxiv.org/abs/2611.17482PreviousPhysical-Risk-Aware Decentralized Agents for Constrained Vehicle CommunicationsNextA Push Down the Mountain: Framing Effects and Internal State Interventions on Collusive Behavior in a Long-Horizon LLM Agent
Related posts
Courteous Anticipation: Improving Long-Lived Task Planning in Persistent Shared Environments
0arXiv cs.RO
Foundation Model Driven Robotics: A Comprehensive Review
0arXiv cs.RO
Disturbance-Aware Informative Planning in Spatiotemporal Environments
0arXiv cs.RO

I tore down ai-memory: 528,000 lines of trending code, and you probably don't need it
0dev.to AI
Why Text-Only Feeds Are Winning Back Our Attention
0dev.to AI
Which Job Goes First? Picking the First Job Out of the 6pm Pile
0dev.to AI