💻 computer science

LiDAR-based Crowd Navigation with Visible Edge Group Representation

This paper proposes a LiDAR-based crowd navigation framework using a simplified visible edge group representation that achieves comparable safety and socialness to complex tracking methods in dense crowds while offering faster computation and robustness to occlusions.

Original authors: Allan Wang, Aaron Steinfeld

Published 2026-04-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Allan Wang, Aaron Steinfeld

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a busy airport terminal. You don't stop to track every single person's name, history, or exact future path. Instead, you see a group of friends walking together. You don't think, "I need to avoid Person A, then Person B, then Person C." You think, "That's a cluster of people; I'll give that whole cluster a wide berth."

This paper is about teaching a robot to do exactly that.

The Problem: The Robot's "Super-Vision" Trap

Most robots trying to navigate crowds are like paranoid accountants. They try to track every single human individually, calculating their speed, direction, and future path with perfect precision.

The Flaw: In a real, dense crowd, people block each other (occlusion). The robot's sensors get confused, and it can't see everyone clearly. It's like trying to count every grain of sand in a storm while wearing blinders.
The Result: The robot gets stuck, acts aggressively, or crashes because it's trying to solve a math problem that is too hard for the messy real world.

The Big Discovery: "Good Enough" is Perfect

The researchers (Allan Wang and Aaron Steinfeld) made a surprising discovery. They tested a complex system that tried to predict exactly how a group of people would move in the future. They found that even if the robot's prediction was slightly wrong, the robot still navigated safely.

Think of it like driving on a highway. You don't need to know exactly where every other car will be in 10 seconds to drive safely. You just need to know, "There's a car ahead, and it's moving forward." The exact prediction doesn't matter as much as having a general idea.

The Solution: The "Visible Edge" Pentagon

Instead of trying to track every person in a group, the robot now looks at the group as a single shape based only on what it can see.

The Analogy: Imagine a group of friends walking together. From the robot's perspective, it can only see the "front" of the group (the people closest to it) and the "sides" (the leftmost and rightmost people). The people in the middle are hidden.
The Magic Shape: The robot draws a simple pentagon (a five-sided shape) around this visible part.
- It finds the person closest to it.
- It finds the person furthest to the left.
- It finds the person furthest to the right.
- It adds a little "buffer zone" behind them to account for the hidden people.
The Result: Instead of tracking 10 people, the robot only tracks 3 points to define the whole group. It's like seeing a flock of birds and just tracking the outline of the flock rather than counting every bird.

Why This is a Game-Changer

Speed: Because the robot is doing simple geometry instead of complex tracking, it thinks much faster. It's the difference between solving a calculus equation and drawing a quick sketch.
No "Magic" Required: It doesn't need expensive cameras or perfect tracking software. It works directly with the robot's laser scanner (LiDAR), which is like a bat using sonar to see the world.
Socially Smarter: By treating groups as single units, the robot respects "social bubbles." It doesn't try to squeeze between two friends walking arm-in-arm. It waits or goes around the whole group, making humans feel more comfortable.

The Real-World Test

The team built a robot and tested it in a real room with real people forming groups.

The Old Way (Tracking Individuals): The robot would sometimes cut in front of people or act nervously because it was trying to predict individual paths.
The New Way (Visible Edges): The robot acted more like a polite human. It saw a group, drew its invisible pentagon, and gave them a wide, safe detour.

The Takeaway

This paper proves that robots don't need to be perfect mathematicians to navigate crowds. They just need to be good observers. By simplifying the world into "visible edges" and treating groups as single shapes, robots can move through busy places faster, safer, and more politely—just like a human would.

1. Problem Statement

Navigating mobile robots in dense pedestrian crowds is a significant challenge. Existing approaches face two primary limitations:

Perception Reliance: Most state-of-the-art methods rely on perfect perception or external tracking modules (e.g., Bytetrack) to identify and track individual pedestrians. In high-density crowds, heavy occlusion makes reliable individual tracking difficult and error-prone.
Computational Complexity: While group-based navigation (treating clusters of people as single entities) has been shown to improve safety and social compliance, existing group models (like G-MPC) often require complex convex hull representations and computationally expensive prediction models (e.g., image-sequence predictors) that are too slow for real-time deployment on robots.

The authors hypothesize that high-precision group prediction is not strictly necessary for safe navigation and propose a simplified representation that can be derived directly from sensor data (LiDAR) without tracking individuals.

2. Methodology

A. Core Insight: Marginal Impact of Prediction Accuracy

Through analysis of the Group-based Model Predictive Control (G-MPC) framework, the authors discovered that inaccuracies in predicting the future state of a group have a marginal impact on overall navigation performance. This observation allows for the simplification of group representations without sacrificing safety.

