Search
Close this search box.

Hybrid Motion Planning

Abstract

Hybrid Motion Planning

The basic motion-planning problem is to plan a collision-free motion for objects moving among obstacles between free initial and goal positions, or to determine that no such motion exists. The basic problem as well as numerous variants of it have been intensively studied over the past two decades yielding a wealth of results and techniques, both theoretical and practical. In this paper, we propose a novel approach to motion planning, namely hybrid motion planning, in which we integrate complete solutions along with Probabilistic Roadmap (PRM) techniques in order to combine their strengths and offset their weaknesses. We incorporate robust tools, that have not been available before, in order to implement the complete solutions. We exemplify our approach in the case of two discs moving among polygonal obstacles in the plane. The planner we present easily solves problems where a narrow passage in the workspace can be arbitrarily small. Our planner is also capable of providing correct nontrivial “no” answers, namely it can, for some queries, detect the situation where no solution exists. We envision our planner not as a total solution but rather as a new tool that cooperates with existing planners. We demonstrate the advantages and shortcomings of our planner with experimental results.

Links

  • Shai Hirsch and Dan Halperin
    Hybrid Motion Planning: Coordinating Two Discs Moving Among Polygonal Obstacles in the Plane
    Algorithmic Foundations of Robotics V, Volume 7 of STAR, pages 225–241, Nice, 2002 [link][bibtex]
  • Shai Hirsch and Eran Leiserowitz
    Exact Construction of Minkowski Sums of Polygons and a Disc with Application to Motion Planning
    Tel Aviv University Technical Report ECG-TR-181205-0, 2002 [gzipped ps][bibtex]

Contacts

Shai Hirsch
@techreport{hl-ecmsp-02,
  author = {Shai Hirsch and Eran Leiserowitz},
  title = {Exact Construction of Minkowski Sums of Polygons and a Disc with Application to Motion Planning},
  institution =  {Tel Aviv University},
  type = {ECG-TR},
  number = {181205-0},
  year = {2002}
}
@incollection{hh-hmpct-02,
  author = {Shai Hirsch and Dan Halperin},
  editor = {Jean-Daniel Boissonnat and Joel Burdick and Ken Goldberg and Seth Hutchinson},
  title = {Hybrid Motion Planning: Coordinating Two Discs Moving among Polygonal Obstacles in the Plane},
  bookTitle = {Algorithmic Foundations of Robotics V},
  series = {Springer Tracts in Advanced Robotics ({STAR})},
  volume = {7},
  year = {2004},
  publisher = {Springer},
  pages = {239--255},
  doi = {10.1007/978-3-540-45058-0_15}
}

Yair Oz - Webcreator

Contact

Skip to content