Hierarchical navigation of spatio-temporal graph for crowds
LIN Si-chao
ZHOU Zhi-qian
REN Jun-kai
ZENG Zhi-wen
CHANG Meng-di
ZHENG Zhi-qiang
LU Hui-min
Abstract：Crowd environment is one of the important application scenarios for ground mobile robots.However,due to pedestrians' decision-making abilities and the inherent uncertainty of their behavior,achieving autonomous and safe navigation in crowded environments has emerged as a significant challenge in the field of service robots.To address this,this paper proposes a spatio-temporal-graph-based hierarchical crowd navigation(STG-HCN)that provides both global and local solutions.Firstly,the STG-HCN introduces Delaunay triangulation to describe the topological relationship of crowd-s.This approach gives rise to a spatio-temporal graph search algorithm,facilitating the rapid generation of global paths.Secondly,considering the dynamic attributes of pedestrians,the paper further integrates pedestrian speed and perspective information.This leads to the proposal of a forward attention potential field based on a Gaussian distribution,aimed at evaluating the impact of the global path on pedestrians.Furthermore,time-varying collision avoidance constraints are for-mulated for dynamic pedestrians,and a receding horizon optimization framework is introduced to solve the time-varying constrained optimization problem,thereby significantly enhancing the motion safety of the robot's global path tracking.To validate the effectiveness of the proposed algorithm,this paper conducts extensive simulation and real-world experiments.Simulation results indicate that STG-HCN can reduce the average number of collisions by 55.7％compared to the bench-mark algorithms.Additionally,real-world experiments conducted using a Fetch robot demonstrate the algorithm's efficacy in practical crowd scenes.
Keywords：service robotsdynamic path planningreceding horizon controlcrowd navigahtion
Publication Date：2025-10-30
Online Publishing Date：2025-11-13(First online date of this platform, not the publication date of the document)
Pages：11( 1946-1956 )