Applications of Computational geometry Algorithms in Robotics

 Hello Friends,In this Post we will understand The applications of Computational Geometry in Robotics.

The field of robotics studies the design and use of robots. As robots  are geometric objects that operate in a 3-dimensional space the real world it is obvious that geometric problems arise at many places.

Most industrial robots are robot arms with a fixed base. The parts operated on by the robot arm have to be supplied in such a way that the robot can easily grasp them. Some of the parts may have to be immobilized so that the robot can work on them. They may also have to be turned to a known orientation before the robot can work on them. These are all geometric problems.

we would like to give a robot high-level tasks “vacuum the room" and let the robot findout the best way to execute the task. This involves planning motions. Motion Planning involves computational geometry algorithms.

Shortest Paths for a Point Robot: (Source: Computational Geometry algorithms,Springer)

Fig 1
Let us Consider above as the space in which our point Robot is going Navigate.We have Drawn a Roadmap For robot in the space available for the navigation between the obstacles which are shown as polygons.

Fig 2

Suppose We want to find the Shortest path between Pstart and Pgoal we need to find the shortest find in the roadmap.
But as shown in Fig 2. our shortest path in road map is not matching with the real shortest path.

For the solution of above problem we have a rule which states that-
Any shortest path between pstart and pgoal among a set S of disjoint polygonal obstacles is a polygonal path whose inner vertices are vertices of S. 




Fig 3


Algorithm SHORTESTPATH(S, pstart, pgoal):

 Input : A set S of disjoint polygonal obstacles, and two points pstart and pgoal in the free space. 

Output. The shortest collision-free path connecting pstart and pgoal. 

Step 1. Draw the Visibility Graph for the space(as Shown in above in Fig 3.

Step 2. Assign each arc (v,w) in Visibilty graph a weight, which is the Euclidean length of the segment vw. 

Step 3. Use Dijkstra’s algorithm to compute a shortest path between pstart and pgoal in Visibility Graph.

In this way there are many computational Geometry Algorithms which are usefull in the field of Robotics.


Comments

Post a Comment

Popular posts from this blog

Applications of Computational Geometry in Geographic Information Systems(GIS)

  Before we discuss the Applications of Computational Geometry in GIS we first need to know what GIS is,don't we?So GIS basically stores information like shape of country,the rainfall a given region receives,heights of mountains in the region,population count,cities etc.With GIS we can extract information about the given region of interest.For example,a seismologist may analyze the region to determine whether the region is prone to earthquake activities.Since GIS mainly deals with planar surfaces and manmade structures like buildings,several geometric problems arise.Since the geographic dataset is so large,we have to come with effective and faster algorithms to solve problems. GIS works well with combination of  data.Lets say we have a map of region which consists of a 'network' of rivers,cities,railroads.What GIS does is it splits the map into 'layers' such that each layer contains only one type of information.In the above context,we will have separate layers cons...
Read more

Important Fields in Computational Geometry and their Significance

 The field of Computational geometry emerged in order to tackle the challenges posed by geometric problems.Important applications of Computational Geometric algorithms includes robotics(motion planning and visibility problems)geographic information systems(geometrical location and search,route planning),integrated circuit design(IC geometry design and verification),computer-aided engineering(CAE) and computer vision.(3D reconstruction). The two main branches of Computational Geometry are Computational computational geometry and numerical computational geometry. Computational computational geometry:-The work carried out in this field mainly consists of developing efficient algorithms and data structures for solving problems related to general geometric objects and concepts like polygon,lines points etc.Developing asymptotically faster algorithms when the dateset consists of millions of sample points is one of the important goals of researchers in this field. Numerical Computational ...
Read more