H-TRIP: Exact Many-to-Many Distance Index for Multi-Robot Exploration

Elif A. Özaslan; Tolga Özaslan

cs.RONov 5, 2026

H-TRIP: Exact Many-to-Many Distance Index for Multi-Robot Exploration

Authors: Elif A. Özaslan, Tolga Özaslan

Organizations: Department of Mathematics, Kastamonu University, Kastamonu, Türkiye · Department of Computer Engineering, Ankara Yıldırım Beyazıt University, Ankara, Türkiye

Abstract

Frontier-based exploration systems repeatedly evaluate geodesic travel costs between robot poses and candidate viewpoints, and tour-based planners consume the full pairwise distance matrix built from them. Recomputing these matrices with one graph search per source scales with the explored map size, whereas distance caches that refresh only locally affected or newly created frontiers can retain stale costs between surviving pairs when newly discovered free space creates a global shortcut. We present H-TRIP (Hierarchical Tropical Rank-one Incremental Propagation), an exact distance index grounded in Kleene algebra over the min-plus semiring for monotonically growing occupancy grids. H-TRIP partitions the known map into a spatial hierarchy with fixed boundary ports. Each unknown-to-free revelation is decomposed into efficient rank-one min-plus edge insertions at the affected leaf, and only decreased port-to-port summaries are propagated along its ancestor chain. A shared hierarchical lift evaluates the dense many-to-many matrix of shortest distances for all active query points on the occupancy map. We prove that sequential insertions preserve exact shortest-path distances on the grid. Benchmark experiments confirm exact agreement with reference searches on fully built maps and show that dense many-to-many queries at a few dozen viewpoints are up to two orders of magnitude faster than sequential k x BFS. On exploration runs with sixteen robots, in-loop queries on the growing occupancy graph are 2.21x-8.59x faster than co-scheduled k x BFS on maps with side 256, 512, and 1024 cells.

Figures & tables

Panel of Figure 1 — Fig. 1: We tested H-TRIP in simulation, where lidar-equipped robot teams of different sizes explored occupancy grids of different side lengths. The panels show three representative frames from these runs. The yellow lattice is the leaf-tile partition, cyan markers are active frontiers, and colored polylines are assigned open tours.

Panel of Figure 2 — Fig. 2: Fixed-boundary spatial hierarchy. ( a ) Base tile $T$ ( $b=5$ ) stores intra-tile closure $C_{T}$ on all cells and exposes summary $S_{T}$ on perimeter $B_{T}$ . ( b ) Super-tile $U$ ( $g=2$ ) aggregates child boundaries into $V_{U}$ : interior cells are condensed into summaries $S_{T_{i}}$ , dark blue perimeter cells form exposed parent ports $B_{U}$ , and light blue cells are interior seams where gold arrows mark passable cross-child edges.

Panel of Figure 3 — Fig. 3: One occupancy opening climbs the hierarchy of Fig. 2 , whose leaves have side $b=5$ and whose super-tiles aggregate $g=2$ children. ( a ) On child $T_{2}$ , a newly free cell decreases occupancy adjacency at its neighbors, and RepairClosure shortens paths to the perimeter so that those decreases leave as $\Delta S_{T_{2}}$ on $B_{T_{2}}$ . ( b ) Super-tile $U_{1}$ receives that summary through $\varphi_{T_{2}\to U_{1}}$ together with a newly passable seam, after which RepairClosure writes $\Delta S_{U_{1}}$ on $B_{U_{1}}$ . ( c ) Super-tile $U_{5}$ applies the same interface step to its $10\times 10$ children $U_{1},\ldots,U_{4}$ , where $\varphi_{U_{1}\to U_{5}}$ plants $\Delta S_{U_{1}}$ and RepairClosure writes $\Delta S_{U_{5}}$ on $B_{U_{5}}$ .

Panel of Table 4 — Table I: Evaluation maps from the MovingAI open-source set [ 22 ]

