Contents

• Motivation
• Example: Some-Sample-Task
• Past Work
• Methodology (etc.)
• Sample Input-Output
• On-Line Links
• Bibliography

Motivation

MOTIVATION

The moral of this story is that no matter how much fun it is to concentrate on where you are, having a map of where you can and cannot go will allow you to plan ahead and avoid areas that could get you in all sorts of trouble.
 

Sample task

1)Spatial planning problems. Spatial planning problems are caused by the physical constraint that solids cannot overlap, which places limits on where objects can go relative to each other. A familiar example would be the task of finding the space in a packed car boot for one more suitcase (Lozano-Pérez , whilst the classic example (from which the problem genre has taken its popular name, Schwartz and Sharir;is the Piano Mover's problem of getting a solid object from one place to another without damaging anything in the process.

<courtsey:www.stanford.edu>

2) Gross motion planning, where the task is to efficiently navigate a robot from an initial position to some goal, avoiding any obstacles on the way. There are a number of different types of robot, the main two types being mobile robots (such as the increasingly popular Automated Guided Vehicle) and manipulators (the main four types of which are shown in Figure , reprinted from Groover and Zimmers .

Figure 1.1: The four most common configurations of industrial manipulator: (a) polar coordinate; (b) cylindrical coordinate; (c) jointed arm configuration; (d) cartesian coordinate.
<courtsey:www.stanford.edu>

<courtsey:www.rotex.com>

Past Work

  2)[Gouznes et al :1985]He in this paper he introduced a method called as interval geometry by him.A C-space is divided in equal number of cells and then checked whether prohibited, safe or mixed.A mixed cell is further subdivided untill minimum cell size is reached.We are using the algorithm for polygonal approximation of C-space.
3)[Amato , Bayazit & Dale et al :1998] They in their paper discussed the randomized path planning approach including the visibility search method.Using these method we can construct a graph of representative path in C-space.This paper discuss node generation and connection stratiegies in a cluttered 3-D workspace.We in our work are usig a TWO-D workspace. But the method of creating node and graph search is almost on similar lines.
 4)[Latombe]The book by Latombe on robot motion planning proved to be very beneficial .He has provided algorithm for C-space generation ,search method that we have used in our project.

  4)some other paper are Related paper: L. Kavraki and J.-C. Latombe,1 Randomized Preprocessing of Configuration Space for Fast Path Planning, in the Proceedings of the International Conference on Robotics and Automation, San Diego, CA, 2138-2139, 1994. Also : L. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars,2 Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces, which appeared in the IEEE Transactions on Robotics and Automation.
 
 
 

AIM OF PROJECT

Given start and end position and obstacle position problem is to find a path

<courtsey:paper by latombe>
METHODOLOGY

Methodology is divided into three steps
 
 

1)Entering of obstacle position and charecteristics of manipulator i.e manipulator length with respect to its hinge
 
 

2)GENERATION OF C-SPACE

<courtsey:paper by Latombe>

We are using analytic method to generate C-space

The steps involved are as

1)Take obstacle one by one.Traverse manipulator along every edge and verticesone by one.

2)generate parameteric equation for theta1 and theta2.The equation are as:

a)Translation along an edge with co-ordinate(X1,Y1)and (X2,Y2)

                            L1*cos(theta1)+L2*cos(theta1+theta2)=X1+a(X1-X2).....(1)

                            L1*sin(theta1)+L2*sin(theta1+theta2)=Y1+a(Y1-Y2).....(2)

where,L1=length of first manipulator link

          L2=length of second manipulator link

            a=parameter whose value lies between [0,1]

solving these two equation we get theta1 and theta2 as function of parameter a
 
 

b)Translation along a vertex with co-ordinate(X,Y) by manipulator link with co-ordinate (X1,Y1) and (X2,Y2)

Here (X1,Y1) and (X2,Y2) are function of theta1 and theta2 obtained by using rotation matrix for rotation theta1+theta2 plus translation by length of first manipulator link length
 

X=X1+a(X1-X2).....(1)

Y=Y1+a(Y1-Y2).....(2)

where,L1=length of first manipulator link

             L2=length of second manipulator link
 

3)plot the generated point using openGl

here we generate obstacle C-space
 
 

3)POLYGONAL APPROXIMATION OF GENERATED C-SPACE

We are using recursive division for polygonal approximation of generated C-space

Uniform recursive subdivision

The C-space is divided into equal parts, and each resulting C-space cell is examined and classified as prohibited, safe, or mixed. Prohibited and safe cells are left, whilst mixed cells are divided again. This procedure is repeated until a pre-defined minimum cell size is reached, at which point that cell is classified as either prohibited (a conservative estimate) or as contact. The result of this recursive subdivision is a hierarchical tree, against which a configuration-point can be tested very quickly, and through which paths can be planned using visibility search algorithms.
 

