Unfreezing the robot: Navigation in dense, interacting crowds

By Pete Trautman, Andreas Krause. 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2010

678 citations recorded by the source corpus.

In this paper, we study the safe navigation of a mobile robot through crowds of dynamic agents with uncertain trajectories. Existing algorithms suffer from the “freezing robot” problem: once the environment surpasses a certain level of complexity, the planner decides that all forward paths are unsafe, and the robot freezes in place (or performs unnecessary maneuvers) to avoid collisions. Since a feasible path typically exists, this behavior is suboptimal. Existing approaches have focused on reducing the predictive uncertainty for individual agents by employing more informed models or heuristically limiting the predictive covariance to prevent this overcautious behavior. In this work, we demonstrate that both the individual prediction and the predictive uncertainty have little to do with the frozen robot problem. Our key insight is that dynamic agents solve the frozen robot problem by engaging in “joint collision avoidance”: They cooperatively make room to create feasible trajectories. We develop IGP, a nonparametric statistical model based on dependent output Gaussian processes that can estimate crowd interaction from data. Our model naturally captures the non-Markov nature of agent trajectories, as well as their goal-driven navigation. We then show how planning in this model can be efficiently implemented using particle based inference. Lastly, we evaluate our model on a dataset of pedestrians entering and leaving a building, first comparing the model with actual pedestrians, and find that the algorithm either outperforms human pedestrians or performs very similarly to the pedestrians. We also present an experiment where a covariance reduction method results in highly overcautious behavior, while our model performs desirably.

Subfields: Computer Vision and Pattern Recognition, Ocean Engineering

View Paper: https://www.semanticscholar.org/paper/0ae705501edfa94f610f10424faa7d4e7615a1f8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Ocean Engineering

Citations in the corpus

SS-LSTM: A Hierarchical LSTM Model for Pedestrian Trajectory Prediction (2018, background): “[26] proposed an interaction model to describe cooperative human behaviour in crowded scenes based on the Interacting Gaussian Processes (IGP) model [25].”
Crowd-Robot Interaction: Crowd-Aware Robot Navigation With Attention-Based Deep Reinforcement Learning (2018, methodology): “To address this issue, a large number of works have focused on obstacle avoidance methods that jointly plan plausible paths for all the decision-makers, in hope to make room for each other cooperatively [18].”
Human motion trajectory prediction: a survey (2019, methodology): “Several others can be extended to include further types of contextual information (e.g. Alahi et al. (2016); Trautman and Krause (2010); Vemula et al. (2018); Pfeiffer et al. (2018); Bartoli et al. (2018)) but such extension may lead to involved learning, data efﬁciency and generalization issues…”
Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning (2016, background): “However, since reactionbased methods do not consider evolution of the neighboring agents’ future states, they are short-sighted in time and have been found to create oscillatory and unnatural behaviors in certain situations [10], [13].”
Socially compliant mobile robot navigation via inverse reinforcement learning (2016, background): “Trautman and Krause (2010) demonstrated that mobile robot navigation fails in densely populated environments unless the robot takes into account the interaction between itself and the humans.”
Core Challenges of Social Robot Navigation: A Survey (2021, methodology): “In addition to hard constraint violations, continuous metrics have been proposed to define a robot’s closest distance to a human, known as the safety margin [248] or the minimum distance [168].”
A Survey on Trajectory-Prediction Methods for Autonomous Driving (2022, methodology): “GP can also be used to model interaction-related factors, Trautman et al. [42] use GP for joint collision avoidance to solve the frozen robot problem.”
Robot Navigation in Constrained Pedestrian Environments using Reinforcement Learning (2020, background): “robot problem” [15], [16], in which the planner finds all solutions to be below certain threshold of safety or feasibility, causing the robot to stop and continuously replan while the pedestrians move.”
End-to-end Recurrent Multi-Object Tracking and Trajectory Prediction with Relational Reasoning (2019, methodology): “Initial research modelled social forces using hand-crafted features [21, 22, 23, 24] or MDP-based motion transition models [25], while more recent approaches learn from context information, e.”
Social LSTM: Human Trajectory Prediction in Crowded Spaces (2016, methodology): “However, this simple LSTM is noticeably worse than the Social Force and IGP models which explicitly model Metric Methods Lin LTA SF [73] IGP* [60] LSTM our O-LSTM our Social-LSTM Avg. disp. error ETH [49] 0.80 0.54 0.41 0.20 0.60 0.49 0.50 HOTEL [49] 0.45 0.”
TraPHic: Trajectory Prediction in Dense and Heterogeneous Traffic Using Weighted Interactions (2018, methodology): “Methods that do not model road-agent interactions are regarded as sub-optimal or as less accurate than methods that model the interactions between road-agents in the scene [19].”
Transformer Networks for Trajectory Forecasting (2020, neutral): “245 / [42] 2010 42 N-Linear MLP (Off) 2.”
Predicting actions to act predictably: Cooperative partial motion planning with maximum entropy models (2016, background): “[13] introduced the novel concept of Interacting Gaussian Processes (IGP), where each agent’s”
Planning for Autonomous Cars that Leverage Effects on Human Actions (2016, background): “This builds on work in social navigation which accounts for interaction potentials with human trajectories [11, 23]: the human and the robot trajectories are jointly planned as the optimum of some reward function in order for everyone to reach their goals and avoid each other.”
Learning Social Etiquette: Human Trajectory Understanding In Crowded Scenes (2016, methodology): “Notice that IGP uses the destination and time of arrival as additional inputs (which our method don’t use).”
Human-aware robot navigation: A survey (2013, background): “[26] [104] [98] [91] [71] [65] [49] [48] [39] [37] [12]”
Robot navigation in dense human crowds: Statistical models and experimental studies of human–robot cooperation (2015, methodology): “Extending the human-robot model described in Trautman and Krause [114] provides a mathematical formulation of shared autonomy.”
Social Attention: Modeling Attention in Human Crowds (2017, methodology): “As shown by [28], lack of cooperation leads to the freezing robot problem where the robot believes there is no feasible path in the environment, despite the existence of several feasible”