Patrolling an Area

[Chasney913]

Scenario: I have an robot, that can drive like an automobile, and also swivel in place. The robot cannot tell where it is going, or how long it will take to get somewhere. I have an area, of a variable size, and irregular shape. The robot can tell when it has reached the edge of the area, and react accordingly, but cannot tell how far it is from the edge. The robot can start from any position within the area, facing any direction. The robot can turn a certain amount of degrees, but chances are it will not turn that amount exactly, due to wheel slippage, or motor power.

I need the most efficient (area/time) algorithm for covering the entire area. I have experimented with:

When the robot hits the edge, it turns a full 90, and continues (circular/square sweep)
When the robot hits the edge, it backs up until it hits an edge again, turns 15 degrees, and continues (radial sweep)
Random movement, interrupted by hitting the edge.

None of these are super effective, sometimes only covering areas by dumb luck.

Any suggestions? Questions? Comments? Other things ending in question marks?

[luby]

If the shape is all convex angles, I would suggest going till it hit something, turn ninty degrees going forward a tiny bit, turning another 90 degrees and go till it hits something. Lather, Rinse, Repeat.

[Weregoose]

What I'm thinking is, if it hits a wall, it should turn either left or right, then run parallel to the wall about the machine's length, and then rotate so as to travel perpendicular to the wall.

[DarkerLine]

[Pseudoprogrammer]

Find a wall and proceed to run in spiral-ish type path until all area has been covered?

[Chasney913]

The shape I had to deal with the most is hourglass-like, although not entirely symmetrical. I've tried the spiral path, I forgot to mention. The problem is that the robot never makes the same exact angle twice, so it eventually gets off track.

[Pseudoprogrammer]

I see... what surface are you operating on?

[Chasney913]

The robot is operating on a pegboard, with electrical tape denoting edges. Fancy, I know.

I don't know that the surface matters much, but it is a good surface to run on. (Good friction, not too uniform, etc.)

[Adamant]

Can it tell how long it has been rolling since it last hit something? If it can, this problem shouldn't be that hard at all. You can just have it do a figure 8 like shape between the "triangles" of the hour glass, and have the shape slowly shrink inwards.

If it can't, you can always just have it snake up and down the hourglass (Have it go forwards until it hits something, have it turn 90 degrees and go forward a bit, then have it turn 90 more degrees until it hits something). However, this won't work if the shape bends inwards perpendicularly to the direction the robot is traveling (which I doubt is happening... right?)

[Chasney913]

I could add a timer, but I'm not quite sure how well it works. I'd rather not use it though, although I can try.

As for the second idea, it would probably work well, it's just that the robot can't make exact angle turns every time. Also, I forgot to mention, the robot does not have a command "Turn x number of degrees (or radians)", I can simply tell it to rotate a direction for a length of time. As the batteries run out, the robot will lose motor power, and turn a smaller angle each time, throwing off the accuracy. I suspect I'll just have to go with my radial sweep, unless there are other suggestions.

[bukwirm]

I have dealt with something like this - I suggest you get a lot of batteries and replace them frequently. That will help you avoid variations due to batteries.

Personally, I like the idea of taking a path like this (follow the arrows):

>>>>>>>v
v<<<<<<<
>>>>>>>v
<<<<<<<<

So the robot goes one way until it his a wall, turns 90 right, moves forward a short distance, turns 90 right, then continues, etc. This depends on how you hit the walls and how close together the walls are, of course.

[Recursive Acronym]

The battery problem could be fixed with rechargeables, which output a steady (but less than regular batteries) power supply.
Are we working with the Lego RCX here? Regardless, get a way to count wheel rotations. The following statements about Legos can also work with other materials. With Legos, you can do well if you use a regular rotation sensor, use a touch sensor with cams, or use a light sensor with a special printed 4-gradient wheel. Have a motor controlling each wheel (no treads and a pivoting wheel as the third support). If you want to put a sensor on both wheels, then just do that and ignore the rest of this post. Otherwise, use gears in clever way so that the your differential gear is connected both wheels, is geared up for like, say, 3x rotation speed as compared to the wheels if you don't have an actual rotation sensor, and has the inputs rotating in opposite directions when the robot moves forward. Then, attach a rotation sensor/improvised sensor. If the sensor detects a movement, it means that the robot is turning. If it is a touch sensor, all you can do is know that you're screwed. If it is light/rotation, you can use the direction of the rotation to determine which wheel rotates faster to correct your robot's movement. And, of course, you can use the speed of rotation to determine how fast your robot turns if you turn by only rotating one wheel at once. If you need to be able to rotate in place, then make the two feeds to the differential rotate in the same direction. You won't be sure that your robot moves straight forward, though.

[Chasney913]

I am working with an RCX, currently using rechargables. However, it seems to drain them quite quickly. In about 3 hours, is my guess. I don't have a rotation sensor, so that's out of the question. I like the touch or light sensor idea, however I need the two touch sensors for other things (I need it to detect foreign objects).

With the radial sweep, it works well. I had it sweeping the entire area, and relatively effectively, too. The only issue was, it takes a really long time, because turning 90 degrees 10 degrees at a time takes a while. I could speed it up as it goes forward and backward, but then it goes so fast the sensors don't read the edge of the area. I have to go quite slow, which takes a long time.

[Recursive Acronym]

Using rechargeables, the battery power should remain relatively constant until they die, so you should just time the turns and then duplicate that turning time when the robot clears the area. What is this for, by the way?

[Chasney913]

http://iitrl.acadiau.ca/rpc2007/

[Igrek]

I have 2 of these at home...
I don't have an rotation sensor either, but when I needed one I did this:
-I took a round piece of paper, I collared one half black and left one half white.
-I putted it on on a small wheel and putted a light sensor next to it, so I made a rotation-sensor.
-I could count the rotations by using only one light sensor, but not degree-accurate, it worked quite well.

I believe this will not help you because you are using the 3 sensor port already...

PS: I didn't build any robots for years.

[Recursive Acronym]

I'm pretty sure that you (Chasney913) aren't supposed to get outside help on this.

[Igrek]

You are right but I'm not sure whether or not he is or is not interested in this rotation sensor, so I posted how it is possible to do anyway...

[Chasney913]

I'm not looking for specifics, just your thoughts. I still have to program it, and whatnot, test it, and see if it works. Plus, they tend to be quite lax with the rules, however, that's not my excuse. Basically, the rules say that I shouldn't go trolling for code created for this express purpose. Like I said, I still have to do quite a bit of work, as opposed to just copying something.

Thanks for the help, by the way. Some of the ideas are pretty creative. Most of the ideas I've seen tend to be along the lines of random bouncing.

[Igrek]

What are you planning to use to program the RCX (robot)? I only used the 'thing' that came with it where you have to put puzzle pieces into each other to make a program, thought I know there is 'LEGO MINDSTORMS SDK 2.0' and maybe other software to program the RCX.