Yes... keep discussing. Do my work for me!
Maze Solving Robot (AKA Sushi shows off at work)
Started by SushiKitten, Feb 19 2013 08:44 AM
39 replies to this topic
#22
Guest_ElatedOwl_*
Guest_ElatedOwl_*
-
- Guests
Posted 20 February 2013 - 08:27 AM
I was assuming currentPos is updated in the while(move forward) loop. I'm assuming there's a way to control either how much RPM it has or a way to track wheel rotations so you can calculate an accurate distance (assuming the wheels don't slip).Yours would not work either since it doesn't discern distance, If it traveled from (-1, 2) to (-1, -1) it would actually assume it was at (-1, 1) what I propose is a timer which times the time taken between turns.
If it started at the right and traveled to the left then headed to the end and turned left then followed the loop for 3 more turns so it is back at the start of the loop. My logic is it then starts the loop again and times the turns, it would read 1.5, 1, 1.5, 1 since parallel lines on a rectangle have the same distance it would now have the information to know that it has traveled the entire rectangle since all parallel sides were equal It could then go to the turn stored after the loop and know where to leave.
I haven't done coding in about 7 years so forgive this...
If turn left.counter = 4 then
turn left(starttimerloop)
Else delete left.counter
Starttimerloop
get time.a
turn left
get time.b
turn left
get time.c
turn left
get time.d
If Time.a = Time.c and Time.b = Time.d then
travel a + b
Turn right or straight until time.e =/= time.a or time.b................. et cetera
As I said before, sorry about my lack of syntax for this. I can't see any logic errors though and this code assumes there is a certain logic in the robots methodology for figuring out the maze, which it can return to one a loop has been flagged it also assumes a geometric world of 90 degree angles. Once a loop is flagged it can delete the information from the loop and just remember the second L turn.
From what Sushi said I gather it just has a 1D array simply stating L, R, S, S, L ,R for its solved path when it finds a dead end it inverses the last turns made until it reaches another branch and deletes that information. My method uses its old framework but just adds a timer after storing a L, L, L, L or R, R, R, R so it becomes L(1.5), L(1), L(1.5), L(1).
Edit (Add) After watching the video it confirmed my theory that it "keeps its right hand on the wall" as its method for solving the maze, that is it prioritizes R over L until it discounts that area then it travels backwards along the incorrect path and inverts the R to L or L to R then discounts that branch and continues prioritizing R over L. Mine could be used under this existing framework assuming the robot has a timer function.
It wouldn't be entirely accurate since the robot isn't guaranteed to be dead center on the line, but you could have some kind of tolerance rounding.
Using wall following assumes that if you follow the wall every path would be traversed - use the maze I made, that will not work.
Your loop detection is also assuming that it's a 4 point rectangle - consider the path of my example maze using the right hand rule.
Start 0, 0
0, 1 - turn right
1, 1
2, 1 - turn right
2, -1
-1, -1
-1, 2 - turn right
0, 2 - turn right
0, 1
0, 0 - dead end, turn around
it'll loop from there
#23
SpleenBeGone
-
- Administrators
-
- 14,951 posts
Deer Leader of the Goriest Revolution
- LocationHouston
Posted 20 February 2013 - 09:07 AM
I'm assuming the thing has a light sensor, and that's how it follows the line. If so, a second one could easily keep up with the wheel rotation in the same way that mouse scroll wheels work.
#24
SIlhouette
-
- Members
-
- 383 posts
Megabyte
Posted 20 February 2013 - 09:32 AM
I was assuming currentPos is updated in the while(move forward) loop. I'm assuming there's a way to control either how much RPM it has or a way to track wheel rotations so you can calculate an accurate distance (assuming the wheels don't slip).
It wouldn't be entirely accurate since the robot isn't guaranteed to be dead center on the line, but you could have some kind of tolerance rounding.
Using wall following assumes that if you follow the wall every path would be traversed - use the maze I made, that will not work.
Your loop detection is also assuming that it's a 4 point rectangle - consider the path of my example maze using the right hand rule.
Start 0, 0
0, 1 - turn right
1, 1
2, 1 - turn right
2, -1
-1, -1
-1, 2 - turn right
0, 2 - turn right
0, 1
0, 0 - dead end, turn around
it'll loop from there
Yeah I saw that also but I just assumed it would always work on a 90 degree maze, yours fails on any maze with different angles also, seems we need to think a little harder, if we had the memory for extra allocation it would be easier, we could have a constant distance checker, angle of rotations, waveform algorithms for curves...
Any chance we can upgrade the little guy?
#25
Guest_ElatedOwl_*
Guest_ElatedOwl_*
-
- Guests
Posted 20 February 2013 - 10:03 AM
I wasn't referring to different angles o.OYeah I saw that also but I just assumed it would always work on a 90 degree maze, yours fails on any maze with different angles also, seems we need to think a little harder, if we had the memory for extra allocation it would be easier, we could have a constant distance checker, angle of rotations, waveform algorithms for curves...
Any chance we can upgrade the little guy?
It would work at different angles, though. To track currentPos you're assuming that start only has 1 path directly out of it and that start is (0, 0) and everything is relative to that. The first direction you head from is at angle 0. You'd have a global variable, facing, that gets updated whenever you turn, (ie 90 degrees if facing east) and when you go to update currentPos from the last position you just determine the point it's at using the angle you're facing, the previous position and the distance travelled - I'm assuming it's just Tan(angle) to get the slope, then just doing x = distance/sqrt(1+slope^2) and using y=slope*x to get y. I haven't done any kind of serious math in a long time so pardon any errors
#26
SIlhouette
-
- Members
-
- 383 posts
Megabyte
Posted 20 February 2013 - 12:30 PM
Edit (add) (I'll recheck this in the morning but I think I understand now lol, this post you're about to read is stupid)
Ahh sorry I only glanced at what you said earlier, sorry about that, my mind was mostly elsewhere and not focused enough (even though I find this incredibly interesting).
I don't completely follow as to why you can discard the angles and distance since it would need to compare it against 0,0
Yeah I follow what you mean about me being incorrect though. I was originally going to state that it would just memorize its route like normal and if the same directions repeated >4 then it could retrace the inversex2 and see if it gets the same result inverted twice. I don't know how much memory that would take... sounds like a lot more then we would have available. As such I remembered that I had solved the issue, but when I discarded it later I forgot to make a personal note that it was again unsolved, so I didn't register what you were talking about. My apologies.
As I said before I think yours would have a memory problem also after adding angles for each plotted point and the distance/timer that we have taken for granted as actually being apart of the robot. :-P
This is now 4D array since distance would need to be constantly checked against any 2 angles that = 180 degrees so I can place its negative values into a proper array.
example of this is. Variables (X, Y, Distance, Angle) (R=right L=left S=straight under old system)
(0, 0) S
(0, 1, 1, 0) R
(1, 1, 1, 90) S
(2, 1, 1, 0) R
(2, -1, 2, 90) <------------- that was the important turn not for the loop because your system will track loops but for all information required to plot that it went 180 degrees of 0, 0 but is not at 2, 0 since distance = 2. So now plot becomes y = 1 + (-distance). I think in its memory it could store 18 turns... don't hold me to that, it just sounds about right.
What is really cool about this system is it could have a function that could have it go cross country and drive over white areas to any place it has been before since it can plot the distance from (0, 0) by any of your favourite geometric formulas. If only we had the space.
I prefer your method I just proposed my alternate one for space issues, not that mine works all that well anyways.
Edit (Rephased some shit since its now 6 am and I haven't slept since I've been watching dothack and haven't been able to stop myself, my brain is in that giddy stupid stage)
Ahh sorry I only glanced at what you said earlier, sorry about that, my mind was mostly elsewhere and not focused enough (even though I find this incredibly interesting).
I don't completely follow as to why you can discard the angles and distance since it would need to compare it against 0,0
Yeah I follow what you mean about me being incorrect though. I was originally going to state that it would just memorize its route like normal and if the same directions repeated >4 then it could retrace the inversex2 and see if it gets the same result inverted twice. I don't know how much memory that would take... sounds like a lot more then we would have available. As such I remembered that I had solved the issue, but when I discarded it later I forgot to make a personal note that it was again unsolved, so I didn't register what you were talking about. My apologies.
As I said before I think yours would have a memory problem also after adding angles for each plotted point and the distance/timer that we have taken for granted as actually being apart of the robot. :-P
This is now 4D array since distance would need to be constantly checked against any 2 angles that = 180 degrees so I can place its negative values into a proper array.
example of this is. Variables (X, Y, Distance, Angle) (R=right L=left S=straight under old system)
(0, 0) S
(0, 1, 1, 0) R
(1, 1, 1, 90) S
(2, 1, 1, 0) R
(2, -1, 2, 90) <------------- that was the important turn not for the loop because your system will track loops but for all information required to plot that it went 180 degrees of 0, 0 but is not at 2, 0 since distance = 2. So now plot becomes y = 1 + (-distance). I think in its memory it could store 18 turns... don't hold me to that, it just sounds about right.
What is really cool about this system is it could have a function that could have it go cross country and drive over white areas to any place it has been before since it can plot the distance from (0, 0) by any of your favourite geometric formulas. If only we had the space.
I prefer your method I just proposed my alternate one for space issues, not that mine works all that well anyways.
Edit (Rephased some shit since its now 6 am and I haven't slept since I've been watching dothack and haven't been able to stop myself, my brain is in that giddy stupid stage)
#27
Guest_ElatedOwl_*
Guest_ElatedOwl_*
-
- Guests
Posted 20 February 2013 - 01:48 PM
Don't get me wrong, I'm not trying to post in argumentative manner - I am genuinely curious about your approach and I am sincerely speaking from an engineering standpoint and not a personal one. (so if I came across dickheaded that was not my intent)
You wouldn't be discarding the angle and distance, rather, using it to compute the position of our nodes (or intersections/joints/whatever). The math above is wrong (thanks, yahoo answers) and this appears to be appropriate
x1 = x0 + cos(angle)*distance
y1 = y0 + sin(angle)*distance
So, we start at (0,0) and we can only move north from there.
The robot travels 1 meter (or whatever unit you want to use) and reaches another node.
We know our angle is 90, our (x0, y0) is (0, 0) and our distance is 1.
x1 = 0 + cos(90)*1
y1 = 0 + sin(90)*1
x1 = 0 + 0*1
y1 = 0 + 1*1
(x1, y1) = (0, 1)
Therefore we are at node (0, 1). From here let's say we want to move east
The robot travels 2 meters until it reaches another node.
Our angle is 0, our (x0, y0) is (0, 1) and our distance is 2.
x1 = 0 + cos(0)*2
y1 = 1 + sin(0)*2
(x1, y1) = (2, 1)
As far as memory goes, we're looking at 1kb reserved for the map which leaves us with 1kb for everything else. (mind you, it doesn't need to be reserved and it would fit a very, very large maze - one with 73 nodes)
What I'm proposing requires you store the old position (which is 1 byte; we can pull the (x,y) from the map array with a pointer) and a distanceTravelled which, depending on what type of unit you want, is going to range from 1 byte to 4 bytes.
You wouldn't be discarding the angle and distance, rather, using it to compute the position of our nodes (or intersections/joints/whatever). The math above is wrong (thanks, yahoo answers) and this appears to be appropriate
x1 = x0 + cos(angle)*distance
y1 = y0 + sin(angle)*distance
So, we start at (0,0) and we can only move north from there.
The robot travels 1 meter (or whatever unit you want to use) and reaches another node.
We know our angle is 90, our (x0, y0) is (0, 0) and our distance is 1.
x1 = 0 + cos(90)*1
y1 = 0 + sin(90)*1
x1 = 0 + 0*1
y1 = 0 + 1*1
(x1, y1) = (0, 1)
Therefore we are at node (0, 1). From here let's say we want to move east
The robot travels 2 meters until it reaches another node.
Our angle is 0, our (x0, y0) is (0, 1) and our distance is 2.
x1 = 0 + cos(0)*2
y1 = 1 + sin(0)*2
(x1, y1) = (2, 1)
As far as memory goes, we're looking at 1kb reserved for the map which leaves us with 1kb for everything else. (mind you, it doesn't need to be reserved and it would fit a very, very large maze - one with 73 nodes)
What I'm proposing requires you store the old position (which is 1 byte; we can pull the (x,y) from the map array with a pointer) and a distanceTravelled which, depending on what type of unit you want, is going to range from 1 byte to 4 bytes.
#28
SIlhouette
-
- Members
-
- 383 posts
Megabyte
Posted 20 February 2013 - 03:28 PM
Yeah I figured that out, which is why my idea was stupid. :-P
I realise now that the variables you were wiping didn't require storing because it wasn't a matter of maths it was a matter of direction, I was looking at it wrong. Therefor although actual angles are important once you have the direction after doing the maths for x, y you don't require a stored reference to do further math, it becomes static.
Don't worry I wasn't seeing your argument as a tool to win, I saw it as a tool to learn. I just thought it required storing because my new version required a constant reference and check and it was an adaption of yours.
I realise now that the variables you were wiping didn't require storing because it wasn't a matter of maths it was a matter of direction, I was looking at it wrong. Therefor although actual angles are important once you have the direction after doing the maths for x, y you don't require a stored reference to do further math, it becomes static.
Don't worry I wasn't seeing your argument as a tool to win, I saw it as a tool to learn. I just thought it required storing because my new version required a constant reference and check and it was an adaption of yours.
#29
SushiKitten
-
- Members
-
- 1,916 posts
Coffee Cat
- LocationCanada
Posted 22 February 2013 - 05:08 AM
Emo that is a very good way to go about it. I probably would have tried a couple different ways before I came to that idea.
I'll try to implement it later on and I'll post a video. I've sort of strayed from making the robot do things to making a few resources for students, such as installation packages and instructions.
I'll try to implement it later on and I'll post a video. I've sort of strayed from making the robot do things to making a few resources for students, such as installation packages and instructions.
#30
SIlhouette
-
- Members
-
- 383 posts
Megabyte
#31
SushiKitten
-
- Members
-
- 1,916 posts
Coffee Cat
- LocationCanada
Posted 13 March 2013 - 07:21 AM
They beat me to it!
That was totally my next project.
#32
SIlhouette
-
- Members
-
- 383 posts
Megabyte
Posted 13 March 2013 - 10:37 AM
If you make a flying automated transport or FAT for short then everyone will forget about the robot car.
#33
SpleenBeGone
-
- Administrators
-
- 14,951 posts
Deer Leader of the Goriest Revolution
- LocationHouston
Posted 15 March 2013 - 01:49 PM
Make a quadro copter!
#34
SushiKitten
-
- Members
-
- 1,916 posts
Coffee Cat
- LocationCanada
Posted 16 March 2013 - 05:10 AM
Actually what I thought would be fun is trying to make a biped to show off in the sci-fi convention eventually. I have all the resources I need at the engineering building. And this is just too cool:
That would be a very large project though, and to go from a tiny premade robot like the 3pi to making my own biped seems like a huge leap. Maybe it's better to wait a couple years, I have a course in the mechanics of robots I can take later down the road.
#35
SIlhouette
-
- Members
-
- 383 posts
Megabyte
Posted 16 March 2013 - 07:55 AM
Actually what I thought would be fun is trying to make a biped to show off in the sci-fi convention eventually. I have all the resources I need at the engineering building. And this is just too cool:
That would be a very large project though, and to go from a tiny premade robot like the 3pi to making my own biped seems like a huge leap. Maybe it's better to wait a couple years, I have a course in the mechanics of robots I can take later down the road.
If I was in a dark ally and that thing was walking towards me I would shit myself.
#36
SpleenBeGone
-
- Administrators
-
- 14,951 posts
Deer Leader of the Goriest Revolution
- LocationHouston
Posted 16 March 2013 - 09:12 AM
If you have the skill to do the programming, a biped robot shouldn't be that hard to make. If you want to make a walking robot though, try something like this:
#37
SushiKitten
-
- Members
-
- 1,916 posts
Coffee Cat
- LocationCanada
Posted 16 March 2013 - 09:30 AM
Yeah, that's probably a better start, a lot less balancing, haha.
#38
SpleenBeGone
-
- Administrators
-
- 14,951 posts
Deer Leader of the Goriest Revolution
- LocationHouston
Posted 16 March 2013 - 09:45 AM
Plus if you make it move fast, it's creepy as hell.
#39
DeadChannel
-
- Members
-
- 1,088 posts
Gigabyte
- LocationNotlob
Posted 21 June 2013 - 11:03 PM
Heh, this is pretty cool. Are you on societyofrobots.com
I'm fearful, I'm fearful, I'm fearful of flying, and flying is fearful of me.
#40
SushiKitten
-
- Members
-
- 1,916 posts
Coffee Cat
- LocationCanada
Posted 22 June 2013 - 06:35 AM
Thanks! I was on there for a while, they were giving me some advice. Mostly my personal projects have been put on hold since I'm in classes now but I'll probably start working on them again in the fall.
As for the maze solving robot, my supervisor is piloting the labs I created over the summer semester and as far as I know the students love playing with the robot. I'm so proud, haha.
