Navigating the Proximity-Safety Balance: Constraint Decomposition for Human Following in Pedestrian Crowds

This paper addresses the inherent conflict in human-following robot navigation between maintaining close proximity to a target human and navigating safely among surrounding pedestrians and obstacles, a conflict that intensifies in dense crowds where aggressive following risks collisions and conservative margins lead to target loss. The authors argue that existing reinforcement learning (RL) methods encode competing objectives into a single dense reward through weighted summation, making the proximity-safety balance implicit, difficult to adjust, and offering no guarantee that the resulting behavior reflects the designer’s intended trade-off.

To address these limitations, the paper proposes a novel framework that decomposes the human-following task into a sparse task reward and three independent cost constraints within a multi-constraint constrained RL (CRL) formulation. Specifically, the task is formulated as a Constrained Markov Decision Process (CMDP) with: 1) a following cost C t F penalizing deviation from the target, 2) a human collision cost C t H penalizing proximity to other humans, and 3) an obstacle collision cost C t O penalizing proximity to static obstacles. The trade-off is managed through cost thresholds with direct behavioral meaning (e.g., tolerable intrusions or desired following distance) rather than implicit reward weight ratios. The objective is to maximize cumulative reward while keeping human and obstacle safety costs below limits delta H and delta O, and maintaining the following cost at a desired level delta F, where the following cost uses an equality constraint to maintain a desired distance rather than minimizing it.

The paper further integrates prediction uncertainty of human motions into both the observation space and cost formulation to enhance safety under unpredictable conditions. The uncertainty is computed by an adaptive conformal inference (ACI) module that maintains online error bounds adapted to actual prediction quality, using multiple parallel estimators updated via a formula involving learning rates and target miscoverage rates. These per-human, per-horizon uncertainty estimates are incorporated into human feature tokens and into the human safety cost design, where safety regions around predicted positions are scaled by the uncertainty bounds—expanding protection when motion is uncertain and contracting it when predictions are reliable.

The policy network combines an attention-based Transformer for social interaction modeling with a 3D convolutional neural network (CNN) for spatial constraint reasoning from local occupancy grid maps (OGMs) over recent time steps. Early fusion is implemented by embedding robot state, target information, obstacle features, and human features into a shared representation space, allowing self-attention to model all pairwise interactions including obstacle-human and obstacle-robot relationships. Human tokens are ordered by distance to the robot, and sinusoidal positional encoding with a binary mask for undetected humans is applied. The robot token output is processed by an MLP to produce the final representation for the CRL policy module.

The entire system is jointly optimized under the CRL framework using PPO-Lagrangian, with four separate critics estimating value functions for the reward and each cost independently. Four distinct advantage estimates are computed using Generalized Advantage Estimation (GAE) and combined into a single advantage signal with Lagrangian multipliers, which are dynamically adjusted via dual gradient descent to enforce the cost constraints. The actor is updated using the PPO clipping objective. While multiple critics are used during training, only the actor network is needed at inference, so computational cost at deployment is identical to single-critic approaches.

The reward function provides sparse feedback only for task outcomes: success, collision, or target lost. The following cost C t F measures the robot’s distance beyond a personal space threshold d personal, encouraging a moderate following distance. The human safety cost C t H quantifies collision risk by measuring intrusions into uncertainty-aware safety regions around each human, with regions around current positions using a fixed buffer and regions around predicted positions scaled by ACI uncertainty bounds. The obstacle safety cost penalizes the robot for getting too close to static obstacles based on a safe distance threshold.

Experiments were conducted in a cluttered indoor environment with randomly generated static obstacles, 40 humans, and the robot initialized near a target human. The authors extended the CrowdNav simulator with static obstacles for more realistic evaluation. Evaluation metrics include Success Rate (SR), Collision Rate (CR), Target Lost Rate (TLR), and Average Following Distance (AFD). Baselines include three subgoal-guided methods (SG-HA*, SG-ORCA, SG-MPC) and a state-of-the-art RL method (OGM-HEIGHT), plus two ablation models (RL without uncertainty, and RL+ACI with uncertainty but standard RL with weighted penalties).

In-distribution results show that traditional subgoal-guided methods exhibit substantially lower SR and higher CR and TLR compared to RL-based methods. The proposed method significantly outperforms OGM-HEIGHT, achieving a 25.76% higher SR while reducing overall CR by 18.56%, human CR by 10.72%, and obstacle CR to the lowest 5.44% among learning-based methods. The full model outperforms both ablation models by 10.08% and 6.48% in SR while reducing human CR by 5.04% and 2.08%, obstacle CR by 2.88% and 2.48%, and TLR by 2.16% and 1.92%.

A key comparison validates that explicit cost constraints provide more interpretable and predictable behavioral control than reward-based penalty encoding. Three constraint profiles were configured: safety-conservative (delta F=4.0, delta H=3.2), balanced (delta F=3.6, delta H=3.6), and aggressive-following (delta F=3.2, delta H=4.0). As the profile shifts from safety-conservative to aggressive-following, AFD decreases from 2.54 to 2.23 and TLR drops from 10.08% to 3.20%, while human CR rises from 8.80% to 14.24%, showing each cost threshold maps directly and predictably onto its intended behavioral aspect. In contrast, reward weight tuning produces inconsistent and counterintuitive outcomes: doubling w H yields a negligible 0.08% reduction in human CR, and doubling w F leaves AFD completely unchanged at 2.26 while simultaneously raising TLR and human CR, making both following and safety worse.

