PaperlayerView exact revision on arXiv

Source-linked AI summary

PRM-RL: Long-range Robotic Navigation Tasks by Combining Reinforcement Learning and Sampling-based Planning

Aleksandra Faust, Oscar Ramirez, Marek Fiser, Kenneth Oslund, Anthony Francis, James Davidson, Lydia Tapia

arXiv:1710.03937v2cs.AIcs.LGcs.RO

TL;DR

Long-range navigation must combine global path finding with local control that respects robot dynamics, task constraints, and noisy sensing. PRM-RL trains local point-to-point RL policies, uses them to build PRM roadmaps, and reuses them during execution; across indoor and aerial tasks, it completed trajectories exceeding 210 m and flights over 1 kilometer while satisfying reported constraints.

  • Problem

    Long-range navigation is difficult because global maps create sparse rewards, while executing paths requires handling dynamics, task constraints, environmental changes, and sensor noise.

  • Method

    PRM-RL trains local RL agents, builds roadmaps by retaining configurations the agents can reliably connect through collision-free trajectories, and queries those roadmaps for long-range navigation.

  • Results

    Across two experimentally verified tasks, PRM-RL completed indoor trajectories over 210 m and aerial flights over 1 kilometer in a planning space 63 million times larger than training.

  • Takeaways & Limitations

    Combining sampling-based planning with RL expands long-range navigation beyond the short-range limitations of either approach alone.

Abstract

from arXiv · show

We present PRM-RL, a hierarchical method for long-range navigation task completion that combines sampling based path planning with reinforcement learning (RL). The RL agents learn short-range, point-to-point navigation policies that capture robot dynamics and task constraints without knowledge of the large-scale topology. Next, the sampling-based planners provide roadmaps which connect robot configurations that can be successfully navigated by the RL agent. The same RL agents are used to control the robot under the direction of the planning, enabling long-range navigation. We use the Probabilistic Roadmaps (PRMs) for the sampling-based planner. The RL agents are constructed using feature-based and deep neural net policies in continuous state and action spaces. We evaluate PRM-RL, both in simulation and on-robot, on two navigation tasks with non-trivial robot dynamics: end-to-end differential drive indoor navigation in office environments, and aerial cargo delivery in urban environments with load displacement constraints. Our results show improvement in task completion over both RL agents on their own and traditional sampling-based planners. In the indoor navigation task, PRM-RL successfully completes up to 215 m long trajectories under noisy sensor conditions, and the aerial cargo delivery completes flights over 1000 m without violating the task constraints in an environment 63 million times larger than used in training.

I. INTRODUCTION

PRM-RL addresses long-range navigation by combining sampling-based path finding with RL-based local control. It targets environments where robots must travel far while handling obstacles, noisy sensing, dynamics, and task constraints.

  • Motivation: Long-range navigation combines collision-free path finding to distant goals with local control that produces feasible robot actions.The tasks require safe movement over substantial distances while satisfying constraints.
  • Sampling-based planning: PRMs approximate configuration-space topology by sampling configurations and connecting pairs with collision-free local paths.Traditional connections commonly use line-of-sight tests or inexpensive local planners.
  • Motivation: RL agents can handle task constraints, environmental changes, sensor noise, measurement errors, and unmodeled dynamics, but sparse long-range rewards make training difficult.Complex maps can also leave agents successful only at short range because of local minima.
  • PRM-RL: PRM-RL builds roadmap connectivity by testing whether an RL agent can repeatedly navigate between configurations along collision-free trajectories.This replaces traditional straight-line C-space connectivity with locally executable, task-aware connections.
  • Evaluation: PRM-RL was evaluated on differential-drive indoor navigation and aerial cargo delivery, including physical-robot experiments.The indoor task uses LIDAR and noisy simulation; the aerial task involves suspended-load constraints.

II. RELATED WORK

The paper relates PRM-RL to sampling-based planning and reinforcement-learning methods for robotic control. Its method uses RL as a local planner while separating learned task dynamics from deployment-environment structure.

  • Sampling-based planning: Prior PRM integrations with RL often use roadmap nodes to reduce the state space, whereas this work applies RL in the full state space as a PRM local planner.The paper also builds on earlier aerial cargo delivery work that tracked paths from straight-line PRMs.
  • Reinforcement learning: DDPG and CAFVI are continuous-state, continuous-action RL methods used here for indoor navigation and aerial cargo delivery, respectively.DDPG supports high-dimensional raw sensor control, while CAFVI is feature-based.
  • PRM-RL pipeline: PRM-RL proceeds through RL training, roadmap creation, and roadmap querying, with the learned agent reused as the deployment-specific local planner.The roadmap can support multiple queries when the same agent controls execution.
  • Evaluation environments: The indoor environments are derived from real building plans, with one small map for training and larger maps for roadmap construction and evaluation.Figure 2 distinguishes obstacle-danger regions, free-space sampling regions, PRM waypoints, and executed trajectories.
  • Evaluation environments: The indoor agent uses LIDAR observations, while the experimental setup includes noisy sensing and dynamics intended to represent the physical robot.These design choices connect the related methods to the paper’s robustness-oriented evaluation.

A. RL agent training

PRM-RL trains local RL policies in compact environments using continuous state and action spaces. The policies observe task-relevant robot states, receive shaped rewards, and are intended to transfer across larger deployment environments.

  • Problem formulation: PRM-RL begins with valid start and goal states in the robot’s state space, whose points must satisfy task constraints and collision-free configuration-space projections.Completion requires the projected state to lie within a goal tolerance in configuration space.
  • State representation: The indoor state combines goal-relative polar coordinates with 64 LIDAR rays, while the aerial state contains quadrotor-load positions, velocities, and load angles.The resulting state dimensions are R66 for indoor navigation and R10 for aerial cargo delivery.
  • Action representation: Indoor actions are left and right wheel speeds, whereas aerial actions are three-dimensional accelerations applied to the quadrotor.Both tasks use continuous action spaces for more precise control and faster policy evaluation.
  • Training setup: The simulator models unknown dynamics through a black-box transition process and adds Gaussian observation noise N(0, 0.1) for indoor training.The indoor simulator operates at 5 Hz.
  • Reward and policy learning: The agent learns a policy mapping observed states to actions by maximizing long-term return from task-specific rewards.Rewards include goal attainment, obstacle avoidance indoors, and load-displacement minimization for aerial delivery.

B. PRM construction

PRM-RL modifies probabilistic roadmap construction by using RL-based point-to-point success under noisy task dynamics to determine connectivity between sampled configurations.

  • PRMs sample collision-free configurations and connect nearby nodes when a local planner finds an obstacle-free path.The resulting graph approximates the topology of the robot configuration space.
  • PRM-RL adds an edge only when an RL agent consistently completes the point-to-point task between two configurations.This replaces traditional obstacle-free local-path testing with task-aware execution under noise and dynamics.
  • Multiple state-space variations around each configuration are tested, and connectivity requires exceeding a specified success-rate threshold.The state space includes task-relevant variables beyond the configuration space.
  • Because sensor noise prevents guaranteed collision-free execution, PRM-RL later estimates a lower bound on collision probability instead.The roadmap prioritizes robust task execution rather than geometric guarantees alone.
  • PRM-RL estimates edge length from successful trajectories by averaging trial distances, including stepwise travel and remaining goal distance.This associates each accepted edge with an empirically measured trajectory cost.

C. PRM-RL Querying

PRM-RL queries a roadmap for waypoint sequences, then uses the RL agent to navigate between successive waypoints while evaluating the method across indoor environments and baselines.

  • PRM-RL Querying: A roadmap query returns waypoints, and a higher-level planner invokes the RL agent to reach each successive waypoint.The next goal is activated when the robot enters the current waypoint’s goal range.
  • PRM-RL Querying: The roadmap-building algorithm samples start and goal state variations, runs bounded RL trajectories, and accepts edges according to repeated success.Its inputs include a success threshold, attempt count, goal tolerance, maximum steps, task predicate, policy, and dynamics model.
  • PRM-RL Querying: The indoor RL agent uses a 0.5 m goal tolerance during training and execution to operate with noisy sensors and dynamics.The supplied implementation passage also reports DDPG training and detailed network and optimization settings.
  • PRM-RL Querying: The query-stage evaluation compares PRM-RL with straight-line PRMs across 100 queries, examining construction cost, trajectory quality, simulated execution, and experiments.The study omits RRTs because their one-time planning cost is considered prohibitively expensive for on-the-fly construction.

1) Roadmap construction evaluation:

