# HEIGHT: Heterogeneous Interaction Graph Transformer for Robot Navigation in Crowded and Constrained Environments

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 78 references that are in the map.
- First posted on arXiv 19 Nov 2024.

## Builds on (most cited first, 30 of 46)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [YOLOv3: An Incremental Improvement](https://mlsanity.com/paper/1804.02767/) (2018)
- [Planning-oriented Autonomous Driving](https://mlsanity.com/paper/2212.10156/) (2022)
- [Simple Online and Realtime Tracking with a Deep Association Metric](https://mlsanity.com/paper/1703.07402/) (2017)
- [NuPlan: A closed-loop ML-based planning benchmark for autonomous vehicles](https://mlsanity.com/paper/2106.11810/) (2021)
- [Structural-RNN: Deep Learning on Spatio-Temporal Graphs](https://mlsanity.com/paper/1511.05298/) (2015)
- [Habitat 3.0: A Co-Habitat for Humans, Avatars and Robots](https://mlsanity.com/paper/2310.13724/) (2023)
- [Social Attention: Modeling Attention in Human Crowds](https://mlsanity.com/paper/1710.04689/) (2017)
- [Crowd-Robot Interaction: Crowd-aware Robot Navigation with Attention-based Deep Reinforcement Learning](https://mlsanity.com/paper/1809.08835/) (2018)
- [Socially Compliant Navigation Dataset (SCAND): A Large-Scale Dataset of Demonstrations for Social Navigation](https://mlsanity.com/paper/2203.15041/) (2022)
- [Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning](https://mlsanity.com/paper/1609.07845/) (2016)
- [The Ingredients of Real-World Robotic Reinforcement Learning](https://mlsanity.com/paper/2004.12570/) (2020)
- [Motion Planning Among Dynamic, Decision-Making Agents with Deep Reinforcement Learning](https://mlsanity.com/paper/1805.01956/) (2018)
- [Core Challenges of Social Robot Navigation: A Survey](https://mlsanity.com/paper/2103.05668/) (2021)
- [Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning](https://mlsanity.com/paper/1709.10082/) (2017)
- [Augmenting Reinforcement Learning with Behavior Primitives for Diverse Manipulation Tasks](https://mlsanity.com/paper/2110.03655/) (2021)
- [SACSoN: Scalable Autonomous Control for Social Navigation](https://mlsanity.com/paper/2306.01874/) (2023)
- [Principles and Guidelines for Evaluating Social Robot Navigation Algorithms](https://mlsanity.com/paper/2306.16740/) (2023)
- [Intention Aware Robot Crowd Navigation with Attention-Based Interaction Graph](https://mlsanity.com/paper/2203.01821/) (2022)
- [Socially Compliant Navigation through Raw Depth Inputs with Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1710.02543/) (2017)
- [Auto-Tuned Sim-to-Real Transfer](https://mlsanity.com/paper/2104.07662/) (2021)
- [Relational Graph Learning for Crowd Navigation](https://mlsanity.com/paper/1909.13165/) (2019)
- [Decentralized Structural-RNN for Robot Crowd Navigation with Deep Reinforcement Learning](https://mlsanity.com/paper/2011.04820/) (2020)
- [Social Attention for Autonomous Decision-Making in Dense Traffic](https://mlsanity.com/paper/1911.12250/) (2019)
- [Planar Robot Casting with Real2Sim2Real Self-Supervised Learning](https://mlsanity.com/paper/2111.04814/) (2021)
- [Reinforcement Learning for Autonomous Driving with Latent State Inference and Spatial-Temporal Relationships](https://mlsanity.com/paper/2011.04251/) (2020)
- [DRL-VO: Learning to Navigate Through Crowded Dynamic Scenes Using Velocity Obstacles](https://mlsanity.com/paper/2301.06512/) (2023)
- [Robot Navigation in Crowds by Graph Convolutional Networks with Attention Learned from Human Gaze](https://mlsanity.com/paper/1909.10400/) (2019)

## Built on by (most cited first, 9 of 9)

- [SocialNav-SUB: Benchmarking VLMs for Scene Understanding in Social Robot Navigation](https://mlsanity.com/paper/2509.08757/) (2025)
- [ComposableNav: Instruction-Following Navigation in Dynamic Environments via Composable Diffusion](https://mlsanity.com/paper/2509.17941/) (2025)
- [TRANS: Terrain-aware Reinforcement Learning for Agile Navigation of Quadruped Robots under Social Interactions](https://mlsanity.com/paper/2602.12724/) (2026)
- [FlashNav: Training Deployable Robot Navigation Policies in Seconds](https://mlsanity.com/paper/2606.15846/) (2026)
- [SPLC: Social Preference Learning for Crowd Robot Navigation](https://mlsanity.com/paper/2607.01925/) (2026)
- [Navigating the Proximity-Safety Balance: Constraint Decomposition for Human Following in Pedestrian Crowds](https://mlsanity.com/paper/2608.10056/) (2026)
- [PRISM: Predictive Representation of Interaction Style and Motion for Social Robot Navigation](https://mlsanity.com/paper/2609.18125/) (2026)
- [SoGuDiff: Socially Guided Diffusion for Steerable, Norm-Grounded Robot Navigation](https://mlsanity.com/paper/2609.30560/) (2026)
- [Learning Social Navigation from Internet Videos in the Policy State Space](https://mlsanity.com/paper/2609.37476/) (2026)

## Abstract (arXiv)

We study the problem of robot navigation in dense and interactive crowds with static constraints such as corridors and furniture. Previous methods fail to consider all types of spatial and temporal interactions among agents and obstacles, leading to unsafe and inefficient robot paths. In this article, we leverage a graph-based representation of crowded and constrained scenarios and propose a structured framework to learn robot navigation policies with deep reinforcement learning. We first split the representations of different inputs and propose a heterogeneous spatio-temporal graph to model distinct interactions among humans, robots, and obstacles. Based on the heterogeneous spatio-temporal graph, we propose HEIGHT, a novel navigation policy network architecture with different components to capture heterogeneous interactions through space and time. HEIGHT utilizes attention mechanisms to prioritize important interactions and a recurrent network to track changes in the dynamic scene over time, encouraging the robot to avoid collisions adaptively. Through extensive simulation and real-world experiments, we demonstrate that HEIGHT outperforms state-of-the-art baselines in terms of success, navigation time, and generalization to domain shifts in challenging navigation scenarios. More information is available at https://sites.google.com/view/crowdnav-height/home.