Browse Prior Art Database

ON THE PIANO MOVERS' PROBLEM IV. VARIOUS DECOMPOSABLE TWO-DIMENSIONAL MOTION PLANNING PROBLEMS

IP.com Disclosure Number: IPCOM000128219D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 19 page(s) / 48K

Publishing Venue

Software Patent Institute

Related People

Micha Sharir: AUTHOR [+4]

Abstract

Various special motion planning problems involving arbitrarily many degrees of freedom are shown to admit relatively simple solutions by techniques based on the connectivity graph approach described by Schwartz and Sharir. The solutions exploit the particularly simple configuration space structure of the robot systems considered. A typical problem is that of planning motions for a 2-D robot system consisting of several arms all jointed at one common endpoint and free to rotate past each other. The algorithm given for solving this problem runs in time 0(nk-+*4), where k is the number of arms. (*) This work has been supported in part by ONR Grant N00014-82-K-0381, by a Grant from the U.S.-Israeli Binational Science Foundation, and by a Grant from the Bat-Sheva Fund.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE PIANO MOVERS' PROBLEM IV. VARIOUS DECOMPOSABLE TWO-DIMENSIONAL MOTION PLANNING PROBLEMS

by

Micha Sharir* and Elka Ariel-Sheffi*

Technical Report No. 58 Robotics Report No. 6

February, 1983 *Department of Mathematical Sciences, University of Tel Aviv, and Computer Science Department, Courant Institute of Mathematical Sciences, New York University.

This work has been supported in part by ONR Grant N00014-82-K-0381, by a grant from the U.S.-Israeli Binational Science Foundation, and by a grant from the Bat-Sheva Fund. On the Piano Movers' Problem: IV. Various Decomposable Two-dimensional Motion Planning Problems

Micha Sharir and Elka Ariel

Department of Mathematical Sciences Tel Aviv University

and

Computer Science Department. Courant Institute of Mathematical Sciences

ABSTRACT:

Various special motion planning problems involving arbitrarily many degrees of freedom are shown to admit relatively simple solutions by techniques based on the connectivity graph approach described by Schwartz and Sharir. The solutions exploit the particularly simple configuration space structure of the robot systems considered. A typical problem is that of planning motions for a 2-D robot system consisting of several arms all jointed at one common endpoint and free to rotate past each other. The algorithm given for solving this problem runs in time 0(nk-+*4), where k is the number of arms. (*) This work has been supported in part by ONR Grant N00014-82-K-0381, by a Grant from the U.S.-Israeli Binational Science Foundation, and by a Grant from the Bat-Sheva Fund.

0. Introduction

The 'Piano Movers' problem (see [Re], [LPW]) is that of finding a continuous motion that will take a given body (which may consist of several rigid subparts jointed together) from a given initial position to a desired final position, but which is subject to certain geometric constraints during the motion. These constraints forbid the body to come in contact with certain obstacles or 'walls'. Earlier papers ((SS1], [SS2]) have described a general technique for solving such problems, which is based on decomposition of the space FP of free configurations of the robot system into connected subcells, and an analysis of adjacency relations between these cells. This approach results in the construction of a discrete connectivity graph whose nodes represent the cells in the decomposition of FP, and whose edges connect nodes corresponding

New York University Page 1 Dec 31, 1983

Page 2 of 19

ON THE PIANO MOVERS' PROBLEM IV. VARIOUS DECOMPOSABLE TWO-DIMENSIONAL MOTION PLANNING PROBLEMS

to adjacent cells. Search for a continuous motion between two specified system configurations then reduces to searching for a path in the connectivity graph connecting the two nodes corresponding to the cells containing the initial and final configurations.

FP is a k-dimensional manifold, where k is the number of degrees of freedom of the sys...