PaperlayerView exact revision on arXiv

Source-linked AI summary

Long-Range Indoor Navigation with PRM-RL

Anthony Francis, Aleksandra Faust, Hao-Tien Lewis Chiang, Jasmine Hsu, J. Chase Kew, Marek Fiser, Tsang-Wei Edward Lee

arXiv:1902.09458v2cs.ROcs.AIcs.LG

TL;DR

Long-range indoor navigation must handle noisy sensors and controls across varied, cluttered buildings. PRM-RL combines an RL local planner with probabilistic-roadmap construction and deployment, achieving stronger navigation across simulation and physical robots while remaining subject to static-roadmap and map requirements.

  • Problem

    Long-range navigation requires reliable planning and control over building-scale distances despite noisy sensors, obstacles, and diverse environments.

  • Method

    PRM-RL trains an environment-independent RL local planner, then builds environment-specific roadmaps by retaining connections the planner can reliably execute.

  • Results

    PRM-RL improved performance over baselines and prior work, achieved up to 92.0% success on robots, and reached 83.4% success for kinodynamic planning in simulation.

  • Takeaways & Limitations

    Roadmaps built from execution-time SLAM maps produced simulation success rates very similar to robot observations, helping close the simulation-to-reality gap.

  • Takeaways & Limitations

    PRM-RL requires a map, and its static roadmaps do not re-plan or automatically accommodate large environmental changes.

Abstract

from arXiv · show

Long-range indoor navigation requires guiding robots with noisy sensors and controls through cluttered environments along paths that span a variety of buildings. We achieve this with PRM-RL, a hierarchical robot navigation method in which reinforcement learning agents that map noisy sensors to robot controls learn to solve short-range obstacle avoidance tasks, and then sampling-based planners map where these agents can reliably navigate in simulation; these roadmaps and agents are then deployed on robots, guiding them along the shortest path where the agents are likely to succeed. Here we use Probabilistic Roadmaps (PRMs) as the sampling-based planner, and AutoRL as the reinforcement learning method in the indoor navigation context. We evaluate the method in simulation for kinematic differential drive and kinodynamic car-like robots in several environments, and on differential-drive robots at three physical sites. Our results show PRM-RL with AutoRL is more successful than several baselines, is robust to noise, and can guide robots over hundreds of meters in the face of noise and obstacles in both simulation and on robots, including over 5.8 kilometers of physical robot navigation. Video: https://youtu.be/xN-OWX5gKvQ

I. INTRODUCTION

Long-range indoor navigation separates global path planning from local control because noisy sensing, long episodes, and diverse buildings challenge either component alone. PRM-RL combines an RL local planner with roadmap construction so connectivity reflects what the robot can reliably execute.

  • Long-range navigation requires collision-free paths to distant goals plus local control that handles obstacles, noisy sensors, and localization.
  • Sparse rewards and long episodes make long-range RL difficult, while complex maps expose short-range agents to wide barriers and narrow passages.
  • PRM-RL trains an environment-independent RL agent for local point-to-point navigation, then uses its behavior to construct environment-specific roadmaps.
  • Roadmap edges are added only when the RL agent consistently navigates between workspace points without collision, incorporating robot dynamics and sensor noise.
  • 37.5% increase in navigation success over [23] accompanied improved performance over baselines, greater roadmap success, and robust performance under increasing noise.
  • 92.0% success rates were achieved on robots at three sites, while kinodynamic car-like planning reached 83.4% success in simulation.

2) Reinforcement learning in motion planning:

Motion-planning navigation research uses learned policies to map observations to controls, while hierarchical methods combine global waypoints with local execution. PRM-RL instead uses the obstacle-avoidance policy itself to determine roadmap connectivity for noisy robots.

  • Deep RL has been applied to navigation and control, but longer episodes and sparse rewards make complex long-range tasks harder to train.
  • Unlike hierarchical approaches using straight-line connections, PRM-RL uses the obstacle-avoidance RL policy to connect roadmap edges and tune connectivity to the robot.
  • A P2P policy maps robot observations to linear and angular velocities, generating trajectories under sensor and actuator noise.
  • PRM graph search supplies intermediate waypoints, which the path-following policy traverses using the P2P policy.
  • A path is reliable when the policy’s probability of completing the task exceeds the task-dependent success threshold p_s.

IV. METHODS

