# SuReNav: Superpixel Graph-based Constraint Relaxation for Navigation in Over-constrained Environments

arXiv: https://arxiv.org/abs/2602.06807 · HTML: https://mlsanity.com/paper/2602.06807/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 6 Feb 2026.

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Object Goal Navigation using Goal-Oriented Semantic Exploration](https://mlsanity.com/paper/2007.00643/) (2020)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Orbit: A Unified Simulation Framework for Interactive Robot Learning Environments](https://mlsanity.com/paper/2301.04195/) (2023)
- [NoMaD: Goal Masked Diffusion Policies for Navigation and Exploration](https://mlsanity.com/paper/2310.07896/) (2023)
- [Cognitive Mapping and Planning for Visual Navigation](https://mlsanity.com/paper/1702.03920/) (2017)
- [ESC: Exploration with Soft Commonsense Constraints for Zero-shot Object Navigation](https://mlsanity.com/paper/2301.13166/) (2023)
- [Learning to Navigate in Cities Without a Map](https://mlsanity.com/paper/1804.00168/) (2018)
- [BADGR: An Autonomous Self-Supervised Learning-Based Navigation System](https://mlsanity.com/paper/2002.05700/) (2020)
- [Visual Representations for Semantic Target Driven Navigation](https://mlsanity.com/paper/1805.06066/) (2018)
- [PIDNet: A Real-time Semantic Segmentation Network Inspired by PID Controllers](https://mlsanity.com/paper/2206.02066/) (2022)
- [How To Not Train Your Dragon: Training-free Embodied Object Goal Navigation with Semantic Frontiers](https://mlsanity.com/paper/2305.16925/) (2023)
- [Superpixels: An Evaluation of the State-of-the-Art](https://mlsanity.com/paper/1612.01601/) (2016)
- [Path Planning using Neural A* Search](https://mlsanity.com/paper/2009.07476/) (2020)
- [Constraint-Aware Zero-Shot Vision-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2412.10137/) (2024)
- [ViPlanner: Visual Semantic Imperative Learning for Local Navigation](https://mlsanity.com/paper/2310.00982/) (2023)
- [Incremental Sampling-based Algorithm for Minimum-violation Motion Planning](https://mlsanity.com/paper/1305.1102/) (2013)
- [A Generalized A* Algorithm for Finding Globally Optimal Paths in Weighted Colored Graphs](https://mlsanity.com/paper/2012.13057/) (2020)

## Abstract (arXiv)

We address the over-constrained planning problem 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 generalizations. 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 navigation, 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/.