Close this search box.

Planning Near Optimal Corridors


Planning Near Optimal Corridors
Using Corridors for Motion Planning

The motion-planning problem, involving the computation of a collision-free path for a moving entity amidst obstacles, is a central problem in fields like Robotics and Game Design. In this project we study the problem of planning high-quality paths.

A high-quality path should have some desirable properties: it should be short, avoiding long detours—and at the same time it should stay at a safe distance from the obstacles, namely it should have clearance.

We suggest a quality measure for paths, which balances between the above criteria of minimizing the path length while maximizing its clearance. We analyze the properties of optimal paths according to our measure, and devise an approximation algorithm to compute near-optimal paths amidst polygonal obstacles in the plane.

We also apply our quality measure to corridors. Instead of planning a one-dimensional motion path for moving entity, it is often more convenient to let the entity move in a corridor, where the exact motion path is determined by a local planner. We show that planning an optimal corridor is equivalent to planning an optimal path with bounded clearance.


Example of a BoundedVoronoi Diagram
Example of a Bounded Voronoi Diagram

Polygonal Obstacles
Polygonal Obstacles

Example of a BoundedVoronoi Diagram for Polygons
Example of a Bounded Voronoi Diagram for Polygons


  • Ron Wein, Jur van den Berg, and Dan Halperin
    Planning High-Quality Paths and Corridors amidst Obstacles
    International Journal on Robotics Research, Selected Contributions of the 7th International Workshop on the Algorithmic Foundations of Robotics (WAFR),  27: 1213-1231, 2008 [link] [bibtex]
  • Ron Wein, Jur van den Berg, and Dan Halperin
    Planning High-Quality Paths and Corridors Amidst Obstacles
    Algorithmic Foundations of Robotics VII, pages 491-506, 2008 [link] [bibtex]
  • Ron Wein‘s presentation
    Planning Near-Optimal Corridors Amidst Obstacles
    Presented at the ACS meeting, Athens, May 2006 [ppt]
  • Ron Wein
    The Integration of Exact Arrangements with Effective Motion Planning
    Ph.D. Thesis, Tel Aviv University, March 2007 [pdf] [bibtex]
  • Jur van den Berg
    Path Planning in Dynamic Environments
    Ph.D. Thesis, Utrecht University, The Netherlands, 2007


Ron Wein
Dan Halperin

Yair Oz - Webcreator


Skip to content