CS Paper Radar

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

Tolga Özaslan, Elif A. Özaslan

cs.RO ·submitted 2026-11-05 14:53 UTC · v1
theory

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding

cs.AI ·2026-11-05 ·Stephen Chang, Daniel Harabor
benchmark similarity 0.64
Abstract

LaCAM is a search-based solver for multi-agent pathfinding (MAPF) that runs a depth-first search over joint configurations, using PIBT to generate successors and lazily adding single-agent constraints to explore alternatives. Although LaCAM is complete, it can struggle on dense, corridor-heavy instances because extracting blocking agents from deadlocks requires coordinated moves of several agents, often away from their goals, which PIBT's greedy one-step successors rarely propose and which LaCAM can only reach by enumerating constraints one agent at a time. This paper proposes Goal-Branching, where blocking agents are given temporary goals, each tried as an additional branch of LaCAM's search. We examine random and corridor-aware rules for choosing these temporary goals and show that completeness is preserved for any such rule. On dense instances (60-90% of free cells occupied) of three maze and room maps, Goal-Branching solves 89% of instances against 44% for LaCAM*, and, on instances both solve, it finds a first solution 10-14x faster on maze-32-32-2 and room-32-32-4, and nearly 200x faster in median time at 75% density on room-32-32-4. Solution cost increases by 15-22% on instances both solve, while on open maps and the full MovingAI benchmark its solutions cost no more than those of LaCAM* and it is at most 3% slower.

0.20

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

cs.RO ·2026-11-05 ·Elif A. Özaslan, Tolga Özaslan
benchmarktheoryhot direction similarity 0.61
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.

0.33

Solving Multi-Agent Sokoban via LaCAM

cs.MA ·2026-09-30 ·Keisuke Okumura
benchmark similarity 0.60
Abstract

Sokoban, a puzzle game in which an agent pushes boxes onto unlabelled target locations in a grid world, is a long-standing benchmark planning problem. While it is easy to see the connection to practical applications such as warehouse logistics with autonomous forklifts, its multi-agent counterpart has remained underdeveloped. This is because Multi-Agent Sokoban is substantially more difficult due to factors specific to multi-agent planning, such as the rapidly growing branching factor as the number of agents grows and the need to handle integrated task assignment and collision-free pathfinding. In this paper, we show that a scalable planner for Multi-Agent Sokoban can be designed by leveraging recent advances in multi-agent pathfinding (MAPF). Specifically, our Sokoban-LaCAM efficiently solves instances involving tens of agents and boxes while preserving both completeness and eventual optimality guarantees. This provides evidence that MAPF can serve as a powerful primitive for solving broader collective automation problems.

0.17

Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding

cs.ET cs.CCcs.DCcs.MA ·2026-10-19 ·Masashi Aono
theory similarity 0.59
Abstract · 33 pages. Ancillary files: Lean 4 development for the finite gadget (theoremA.lean), exhaustive check scripts with frozen expected outputs, …

On ranked directed acyclic graphs coupled by vertex conflicts we study exact-arrival multi-agent path finding (departure and arrival pinned in place and time) posed as a distributed output task: every cell must emit its own bit of a valid joint path-support mask. The machines are cellular: one automaton per cell, state factored over cells, communication only along a fixed local fabric, synchronous rounds, a query-independent output round, no central decoder, and a per-topology transition code. "Necessary" here means: on an explicit hard topology, over all its feasible queries, no universally correct local-only architecture can renounce either temporal orientation; with global flags, impossibility becomes a bandwidth-round trade-off. The class is not vacuous: a flooding machine solves every instance in as many rounds as the diameter of the local fabric. The bound survives two concessions: we supply every agent's exact individual cavity, which alone solves the single-agent problem in zero rounds and makes the single-agent direction theorem vacuous; and we allow $k$ one-bit global aggregate flags. On a twelve-cell, two-agent, depth-three topology no forward-only machine with $k=0$ is correct on two feasible queries, for any number of rounds; the time-reversed topology does the same to backward-only machines. Placing $p$ copies side by side gives, for forward-only machines, $J_R+kR\ge p$ at constant depth, where $J_R$ measures how much of the query reaches the targets' cones and is $0$ here. A backward-only machine solves that family in constant rounds and a flag-streaming one in $\lceil p/k\rceil+O(1)$, so the bound is tight in order; on the composite family neither orientation can be renounced. The finite lemmas of the gadget and the pair-invariance contradictions are checked in Lean 4; the semantic bridge, the cone lemma and the counting are paper proofs. We report no benchmarks.

