A Fast Randomized Method to Find Homotopy Classes for Socially-Aware Navigation

Luigi Palmieri, Andrey Rudenko, Kai Oliver ArrasarXiv 2015 · arXiv

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.

Overview of the navigation environment showing the Voronoi graph and social cost contours around pedestrians.

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.

The anisotropic social force model, showing higher cost contours in the direction of the pedestrian's movement.

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

Abstract

We introduce and show preliminary results of a fast randomized method that finds a set of K paths lying in distinct homotopy classes. We frame the path planning task as a graph search problem, where the navigation graph is based on a Voronoi diagram. The search is biased by a cost function derived from the social force model that is used to generate and select the paths. We compare our method to Yen's algorithm, and empirically show that our approach is faster to find a subset of homotopy classes. Furthermore our approach computes a set of more diverse paths with respect to the baseline while obtaining a negligible loss in path quality.
BibTeX
@misc{palmieri2015fast,
  author = {Luigi Palmieri and Andrey Rudenko and Kai Oliver Arras},
  title = {{A Fast Randomized Method to Find Homotopy Classes for Socially-Aware Navigation}},
  year = {2015},
  eprint = {1510.08233},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.08233},
}
Figure