CS Paper Radar

Going in Circles: Collaborative Multi-Robot Treasure Hunting

Bogumil Kaminski, Pawel Pralat, Maria Sadza

cs.DS cs.CGcs.DM ·submitted 2026-08-12 14:35 UTC · v1

Abstract

This paper investigates a multi-robot search-and-visit problem involving $n$ robots starting at the origin and $k$ unknown treasures hidden on the unit circle $\mathcal{C}$. The robots move independently anywhere in the plane with a maximum speed of 1 and instantly share discovery information. The goal is to determine an algorithm that minimizes the total time needed for all robots to individually visit every treasure. To establish the foundational limits of this task, we first solve an auxiliary optimal routing problem for a single robot on $\mathcal{C}$ that possesses complete prior knowledge of the treasure locations. The exact analysis of this auxiliary problem yields explicit upper and lower bounds for the original search problem.

Comment
30 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Searching the Plane in the Segment Visibility Model

cs.DM cs.DC ·2026-11-02 ·Evangelos Kranakis
theory similarity 0.62
Abstract

We study deterministic search by $n \geq 2$ unit-speed robots starting at the origin of the Euclidean plane. We introduce the concept of \emph{segment visibility} whereby a stationary target $x$ at distance $d=\|x\|>0$ is discovered at the first instant $t$ when $x$ belongs to the segment joining a pair of robots at time $t$. Discovery time is compared with the omniscient optimum $d$. We distinguish two knowledge models according to whether the robots know $d$ in advance. For $n=2$ robots, in the \emph{known-$d$} model, we give a symmetric four-phase algorithm and prove that its competitive ratio is optimal: $1+\sqrt3+π/6$; the matching lower bound follows from the known-distance two-robot shoreline-search theorem through an explicit reduction to segment detection. For $n=2$ robots, in the \emph{unknown-$d$} model, a three-circle construction and a quantitative initial-path estimate yield the stronger lower bound $\sqrt3+π/6+\sqrt{17}/4 \approx3.286425990$, giving an explicit positive cost for not knowing the radius; we also analyze a feasible antipodal-diameter logarithmic-spiral algorithm with optimized ratio $8.928516954\ldots$, thus proving that the competitive ratio when $d$ is unknown is at least $ \sqrt3+π/6+\sqrt{17}/4 $ and at most $8.928516954\ldots.$ For $n \geq 3$ robots, the competitive ratio of finding the target is exactly $\sec (π/n)$ regardless of whether or not $d$ is known to the robots.

0.19

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows

cs.RO ·2026-09-11 ·Ben Rossano, Jaein Lim, Jonathan P. How
similarity 0.61
Abstract · 8 pages, 6 figures

Exploring unknown environments with multi-robot teams can improve efficiency by allowing robots to explore in parallel. However, realizing these gains requires effective information sharing. When communication is intermittent, robots must balance the benefits of sharing information against the cost of diverting from exploration to establish communication. This paper introduces MACE, a decentralized exploration framework that actively evaluates whether establishing communication is worthwhile. At scheduled communication windows, robots estimate the cost of reaching previously identified communication locations. By formulating this decision as a variant of the Vehicle Orienteering Problem, robots evaluate routes based on the travel required to establish communication and the exploration that can be completed along the way. This approach enables robots to communicate more frequently than under purely opportunistic strategies while reducing the unnecessary travel associated with fixed rendezvous strategies. Across a set of simulated environments with varying size and geometry, we demonstrate that MACE reduces the total exploration time by up to 23% compared to existing communication-constrained exploration strategies.

0.21

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

cs.DC cs.CGcs.MA ·2026-10-04 ·Animesh Maiti, Prakhar Shukla, Subhash Bhagat
similarity 0.58
Abstract

Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the \textsc{Min-Max Uniform Circle Formation (MMUCF)} problem requires the robots to move to distinct positions on $\mathbf C$ such that the final configuration forms a regular $n$-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min--max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the $\mathcal{ASYNC}$ model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the \textit{Look--Compute--Move} model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on $\mathbf C$ under the considered model.

0.17

OpenSpace Lab Solution to the IROS 2026 Indoor Exploration Competition

cs.RO ·2026-10-01 ·Yuxuan Zhang, Dong Li, Zezhou Sun, Yuxuan Xu, Siyu Teng +3 more
publishedcode/data similarity 0.57
Abstract · https://github.com/OpenSpace-Lab/Indoor-Exploration-IROS2026

This report presents the \textbf{OpenSpace Lab}'s solution to the Competition on Intelligent Information Gathering for Single and Multi-Robot Systems Workshops, organized as part of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2026. Our team reached 1st place in the Single-Robot Public Track and 3rd place in both the Single- and Multi-Robot Private Tracks. The single-robot framework utilizes pre-trained map completion predictions for global planning to prioritize unexplored areas. To reconcile map coverage with limited operation time, we introduce a remaining-time-based exploration strategy that integrates homing constraints into the decision-making process. For multi-robot exploration, we utilize a utility-driven target selection strategy that balances observation gains, movement costs, and budget constraints, leveraging shared map and intent data to eliminate redundant search and maximize coordination efficiency. Our solution reached a 61.04\% coverage rate in the Single-Robot Public Track, while reaching 39.53\% and 39.91\% coverage in the Single- and Multi-Robot Private Tracks, respectively. An extended full-length paper based on this report is currently being prepared for submission, and the source code will be released upon acceptance of the full manuscript at https://github.com/OpenSpace-Lab/Indoor-Exploration-IROS2026.

0.42

Mobility-Budget-Constrained Submodular Maximization for Distributed Semantic Multi-Robot Exploration