PRM-RL separates long-range planning from local control by training an environment-independent RL policy, building robot- and environment-specific roadmaps, and executing those roadmaps with the same policy.

  • Method: PRM-RL trains a short-range point-to-point RL policy independently of the eventual deployment environment.The policy is trained in a smaller comparable environment to make simulation and training more tractable.
  • Method: The trained policy builds a roadmap by adding workspace-sampled connections only when simulated rollouts exceed the success threshold over repeated trials.This makes roadmap connectivity depend on the capabilities of the particular robot rather than free-space geometry alone.
  • Method: During deployment, the roadmap is queried for waypoints, which the same RL agent executes sequentially until the goal is reached.Each waypoint becomes the agent’s next sub-goal once the robot enters the specified goal radius.
  • Method: PRM-RL’s global planner is decoupled from local-planner construction and training, supporting both differential-drive and carlike robot models.The paper uses this separation to explore two agent models within the same planning framework.
  • Local planner: The local P2P objective is maximizing the probability of reaching the goal without collisions, with AutoRL tuning dense reward parameters for DDPG.The reward includes goal achievement, goal distance, collision, clearance, step, and turning components.

2) P2P for carlike robots:

For carlike robots, PRM-RL adapts the local reward and roadmap procedures to limited turning radius and more complex maneuvers, while retaining repeated RL-based edge validation.

  • P2P for carlike robots: The carlike P2P reward emphasizes progress toward the goal and penalizes backwards speed while omitting several differential-drive reward terms.The omitted terms are goal distance, clearance, and turning, based on analysis of their impact on differential-drive learning.
  • P2P for carlike robots: AutoRL tunes the car model with DDPG while allowing up to 10 training collisions, but evaluation retains the zero-collision objective.This training regime accommodates the car model’s more difficult maneuvering requirements.
  • Roadmap construction: PRMs sample collision-free configurations and connect nearby nodes when a local planner finds an obstacle-free path between them.PRM-RL modifies this connection process by using an RL local planner rather than relying only on geometric line-of-sight paths.
  • Roadmap construction: Each candidate edge is tested through multiple sampled rollouts, and its length is the average successful-edge distance plus the remaining goal distance.An edge is added only when its measured success probability exceeds the threshold.
  • Roadmap construction: Roadmap construction trains one RL agent, samples candidate edges across environments, and evaluates them in parallel before adding successful edges.The procedure accepts edges when AddEdge returns success above threshold.
  • Roadmap construction: The worst-case collision-checking cost is O(Kω*nω), although trials can be parallelized or terminated early after too many failures.The threshold determines the minimum number of successful trials required before early termination.

C. Navigation

Navigation queries the constructed roadmap for sequential waypoints and evaluates PRM-RL across simulated maps, noise and obstacle conditions, robot models, and physical environments.

  • C. Navigation: Navigation adds the start and goal to the roadmap when needed, queries waypoints, and gives them sequentially to the RL agent.If no roadmap path is returned, the start and goal are passed directly to the RL agent.
  • C. Navigation: The evaluation compares PRM-RL with baselines across floorplan and SLAM maps, construction parameters, simulated noise, dynamic obstacles, and robot experiments.The study also examines performance on maps used by a visual-policy baseline.
  • Robot setup: Table I reports AutoRL-tuned reward components for the point-to-point agents.The reward design is described for differential-drive navigation and adapted for the car model.
  • Robot setup: The robot setup uses differential-drive and simple car models controlled by linear and angular velocities, with 2D lidar observations resampled to 64 rays.Both models are represented as circles with 0.3 m radius.
  • Robot setup: Table II covers metric-map environments derived from real building floor plans and SLAM-map environments used for physical deployment.The listed metric environments range from 12 to 200 times the training environment’s area.
  • Robot setup: Roadmaps use uniform random sampling and a 90% effective connection threshold evaluated over 20 attempts.The maximum connection distance is 10 m unless otherwise specified.

4) Roadmap building:

