The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.14 Motion Planning

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A polygonal-shaped robot s in a given starting position in a room containing polygonal obstacles, with a desired ending position t.

Problem: Find the shortest path in the room taking s to t without going through any of the obstacles.

Excerpt from The Algorithm Design Manual: The difficulty of motion planning will be obvious to anyone who has ever had to move a large piece of furniture into a small apartment. The problem of motion planning also arises in systems for molecular docking. Many drugs are small molecules that act by binding to a given target model. The problem of identifying which binding sites are accessible to a candidate drug is clearly an instance of motion planning. Plotting paths for mobile robots is another canonical motion-planning application.

Motion planning also provides a tool for computer animation. Given a set of object models that appear in two different scenes s1$ and s2, a motion planning algorithm can construct a short sequence of intermediate motions to transform s1 to s2. These motions can serve to fill in the intermediate scenes between s1 and s2, with such scene interpolation greatly reducing the amount of work the animator has to do.

Implementations

  • MPK - Motion Planning Kit (C++) (rating 9)
  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 7)
  • RAPID - Robust and Accurate Polygon Interface detection (Binary) (rating 7)
  • SOLID- a library for interface detection (C++) (rating 6)
  • V-COLLIDE- The Collision detection library (Binary) (rating 5)
  • 3D Convex Hull algorithm in Java (C) (rating 3)

    • Recommended Books

    Davenport-Schinzel sequences and their geometric applications by M. Sharir and P. Agarwal Computational Geometry in C by Joseph O'Rourke Robot Motion Planning by J.-C. Latombe
    Planning, geometry, and complexity of robot motion by J. Hopcroft and J. Schwartz and M. Sharir The complexity of robot motion planning by J. Canny

    Related Links

  • UNC's Collision Detection/Proximity Query Packages

    Related Problems
    Intersection Detection
    Minkowski Sum
    Shortest Path


    This page last modified on 2008-07-10 .
    www.algorist.com