cs.RO cs.MA ·2026-10-13 ·Changxuan Yao, Sandilya Sai Garimella, Lu Gan, Panagiotis Tsiotras
published similarity 0.57
Abstract · 5 pages, 3 figures. Accepted to the IROS 2026 SeMaNa Workshop. The first two authors contributed equally

Multi-robot exploration under communication and mobility constraints requires balancing information gain with reachability. We present a distributed semantic exploration framework that combines Dirichlet mapping, budget-constrained trajectory selection, and Resource-Aware distributed Greedy (RAG) coordination. Each robot clusters frontiers, computes terrain- and heading-aware least-cost paths with a single budget-limited Dijkstra search, and selects feasible paths by marginal information gain, represented by the expected reduction in Dirichlet entropy. Each robot's per-round selection is exact, the team's joint per-round information gain is at least half the centralized optimum, and the bound degrades gracefully under limited communication. Ten-run gridworld ablations show improved coverage, semantic mIoU, and map certainty with lower entropy and traversal cost per unit distance than shortest-distance frontier selection. Budget-sensitivity experiments show that an intermediate budget best balances path reach and receding-horizon execution. In photorealistic full-system simulation against five coordination rules run in their native published forms, the proposed method attains the highest mean coverage and semantic accuracy while being the only one that respects the per-trajectory mobility budget.

0.19

When Robots Crash: Optimal Asynchronous Gathering at Weber Meeting Nodes

cs.DC cs.CGcs.MA ·2026-10-03 ·Animesh Maiti, Prakhar Shukla, Abhinav Chakraborty, Subhash Bhagat
theory similarity 0.57
Abstract

We study the \textit{optimal gathering} problem over a finite set of designated \textit{meeting nodes} for \textit{asynchronous, anonymous,} and \textit{oblivious} mobile robots on an infinite grid under crash faults. The robots have global visibility and strong multiplicity detection, but share neither a coordinate system nor chirality. The objective is to gather all non-faulty robots at a \textsc{Weber Meeting Node}, minimizing the total Manhattan distance from their initial positions. Up to $n-2$ robots may crash permanently, and such crashes are indistinguishable from arbitrary delays. Existing approaches often rely on a designated robot to break symmetry, whose crash may block the remaining robots indefinitely. Instead, our approach enables every robot to independently select the same target from its snapshot, while target-dependent restricted shortest paths preserve the target as a \textsc{Weber Meeting Node}. We prove that, under strong multiplicity detection, optimal gathering is impossible from certain fully symmetric configurations. For all remaining configurations, our algorithm \textsc{CrashTolerantWeberGathering()} selects a unique common target, preserves its optimality throughout the execution, and allows non-faulty robots to progress without waiting for crashed robots, thereby guaranteeing gathering in finite time.

0.14

Scalable Multi-Agent Maze Traversal with Local Communication

cs.RO cs.MA ·2026-08-12 ·Julian Rau, Jahir Argote-Gerald, Grace McFassel, Genki Miyauchi, Paul Trodden +1 more
publishedtheory similarity 0.57
Abstract · This manuscript has been accepted for publication in the proceedings of the World Symposium on the Algorithmic Foundations of Robotics (WAFR…

Cave networks, pipe systems, and similar maze-like environments pose significant challenges for multi-agent navigation in unknown settings with limited communication. We propose a distributed algorithm that enables agents to collectively traverse an unknown, possibly cyclic graph. Agents enter sequentially at a designated start node and are tasked to localize and reach an undisclosed goal while avoiding collisions. They coordinate via local communication using leader-follower relationships and leader switching. At any moment in time, exploration is performed by only one of the agents, which runs a single-agent maze solver. We prove that the algorithm is complete, that its makespan is asymptotically equivalent (in the number of agents) to that of an optimal full-knowledge strategy, and derive its time and space complexity. Simulations with up to $625$ agents show a decreasing average sum-of-fuels as the number of agents increases and demonstrate that the proposed approach outperforms a naïve baseline in which all agents independently execute the single-agent solver.

0.16

Asymmetric Decomposition for Multi-Agent Path Finding with Unassigned Agents

cs.RO cs.MA ·2026-11-18 ·Xi Jin, Chen Qian, Renjun Zhang, Guowei Wu, Xiaobo Li +2 more
benchmarktheorycode/data similarity 0.57
Abstract

Robots without assigned tasks may obstruct active robots, while routing them to designated parking locations can cause unnecessary travel. This article proposes flow-oracle conflict-based search (FOCBS) for Multi-Agent Path Finding with unassigned agents (MAPF-UA). FOCBS searches over assigned-agent paths using conflict-based search (CBS) and routes targetless unassigned agents through a min-cost flow oracle. When the selected assigned-agent paths leave unassigned agents no collision-free paths, flow-conflict branching converts min-cut blockers into assigned-agent constraints, which guide the search without excluding optimal solutions. A batched zero-cost warm start accelerates the oracle, and start-avoiding tie-breaking reduces unassigned-agent movement. For feasible instances on finite graphs, we prove termination and global minimization of assigned-agent sum of service time, measured by last-arrival times. Unassigned-agent movement is minimized conditional on the selected assigned-agent paths, without a global lexicographic optimality guarantee. Benchmark experiments show that FOCBS scales well with the number of unassigned agents, and ablation studies show that, compared with discarding non-completable assigned-agent paths, flow-conflict branching solves substantially more instances while retaining optimality. Simulation and physical-robot experiments demonstrate plan executability, with laboratory tests reducing fleet travel by 40.8% relative to the parking-based coordination baseline. The source code and related resources are available at https://github.com/Chin-hsi/focbs

0.50