Artificial Intelligence ME 768 Jan-Apr 2000

 
TWO- DOF MANIPULATOR C-SPACE BASED PATH PLANNING


 

kumar sarvesh

 amit tandon

IIT Kanpur : February 2000


Contents


Motivation

MOTIVATION

Late in the 18th century English aristocrat George Beecham, known for his sense of adventure and fearless dispostion, set off from Southampton on a voyage to the recently colonized continent of Africa, taking only three shirts, a big hat, and some smalls. He shirked off suggestions that he should take a map, declaring that as bold a man as he could deal with anything that he could come across and besides, he continued, so much more could be achieved in life if you concentrated on where you were, rather than where you were going. Less than a week into his trek across the unknown continent, however, he came across a tribe of natives who, despite his considerable protest and physical resistance, boiled him in a big pot and ate him.

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 .

figure45
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

1)[Tomas & Lozanno et al :1983]They formalised the configuaration space approach to spatial planning.Their method was based on method of creating and using map of constraints imposed by geometry In their paper they introduced the method of C-space creation by translating the rigid body around fixed obstacle.They tried to find mapped representation of "Free Space" and then finding free paths using free path algorithm .Our approach is based on this paper But we are generating C-space for a TWO-DOF manipulator not a rigid body with only one DOF as discussed in paper

  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

  An approach to representing the CS-obs is to divide the C-space into cells, then to examine those cells of configurations to see if they are all prohibited, all safe, or a mixture of both, and to label them appropriately. The division of the C-space can take a number of form

Sample Input and Expected Output

INPUT FILE:1)The input consists of specifying the GEOMETRY of arms the vertices of two polygonal arm with respect to their pivots.

                      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

 

  • On-Line Links

  • Annotated Bibliography

    InProceedings{Amato/Bayazit/Dale:1998,
      author =      { Amato,N.M and Bayazit,O.B and L.K Dale},
      title =       {Airthmetic foundati on of robotics },
      booktitle =   {WAFR'98},
      year =        { 1998 },
      keywords =    {OBPRM}, },
      institution = {Texas A&M University,},
      month =       {  August },
      pages =       { 155-168  },

    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


    This proposal was prepared by Sarvesh and Amit as a part of the project component in the Course on Artificial Intelligence in Engineering in the JAN semester of 20YY . (Instructor : Amitabha Mukerjee )

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