PaperlayerView exact revision on arXiv

Source-linked AI summary

Local-Minimum Escaper: Programmatic Subgoal Generation for Robust Navigation in Unknown Environments

Yin Gu, Xinming Zhang, Shanze Wang, Siwei Cheng, Wei Zhang

arXiv:2609.38928v1cs.RO

TL;DR

Mapless robots can become trapped at local minima, while learned recovery behaviors are typically encoded through rewards or policy optimization. LME explicitly generates interpretable subgoals from local observations and uses a local planner to reach them. Experiments in simulation and the real world show generalization to challenging unseen scenarios, including deployment on differential-drive and quadruped robots.

  • Problem

    In unknown environments, robots can become trapped at local minima, and existing learned escape behaviors rely on reward design or policy optimization.

    Source: §I · p. 1

  • Method

    LME generates subgoals from local observations using interpretable criteria about obstacle geometry and candidate safety, then uses a local planner to reach the selected subgoal.

    Source: §I · pp. 1–2

  • Results

    Experiments in simulation and the real world show LME generalizes to challenging unseen scenarios, with successful deployment on differential-drive and quadruped robots.

    Source: §VI · p. 11

  • Takeaways & Limitations

    Generated subgoals can guide different local planners to recover from local minima without additional training.

    Source: §VI · p. 11

Abstract

from arXiv · show

Mapless navigation in unknown and partially observable environments remains challenging for mobile robots, particularly when local minima prevent the robot from making progress toward its goal. Existing local navigation methods often lack an explicit mechanism for escaping such situations, while deep reinforcement learning (DRL) approaches typically learn recovery behaviors implicitly through reward design and policy optimization. In this work, we propose \textbf{LME} (Local-Minimum Escaper), a programmatic hierarchical framework that explicitly generates and reasons subgoals to guide robots out of local-minimum regions. LME operates solely on local observations and selects candidate subgoals using interpretable heuristic criteria that account for both surrounding obstacle geometry and candidate-location safety. A local planner then generates low-level motion commands toward the selected subgoal. This design enables LME to handle environments both with and without local minima within a unified framework, while remaining independent of the underlying local planner and requiring no additional training. Extensive experiments in simulated and real-world environments demonstrate that LME provides robust navigation performance and generalizes to challenging unseen scenarios. Furthermore, the generated subgoals can be used to guide different local planners, substantially improving their ability to escape local minima. Successful deployments on both differential-drive and quadruped robots further demonstrate the practical applicability and generality of the proposed framework.

I. INTRODUCTION

Mapless navigation can leave robots trapped at local minima, while learned recovery methods encode escape behavior indirectly. LME instead explicitly generates interpretable subgoals, building on local navigation approaches that use observations directly rather than requiring a global map.

A. Local and Reactive Navigation

  • Map-based methods such as A* [6] and RRT plan with environment representations, whereas reactive methods generate commands from the robot’s state and local observations.Examples include DWA, and APF; map reliance or manually tuned parameters can limit adaptability to complex, unseen environments.Source: §I · p. 1, A. Local and Reactive Navigation · p. 2

B. DRL for Mapless Navigation

  • DRL maps sensory observations and robot state to motion commands without a global map, with studies addressing dynamic obstacles, narrow passages, and other constraints.The paper notes that local minima have received relatively little attention in unknown environments.Source: §I · p. 1, B. DRL for Mapless Navigation · p. 2

I. INTRODUCTION

  • Local minima can trap mapless robots, and learned escape behaviors rely on reward design or exploration, which can make policies difficult to interpret and verify.A locally goal-directed action may not lead to a feasible route, creating tension between goal-directed rewards and the exploration needed to escape.Source: §I · p. 1, B. DRL for Mapless Navigation · p. 2
  • LME explicitly generates subgoals from local observations using interpretable criteria, while a local planner computes actions toward the selected subgoal.Its criteria consider obstacle geometry and candidate-location safety; the framework supports settings with and without local minima and does not require retraining the underlying planner.Source: §I · pp. 1–2

C. Local-Minimum-Aware Mapless Navigation

Prior local-minimum approaches use learned rewards or exploration mechanisms, leaving recovery behavior implicit; LME encodes avoidance directly and can work with different local planners without retraining. The paper formulates mapless navigation as sequential decisions from local observations, with episode outcomes determining sparse rewards.

C. Local-Minimum-Aware Mapless Navigation

  • Prior local-minimum methods use reward engineering or exploration mechanisms, while LME encodes avoidance directly and can pair with different local planners without retraining.The related-work discussion also identifies learned policies’ black-box nature as making decisions difficult to interpret and verify.Source: C. Local-Minimum-Aware Mapless… · p. 2

