Movement Problems for 2-Dimensional Linkages
- 1 August 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (3) , 610-629
- https://doi.org/10.1137/0213038
Abstract
This paper is motivated by questions concerning the planning of motion in robotics. In particular, it is concerned with the motion of planar linkages from the complexity point of view. There are two main results. First, a planar linkage can be constrained to stay inside a bounded region whose boundary consists of straight lines by the addition of a polynomial number of new links. Second, the question of whether a planar linkage in some initial configuration can be moved so that a designated joint reaches a given point in the plane is PSPACE-hard.Keywords
This publication has 2 references indexed in Scilit:
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- On a General Method of describing Plane Curves of the nth degree by LinkworkProceedings of the London Mathematical Society, 1875