Homework4
Michael Edelson
medelson@andrew
This project was a pretty big change to my program. It forced me to re-write how I stored my world. I ended up choosing A* as my algorithm, using cardinal directions as the allowable directions for the robot to face. The robot was only allowed to move forward, or turn in place. The cost of turning (to any other direction) was ½ of moving one pixel. Keeping the robot only facing 4 directions allowed me to keep a pixel-based representation of the robot (so I could draw it in paint). The program outputs a jpeg every few (50) pixels it checks. The coloring of the jpeg is as follows: Blue is buffered wall: The more blue (brighter), the more directions the robot will hit it in (if it is facing that direction, and will hit it, the blue is 25% brighter). Red are nodes on the closed list. Green pixels are nodes on the open list The videos show the propagation of the explored nodes. Since the algorithm is essentially 4-point connectivity with a bonus for going straight, things propagate in a triangular manner.
Picture of approximate world from success video:
And the Robot used in it (it is just a vertical line)
Algorithm:
Create a start node
Put start node on open list
Loop (while the open list isn't empty)
pop head of open list
if the popped node is the goal, finish!
Find all adjacent nodes in the world
to be adjacent:
One step forward
Turned, but in same position
According to orientation, aren't in a wall
For each adjacent node:
Set backpointer of successor to be the parent node (node previously popped off open list)
Set heuristic to be 4-point connected distance
Set actual cost of the successor to be the parent node's cost + appropriate amount (1 for movement, ½ for turning)
if the node is in the open or closed list, compare actual cost
if the one in the open or closed list is of a lower cost, ignore this successor
otherwise remove it from the list and add the successor to the open list
Add parent to closed list
End loop
I chose 4-point connectivity for a heuristic because those are the paths that my robot could follow. It is forced to be shorter than moving forward and turning in place.