TL;DR
This paper introduces a probabilistic, online tour planner that helps mobile service robots efficiently navigate crowded environments by explicitly predicting and avoiding human congestion. By combining data-driven human trajectory predictions (CLiFF maps) with an online Markov Decision Process (MDP), the robot can dynamically reroute or wait out crowds, significantly reducing tour durations and navigation failures.
What Problem Does This Paper Address?
Whether guiding visitors through a museum or delivering packages in a fulfillment center, service robots often need to visit a sequence of locations (Points of Interest, or POIs). Traditional tour planning treats this as a variation of the Traveling Salesperson Problem or Hamiltonian path problem, optimizing for the shortest geometric route.
However, public spaces are filled with humans moving stochastically. When a robot encounters a crowd, its collision-avoidance maneuvers kick in, slowing it down or causing navigation failures. Standard planners either ignore crowds entirely or treat congestion as a static snapshot at the moment of planning. This paper addresses the gap of predictive, task-level planning—allowing a robot to reason about when and where congestion will occur and proactively adjust its high-level route.
Methods
The authors propose an online framework that bridges continuous human motion prediction with discrete task planning:
- Topological Mapping: The environment is represented as a graph where nodes are POIs and edges represent navigation paths. Edge traversal times are modeled as distributions dependent on the number of humans present.
- CLiFF Maps (Circular Linear Flow Field): The robot uses pre-learned CLiFF maps, which model human velocity and direction at discrete locations using semi-wrapped Gaussian mixture models (SWGMMs). Given an initial observation of a person, the system samples multiple future trajectories to capture motion uncertainty.
- Congestion Bands: To prevent a state-space explosion, predicted human positions are mapped onto graph edges using bounding rectangles. The total human count per edge is calculated using a Poisson binomial distribution and then grouped into discrete "congestion bands" (e.g., empty, low, high).
- Tour MDP & LRTDP: The tour is modeled as a Stochastic Shortest Path Markov Decision Process. The state space tracks the robot's current node, the time elapsed, and the set of visited POIs. The robot can choose to traverse an edge or "wait" for congestion to clear. This MDP is solved online using Labeled Real-Time Dynamic Programming (LRTDP) guided by a Minimum Spanning Tree (MST) heuristic. A time-bounded variant limits planning to 3 seconds per step to ensure real-time execution.
[Human Observations] -> [CLiFF Map Trajectory Sampling] -> [Poisson Binomial Distribution] -> [Congestion Bands] -> [Online LRTDP Planner] -> [Robot Action]
Datasets
The framework was evaluated using two distinct datasets:
- ATC Shopping Mall Dataset: A large-scale, real-world human tracking dataset collected in a shopping mall. 50% of the data was used to train the CLiFF map, and the remaining 50% was used to replay human movements in synthetic routing simulations across maps ranging from 11 to 26 nodes.
- Palazzo Madama Dataset: Real human trajectory data collected from a museum in Turin, Italy, used to populate a high-fidelity physical simulation in Gazebo.
Key Insights and Ideas
- Stochastic Over Static: Factoring in the probabilistic evolution of crowds over time yields much faster tours than re-planning frequently with a static "snapshot" of current crowd locations. Static baselines quickly become obsolete as crowds move.
- The Power of Coarse Granularity: Increasing the number of congestion bands (e.g., from 2 to 8) did not significantly improve tour execution times. This implies that a simple binary distinction (congested vs. uncongested) is often accurate enough for high-level task planning, which keeps the computational overhead low.
- Scalability via Sparsity: While adding more congestion bands increases the theoretical branching factor of the MDP, the median planning time remained stable (~1 second) because crowd congestion is typically sparse and isolated to specific areas of a map rather than blanketed everywhere at once.
Key Results
- Synthetic Mall Simulations: On a 26-node map, the proposed LRTDP planner achieved an average tour execution time of 109.12 seconds, significantly outperforming an online Hamiltonian path baseline solver (132.09 seconds).
- Real-Time Feasibility: The bounded LRTDP variant (capped at 3 seconds of planning per step) performed statistically identically to the unbounded version, proving its viability for real-time deployment.
- Physical Gazebo Simulations: In the museum environment, the congestion-aware planner achieved statistically significant reductions in both overall tour duration and navigation failures (getting stuck in crowds) compared to a shortest-path baseline.
Limitations and Future Work
While effective, the authors note a few areas for improvement:
- Scalability to Massive Environments: As the number of POIs and the size of the environment grow, the state space of the MDP will expand. Future work will explore methods to scale to larger tours.
- Longer Prediction Horizons: The current human trajectory prediction is reliable up to around 50 seconds. Improving the accuracy of long-term human motion forecasting would allow the robot to make even smarter, long-range routing decisions.
Summary updated