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

Elif A. Özaslan, Tolga ÖzaslanarXiv 2026 · arXiv

TL;DR

H-TRIP is a new hierarchical distance index that maintains exact all-pairs shortest paths for robots exploring a growing map. By leveraging "tropical" (min-plus) algebra and a fixed spatial hierarchy, it provides many-to-many distance queries up to two orders of magnitude faster than standard methods—all while guaranteeing that it never returns stale or approximate results.

What Problem Does This Paper Address?

In multi-robot exploration, a fleet of robots must constantly decide which robot should go to which "frontier" (the boundary of known and unknown space). To make optimal assignments, planners need a many-to-many distance matrix: the shortest-path distance between every robot and every potential goal.

The challenge is that the map is constantly growing. As robots discover new free space, they might find a "shortcut" (like a newly opened doorway) that significantly shortens the distance between two points. Standard approaches face a dilemma:

  1. Recompute from scratch: Running a graph search (like BFS or Dijkstra) for every robot is computationally expensive and scales poorly with map size.
  2. Use a cache: Storing previous distances is fast, but caches become "stale" when new shortcuts appear, leading to sub-optimal robot coordination.

The authors call this the Surviving-Pair Shortcut Problem. H-TRIP aims to solve it by providing an index that is both incremental (fast to update) and exact (always correct).

Methods

H-TRIP (Hierarchical Tropical Rank-one Incremental Propagation) combines several clever ideas:

  • Fixed-Boundary Spatial Hierarchy: The map is partitioned into a tree of tiles. Crucially, the "ports" (boundary cells) between tiles are fixed geometrically from the start, regardless of whether they are currently passable. This stability prevents the hierarchy from "churning" as the map is explored.
  • Min-Plus (Tropical) Algebra: The paper treats shortest-path computation as a matrix problem in the "min-plus semiring," where addition is replaced by the min operator and multiplication by +. This mathematical framework allows them to use powerful linear algebra concepts for pathfinding.
  • Rank-One Updates: When a robot discovers new free space, H-TRIP treats it as an edge insertion. Instead of re-running a full search, it uses a "rank-one" update to efficiently patch the local tile's distance matrix. These updates only propagate up the ancestor chain if a boundary-to-boundary distance actually changes.
  • Batched Hierarchical Lift: To answer a many-to-many query, H-TRIP "lifts" all robot and goal positions onto the tile boundaries simultaneously. This amortizes the cost of the hierarchy traversal across the entire distance matrix.
The H-TRIP spatial hierarchy: (a) a base tile with its internal closure and perimeter ports, and (b) a super-tile aggregating children.

Datasets

The authors evaluated H-TRIP using:

  • MovingAI Benchmark: A standard set of 2D occupancy maps including street layouts (Boston, Berlin, Paris) and complex mazes.
  • Simulated Multi-Robot Exploration: Runs with sixteen lidar-equipped robots exploring unknown environments to test the index's performance in a dynamic, "in-the-loop" setting.

Key Insights and Ideas

  • Exactness is a hard requirement: Many hierarchical pathfinders trade accuracy for speed (returning "near-optimal" paths). H-TRIP is mathematically proven to be exact, ensuring planners always have the true geodesic distance.
  • Amortization wins: The most expensive part of a hierarchical query is "attaching" a point to the boundary ports. By doing this once for all $k$ viewpoints and then resolving the $k \times k$ matrix, H-TRIP achieves massive speedups for multi-robot teams.
  • Locality of updates: Most sensor readings only affect a single leaf tile. By confining the update work to the affected tile and its direct ancestors, H-TRIP avoids the "global" cost of standard search algorithms.
An update propagating through the hierarchy: a new cell in a leaf tile shortens paths to the perimeter, which then updates the parent super-tiles.

Key Results

  • Zero Mismatches: Across nearly 180,000 test queries, H-TRIP produced results identical to exhaustive BFS/Dijkstra searches.
  • Massive Speedups: On fully revealed maps, H-TRIP was 7x to 11x faster than standard methods for street maps and up to 82x faster for maze-like environments.
  • Exploration Performance: In active exploration scenarios with 16 robots, H-TRIP was 2.21x to 8.59x faster than the baseline, allowing for more frequent planning cycles and better coordination.
Comparison of query times during exploration. As more of the map is covered, H-TRIP maintains a significant speed advantage over standard k x BFS.

Limitations and Future Work

  • Insertion-Only: Currently, H-TRIP only handles "monotonic growth" (unknown space becoming free). It does not yet support "deletions" (e.g., a dynamic obstacle appearing in a previously free area), which would require more complex "rank-one" decreases or partial rebuilds.
  • Memory Overhead: Storing dense distance matrices for every tile in the hierarchy requires significant memory (e.g., ~3GB for a 1024x1024 map). The authors suggest exploring sparser representations in the future.
  • 2D Focus: The current implementation is tailored for 2D occupancy grids; extending this to 3D or more complex topological graphs is a potential next step.

Summary updated

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.
BibTeX
@misc{ozaslan2026h,
  author = {Elif A. Özaslan and Tolga Özaslan},
  title = {{H-TRIP: Exact Many-to-Many Distance Index for Multi-Robot Exploration}},
  year = {2026},
  eprint = {2611.08139},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08139},
}
Figure