Dynamic Channel: A Planning Framework for Crowd Navigation

Cao, Chao; Trautman, Peter; Iba, Soshi · 2019 · OpenAlex-citations

DOI: 10.1109/icra.2019.8794192

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of real-time robot navigation in dense, dynamic human environments. Existing path planning methods typically fail to balance global optimality with computational efficiency; global planners often assume static environments to avoid the exponential computational cost of adding time as a dimension, while local planners focus only on imminent collision avoidance, neglecting long-term trajectory optimality. To resolve this "global to local quandary," the authors propose a framework called Dynamic Channels, which integrates high-level topological path planning with low-level motion planning to generate feasible, optimal, and socially compliant trajectories. The methodology abstracts the environment using Delaunay Triangulation based on pedestrian positions. The planner constructs a dual graph where vertices represent faces of the triangulation and edges represent adjacency between faces. This structure allows the system to reason about obstacle dynamics efficiently by projecting pedestrian velocities onto the triangulation edges, thereby modeling the time evolution of the environment as a network. The core concept is the "dynamic channel," defined as the time-evolving triangulated polygon bounded by pedestrian pairs. The planner calculates the width of "gates" (distances between pedestrian pairs) over time and determines feasible time intervals when these gates are wide enough for the robot to pass safely, accounting for the robot’s radius and a safety margin. A modified A* algorithm then searches this graph to compute the optimal path, ensuring that the robot’s estimated time of arrival at each gate aligns with the feasible passage windows. The authors evaluate the approach using thousands of real-world pedestrian datasets and compare it against state-of-the-art algorithms for dynamic obstacle avoidance. The results demonstrate that the Dynamic Channel framework significantly outperforms existing methods in task completion rates. Crucially, the approach remains real-time computable even in scenarios with large numbers of dynamic obstacles, overcoming the computational prohibitions associated with traditional time-expanded search spaces. The framework also naturally incorporates certain social norms, such as favoring passage behind pedestrians rather than in front, which reduces travel distance and improves safety. The significance of this work lies in its ability to provide a complete planning pipeline that guarantees both global optimality and safe navigation in dynamic crowds without sacrificing computational efficiency. By leveraging computational geometry to handle obstacle dynamics, the method offers a robust solution for service, safety, and logistic robotics operating in close proximity to agile pedestrians. The paper provides completeness proofs for the approach and suggests that the framework can be further extended to explicitly encode complex social interactions, such as non-crossable edges for groups of people, enhancing the robot's social compliance.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• anticipation