Out-of-distribution (OOD) evaluations were conducted under four scenarios: a narrow corridor environment with bidirectional pedestrian flow, environments mixed with 15% rushing humans (speeds 1.4–1.7 m/s), environments using the social force (SF) pedestrian model, and environments with pedestrian group dynamics. In the corridor environment, the proposed method maintains a low human collision rate of 8.48%, reducing it by 20.48% compared with OGM-HEIGHT and by 12.56% and 6.64% compared with the two ablations, while achieving higher success rates exceeding OGM-HEIGHT by 33.52% and the ablations by 12.24% and 6.80%. In the rushing humans scenario, the method achieves the best overall performance with SR of 70.56% and human CR of 19.36%. In the SF pedestrian model scenario, the method achieves SR of 64.32% and human CR of 20.08%. In the group dynamics scenario, the method achieves SR of 59.68% and human CR of 32.64%. The paper notes that the policy is most likely to break in scenarios with dense and fast-moving crowds, as well as unpredictable pedestrian behaviors such as sudden turns and closely aligned group movements.

Real-world deployment was validated on a ROSMASTER X3 robot with Mecanum wheels running ROS 2, using 2D LiDAR perception, DR-SPAAM for human detection, SORT for tracking, and a CV predictor with ACI uncertainty bounds. Across 10 test trajectories, the robot successfully completed 7, following the target human while navigating among moving pedestrians and static obstacles. The three failures stemmed from upstream perception limitations (missed detections of dynamic obstacles, inaccurate static boundary estimations) and the target human exceeding the robot’s maximum speed, while the navigation policy itself remained robust throughout all runs.

The main contributions of the paper are: 1) proposing a novel framework that decomposes human-following objectives into a sparse task reward and independent cost constraints, with trade-off managed through behaviorally meaningful cost thresholds and jointly optimized using PPO-Lagrangian; 2) integrating prediction uncertainty of human motions into the observation space and cost formulation, and designing a unified policy network with spatial constraint reasoning for safe human following under uncertain and dynamic pedestrian environments; and 3) extending CrowdNav with static obstacles and conducting extensive evaluations with varying crowd densities, pedestrian behaviors, and environment layouts, plus real-robot deployment under ROS 2.

Improvements to AI systems:

1. Constraint-based objective decomposition: Replace single dense reward functions with a CMDP formulation that separates sparse task rewards from independent, behaviorally interpretable cost constraints (e.g., following distance, human safety, obstacle safety). This allows AI systems to enforce explicit trade-offs via thresholds (e.g., δ F, δ H) rather than opaque reward weights, enabling predictable and adjustable behavior in multi-objective tasks.

2. Uncertainty-aware safety margins: Integrate adaptive conformal inference (ACI) to compute per-agent, per-horizon prediction uncertainty, and scale safety regions dynamically—expanding when predictions are uncertain, contracting when reliable. This improves robustness in dynamic environments by preventing collisions under unpredictable human motion without over-conservatism.

3. Unified spatiotemporal perception with early fusion: Combine a Transformer for social interaction modeling with a 3D CNN for local occupancy grid maps (OGMs) over time, embedding robot state, target, obstacles, and humans into a shared space. This enables joint reasoning over all pairwise interactions (human-human, human-obstacle, robot-obstacle) and spatial constraints, improving navigation in cluttered, crowded scenes.

4. Multi-critic PPO-Lagrangian training: Use separate critics for reward and each cost constraint, with GAE-based advantage estimates combined via dynamically adjusted Lagrangian multipliers. This enforces hard safety constraints during training while keeping inference-time computation identical to single-critic methods, enabling safe deployment on resource-constrained robots.

5. Cost-threshold-based behavioral control: Allow designers to set cost limits (e.g., maximum tolerable human intrusion, desired following distance) that map directly to observable behaviors. This yields predictable changes—e.g., shifting from safety-conservative to aggressive-following reduces target loss but increases human collision rate—unlike reward-weight tuning, which often produces counterintuitive results.

6. OOD generalization via uncertainty and constraint robustness: By training with uncertainty-scaled costs and explicit constraints, the system generalizes to unseen scenarios (narrow corridors, rushing pedestrians, social force models, group dynamics) with lower collision rates and higher success rates than baselines, making it suitable for real-world deployment where pedestrian behavior is diverse and unpredictable.

---

What the improved AI system can do:

• Navigate human-following tasks in dense, dynamic crowds while maintaining a user-specified balance between proximity to the target and safety from collisions, with direct control over trade-offs via interpretable thresholds.

• Adapt its safety margins in real time based on prediction confidence—tightening around predictable pedestrians and expanding around erratic ones—reducing collision risk without sacrificing following performance.

• Reason jointly over social interactions and spatial constraints (e.g., obstacles, walls) using a unified attention+CNN architecture, enabling safe path planning in cluttered indoor environments with moving humans and static obstacles.

• Deploy on real robots with limited compute (e.g., ROS 2, LiDAR, low-power embedded systems) because only the actor network is needed at inference, while training enforces hard safety constraints via multi-critic Lagrangian optimization.

• Achieve robust performance out-of-distribution—including narrow corridors, rushing pedestrians, social-force-based crowds, and group dynamics—with lower collision rates and higher success rates than prior RL and subgoal-based methods.

• Provide predictable, tunable behavior for designers: adjusting a single cost threshold (e.g., δ H) yields the intended effect (e.g., lower human collision rate) without unintended side effects, unlike reward-weight tuning which often degrades both safety and following quality.