![]() |
The above picture shows the Trilobot Mobile Robot from Arrick Robotics, advertised to be intended for AI research and education, so I chose him to represent this assignment. He can move around his environment and pick up things, and he uses informed search, as opposed to a blind search.
This homework assignment is to program an A* heuristic search (graph 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 agent is located at point A and he needs to get to point C. He can move to any of a finite set of points in his environment. However, there are also a set of obstacles, so he cannot move directly from A to C, but must instead avoid the obstacles. The points in the space have real coordinates (x,y) and are just the vertices of the obstacles. To make the problem a little computationally simpler, we will limit the obstacles to be rectangles.
The agent wants to plan a path from A to C that does not cut across any of the obstacles. A move must be from some vertex I to another vertex J (the robot will never be at a point other than a vertex, unless it is moving from one vertext to another). I and J may be on the same rectangle or on two different ones. He is allowed to move along an edge of an obstacle, just not through it.
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 possible operators at each state are just the moves to any of the
other states. Many of them will be illegal, because the line from the
current state to the other state intersects a rectangle. Therefore,
you will need to code a utility function that determines if a
given line segment intersects a given rectangle. The heuristic function h should use the
straight line distance from the current vertex to the goal vertex, which can never
overestimate the true distance.
Point     Cumulative Cost
(0,0)       0.0
(4,0)       4.000
(9,6)       11.810
Turn In: here
LATE POLICY: Programs may be turned in until Tuesday night, January 29 at 11:59pm. 10% off for each day late.
CHEATING POLICY: All work on this assignment must be your own. You may discuss the assignment with other members of the class, but your code should not look like anyone else's code in this class or prior classes or on the web. Having the same code with different names for the variables doesn't work either. We check. Thanks.