When an autonomous vehicle or mobile robot enters a dense crowd or tight traffic, traditional navigation systems frequently grind to a halt. This phenomenon—known as the freezing robot problem—occurs when a robot becomes immobilized despite the physical existence of open, navigable space.
To understand why robots freeze, we have to look at how they traditionally perceive the world. For decades, the standard paradigm has been to treat humans and other vehicles as passive, independent dynamic obstacles. The robot senses its environment, predicts the future trajectories of surrounding agents as fixed paths or probabilistic cones, and then plans a collision-free path around them.
In dense environments, this decoupled approach fails. Because human trajectories are highly dynamic, a robot's conservative safety constraints will flag every possible local path as a potential collision risk. As highlighted by Amir Hossain Raj et al. in Targeted Learning: A Hybrid Approach to Social Robot Navigation and Chittaranjan Srinivas Swaminathan et al. in Benchmarking the utility of maps of dynamics for human-aware motion planning, this lack of interactive foresight leads directly to navigation paralysis. The robot cannot find a path that is guaranteed to be safe under the assumption that humans will ignore its presence, so it simply stops moving.
The solution emerging across recent research is a shift toward interaction-aware planning. Instead of treating navigation as a defensive avoidance problem, modern frameworks treat it as an active negotiation, modeling how the robot’s own actions will influence the behavior of the crowd.
Breaking the Predict Then Plan Bottleneck
The root of the freezing problem lies in the sequential nature of the traditional pipeline: Perceive $\rightarrow$ Predict $\rightarrow$ Plan. This architecture assumes that prediction is independent of the robot's future actions. In reality, human navigation is a closed-loop feedback system; if a robot asserts itself into a space, a human pedestrian or driver will often alter their path to accommodate it.
To capture this dynamic, researchers have introduced planning-informed trajectory prediction. By conditioning the prediction of surrounding agents on the robot's own intended future trajectory, the robot can evaluate how its maneuvers will actively reshape the environment.
Traditional Decoupled Pipeline:
[Predict Human Trajectory] ---> [Plan Robot Path Around It] (Leads to Freezing)
Interaction-Aware Pipeline:
[Proposed Robot Plan] ---> [Predict Human Response] ---> [Evaluate Joint Safety]
The authors of PiP: Planning-Informed Trajectory Prediction for Autonomous Driving demonstrated that informing prediction models with the ego-vehicle's future plans yields significantly more realistic trajectory forecasts in dense traffic. Similarly, Jerry Liu et al. developed an energy-based deep structured model in Deep Structured Reactive Planning to perform reactive planning. When the system recognizes that a specific forward movement will induce a surrounding driver to yield, it unlocks valid trajectories that a traditional, passive planner would have discarded as unsafe. This insight is echoed by Hengli Wang et al. in End-to-End Interactive Prediction and Planning With Optical Flow Distillation for Autonomous Driving, showing that modeling these mutual dependencies prevents the vehicle from becoming trapped during complex highway merges.
Navigation as a Dynamic Game
To formalize this mutual adaptation mathematically, researchers frequently turn to game theory. Rather than optimizing a single agent's path against a changing backdrop, navigation is framed as a multi-agent dynamic game where all participants simultaneously optimize their own objectives subject to joint safety constraints.
In ALGAMES: A Fast Solver for Constrained Dynamic Games, Mac Schwager et al. introduced a high-performance solver capable of finding Nash equilibria in real-time. By solving for a trajectory where no agent can improve their outcome by deviating, the robot can actively negotiate right-of-way. This game-theoretic framing can also be structured hierarchically. For instance, Zhiyu Huang and Haochen Liu proposed a leader-follower (Stackelberg) model in Learning Interaction-aware Motion Prediction Model for Decision-making in Autonomous Driving, where the autonomous vehicle acts as the leader, choosing an assertive action while explicitly anticipating how human followers will reactively adjust.
A core challenge of game-theoretic planning is that human intent is rarely certain. If a robot assumes a human is perfectly cooperative, it risks collisions; if it assumes the human is entirely unyielding, it freezes. To balance this, Forrest John Laine et al. introduced a multi-hypothesis framework in Multi-Hypothesis Interactions in Game-Theoretic Motion Planning that maintains multiple parallel game formulations based on varying levels of human politeness, allowing the robot to smoothly interpolate between assertiveness and caution as its confidence updates online.
Proactive Nudging and Social Agency
If a robot remains entirely passive, humans will naturally exploit its safety-first programming, intentionally obstructing its path and causing deadlocks, a behavior documented by Xiang Chang et al. in "It Must Be Gesturing Towards Me": Gesture-Based Interaction between Autonomous Vehicles and Pedestrians. Overcoming paralysis requires the robot to exercise social agency—actively communicating its intent through its physical motion or explicit signaling to "nudge" the crowd into cooperation.
This nudging can be executed purely through trajectory design. In Lane-Change in Dense Traffic With Model Predictive Control and Neural Networks, Sangjae Bae et al. combined Model Predictive Control with social generative networks to let vehicles proactively nudge their way into gapless traffic, forcing surrounding drivers to slow down and create a gap. This leverages the insight from S. Shankar Sastry et al. in Planning for Autonomous Cars that Leverage Effects on Human Actions that an autonomous car can use subtle physical positioning to signal intent.
On a pedestrian level, the single-author paper by Yusuke Tamura, 2A1-D18 Implicit Guidance of Human Movement by Movement of a Mobile Robot, demonstrated that a mobile robot can implicitly guide human walking paths purely through its own trajectory choices, leveraging natural human repulsive forces to clear its own path.
When spatial maneuvering is insufficient, robots can leverage active communication channels. Quecheng Qiu et al. introduced "interaction capacity" in Learning to Socially Navigate in Pedestrian-rich Environments with Interaction Capacity, decoupling the social decision of when to signal pedestrians (e.g., via an audible beep or light) from how to steer, giving the robot a mechanism to ask the crowd to yield.
In ultra-dense crowds where contact-free navigation becomes mathematically impossible, Aude Billard argues in Safety Concerns Emerging from Robots Navigating in Crowded Pedestrian Areas that robots must transition away from strict obstacle avoidance toward managing intentional, low-force physical contact as a functional requirement for navigation.
Modeling Social Context and Crowd Cohesion
To negotiate effectively, a robot cannot treat a crowd as a uniform collection of isolated points. It must understand the underlying social structures of the space it is traversing.
For example, cutting through a group of friends walking together causes significant social disruption and can trigger unpredictable defensive maneuvers from pedestrians. To address this, Adarsh Jagan Sathyamoorthy et al. developed the CoMet framework in CoMet: Modeling Group Cohesion for Socially Compliant Robot Navigation in Crowded Scenes. By analyzing visual features like proximity and face-to-face interactions, the robot quantifies group cohesion, choosing to steer entirely around tight-knit groups while confidently weaving through loose gaps between unassociated pedestrians. This social awareness alone was shown to reduce freezing behavior by 57%.
[Pedestrian A] <--- tight cohesion ---> [Pedestrian B]
XXXXX
Robot chooses detour
XXXXX
[Pedestrian C] <--------- loose gap ---------> [Pedestrian D]
===================>
Robot weaves through
By combining these social context metrics with attention-based deep reinforcement learning, as seen in Crowd-Robot Interaction: Crowd-aware Robot Navigation with Attention-based Deep Reinforcement Learning by Changan Chen et al., or psychological frameworks like Social Value Orientation in Interaction-Aware Decision-Making for Automated Vehicles Using Social Value Orientation by Luca Crosato et al., modern planners can align their trajectories with human expectations.
Ultimately, interaction-aware planning works because it replaces an over-conservative, defensive mathematical formulation with a cooperative one. By recognizing that its own movements can induce space-sharing behaviors, the robot transforms a crowded space from an impassable wall of obstacles into a negotiable social dance.