A. Problem Formulation

  • Mapless navigation is formulated as sequential decision-making toward a target in an unknown environment without access to a global map.Fig. 1 depicts LiDAR beams, the final goal, and potential LME subgoals.Source: A. Problem Formulation · p. 2, Figure 1 · p. 3
  • The policy observes laser scans, relative target position, current velocities, and velocity and acceleration limits, then outputs continuous linear and angular velocities.Source: A. Problem Formulation · pp. 2–3
  • LME uses a sparse episode-level reward based on success, crash, or timeout, with success reward depending on steps taken and negative penalties for crashes and timeouts.The objective is to maximize expected reward.Source: A. Problem Formulation · p. 3

B. Policy Framework

LME represents navigation as a three-module program that generates and maintains subgoals before a local planner produces actions. Its subgoal-generation program scores sampled candidates with criteria for goal progress, safety, obstacle bypassing, and historical avoidance.

B. Policy Framework

C. Subgoal Generation Program

  • Candidate scoring favors points closer to the target and penalizes points that deviate from the robot’s forward direction.The directional criterion discourages frequent heading changes.Source: C. Subgoal Generation Program · p. 3
  • Reachability criteria require clearance on the origin-to-subgoal path and favor candidates with a clear path to the target within the visible field.The target-path criterion optimistically assumes no obstacles in unobserved regions.Source: C. Subgoal Generation Program · p. 4
  • The surmount feature scores candidates near a point offset from the target-facing boundary of an obstacle blocking the target.Scan points less than 2r apart are grouped into sectors; bypassing a blocking sector is favored over heading straight toward the target when that would trap the robot.Source: C. Subgoal Generation Program · p. 4
  • Historical avoidance treats recent robot positions as virtual obstacles and penalizes candidate paths that pass too close to them.The FIFO queue stores positions from the most recent k time steps.Source: C. Subgoal Generation Program · pp. 4–5

D. Subgoal Maintenance Program

The maintenance module chooses whether to keep the previous subgoal or switch to a newly generated one. It updates the old subgoal’s robot-relative position using recent motion before comparing scores.

D. Subgoal Maintenance Program

  • The maintenance module retains the previous subgoal or switches to a new one by checking whether the old one was reached and comparing their scores.This balances the efficiency cost of frequent switching against missing better alternatives by following an old subgoal too long.Source: D. Subgoal Maintenance Program · p. 5
  • The previous subgoal’s robot-relative position is updated using forward translation and rotational compensation from successive velocities.The update approximates relative motion with a first-order motion model.Source: D. Subgoal Maintenance Program · p. 5

E. Local Planner

LME’s local planner turns a subgoal’s relative distance and bearing into low-level control commands, but the framework can also use other local planners. Its described controller steers toward the subgoal while respecting motion constraints.

E. Local Planner

  • LME does not restrict the low-level planner; classical methods such as DWA and DRL-based approaches can be integrated.The experiments explore alternative local planners.Source: E. Local Planner · p. 5
  • The described planner steers angular velocity toward the subgoal and commands positive forward velocity only when the subgoal is in front.The planner computes actions from subgoal distance and bearing, current velocity, and maximum velocity and acceleration constraints.Source: E. Local Planner · p. 5
  • Both controllers use acceleration-limited motion, with symmetric deceleration near the target; the angular controller switches to PD behavior for small angular errors.The linear controller maintains constant velocity when remaining distance exceeds stopping distance.Source: E. Local Planner · p. 5

F. Program Optimization

The program’s non-differentiable parameters are optimized with gradient-free Bayesian optimization. The supplied map figure identifies the training and testing maps used in ROS Stage.

F. Program Optimization

  • 150 Bayesian-optimization steps maximize reward R to set the program’s non-differentiable parameters.Gradient-based optimization is unsuitable for the discrete program structure.Source: F. Program Optimization · p. 5
  • Parameters w and d are constrained to positive real numbers.The passage identifies these as parameters requiring optimization.Source: F. Program Optimization · p. 5
  • Fig. 3 identifies the ROS Stage training map and testing map.The training map has dense small obstacles and few local minima; the unseen testing map has long walls that introduce local-minimum regions.Source: Figure 3 · p. 6

G. Extension to Non-Circular Robot Shapes

LME extends to non-circular robots by using collision-radius bounds to reason about subgoal reachability. Its conservative radius choice favors guaranteed collision safety, and adapting to a new shape requires only changing that parameter.

G. Extension to Non-Circular Robot Shapes

IV. EXPERIMENTS IN SIMULATION

LME transfers from its training map to an unseen map with similar success, and performs best overall in the BARN comparison. The experiments also show that its subgoals can improve different local planners without retraining.