0.30

PSPACE-Completeness of Multi-Agent Path Finding for Large Agents

cs.CC ·2026-08-13 ·Maichi Zhang, Naoyuki Kamiyama, Kanae Yoshiwatari
similarity 0.59
Abstract

Multi-Agent Path Finding for Large Agents (LA-MAPF) is a geometric variant of MAPF in which agents are modeled as disks and conflicts are determined by physical overlap in the underlying Euclidean workspace. The goal of LA-MAPF is to decide whether there exists a sequence of conflict-free transitions from a start configuration to a goal configuration. Agafonov and Yakovlev proved that LA-MAPF is NP-hard. In this paper, we strengthen their result by proving that LA-MAPF is PSPACE-complete via a polynomial-time reduction from Restricted Sliding Tokens.

0.04

Space Complexity of Reachability in Simple Path Graphs

cs.CC ·2026-10-20 ·Krishnamoorthy Dinesh, Chandana Sasidharan
published similarity 0.58
Abstract · 17 pages, 9 figures

One of the central questions in space complexity is whether nondeterministic logspace computations ($\textsf{NL}$) can be simulated in unambiguous logspace ($\textsf{UL}$). A stronger notion, \emph{reach unambiguity} ($\textsf{RUL} \subseteq \textsf{UL} \cap \textsf{co}\textsf{UL}$), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph reachability is $\textsf{NL}$-complete, planar graph reachability is in $\textsf{UL}$ and undirected graph reachability is in deterministic logspace ($\textsf{L}$). In this work, we study the space complexity of reachability problem for restricted directed graph families and show the following. - For reach unambiguous graphs (graphs with at most one path from start vertex to every vertex), Lange (Lange 97) showed that reachability is in $\textsf{RUL}$. As our main result, we show that for simple path graphs (introduced in Kannan et.al. 08), which contains reach unambiguous graphs), where each vertex has at most one simple path from the start, we show that the reachability problem lies in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. - Our first result can also be equivalently stated as: the recognition problem for simple path is in $\textsf{UL} \cap \textsf{co}\textsf{UL}$ if and only if the reachability problem restricted to simple path graphs is also in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. Inspired by this, we investigate the complexity of graph recognition versus graph reachability for graph classes. Observe that for any graph class, solving reachability (for the class) also solves the recognition problem for that class. We show that for reach unambiguous graphs, solving recognition is as hard as solving reachability (making both of them $\textsf{RUL}$-complete). (Abstract shortened to meet arXiv limits)

0.62

Bridging the Gap Between Plain VASS and Branching VASS

cs.LO cs.FL ·2026-09-14 ·Clotilde Bizière, Jérôme Leroux, Grégoire Sutre
publishedtheory similarity 0.57
Abstract · 25 pages, extended version of the paper with same title and same authors presented at FOSSACS'26

Vectors addition systems with states (VASS), a model equivalent to Petri nets, are finite-state machines with finitely many counters ranging over the natural numbers. The decidable reachability problem for VASS has many applications in logic, automata, and verification. In this paper we study the reachability problem for BVASS, a branching generalization of VASS. We show that BVASS reachability sets are very similar to VASS reachability sets, namely that they are sections of VASS. Our proof relies on a new well-quasi-order (wqo) on BVASS runs that generalizes the well-known wqo on VASS runs. By leveraging an amalgamation property, we prove that every BVASS run can be transformed into an equivalent one of bounded branching complexity. This allows us to derive several results on the geometry of BVASS reachability sets. As an application we obtain that reachability sets of 5-dimensional BVAS are effectively semilinear, as is the case for 5-dimensional VAS.

0.58

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

cs.AI ·2026-08-25 ·Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini
benchmarktheory similarity 0.57
Abstract

Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.

0.16