HOPHY: A Hierarchical Hypergraph Representation for Off-Road Path and Mission Planning

Published September 18, 2026 · Category: Robotics

Overview

arXiv:2609.20694v1 Announce Type: new Abstract: Mission-level autonomy for disaster response, search and rescue, and tactical UGV operations requires repeated path and mission planning as terrain conditions, agent types, and objectives change. Pixel-grid search is costly for repeated kilometer-scale queries, while semantic abstractions must maintain valid costs and connectivity as conditions change. We present HOPHY (Hierarchical Off-Road Planning using Hypergraphs), a reusable hierarchical terrain representation that organizes map-scale terrain into geometrically connected semantic regions (GSNodes), connectivity-preserving critical regions (Coarse Regions), and typed hyperedges for terrain, agent, and weather context. Hyperedge intersections select affected regions and incident edges for state updates without rebuilding the hierarchy. Across real off-road maps spanning kilometer-scale areas, HOPHY achieves 100% planning success and less than 0.01% median cost deviation from the oracle (pixel A*), with substantially lower query and replanning latency than the evaluated pixel and abstraction baselines. Applied to a multi-robot task-allocation (MRTA) problem, these gains reduce total computation by 79x over pixel A* and 7.2x over the fastest abstraction baseline, with mission makespan comparable to pixel A*. Finally, we demonstrate HOPHY on a physical Clearpath Jackal that successfully executes a 1.5-km, eight-task mission across mixed-surface outdoor terrain and a blockage-triggered replanned route.

Source

Originally published at arxiv.org.

Related Articles

• GAVEL: Graph World Models for Verified and Efficient Long-Horizon LLM Task Planning
• Time-Efficient Iterative Learning Planning for Safety-Critical Dynamic Obstacle Avoidance
• MoWAM: Explicit Future Motion Prediction for Efficient World Action Models