Hybrid Motion Planning
![[Planar Map]](../images/hybrid.gif)
Abstract
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
Proc. 5th Workshop on Algorithmic Foundations of
Robotics (WAFR), Nice,
2002, pp, 225-241.
[BibTex, gzipped PostScript]
- 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
[BibTex, gzipped PostScript]
Contact
| Shai Hirsch
|
|
|
![[Projects Page]](../images/icons/projects.gif)
![[Top]](../images/icons/top.gif)
Site is maintained by
Efi Fogel.
Last modified: June 01 2004.
