This assignment is about a robot that can move around his environment and he uses informed search.
This homework assignment is to program an A* heuristic search to allow an agent to compute the shortest path from a start point to a goal point that goes around obstacles. The scenario of this problem is that the robot, of a circular shape, is located at point A and he needs to get to point C. He can move to any point that has a non negative coordinates. However, there are also a set of obstacles, so he cannot move directly from A to C, but must instead avoid the obstacles. To make the problem a little computationally simpler, we will limit the obstacles to be rectangles, circles and squares.
The robot (circle) wants to plan a path from A to C that does not cut across or touch any of the obstacles. A move from a point X can be one unit in each of the four directions: left, right, up and down. A move from one point to another must not go through or touch any obstacle.
For the A* algorithm, you will need an Open list and a Closed list. The Open list contains states that have been generated and not yet expanded. The Closed list contains states that have already been expanded. Each state contains at least the following:
• the coordinates of a point
• the g-value cost of the path from the initial state to this state
• the h-value that estimates the cost from this state to the goal
• the f-value that is the sum of these two
• Apointer to the parent state
The possible operators at each state are just the moves to any of the other states. Many of them will be illegal, because moving the robot (circle) from the current state to the other state intersects or touches an obstacle. Therefore, you will need to code a utility function that determines if a given circle intersects a given rectangle, square and circle. The heuristic function h should use the straight line distance from the current state to the goal state, which can never overestimate the true distance.
Testing
Your program should read the input data from a file. The format of the file is as follows.
1. The first line contains 3 numbers separated by spaces. These are the X and Y (integers) coordinates of the center of the robot (circle) initial state, and the raduis (float) of the circle.
2. The second line contains 2 integers separated by spaces. These are the X and Y coordinates of the center of the robot (circle) goal state.
3. The third line contains 1 (integer) number. This is the number of obstacles.
4. Each of the remaining lines gives the type and position of an obstacle. A circle obstacle is represented by a line containing character C/c two integer numbers representing the coordinates of the center, one real number representing the radius. A rectangle obstacle is represented by a line containing the character R/r, two integer numbers representing the coordinates of the upper-left corner, a real number representing the length and a real number representing height. A square obstacle is represented by a line containing the character S/s, two integer numbers representing the coordinates of the upper-left corner, and a real number representing the length.
Results
Your solution will be the minimal path from the start state to the goal state that does not intersect or touches the obstacles. You should output both the path and its cost. The path can be found by following the parent pointers backward from the goal state. For example, the program should execute as follows:
Enter input file name and path: c:\points.txt
The path from the initial to goal state is:
1,15
1,14
1,13
2,13
2,14
…
50,50
Total distance is …
ارجو الرد ع الايميل zozakash@hotmail.com
والكم كل الشكر