Overview

Sampling-based motion planners are highly effective at solving complex planning problems, but they can struggle in particularly difficult scenarios — such as environments with narrow passages — where the search space is vast and unguided exploration is inefficient. Humans, on the other hand, can often intuitively identify these challenging regions and approximate reasonable solutions, but lack the speed and precision required to execute low-level planning tasks like collision checking.

Collaborative planning bridges this gap by combining the complementary strengths of human intuition and automated planning. Users provide high-level spatial guidance to direct the planner’s search, while the planner handles the computationally intensive low-level work. This cooperation allows the system to overcome challenges that either the human or planner would struggle with alone.

Region Steering

Region Steering (Denny et al., 2014) introduces a cooperative strategy in which a human user and a Probabilistic Roadmap Method (PRM) planner jointly build a roadmap of the planning space.

The key mechanism is two-way communication between the user and the planner:

  • User → Planner: The user defines regions — bounding volumes in the workspace — to bias sampling toward or away from specific areas. This lets the user focus the planner’s attention on challenging regions (e.g., narrow passages) that would otherwise be undersampled.
  • Planner → User: The planner continuously displays its roadmap progress and colors each region based on its perceived usefulness, giving the user feedback to refine their guidance.

This interaction preserves the probabilistic completeness of the underlying PRM planner, ensuring theoretical guarantees are maintained even with human input.

Region Steering

Results: Compared to fully automated approaches like Gaussian PRM, Region Steering demonstrates:

  • Reduced roadmap construction time
  • Smaller roadmap sizes
  • Greater customizability of the resulting roadmap

General Region-Based Framework

Building on Region Steering, Denny et al. (2018) introduce a generalized region-based framework applicable to any sampling-based planning approach, not just PRM-style roadmap construction.

The framework is explored in three variants:

  • Graph-based: Applied to roadmap planners (e.g., PRM)
  • Tree-based: Applied to tree planners (e.g., RRT)
  • Hybrid: Applied to methods combining both roadmap and tree structures

By abstracting the region-weighting mechanism from any specific planner, this framework enables human guidance to benefit a broad class of sampling-based motion planners. Experimental results confirm reduced planning time across multiple difficult scenarios, validating the generality of the approach.

Publications

Updated: