SuReNav: Superpixel Graph-Based Constraint Relaxation for Navigation in Over-Constrained Environments
Keonyoung Koh, Moonkyeong Jung, Samuel Seungsup Lee, Daehyung Park
AI summary
Problem
Traditional navigation planners struggle in semi-static environments because they rely on rigid, pre-defined constraint costs and fail to accurately identify which constrained regions can be safely relaxed without overestimation.
Approach
The method models the environment as a superpixel graph, trains a graph neural network on human navigation demonstrations to estimate regional relaxation costs, and integrates these costs into a differentiable A* planner for dynamic path planning.
Key results
- Formalization of constrained-region relaxation for reactive planning
- GNN-based regional constraint cost estimator
- End-to-end training via differentiable A* planner
- Highest human-likeness scores with balanced safety and efficiency in simulation and real-world Spot robot tests
Why it matters
It advances autonomous navigation by enabling robots to safely and efficiently navigate complex, changing real-world environments by mimicking human constraint relaxation strategies.
Abstract
We address the over-constrained planning prob- lem in semi-static environments. The planning objective is to find a best-effort solution that avoids all hard constraint regions while minimally traversing the least risky areas. Conventional methods often rely on pre-defined area costs, limiting gener- alizations. Further, the spatial continuity of navigation spaces makes it difficult to identify regions that are passable without overestimation. To overcome these challenges, we propose SuReNav, a superpixel graph-based constraint relaxation and navigation method that imitates human-like safe and efficient navigation. Our framework consists of three components: 1) superpixel graph map generation with regional constraints, 2) regional-constraint relaxation using graph neural network trained on human demonstrations for safe and efficient navi- gation, and 3) interleaving relaxation, planning, and execution for complete navigation. We evaluate our method against state- of-the-art baselines on 2D semantic maps and 3D maps from OpenStreetMap, achieving the highest human-likeness score of complete navigation while maintaining a balanced trade- off between efficiency and safety. We finally demonstrate its scalability and generalization performance in real-world urban navigation with a quadruped robot, Spot. Code and Videos are available at https://sure-nav.github.io/.