Consider an idealization of a problem where a robot has to navigate its way arou

Question

Consider an idealization of a problem where a robot has to navigate its way around obstacles. The goal is to find the shortest distance between two points on a plane that has convex polygonal obstacles. The shortest path from one polygon vertex to any other in the scene consists of straight-line segments joining some of the vertices of the polygon. (Note that the start and the end goal points may be considered polygons of size 0).

Polygon 1: ((220, 616), (220, 666), (251, 670), (272, 647))

Polygon 2: ((341, 655), (359, 667), (374, 651), (366, 577))

Polygon 3: ((311, 530), (311, 559), (339, 578), (361, 560), (361, 528), (336, 516))

Polygon 4: ((105, 628), (151, 670), (180, 629), (156, 577), (113, 587))

Polygon 5: ((118, 517), (245, 517), (245, 577), (118, 557))

Polygon 6: ((280, 583), (333, 583), (333, 665), (280, 665))

Polygon 7: ((252, 594), (290, 562), (264, 538))

Polygon 8: ((198, 635), (217, 574), (182, 574))

Question: Implement an algorithm to find the shortest path from the start node to the end node using an A* (A-star) heuristic search. Use the straight-line distance to the end node as a heuristic function. Show your pseudo code for this algorithm.

Hint: Define the necessary functions to implement the search problem. This should include a function that takes a vertex as input and returns the set of vertices that can be reached in a straight line from the given vertex. You may need to implement a function that detects whether or not two line segments intersect. The problem can be solved using shortest path algorithms but you are required to use A*.  

Explanation / Answer

ANS:

CODE IS BELOW

Hello,

Yes, We can solve this problem in breadth first search, but the thing here is breadth first search algorithm will result into the worst case possible. This can be reduced by using A* Algorithm. Since the question is only in breadth first search, I'll answer according to it. In breadth first search (BFS) evey neighbour node is visited from the root node. and next the neighbour node of first visited node is examined. This process continues till all the vertex are examined. On considering this we could assume that the robot visits the grid accordingly so that it will not collide with any obstacles. we can code up the algorithm. Below is the C code you could use to solve this problem.

//Code for the above problem:

#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;

class robot
{
public :
int x;
int y;
};
int main()
{
int block[8][8] = {
    {1,1,1,1,1,1,1,1},
    {1,0,0,0,1,1,1,1},
    {1,1,0,0,1,1,1,1},
    {1,1,0,0,1,1,1,1},
    {1,1,1,2,0,1,0,0},
    {1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1}
};
int rw = 8;
int cl = 8;
int dis[rw][cl];
for(int u = 0;u<rw;u++)
{
    for(int v =0;v<cl;v++)
    {
        dis[u][v] = -1;
    }
}
queue<robot> iterator;
robot r;
r.x = 0;
r.y = 0;
dis[0][0] = 0;
iterator.push(r);

while(!iterator.empty())
{
    r = iterator.front();
    iterator.pop();
    for(int p = -1;p<2;p++)
    {
        for(int q = -1;q<2;q++)
        {
            if(p == q)continue;
            int i = r.x + p;
            int j = r.y + q;
            if(i<0)i=0;
            if(j<0)j=0;
            if(i>rw-1)i=rw-1;
            if(j>cl-1)j=cl-1;

            if(i== r.x && j == r.y)
            continue;
            if(dis[i][j] == -1)
            {
                if(block[i][j] != 0)
                {
                dis[i][j] = dis[r.x][r.y] + 1;
                robot rn;
                rn.x = i;
                rn.y = j;
                iterator.push(rn);
                }
            }

        }
    }
}

for(int x = 0;x<rw;x++)
{
    for(int y =0;y<cl;y++)
    {
        printf("%d ",dis[x][y]);
    }
    printf(" ");
}
return 0;
}

Hope I have solved your problem :)

THANK YOU

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects