Shiny Doom Forum

[rklee]

Hey for those of you who are interested in Programming and Robotics (Max???) would be greatly interested to see your solutions/ideas to my robotics labs... Or perhaps for your own pleasure.
http://www.andrew.cmu.edu/course/16-362-862/
lab notes are down at bottom.

For this most recent lab...
Problem - The robot should generate the optimal conditional plan to reach a goal given a maze (without moving) and given several possible starting locations (your exact position is unknown) then move to the goal following that plan. (Robot has sonar sensors... in previous lab we've already done all the movement commands and allignment so it can exactly move one cell at a time and reallign it self each time. The robot also can match sonar data to walls... so it can figure out what walls are around it)
Example of conditional plan (move forward, if there is a wall to right, turn left, move forward, otherwise turn right move forward.)

My Solution -
We look at all possible movements from all the possible starting locations and orientations. (F L R FF FL FR FFF FFL FFR FLF FLL FLR FRF FRL FRR ..etc)
also some can be eliminated FRR is same as FRL... etc) (F = move forward, R = turn right, L = turn left)
We figure out how many possible locations can be eliminated. Example, given the following map:

Circles are robots, lines are walls, goal can be anyone, the line on the robot determines the direction it is Facing.

We know that even without moving we can isolate 4. meaning we can say
*IF (what do I see = only rear wall) (we're at location 4 plan a path to goal using breadth first search and execute)
*ELSE
We look at F, IF we move front... can we isolate another robot? We can isolate robot 1
*Move forward
*IF(What do I see = NO WALLS)
* we are at location 1 + move forward, plan breadth first search from that location to goal and execute.
WE then can ignore L and R since they without moving forward we get no new information
We look at FF
This will isolate the last two.
*ELSE
*Move Forward
* IF (What do I see = Front Wall and Right Wall)
* we are at Location 2 + Front Front generate breadth first search from here to goal and execute
* else
* we are at location 3 + Front Front generate breadth first search from here to goal and execute.
DONE

So even without moving we can generate the conditional plan (the lines with the *s). Also the generation of the breadth first search can be done before any movement since we know the conditional plan and know what movements are required.

This is very similar to lab 4.2 whose solution was to moves in a random fasion and looks at the walls around it to eliminate possible starting locations in order to find where we are in the maze. Except this will find the optimal path to traverse to figure out where we are. Basically we are doing a breadth first search to find the optimal path to figure out where we are, then using breadth first search to find the optimal path from where we are to the goal. And we can do all this planning BEFORE we even have to move!!! Cool eh???

Issues I have - if a movement eliminates 2 robot locations this needs to be ketp in mind. Since those two only need to be isolated from each other afterwards and NOT need to be isolated further from all the other possible starting locations. This could get hairy I think interms of ease of programming

Anyone else have any ideas?
_________________
"My Heart Is In the Work" - Andrew Carnegie

[rklee]

no one is interested


fine


just lookie this video then

http://www.shinydoom.com/rklee/webpictures/110304/wavefront3mb.wmv
_________________
"My Heart Is In the Work" - Andrew Carnegie