A New Dimension towards the Determination of Shortest Path for Robots using Convex Polygons
| Autor: | Ushaa Eswaran, T. C. Manjunath |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Mathematical optimization
Computer science Fast path Collision Any-angle path planning Longest path problem Vertex (geometry) Computer Science::Robotics Widest path problem Euclidean shortest path Obstacle avoidance Shortest path problem Search problem K shortest path routing Motion planning Heuristics Yen's algorithm Constrained Shortest Path First |
| Zdroj: | International Journal of Computer Applications. 25:14-20 |
| ISSN: | 0975-8887 |
| DOI: | 10.5120/2997-4027 |
| Popis: | paper, a optimal path planning algorithm using motion heuristics coupled with search problem is designed for a robot in a workspace full of obstacles which are polyhedral and consisting of different types of objects. Both in the simulation as well as in the real time is considered herewith. A new method of finding an obstacle collision free path from the source to the goal when the workspace is cluttered with obstacles is also developed using motion heuristics using an user friendly GUI developed in C++. The method presented is similar to the method of finding / searching a path by the humans when he / she is moving in a vehicle from the source to the destination. The method was also implemented on a real time system, say a robot and was successful. Artificial Intelligence which uses motion heuristics (search methods) is used to find the obstacle collision free path. Also, the shortest path from the source to the destination is also determined by making use of various types of sensing techniques. Here, we have presented the chain coding method of obtaining the shortest path form source to goal. Also, the mathematical development & the graphical design of the path is also incorporated in the research work undertaken in this paper & three equations are formulated. The parameters are taken into consideration while designing the path in between the obstacles are the vertices & edges of the different types of obstacles that occur in the path of motion when the robot is traversing from the source to the goal. Three types of interactions are considered while designing the path, viz., interaction between vertex of one obstacle & the other, interaction between edge of one obstacle & the other, interaction between an edge of one obstacle & the vertex of another obstacle. The main advantages of the designed path are it generates paths for the mobile part that stays well away from the obstacles ; since, the path is equidistant or midway between the obstacles and avoids collision with the obstacles, this method of planning the path using gross motion technique is, it is quite effective especially when the workspace of the robot is sparsely populated with obstacles, the path obtained is the shortest path, the path is a obstacle collision free path, the path is equidistant from the obstacles and there is no chance of collisions. To conclude, we design a novel method of searching a obstacle collision free path ( motion ) from the source to the goal in the free work space of the robot by using search technique in Artificial Intelligence using simulation in C++ & in Matlab. The work done in this paper is the simulation of the algorithm developed in (1). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|