A. Training in Simulation

  • Training uses ROS Stage with 600 episodes and fixed sampled configurations; one run takes approximately 1.5 hours.The simulated robot is circular with a 0.2 m radius, and the training map has dense small obstacles but few local minima.Source: A. Training in Simulation · p. 6
  • LME achieves success rates close to 95% on both the training map and an unseen map with substantially different layouts.The unseen map contains long walls and local-minimum regions, and the transfer shows no noticeable performance degradation.Source: A. Training in Simulation · p. 6

B. Performance Validation in BARN

  • BARN evaluation uses 100 challenging maps, including constrained regions prone to trapping robots in local optima.The benchmark robot is a rectangular Jackal differential-drive platform.Source: B. Performance Validation in BARN · p. 6
  • LME achieves the best overall performance in BARN, outperforming traditional and DRL-based methods; LME-augmented planners perform comparably to global-planner approaches.The comparison reports that DWA success rises from 0.60 to 0.85 with LME, alongside reductions in collision and timeout rates.Source: Table II · p. 7, B. Performance Validation in BARN · pp. 7–8
  • Adding LME subgoals improves DWA and DRL-DCLP without retraining or additional parameter tuning.For DWA, success rises from 0.60 to 0.85; the DRL-based method also has higher success and fewer timeouts.Source: B. Performance Validation in BARN · pp. 7–8

C. Trajectory Visualization

Trajectory examples contrast LME’s navigation around complex obstacles with local planners becoming trapped, and show a looping failure by S3-FISVFH in a dense obstacle cluster.

C. Trajectory Visualization

D. Interpretability of LME

LME's feature contributions make its subgoal decisions inspectable, while ablations show that collision avoidance and subgoal maintenance are especially consequential. Other scoring criteria also contribute, though their effects vary and may be complementary.

D. Interpretability of LME

  • Feature contributions can be inspected: co penalizes candidates whose direct path intersects an obstacle, while ct favors apparently direct routes through unobserved regions.Considering multiple features, particularly ct, selects a subgoal that guides the robot around the full obstacle; the authors describe this decomposable rationale as an interpretability advantage over many DRL approaches,.Source: D. Interpretability of LME · p. 8

E. Ablation Studies

  • Removing co has the largest impact; removing ct or amount degrades obstacle navigation, while removing aclose or ch causes moderate degradation and removing adev barely changes success.The authors note that adev still encourages forward-facing subgoals.Source: E. Ablation Studies · p. 8
  • Without subgoal maintenance, the robot switches subgoals more often, behaves less stably, and achieves a lower success rate.The scoring criteria may complement one another, so removing one criterion does not always cause a substantial drop.Source: E. Ablation Studies · p. 8

V. EXPERIMENTS IN THE REAL WORLD

Real-world tests cover wheeled-robot navigation in complex static layouts and dynamic-obstacle scenarios. LME-based guidance helps robots reach targets in local-minimum situations, and the maintenance module can switch subgoals when the current one becomes unsafe or unreachable.

V. EXPERIMENTS IN THE REAL WORLD

  • The evaluation included manually designed and realistic local-minimum scenarios with static and dynamic obstacles, using differential-drive wheeled and quadruped robots.The wheeled-robot setup used a map only to localize the target, not as policy input.Source: §V · pp. 8–9, A. Navigation Results for Wheeled Robots · p. 9

A. Navigation Results for Wheeled Robots

  • In Real1–Real4, LME-based guidance reached targets where DRL-DCLP stalled; LME-DRL trajectories were smoother than LME's, while DWA-based methods performed comparably to DRL-based approaches.The layouts include narrow passages, irregular obstacles, concave corridors, and semi-enclosed structures.Source: A. Navigation Results for Wheeled Robots · p. 9, Figure 9 · p. 10, Figure 10 · p. 10
  • When a pedestrian blocked a narrow passage, LME and LME-DRL rerouted; maintenance switches to a new subgoal when the current one becomes unsafe or unreachable.The results suggest the subgoal generator can rapidly produce new subgoals as the environment changes.Source: A. Navigation Results for Wheeled Robots · p. 10

B. Navigation Results for Quadruped Robots

On a quadruped robot, LME navigated two challenging scenarios to the target without collision. The conclusion reports generalization to unseen environments and use of LME's subgoal guidance with different local planners.

B. Navigation Results for Quadruped Robots

  • The policy reached the target without collision in both quadruped scenarios, demonstrating transfer from simulation to a real platform with different locomotion dynamics.The robot operated at 8 Hz with maximum linear velocity limited to 0.66 m/s and a 0.3 m collision radius.Source: Figure 15 · p. 11, B. Navigation Results for Quadruped… · p. 11

VI. CONCLUSION

  • The conclusion reports generalization to challenging unseen scenarios and says LME can guide different local planners to recover from local minima without additional training.Successful deployments on differential-drive and quadrupedal robots further support the framework's practical applicability and generality.Source: §VI · p. 11
Loading 2609.38928v1…