Source-linked AI summary
Relational Graph Learning for Crowd Navigation
Changan Chen, Sha Hu, Payam Nikdel, Greg Mori, Manolis Savva
TL;DR
Crowd navigation requires safe, efficient decisions despite interacting humans whose future motions are uncertain. The paper proposes relational graph learning with model-based reinforcement learning and multi-step lookahead, reporting better navigation than baselines and improved behavior in challenging scenarios.
Problem
Crowd navigation requires reasoning about interactions among humans and predicting their motions to avoid collisions and maintain safe distances.
Method
The method dynamically learns relations among agents, uses a GCN for higher-order interaction representations, predicts human motion, and performs d-step lookahead planning.
Results
The full multi-step model outperforms baseline methods, while d-step planning improves success rate, reduces extra time, and increases average return over one-step planning.
Takeaways & Limitations
Relational graph learning combined with predicted human motion supports efficient navigation and handles challenging oscillatory and freezing scenarios.
Abstract
from arXiv · showhide
We present a relational graph learning approach for robotic crowd navigation using model-based deep reinforcement learning that plans actions by looking into the future. Our approach reasons about the relations between all agents based on their latent features and uses a Graph Convolutional Network to encode higher-order interactions in each agent's state representation, which is subsequently leveraged for state prediction and value estimation. The ability to predict human motion allows us to perform multi-step lookahead planning, taking into account the temporal evolution of human crowds. We evaluate our approach against a state-of-the-art baseline for crowd navigation and ablations of our model to demonstrate that navigation with our approach is more efficient, results in fewer collisions, and avoids failure cases involving oscillatory and freezing behaviors.
I. INTRODUCTION
Crowd navigation requires predicting human motion while reasoning about interactions among the robot and all humans. The proposed relational graph learning approach combines interaction reasoning, human-motion prediction, and farsighted planning for safer navigation.
- Crowd navigation is challenging because the robot must predict human motions while avoiding collisions and maintaining safe, socially appropriate distances.
- The approach learns relations among the robot and humans, then uses a GCN to compute interaction features for all agents.
- Predicted interaction features support joint planning of efficient robot navigation and prediction of present human motion.
- The model predicts future human motions and plans for crowd navigation simultaneously using model-based reinforcement learning.
- The authors report better performance than prior baselines and qualitative mitigation of oscillatory or freezing behaviors.
II. RELATED WORK
Prior crowd-navigation methods use hand-crafted interaction models, trajectory predictors, or deep reinforcement learning, but often simplify interactions or fail to use predictions for policy decisions. The paper positions relational graph learning and planning as a way to model richer agent interactions.
- Rule-based methods model interactions through hand-crafted mechanisms such as social forces, reciprocal collision avoidance, or interaction potentials.
- Social-LSTM predicts human trajectories from large datasets, but trajectory forecasting alone does not directly solve crowd-navigation policy decisions.
- LM-SARL learns robot representations with attentive pooling but simplifies crowd interactions and does not explicitly model human motions.
- The proposed model dynamically infers a crowd-robot relation graph at each time step and learns each agent’s state representation from it.
- The method augments relational modeling with a simplified MCTS-style planning algorithm during training and testing.
A. Deep Reinforcement Learning for Crowd Navigation
The crowd-navigation problem is formulated as sequential decision making over observable robot and human states. The optimal policy maximizes expected discounted reward, while the proposed framework addresses unknown dynamics through learned prediction and planning.
- Each agent state includes observable position, velocity, and radius information, while the robot state aggregates the robot and human states.
- The policy maps the crowd state to an action that maximizes expected return under the environment’s transition dynamics.
- The transition probability represents how agent actions change the state, but it is usually unknown to the navigating agent.
- The reward function rewards task completion and penalizes collisions or uncomfortable distances.
- The formulation extends to settings with N non-cooperative agents whose observable states are available but whose intents or policies are unknown.
B. Model Predictive Relational Graph Learning
The model represents the crowd as a graph whose learned relations encode interactions among agents. Relational graph features are used to represent the robot and humans for value estimation and motion prediction.
- The crowd is modeled as a graph, with relations among all agents used to compute robot and human state representations through a GCN.
- The graph supports a value-estimation module and a state-prediction module for the current crowd state.
- RGL learns both robot-to-human and human-to-human attention, propagating agent features through message passing to capture higher-order interactions.
- The initial graph vertices contain agent state values before they are transformed into learned representations.
1) Relation Inference:
The model embeds robot and human states into a shared latent space, infers pairwise relations from feature similarity, and uses a GCN to propagate relation-weighted information.
- Relation Inference: Robot and human states are embedded with separate MLPs into a shared latent feature matrix X.
- Relation Inference: An embedded-Gaussian similarity function computes pairwise relations, forming the relation matrix A with a softmax over latent features.
- Relation Inference: Figure 1 represents stronger pairwise interactions with thicker connecting lines.
- Relation Inference: The GCN updates each node by aggregating neighbor features weighted by A, with layer-specific weights, activation, and a residual connection.
2) Interaction Modeling:
The interaction model produces agent-level state representations, then jointly estimates robot state values and predicts future human states to support navigation decisions.
- Interaction Modeling: After L graph-propagation layers, Z_t represents each agent’s state and encodes its local interactions.
- Interaction Modeling: The value module applies a relational graph model and an MLP to predict values over a discretized action space using lookahead.
- Interaction Modeling: The prediction module uses relational features and an MLP to predict each human’s next state from modeled human-human interactions.
- Interaction Modeling: Joint value estimation and human-motion prediction help encode human motion and better address freezing-robot behavior.
C. Relational Forward Planning and Learning
Simplified MCTS augments relational graph learning with multi-step rollouts through predicted crowd states and value estimates, trading computation for longer-horizon decisions.
- C. Relational Forward Planning and Learning: Simplified MCTS supplies bootstrapped learning targets and a farsighted policy by simulating multiple future steps.
- C. Relational Forward Planning and Learning: Increasing simulation depth improves performance potential while increasing computational cost.
- C. Relational Forward Planning and Learning: The planner performs d-step rollouts with crowd-state prediction and value estimation, selecting the action with maximum predicted return.
- C. Relational Forward Planning and Learning: Action-space clipping and recursive search over the top-w next states reduce computation while improving value estimates for unseen states.
D. Joint Value Estimation and State Prediction Learning
Training combines demonstrator imitation learning for initialization with reinforcement learning for value estimation and supervised learning for human-state prediction.
- D. Joint Value Estimation and State Prediction Learning: Imitation learning from collected ORCA demonstrator experience initializes the model before reinforcement learning refines the policy.
- D. Joint Value Estimation and State Prediction Learning: Imitation learning addresses sparse navigation rewards that otherwise prevent reinforcement-learning convergence.
- D. Joint Value Estimation and State Prediction Learning: The value model fV is trained with reinforcement learning, while the prediction model fP is trained with supervised learning.
IV. EXPERIMENTAL RESULTS
Experiments evaluate relational graph learning for crowd navigation under circle-crossing scenarios and examine multi-step planning in challenging interactions. The results indicate that learned human-motion prediction and deeper lookahead improve navigation performance and help avoid collision, oscillatory, and freezing behaviors.
- Quantitative Evaluation: All models are evaluated on 500 random circle-crossing test cases with five humans, using Success, Collision, Extra Time, Avg. Return, and Max Diff. metrics.The robot is invisible to humans, and human behavior is generated with ORCA parameters sampled from a Gaussian distribution.
- Quantitative Evaluation: MP-RGL-Multistep is the best-performing model, while d-step planning improves success rate, reduces extra time, and increases average return compared with MP-RGL-Onestep.The comparison isolates the effect of deeper planning after introducing graph-based interaction modeling and state prediction.
- Quantitative Evaluation: The best-performing model is not collision-free because invisible humans and the lack of next ground-truth states make some collisions unavoidable.The authors give converging humans surrounding the robot as an example of an unavoidable collision case.
- Computation and Qualitative Evaluation: The GNN-based state feature extractor is computationally efficient for relatively small crowds because its computation is a matrix multiplication with negligible change as agent count increases.The authors compare this favorably with attention-based crowd-navigation work.
- Qualitative Evaluation: Two-step lookahead avoids a collision that one-step planning would cause by predicting human motion and assigning low value to the dangerous 210° direction.The model detects the strong relation between nearby humans #0 and #3 and instead selects the 30° direction.
- Qualitative Evaluation: Two-step planning selects 45° toward the goal when one-step planning prefers 225°, because the predicted later positive reward compensates for an immediate discomfort penalty.This scenario places human #3 near the robot’s goal and illustrates a non-myopic decision.
V. REAL-WORLD DEMONSTRATIONS
The trained policy is deployed on a Pioneer robot equipped with depth and LiDAR sensing for real-world crowd-navigation demonstrations. Human positions and velocities are estimated from depth detections and extended Kalman filtering.
- Platform: The policy is deployed on a Pioneer robotic platform equipped with an Intel RealSense ZR300 camera and a Hokuyo 2D LiDAR.The deployment is used for real-world demonstrations of modeling relations among interacting people.
- Perception: YOLO detects 2D human positions from depth data, while an extended Kalman filter tracks humans and computes their velocities.These estimates provide the human-state inputs used during the demonstrations.
VI. CONCLUSION
The paper addresses crowd navigation by representing human-robot and human-human interactions as a graph, using GCNs for interaction features, and combining prediction with future planning. It reports strong baseline performance while identifying temporal modeling of past human trajectories as an extension.
- The model represents human-robot and human-human interactions as a graph and uses GCNs to compute interaction features for value estimation and human-motion prediction.
- d-step planning lets the model explicitly plan into the future under a specific search budget.
- The model outperforms baseline methods by a large margin and handles challenging navigation scenarios.
- Modeling temporal dynamics of past human trajectories could help infer individual intent and group structure among humans.