Roadmap construction is evaluated at three sampling densities, comparing PRM-RL’s RL local planner with a straight-line local planner across connectivity, collision-checking cost, and query success.

  • Roadmap construction evaluation: Roadmaps use 0.1, 0.2, and 0.4 samples per meter squared, with edges accepted at an 85% success rate over 20 trials.Nearest neighbors within 10 m are attempted during construction.
  • Roadmap construction evaluation: Higher sampling density produces larger roadmaps and more successful queries across environments and local-planner methods.The evaluation also compares nodes, edges, collision checks, and success on 100 randomly generated queries.
  • Roadmap construction evaluation: RL-local-planner roadmaps contain 15% and 50% more edges than straight-line roadmaps because the RL agent can navigate corners and small obstacles.The number of nodes does not depend on the local planner, whereas edges and collision checks do.
  • Roadmap construction evaluation: The RL local planner performs approximately 10–20 times more collision checks because edge validation uses repeated trials and early termination for consistently failing edges.The straight-line planner uses a single trial to accept or reject an edge.

2) Expected trajectory characteristics:

Expected trajectory characteristics are estimated from 100 random queries on the densest roadmaps, comparing waypoint counts, lengths, durations, and success-risk estimates for RL and straight-line planners.

  • Expected trajectory characteristics: The expected success rate over multiple waypoints is 0.85^n_w, where n_w is the number of waypoints.This models edge successes as independent events and provides a lower bound on trajectory success.
  • Expected trajectory characteristics: For Building 2, the lower-bound trajectory success is 37%, while Building 3 has a 13% lower bound under the reported waypoint counts.The calculations are 0.85^6.05 and 0.85^12.65, respectively.
  • Expected trajectory characteristics: PRM-RL paths generally contain more waypoints than straight-line paths, except in Building 3, where the RL agent can execute some turns without an added waypoint.Building 3 is the largest environment and requires more turns.
  • Expected trajectory characteristics: RL-agent trajectories are longer and slower because their estimates use more realistic execution behavior.The straight-line local planner is more optimistic and assumes 100% success on planner trajectories.

3) Actual trajectory characteristics:

PRM-RL succeeds more often than the straight-line planner, especially in the largest environment, while unsuccessful queries typically fail after few waypoints.

  • The RL agent achieves a higher success rate than the straight-line planner.
  • PRM-RL has the highest overall success rate and performs best in Building 3, the largest environment.
  • Shorter successful queries use fewer waypoints than expected, whereas unsuccessful queries typically fail after only a few waypoints.
  • PRM-SL performs worst in Building 3.

4) Physical robot experiments:

Real-robot trials tested PRM-RL in a compact obstacle course and showed repeatable goal-region attainment despite sensor-noise-induced trajectory variation.

  • The physical test environment contained four obstacles distributed through an 8 m by 3 m space.
  • The single-query trajectories varied across trials because of sensor noise.The trajectories were captured with a motion-capture system, and the figure shows five colored trials.

B. Aerial Cargo Delivery

Aerial cargo-delivery evaluation compares PRM-RL with PRM-SL across long urban trajectories, emphasizing load-displacement compliance and the computational and temporal costs of robust control.

  • The city simulation spans 450 m by 700 m with 200 m height, and evaluation uses 100 depot-to-random-goal queries.The planning bounding box is 63 million times larger than the RL training environment.
  • The longest PRM-RL trajectory exceeds 1 kilometer while remaining under the required 45° load-displacement limit.Continuous PRM-RL load displacement stays consistently below that of the discrete planner.
  • PRM-RL trajectories take longer to complete because they generally contain five times more waypoints.Near the origin, PRM-RL and PRM-SL have similar durations; the difference grows with goal distance.
  • Action filtering guarantees load-displacement constraints but adds 1.7 million collision checks per local-planner step.The resulting discrete planner is computationally prohibitive for building PRMs on the fly.
  • The physical experiments used an AscTec Hummingbird carrying a 62-centimeter suspended load weighing 45 grams.The experimental environments measured 3 m by 4 m by 2 m and required load displacement below 10°.

2) Experimental results:

Physical experiments compare PRM-RL with PRM-SL under aerial load constraints and report close simulation-to-experiment agreement for PRM-RL.

  • Vehicle and load trajectories match closely between simulation and experiment, while load displacement stays under 10°.
  • A 10° discrepancy between simulation and experiments remains because of unmodelled load turbulence.The paper reports this discrepancy as consistent with earlier results.
  • PRM-SL exceeds the 10° load-displacement limit 2.5 seconds into the flight, whereas PRM-RL rejects edges exceeding the limit.
  • Across the two case studies, PRM-RL completes indoor trajectories over 210 m and aerial flights over 1 kilometer, with both tasks experimentally verified.
Loading 1710.03937v2…