Communications on Pure and Applied Mathematics · 1983 · 451 citations · 3 references
EngineeringComputer ScienceRobotics EngineeringComputational GeometryMotion PlanningRoboticsCollision DetectionKinematicsObstacle AvoidanceRigid Body DynamicsRigid Body KinematicsRobot Motion PlanningCollision CheckingCollision Detection In Motion PlanningComputational KinematicsMotion Planning In Configuration SpaceRobot Collision CheckingTrajectory Planning For Collision Avoidance
Abstract We present an algorithm that solves a two‐dimensional case of the following problem which arises in robotics: Given a body B , and a region bounded by a collection of “walls”, either find a continuous motion connecting two given positions and orientations of B during which B avoids collision with the walls, or else establish that no such motion exists. The algorithm is polynomial in the number of walls ( O ( n 5 ) if n is the number of walls), but for typical wall configurations can run more efficiently. It is somewhat related to a technique outlined by Reif.
3
Complexity of the mover's problem and generalizations
John H. Reif · 1979 · 769 citations
Robot-manipulator control algorithms
M.S. Konstantinov · Mechanism and Machine Theory · 1979 · 17 citations