4)PATH PLANNING:Generating path from start and goal position using visibility search method


<courtsey:paper by Latombe>

Algorithm is as follows
1)Construct visibility graph ,G.
2)Search G for a path from initial position to final.
3)If path found return it or indicate failure.
4)Use A* alogorithm.

Sample Input and Expected Output

                      2)specifcation of environment in terms of convex polygon as obstacle position and their coordinates specification with respect to global frame.

                     3)Start and goal position
 This has been stored in data file "manip" and "obs".The last line of file"manip" gives "START" and "GOAL" position.

DATA FILE FORMAT

1)manip
 

LINE 1 to LINE M: From this line give the coordinates (x,y) of the vertices of the FIRST polygon in counter-clockwise order assuming that it is pivoted about the origin(0,0). Keep giving each vertex on each seperate line. To mark that the last vertex has been given ,put a * after the last entry. Let's say there are "M" vertices.

LINE M+1 : Give the coordinates(x,y) of the pivot, that is the coords of the point on link1_polygon about which the link2_polygon is pivoted. Give these in the reference frame of polygon1; hence the y-component has to be zero.

LINE M + 2 : From this line give the coordinates (x,y) of the vertices of the SECOND polygon in counter-clockwise order assuming that it is pivoted about the origin(0,0). Keep giving each vertex on each seperate line. To mark that the last vertex has been given ,put a * after the last entry.

LINE 2M +1:Coordinates of start position

LINE 2M+2 :Coordinates of GOAL position.

-1 -1

-1 1
6 1
6 -1*
5 0 Pivot point for link 2

-0.5 -1
-0.5 1
4 1
4 -1 *
5.7 0
9 10
2)obs

LINE 1:Give The number of obstacle
LINE 2:give number of edges of first obstacle,say N
LINE 3 to LINE N:Give coordinates of obstacle in anticlockwise order.
1
4
2 0
2 3
5 9
6 1
 OUTPUT FILE:The output is a continuous collision free path(in C-space)that bring the robot from initial configuaration to final while avoiding the collision.

1)C-space generation

OBSTACLE 1
-6 -6
-6 -7
-5 -7
-5 -6  :

OBSTACLE 2
5 5
5 7
7 7
7 5
~

OBSTACLE 3
-5 5
-5 7
-7 7
-7 5
 
 

OBSTACLE 4
-6 -4
-5.5 5
-4 6
~

2)Path planned
The path planned  for different case are as
1)CASE1

2)CASE 2

3)CASE 3

 

• This is a paper by Browes that consist of adaptive grid division
• This site has lot of refrence material available . here .

Annotated Bibliography

annote ={

 Recently, a new class of randomized path planning methods, known as Probabilistic Roadmap Methods (PRMs) have shown great potential for solving complicated high-dimensional problems. PRMs use randomization (usually during preprocessing) to construct a graph of representative paths in C-space (a roadmap) whose vertices correspond to collision-free configurations of the robot and in which two vertices are connected by an edge if a path between the two corresponding configurations can be found by a local planning method.

This work describes and evaluates various node generation and connection strategies for one such PRM, the obstacle-based probabilistic roadmap method (OBPRM), in cluttered 3-dimensional Workspaces. Various node generation strategies are evaluated in terms of their ability to produce nodes in difficult regions of C-space; our results include recommendations for selecting appropriate node generation strategies for different types of objects, and a default strategy for use when objects cannot be classified easily. We also propose and analyze a multi-stage strategy for connecting the roadmap nodes; the use of different local planners at different stages is shown to enhance the connectivity of the resulting roadmap significantly.

}}
InProceedings{Kant/Zucker:1988,
  author =      {Kant K and Zucker S. },
  title =       { IEEE Transaction on robotics and automation},
  booktitle =   {IEEE'88},
  year =        { 1988 },
  keywords =    {V.graphs}, },
  month =       {  January},
  pages =       { 155-168 },

annote={

 The method proposed here involves collision avoidance of rectangles based upon the search of a VGRAPH. This method also suggests the use of a Low Level controller Collision Avoidance Module. This controller would use low level information about the environment to behave as if experiencing forces from workspace obstacles. The manipulator would be experiencing a pull to the goal state. This method produces a Kinematic and Dynamic, Time Optimal path. None of the implementation details were given in the paper.}}

some other bibliography in postscript format
 
 

1)Randomised Preprocessing of configuaration space for fast path planning,Latombe
 
 

click

 2)Assembly sequence , by Goldwasser and Motwani

click

 [ COURSE WEB PAGE ] [ COURSE PROJECTS 2000 (local CC users) ]