B. Visible Edge-Based Group Representation

Instead of tracking every individual or modeling complex convex hulls, the authors propose a Visible Edge representation:

Input: The method operates directly on LiDAR scan points (or pedestrian states in simulation).
Clustering: Scan points are clustered (using DBSCAN) to identify potential groups.
Geometric Abstraction: For each group, the robot identifies three key points based on the "visible edge" (the part of the group closest to the robot):
- $p_{c,j}$ : The point on the group closest to the robot.
- $p_{l,j}$ : The leftmost visible point from the robot's perspective.
- $p_{r,j}$ : The rightmost visible point from the robot's perspective.
Pentagon Construction: To account for occlusions behind the visible edge, a fixed offset ( $d$ ) is applied behind the visible edge points. This forms a pentagon defined by five points: $\{p_{l,j}, p_{c,j}, p_{r,j}, p_{ro,j}, p_{lo,j}\}$ .
Prediction: Instead of predicting the trajectory of every individual or the entire convex hull, the system only tracks and predicts the future trajectories of the three key points ( $p_c, p_l, p_r$ ) using a lightweight trajectory predictor (Social-GAN).

C. Integration into MPC

The proposed representation is integrated into a Model Predictive Control (MPC) framework (edge-MPC):

Cost Function: The robot minimizes a cost function that balances reaching the goal and maintaining a safe distance from the predicted group pentagons.
Distance Calculation: The distance between the robot and a group is calculated as the minimum distance to any of the five line segments forming the pentagon.
Efficiency: By reducing the prediction target from a full convex hull or individual trajectories to just three points, the computational load is significantly reduced.

3. Key Contributions

Theoretical Insight: Demonstrated that group prediction accuracy has a marginal effect on downstream navigation performance, justifying the use of simplified representations.
Novel Representation: Proposed the Visible Edge-based Group Representation, a geometric abstraction (pentagon) derived directly from LiDAR scans that bypasses the need for individual pedestrian tracking.
Efficiency: Developed a framework that is significantly faster than existing group-based MPC (G-MPC) while maintaining comparable safety and social metrics.
Real-World Deployment: Successfully deployed the system on a real robot equipped with LiDAR and depth cameras, validating its practicality in high-density crowds.

4. Experimental Results

Simulation Evaluation

The system was tested on ETH and UCY datasets in both "Perfect Perception" (ground truth) and "LiDAR" (simulated sensor noise/occlusion) settings.

Safety: The proposed edge-MPC achieved a Minimum Distance (MinD) comparable to the complex G-MPC (convex hull) and significantly higher (safer) than individual-based methods (pedestrian MPC) and DRL baselines.
- Example: In Online settings, edge-MPC MinD was ~1.75m vs. 0.92m for DRL.
Socialness: The robot exhibited more conservative behavior, respecting group spaces and avoiding "cutting through" groups.
Computation Speed: edge-MPC was 3x to 10x faster than the baseline G-MPC.
- Perfect Perception: 0.153s/step (edge-MPC) vs. 0.841s/step (G-MPC).
- LiDAR Setting: 0.115s/step (edge-MPC) vs. 1.766s/step (G-MPC).
Success Rate: Achieved comparable Success Rates (SR) to G-MPC (e.g., 99.8% vs 99.8% in Online LiDAR settings).

Real-World Experiment

Setup: A custom robot with a 3D LiDAR (used as 2D) and depth cameras navigated a 10x9m room with 6 human participants forming 3 groups.
Comparison: Compared edge-MPC (no tracking) vs. CrowdAttn-RL (requires YOLO/SORT tracking).
Behavior:
- edge-MPC: Behaved conservatively, often detouring behind groups or performing wide maneuvers to avoid them entirely.
- CrowdAttn-RL: Tended to cut in front of pedestrians or pass through the middle of approaching groups.
Human Feedback: Participants rated edge-MPC as more natural and comfortable in crossing scenarios. In flow scenarios, edge-MPC was rated slightly lower due to the difficulty humans had predicting the robot's wide avoidance maneuvers, despite the robot maintaining larger safety distances.

5. Significance

This paper bridges the gap between theoretical group-based navigation and practical deployment. By proving that simplified, sensor-direct group representations are sufficient for safe navigation, the authors enable:

Robustness: Navigation in dense crowds where individual tracking fails due to occlusion.
Real-time Performance: The ability to run complex group-aware planning on embedded robot hardware (Jetson AGX Orin) without external tracking infrastructure.
Social Compliance: A navigation strategy that inherently respects social group dynamics, leading to safer and less intrusive robot behavior in public spaces.

The work suggests that future social navigation systems should prioritize robust, simplified geometric abstractions over complex individual tracking and high-fidelity prediction models.