Abstract
Navigating robots through crowded human environments requires more than just finding the shortest path; it requires identifying multiple topologically distinct routes to ensure adaptability. This paper presents the Randomized Homotopy Classes Finder (RHCF), an algorithm that utilizes biased random walks on a Voronoi graph to quickly discover diverse homotopy classes. By incorporating a social force model into the cost function, RHCF generates paths that are both socially acceptable and computationally efficient, outperforming traditional deterministic methods in real-time scenarios.
Introduction
In dynamic environments like airports or busy hallways, a single optimal path often becomes obsolete the moment a pedestrian moves. Standard planners like A or RRT typically fail to provide alternative routes that are fundamentally different—known as homotopy classes. If a robot's primary path is blocked, it may experience "freezing" behavior while re-planning. To solve this, robots need a set of "Plan B" routes pre-calculated. The challenge lies in finding these diverse paths rapidly enough for real-time interaction.
The Randomized Homotopy Classes Finder (RHCF)
The proposed RHCF method shifts away from exhaustive deterministic searches toward a randomized approach that prioritizes diversity and speed.
1. Navigation Graph Construction
The environment is represented using a Voronoi diagram where pedestrians are treated as obstacles. This approach naturally identifies the "gaps" between individuals or groups as potential navigation channels. Unlike a standard grid, the Voronoi graph captures the essential topology of the space, ensuring that paths found on the graph represent distinct ways to navigate around obstacles.
2. Social Cost Function
Rather than simple distance, the algorithm employs a cost function based on the Social Force Model. This model accounts for "social pressure," recognizing that humans have personal space requirements. Crucially, the model is anisotropic: the perceived cost is higher for space directly in front of a person than behind them, reflecting natural human behavior.
3. Biased Random Walk
The core innovation of RHCF is the use of a biased random walk on the Voronoi graph. Instead of using Yen’s algorithm to find the $K$-shortest paths (which is computationally expensive and often yields nearly identical routes), RHCF performs iterative random walks. The probability of a walk transitioning to an adjacent node is inversely proportional to the social cost of the connecting edge. This bias ensures the algorithm explores high-quality paths while the inherent randomness naturally discovers different homotopy classes.
Results and Discussion
The algorithm was evaluated in various simulated crowd scenarios, ranging from simple lines of people to dense, surrounding crowds.
- Computational Efficiency: RHCF demonstrated a significant speed advantage. For finding the first five homotopy classes, it was at least five times faster than Yen’s algorithm across all tests. In dense scenarios like the "Wall of People," it achieved a 60x speedup.
- Path Diversity: Using the Robust Diversity ($RD_k$) metric, the researchers found that RHCF consistently produced more "spread out" and distinct alternatives compared to the baseline. This diversity is critical for robust navigation in unpredictable crowds.
- Quality vs. Speed: While randomized, the paths found by RHCF maintained high quality, typically reaching 70-80% of the theoretical ideal ranking provided by slower deterministic methods.
Conclusion
RHCF provides a scalable and fast solution for socially-aware robot navigation. By leveraging the topological properties of Voronoi graphs and the efficiency of biased random walks, it allows robots to maintain multiple viable navigation strategies simultaneously. Future work will focus on integrating these high-level topological paths with low-level kinodynamic controllers to account for robot physics and further refining the random walk to avoid redundant exploration.
Summary updated