PRM-RL builds roadmaps with stochastic local-planner rollouts, outperforming geometric and prior baselines while trading higher construction cost for stronger long-range navigation.

  • Roadmap construction: PRM-RL uses Monte Carlo rollouts of a stochastic obstacle-avoiding policy to decide which roadmap edges are consistently navigable.The baselines instead use AutoRL, straight-line planning, artificial potential fields, or dynamic-window avoidance.
  • Trade-offs: PRM-RL targets multi-query navigation, producing paths in less than a second from a pre-built roadmap, whereas an RRT query takes about 100 seconds.The roadmap itself may take hours to build, but the resulting graph supports many fast queries across robots.
  • Performance: 91.7% average success in dense floorplan roadmaps, exceeding pure AutoRL by 83.2%, dense PRM-SL by 82.2%, and dense PRM-DWA by 51.6%.Dense PRM-RL and PRM-SL paths remained within 10% of the shortest feasible path, while DWA produced longer paths but better obstacle clearance.
  • Trade-offs: Roadmap construction requires 1–2 orders of magnitude more collision checks than PRM-SL, but runtime path finding requires no collision checking.Planning remains below one second even on the densest maps; PRM-RL execution is almost five times longer than PRM-SL because its controller adapts to uncertainty.
  • Performance: 86.5% success with a sparse PRM and AutoRL policy, a 37.5% increase over the 49% sparse PRM-HTRL result.Increasing roadmap density added 5.2% success and reduced errors by 38.6%.

C. PRM-RL Robustness to Noise

PRM-RL remains effective under sensor and action noise, while roadmap density and connection thresholds expose a trade-off between success, construction cost, and collision-checking effort.

  • Noise robustness: At 0.9 m noise, PRM-RL’s success degrades 28% for lidar noise and 37% for action noise, while outperforming PRM-GAPF and PRM-DWA in all conditions.PRM-GAPF and PRM-DWA fall below 1% under lidar noise and retain only 39% and 54% of peak performance under action noise.
  • Noise robustness: PRM-RL is resilient to lidar, localization, and actuator noise on the order of tens of centimeters, exceeding typical observed platform errors.The authors connect this resilience to the local planner’s noise sensitivity.
  • Sampling density: Success increases with sampling density up to 1.0 samples per meter, after which performance levels off while collision checks rise rapidly.The experiments use sparse density 0.4 samples per meter and dense density 1.0 samples per meter.
  • Model dependence: The car model’s success rate differs from the differential-drive model, indicating that success depends on the robot model as well as the map.The density trend is interpreted relative to the local planner’s ability to reach nearby roadmap nodes.
  • Connection threshold: A 100% connection-success threshold produces the most reliable large-roadmap roadmaps while requiring fewer collision checks through earlier failure termination.The reported threshold recommendation is as high as possible, with 90% or higher identified as a useful region.

E. PRM-RL Performance on SLAM Maps

PRM-RL transfers from SLAM-derived maps to large physical environments and robots, retaining strong comparative performance and a small simulation-to-real gap across testbeds.

  • SLAM-map evaluation: 89% success on dense SLAM-map roadmaps, a 97% relative increase over PRM-DWA and a 157% increase over PRM-GAPF.Performance is lower but comparable to floorplan-map results and exceeds the other evaluated baselines.
  • Large-scale maps: A 15,900-sample quad-building roadmap achieved 57.3% success over 1,000 simulated attempts with paths up to 1000 m.The roadmap contained 689,000 confirmed edges, took four days to build, and required 1.1 billion collision checks.
  • Physical robots: 84.6% success on Physical Testbed 2 with a 1.0-samples-per-meter, 100%-threshold roadmap over 2542.1 m of travel.The longest successful trajectory was 221.3 m, compared with 37.5% success for the sparser 90%-threshold variant.
  • Physical robots: 92.2% success for the dense map versus 85.9% for the sparse map in novel Physical Testbed 3.The denser map reduced robot traversal by an average of 2.5 m per run.
  • Simulation transfer: 85.8% robot success with an average simulation-to-real gap of 7.43% across roadmaps with varied densities and success criteria.The authors report that simulation improvements or regressions are likely to be reflected on robots despite more aggressive robot termination policies.

H. PRM-RL with Kinodynamic Constraints

