# Area coverage of autonomous underwater robot

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

• 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:

### Figure numbering:

1 2
3 4
5 6
7

References:

• Do you have a single question? It seems a very open-ended problem at the moment. Also, it's not entirely clear what the wheels are for - is the machine denser than water so it sits on the bottom? If so does it need to clean the tank sides?
– Andy
Commented Oct 12, 2016 at 13:31
• The robot will use magnetic wheels, so that it is also possible to clean the sides, e.g. this kind of robot. My main objective is to find an coverage algorithm that is as efficient as possible with the limited sensor alternatives as mentioned in the post (at least more efficient than random walk) Commented Oct 12, 2016 at 14:02
• Welcome to Robotics user2594166. On stack exchange, it is better to edit your question to add information requested in comments, rather than adding more comments. Comments are for helping to improve questions and answers, and are distracting, so we try to keep them to a minimum. If all of the information needed to answer the question is contained within it, the comments can be tidied up (deleted). Commented Oct 13, 2016 at 9:14

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)
actualHeight = PressureSensor();
steerDifferential = PID(desiredHeight-actualHeight);
LeftWheel.Speed(speed - steerDifferential);
RightWheel.Speed(speed + steerDifferential);
end
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.

• Thank you for your answer! You successfully described the many thoughts I have on this project :) I really like your solution, but in this case the level of fluid varies, so as you pointed at the flow will affect the pressure readings and cause false depth measurement. In addition, the tank has not necessary straight sides, so in some cases it would not be possible to measure the distance to the bottom of the tank or water line. The plan is to attach relevant sensors to a prototype and manually drive the robot to collect data. Then post-process the data to see which sensor is applicable. Commented Oct 17, 2016 at 10:05
• @user2594166 - Well, I would just point out that the absolute height doesn't matter too much. Say you have your system designed for four robots, each cleaning a swath (h/4) tall. Now assume the cylinder is only half full. The "top" robot is looking to clean from depth (0) to depth (-h/4). This region actually exists, but it's not (h) to (3/4 h), it's (1/2 h) to (1/4 h). But the robot doesn't know how full the cylinder is, so it starts cleaning that surface, 0.25-0.5h. Similarly, the second robot cleans the (1/4 h) to (0) height band, because that region also exists.
– Chuck
Commented Oct 17, 2016 at 12:38
• Robots three and four cannot get deep enough to clean their band. If you had an ultrasonic sensor that detects the "floor" of the cylinder, then you could just have them stop looking once they got so deep that they found the floor. At that point, robots 3 and 4 stop searching and thus just become obstacles for robot 2 to drive around. Now also, because they are at the bottom, as the water tank fills, at some point robot 3 will detect that it's at the depth associated with its assigned band and can auto-resume cleaning. Likewise again for robot 4.
– Chuck
Commented Oct 17, 2016 at 12:41
• Essentially, the optimum use of the robots would be to have each robot be assigned to a quarter of the depth band, not the height band, but if you can't determine on-the-fly how deep the water is, then an easy routine would be to have each robot assigned to a depth range based on the height, and have the robots sequentially go to a "sleep" mode when they find bottom and still are unable to get to their assigned depth. As the tank fills, the sensed depth increases and the robots "wake" again and resume cleaning.
– Chuck
Commented Oct 17, 2016 at 12:43