Map	Index	Full build	$k\times$ BFS	H-TRIP	vs BFS	Break-even
$M_{1}$	$87\,\mathrm{MB}$	$0.71\,\mathrm{s}$	$32.7\,\mathrm{ms}$	$3.3\,\mathrm{ms}$	$9.9\times$	$24$
$M_{2}$	$3175\,\mathrm{MB}$	$79.9\,\mathrm{s}$	$554.2\,\mathrm{ms}$	$49.8\,\mathrm{ms}$	$11.1\times$	$158$
$M_{3}$	$404\,\mathrm{MB}$	$1.07\,\mathrm{s}$	$149.4\,\mathrm{ms}$	$1.81\,\mathrm{ms}$	$82.6\times$	$7$
$M_{4}$	$404\,\mathrm{MB}$	$3.40\,\mathrm{s}$	$207\,\mathrm{ms}$	$18.0\,\mathrm{ms}$	$11.5\times$	$18$
$M_{5}$	$351\,\mathrm{MB}$	$6.33\,\mathrm{s}$	$166\,\mathrm{ms}$	$17.0\,\mathrm{ms}$	$9.77\times$	$42$
$M_{6}$	$1629\,\mathrm{MB}$	$63.0\,\mathrm{s}$	$744\,\mathrm{ms}$	$102\,\mathrm{ms}$	$7.28\times$	$98$

Table II: Median query time for

25

viewpoints on a fully revealed map. Index is the size of the H-TRIP index. Break-even is the number of batches that recover the full-build cost against

k\times

BFS.

Table 6

Incremental Computation

See all 13 papers

H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs
Nov 5, 2026Tolga Özaslan, Elif A. ÖzaslanReachability Analysis
Department of Computer Engineering, Ankara Yıldırım Beyazıt University, Ankara, Türkiye · Department of Mathematics, Kastamonu University, Kastamonu, Türkiye
STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation
Oct 8, 2026Gabriel Manuel Garcia, Stéphanie Aravecchia, Miguel Angel Olivares-MendezRobot Navigation Graph-Based Planning
University of Luxembourg, Luxembourg · IRL Georgia Tech-CNRS, Metz, France
Mobility-Budget-Constrained Submodular Maximization for Distributed Semantic Multi-Robot Exploration
Oct 13, 2026Changxuan Yao, Sandilya Sai Garimella, Lu Gan +1Multi-Robot Exploration Informative Path Planning
The authors are with the Institute of Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA.

Nov 5, 2026J/K move · Enter open · S save

H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs

Tolga Özaslan, Elif A. Özaslan

Department of Computer Engineering, Ankara Yıldırım Beyazıt University, Ankara, Türkiye · Department of Mathematics, Kastamonu University, Kastamonu, Türkiye

Reachability Analysis

Open paper AskPDF arXiv

Repeated directed reachability queries arise in online path planning, task-agent allocation, and swarm control on static grid maps, where reachability is asymmetric and full transitive closure is storage-prohibitive. We introduce H-BRICK, a Hierarchical Boundary Reachability Index with Compressed Kleene closure for exact cell-to-cell queries on directed grid graphs. H-BRICK partitions the graph into tiles, computes a local Boolean Kleene closure within each tile, and projects it onto the tile's boundary ports. The resulting directed port-to-port summaries are then composed recursively across shared interfaces up to a single root covering the graph. We prove algebraically that the construction is exact: in the Boolean Kleene algebra of binary relations, every composed summary equals the boundary projection of the regional reflexive transitive closure, and every cell-to-cell query agrees with reachability in the original graph. Experiments on directed grid graphs across diverse map topologies compare H-BRICK against directed search and component-based baselines, and compare its storage requirements against full transitive closure. A batched reachability evaluation further demonstrates that sharing endpoint lifts across many-source/many-target queries amortizes hierarchical traversal and, at k=64, yields a 5.0x-22.9x throughput improvement over the scalar query loop. The results show that hierarchical boundary compression is most advantageous in query-intensive spatial graphs where online search traverses large reachable regions and the hierarchy maintains compact boundary interfaces.

Abstract

Incremental Computation

Explore similar work

H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs

STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation

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