# path planning with invasive measurements

My background is not science, and I hope the question I am about to ask doesn't look like a homework kind of a thing! Anyway, I will try my best to make the point clear.

imagine there is a lake, and a boat equipped with a sensor on that lake. boat can move freely in a contained rectangular shape region on the lake, namely $0 < x < 1 \mbox{ and } 0 < y < 1$ .

the sensor installed on the boat takes measurements at times $t_0, t_1, …$ with constant frequency. Each time sensor shoots a bunch of rays downward (in the shape of a thin cone, like a flashlight) and receives their reflection off the seabed and then sensor returns two numbers; first one indicates the depth of lake at that point and second one indicates something about some quality of soil that makes the seabed at that point. Because the measurements are noisy (we assume distance measurement is perfect, but the measurement about the chemicals found in the seabed is noisy) one can imaging that by taking multiple measurements at a single point $(x_t,y_t)$ and refining those measurements using come filtering method (e.g. Extended Kalman Filter, or some other method) he can increase the certainty about those measurements.

$s(x,y) = f(x,y)+noise(x,y)$ (where 'f' is the true value and 's' is sensors measurement about soil quality)

Now the problem is a path planning problem. We want to know how the boat should explore the lake in the next N seconds (it takes N seconds for the sensor to take say 100 samples). But there are two other factors to take into account.

First; somehow we have a means of estimating the measurements of sensor if the sensor was to be turned off, taken to a random point $(x_r,y_r)$, turned on and take only one measurement. So we have s*(x,y) which has been proven to be a good estimate of s(x,y). We can use S* in our path planning phase.

Second; one can imagine that measurements will not be independent and there is correlation between measurements. This correlation is stronger between nearby point (where $\|(x_1-x_2,y_1-y_2)\|$ is small ) but points that are far apart are less correlated. Also one would imaging that at point where water is shallow and seabed is close to water level, a small movement of boat will result in more varying measurements, while in places where water is quite deep, even if the boat moves a bit, measurement will not change much. (like when I look at a mountain far away, if I move a few meters I still see the same image, but if I am looking at something close to me, moving a few meters will result in different view point). I must say the important measurement for me is the one about soil quality, and distance measurement is only provided to help finding the correlation between measurements made at nearby points, as mentioned above.

I don't know how the measurements are correlated, I can just make some guesses based on the argument above. At time $t=t_0$, boat is at point $(x_0,y_0)$ and all I am given is the tool S*(x,y). and I want to do the path planning for the next N seconds.

I will appreciate any suggestion/help and please let me know if any part of problem is unclear, I know without proper graphs,etc. it is not easy to explain the idea.

My own attempt to solve the problem is as follows: make a regular grid of $m \times n$ on $0<x<1$ and $0<y<1$ and restrict the boat to always be positioned on one of these points. so path planning is on discrete space now. calculate s*(x,y) for all grid points. (Safely assume $(x_0,y_0)$ is also on one of the grid points).

S* tells me estimate measurements at $x,y$ . Because I know the noise model and the filtering scheme that will be used to refine the measurements, I can calculate how many bits of information (reduction of differential entropy) I will gain if I take two or more consecutive measurements from same position. Also by introducing a non-informative prior probability (uniform distribution) over all possible values, it is possible to calculate how much information can be gained by taking a single measurement at a new position.

I define the path planning problem as one of maximising the overall information gain while amount of work (number of samples taken) is fixed. Also samples have to be taken either from same position as previous one (boat stationary) or from a position next the previous sampling location (boat moving, but it's speed is limited so measurements have to be made on neighbouring points on the grid).

Now the question is, if I take a measurement at a point $p_1$, how informative a measurement at a neighbouring point $p_2$ will be, knowing that these two points are somehow correlated.

Now this is were I am stuck! I thought maybe some techniques such as mean field theory or variational methods can help me model the correlation between the points and therefore figure out how redundant a measurement on a point will be if a measurement has been made on at least one of its neighbours. But I can not figure out how to go forward from here.

It would be great if anyone can help me with this problem, or direct me to the right place to ask it.

• An important thing to point is that we can use information we have obtained to pick new points. So I think the answer will be an adaptive triangulation algorithm, now you know the name perhaps you can google the term to learn more. – Ali Aug 20 '13 at 11:37
• Maybe this will get a better answer on Math.SE, because I don't think a lot about this problem is related with physics, except the measurements part. – udiboy1209 Aug 20 '13 at 11:52
• @ali Thanks for your comment. I looked up "adaptive triangulation algorithm". but what it seems to be is a way to fit Delaunay mesh to a "random" surface. I had also thought about using those 'information' at hand for better sampling, e.g. Hamming sampling or some other MonteCarlo method. But to me it seems that those are all applicable if there was a fixed underlying function we wanted to measure. Here, on the other hand, because there are correlation between points, the reward we get for a specific sample we take depends on the previous sampling locations (& possibly their order).Am I right? – user5131 Aug 20 '13 at 12:54
• You didn't have to... A moderator could have migrated it from here, it avoids duplicates. – udiboy1209 Aug 20 '13 at 13:41