PRM-RL extends hierarchical navigation to kinodynamic robots and remains robust across dynamic obstacles, transfer settings, and noisy execution. Its analysis attributes performance to policy-aware roadmap connectivity and obstacle-avoidance behavior.

  • Kinodynamic Constraints: 85.8% average success across four simulated car maps demonstrates PRM-RL’s kinodynamic navigation capability under velocity and acceleration constraints.The roadmap connected reachable nodes using a learned steering policy; a separate roadmap achieved 83.4% success while handling complex turnarounds.
  • Kinodynamic Constraints: PRM-RL’s local planner learns steering for a car model with enforced velocity and acceleration constraints, making the roadmap effectively kinodynamic.
  • Dynamic Obstacles: With 40 moving obstacles, PRM-RL achieved 53.1% performance, exceeding PRM-GAPF at 28.7% and PRM-DWA at 40.3%.The method relied on local obstacle avoidance without explicit replanning.
  • Transfer and Related Methods: On transfer maps, PRM-RL exceeded 90% success and reached 94.6% on a dense map, despite using lidar, continuous actions, and arbitrary goals.Successor Features reported 98% under vision, discretized actions, and a single goal, so the comparison involves different capabilities and task settings.
  • Transfer and Related Methods: PRM-RL generalizes to environments unlike its training and prior test environments and remains competitive with methods designed for other environments.
  • Connectivity Analysis: Policy-aware connectivity avoids unreliable roadmap links, but local safety estimates can overestimate long-path safety under noise and environmental ambiguity.A persistent 0.5 meter localization error caused dangerous wall proximity despite a safety layer, while PRM-RL omitted unreliable connections.

B. PRM-RL Computational Complexity

PRM-RL roadmap construction depends on workspace size, policy range, sampling density, and connection attempts. Longer policy ranges and denser sampling increase cost, while shorter connection distances and parallelization can reduce practical runtime.

  • PRM-RL samples workspace nodes and tests neighbors within the empirically determined policy range, with sampling capped at a density independent of workspace volume.
  • Edge identification costs O(nW log nW), while validating candidate edges requires nω rollouts and approximately O(dπ) collision checks per rollout.
  • Roadmap complexity is O(dπ^2DW+1) in policy range, so the authors recommend choosing connection distance dω < dπ.
  • When the workspace greatly exceeds policy reach, complexity is nearly linear in workspace volume and linear in connection attempts nω.
  • Complexity is quadratic in sampling density ρω, although independent edge attempts permit parallelization up to the expected sample count and beyond with parallel rollouts.
  • Higher success thresholds often reduce early-termination attempts, but the distribution of successes and failures can substantially affect construction cost.Reducing maximum connection distance below policy navigation distance can increase expected edge success and potentially reduce nω.

C. PRM-RL Trajectory Execution

PRM-RL estimates edge reliability from repeated policy rollouts before adding roadmap connections. Because path success compounds across waypoints, the edge threshold strongly affects long-trajectory reliability.

  • 20 Monte Carlo rollouts typically assess each candidate edge using 90% or 100% observed-success thresholds.
  • 95.5% actual edge success follows a 100% observed-success threshold, compared with 86.3% for a 90% threshold.
  • For paths averaging 10.25 waypoints, estimated success is 62.3% with the 100% threshold versus 22.0% with the 90% threshold.

D. Limitations

PRM-RL’s current scope excludes replanning, exploration policies, and online map building, leaving static-roadmap and map-dependent operation as key boundaries.

  • Dynamic environments: PRM roadmaps remain static after construction, so PRM-RL does not re-plan when dynamic obstacle avoidance changes the robot’s route.Updating the roadmap could address this case by supplying a nearer subsequent waypoint.
  • Dynamic environments: Large environmental changes, such as adding or removing a wall, can invalidate existing edges or create new paths.The paper identifies roadmap updating, such as iterative reshaping, as a possible response.
  • Map dependence: PRM-RL requires a map, although an incrementally updated PRM and SLAM system could eventually support online roadmap construction.The paper leaves combined exploration and online map building for future work.
  • Map dependence: Developing an exploration policy remains challenging and is coupled to improving the local planner’s reliability during execution.The stated evaluation focuses on roadmap construction and performance rather than these online capabilities.

APPENDIX TABLE OF SYMBOLS

The appendix records optimization, clipping, discounting, target-update, batch, replay-buffer, and training-step settings for the actor–critic implementation.

  • Optimization: Both actor and critic use Adam with β1 = 0.9, β2 = 0.999, and ϵ = 1e−08.
  • Optimization: The actor learning rate is 1e−05, while the critic learning rate is 0.0005.
  • Learning details: The critic uses γ = 0.995 with Huber loss, and the actor uses DQDA gradient clipping.
  • Training configuration: Training uses 10,000 stabilization steps, 0.0001 soft target updates per step, batch size 512, and a 0.5 million replay-buffer capacity.
  • Training configuration: The policies are trained for 5 million steps.
Loading 1902.09458v2…