Area coverage of autonomous underwater robot

Question

I'm currently working on an autonomous underwater cleaning robot and would like your input on some navigation algorithms

Problem:

Wash the inside of big, open and filled tank, e.g. water storage tank (Figure 1), with an autonomous robot. The inside of the tank is divided in sections, such that the robot has a limited washing area. The washing are can be square, rectangular, parallelogram or other shapes. The inside of the tank may have unknown obstacles, e.g. inlets and outlets. Since the robot will function under water, there are a few limitations when it comes to sensors.

Available sensors:

• Wheel encoders
• Distance measurements, e.g. ultrasonic, sonar, for obstacle avoidance
• Boundary detection
• Bumper with mechanical switch for collisions
• Pressure sensor
• Camera. Not necessary clean water so low visibility is an issue, i.e. difficult/impossible with visual odometry

Non-available sensors:

• INS
• GPS

Current solutions:

• Random walk within boundaries (Figure 2). Either driving in straight lines (Figure 2), spirals (Figure 7) or a combination of lines and spirals (Figure 6)
• Parallel swaths with 30% overlap (Figure 3). Requires cm precision on position estimate to guarantee coverage. Figure 4 shows an identical simulation but with one wheel radius 0.5mm larger than the other. This shows that it is not sufficient to only rely on wheel encoders for positioning as it will drift. With perfect positioning the parallel swath algorithm is 2x more efficient than random walk

One possibility is to add an acoustic navigation system, but it would be too expensive.

This problem is similar to the lawn mower and vacuuming robots. However, it seems like most of the products use random walk or a similar approach. Does anyone know a more efficient algorithm to cover the area based on the information provided?

For all the simulations, the red line represents the robot’s movement and the black is washed area. 

Looking at other similar questions I couldn't find the answers I've been looking for:

• How to localise a underwater robot?
• Robot wire follower + how to position on wire
• Working of Autonomous Lawn mower(ALM) in an unbounded area without a perimeter wire
• What algorithm should I implement to program a room cleaning robot?

Figure numbering:

1 2
3 4
5 6
7

References:

• OmniClimbers: Omni-directional magnetic wheeled climbing robots for inspection of ferromagnetic structures

Answer 1

If you can't localize, you can't do anything that requires localizing.

If you can't use wheel encoders accurately enough to do a rectangular fill (parallel lines) then, by the same reasoning, you can't use them to do any other shaped fill pattern either (concentric circles, spirals, etc.).

I only see one real solution here (that's not random walk), but its success depends on the physical construction of your vehicle and the sensors you're using.

Use the pressure sensor to indicate depth, then build a PID controller around the pressure sensor to steer the vehicle. Your x/y coordinates of the "rectangular" path you're trying to traverse aren't actually x/y coordinates. You're in a cylinder; they're cylindrical coordinates. Really you have h/$\theta$ coordinates.

You're still left with the problem that you can't localize, so you have no absolute $\theta$ coordinate, so you'll never be able to guarantee any coverage in a particular $\theta$ range.

What I would suggest you consider instead of rectangular regions, if you're attempting to make a "cleaning crew" that will work cooperatively to clean the whole structure, is to use cylindrical regions.

So, let's say you have four robots. You could have each robot clean the entire height (0 to h) and a quarter of the circumference (0 to $\pi$/2, etc.). But you can't do this, because there are (presumably) no features by which you could localize in the tank. Every $d\theta$ looks like every other $d\theta$, so you can't assign any robot a particular range in the $\theta$ dimension.

What I'm suggesting you do instead is to have each robot clean the entire circumference (0 to 2$\pi$), then segment by height. Each robot has a pressure sensor and can tell that they are in their correct height band.

Now all you need to do is know that your wheel encoders are accurate enough to detect that you've traversed the circumference plus some overlap tolerance.

This solution requires your ability to resolve your depth accurately. How accurate? I would say you should be at least half the width of the cleaning instrument. If your brush is a foot wide, then you should be able to determine depth accurate to +/- 6 inches. This ensures you're still cleaning in the desired band if you go off-target. This is the minimum resolution; ideally you'll get something much better.

You'll probably want to overlap by (brushWidth - depthAccuracy) to ensure complete coverage where you went off-track during a normal sweep. So, again, if your band is (brushWidth = 1 foot), and you go off-track by -0.5 feet, then the upper +0.5 foot of the band was not cleaned in that segment. Therefore you'd want to overlap (1 foot - 0.5 foot) = 0.5 feet to ensure the whole band was cleaned.

So, your algorithm flow would look something like:

desiredHeight = 0;
finishHeight = h/4;

brushWidth = 1; % Foot
depthAccuracy = 0.5 % Feet

speed = 1; % Percent
circumferenceOverlap = 1.1;

while (desiredHeight <= finishHeight)
    while (deadReckoning < circumference*circumferenceOverlap)
        actualHeight = PressureSensor();
        steerDifferential = PID(desiredHeight-actualHeight);
        LeftWheel.Speed(speed - steerDifferential);
        RightWheel.Speed(speed + steerDifferential);
        deadReckoning = deadReckoning + (LeftWheel.Distance() + RightWheel.Distance())/2;
    end
    deadReckoning = 0;
    desiredHeight = desiredHeight + brushWidth - depthAccuracy;
end

So, briefly again, just keep a running count of how far you've traveled with the wheel encoders. Once you've gone a full circumference plus some tolerance, then increment the height and clean another circumference. This solution leverages the fact that the tank is a cylinder, and that (start = end) on the $\theta$ dimension.

Now, if there are sparse obstacles that maybe you couldn't use to localize everywhere (couldn't see for example), you can setup an avoidance subroutine to go around it. But this should clean the entire tank efficiently. You'll want to tune the PID controller to keep the vehicle on track, but that performance will again be determined by the resolution on the depth sensor.

A word of caution: the pressure sensor corresponds to a depth, as in below the water line, not a height. You should be able to detect the surface of the water by an ultrasound reflection at the air/water interface, and likewise should be able to detect the bottom of the tank by the reflection at the water/tank interface. You should take this into account if you're planning on cleaning the entire tank and not just the submerged portion of the tank.

Also, any flow in the tank will affect pressure readings, which will cause false depth measurements.