Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The scenario is;

We've got $n$ stationary 360$^{\circ}$ sensors in an confined area (each sensor is located at some arbitrary $\left(x,y\right) = \left(x_{n},y_{n}\right)$), once a unit $t$ enters the area, it will be visible to all sensors at once, and we'll want to calculate it's position ($\left(x,y\right) = \left(x_{t},y_{t}\right)$), however the sensors cannot measure exact distance, rather they return a distance interval $\left[mindistance_{n}, \;\; maxdistance_{n}\right]$ (variable for each sensor), also the sensors do not provide orientation. That is the sensors provide an annulus.

Below is an image of the scenario, with $n=3$; Example

The min-distances in this image are $0.5$ and max-distances are $1$. The coordinates are;

  • Black : $\left(x,y\right) = \left(3.5, 5.5\right)$
  • Blue : $\left(x,y\right) = \left(5, 5\right)$
  • Purple : $\left(x,y\right) = \left(4, 4\right)$

The red area is the feasible region, and the blue dot within this is the $\left(t_{x},t_{y}\right)$ I want to locate.


So for the general case;

My input is a matrix; $A = Mat_{n \times 4}\left(\mathbb{R}\right)$, with the following layout; $ \left[ \begin{array}{cccc} x_{1} & y_{1} & mindistance_{1} & maxdistance_{1} \\ \vdots & \vdots & \vdots & \vdots \\ x_{n} & y_{n} & mindistance_{n} & maxdistance_{n} \\ \end{array} \right] $

What I want to do, is to minize the function; $ \sum_{i=1}^{n} \left(dist\left(i\right) - A_{i,3}\right) \cdot \left(dist\left(i\right) - A_{i,4}\right) \quad | \quad dist\left(i\right) = \sqrt{\left(x-A_{i,1}\right)^{2} + \left(x-A_{i,2}\right)^{2}} $

Subject to; \begin{align*} \left(x-A_{1,1}\right)^{2} + \left(y-A_{1,2}\right)^{2} &\geq A_{1,3} \\ \left(x-A_{1,1}\right)^{2} + \left(y-A_{1,2}\right)^{2} &\leq A_{1,4} \\ \vdots \\ \left(x-A_{n,1}\right)^{2} + \left(y-A_{n,2}\right)^{2} &\geq A_{n,3} \\ \left(x-A_{n,1}\right)^{2} + \left(y-A_{n,2}\right)^{2} &\leq A_{n,4} \\ \end{align*} What I'm interested in, is the optimized output '$\left(x_{t},y_{t}\right)$'.

I'm able to do this, using Maples 'NLPSolve', however as I'm going to implement the solution in software. I'll need to get an understanding of how this 'NLPSolve' function works, I've tried searching the web, without any luck.

So my question is, what would an easy to understand algorithm, for solving the above problem look like? - Performance is somewhat unimportant.

The maple program used to find the point, in the above picture is;

$ A := \left[ \begin{array}{cccc} 4 & 4 & 0.5 & 1 \\ 5 & 5 & 0.5 & 1 \\ 3.5 & 5.5 & 0.5 & 1 \end{array} \right]: $

with(Optimization)
constraints := {(x-A[1, 1])^2+(y-A[1, 2])^2 >= A[1, 3], (x-A[2, 1])^2+(y-A[2, 2])^2 >= A[2, 3], (x-A[3, 1])^2+(y-A[3, 2])^2 >= A[3, 4], (x-A[1, 1])^2+(y-A[1, 2])^2 <= A[1, 4], (x-A[2, 1])^2+(y-A[2, 2])^2 <= A[2, 4], (x-A[3, 1])^2+(y-A[3, 2])^2 <= A[3, 4]}
optimize := sum((sqrt((x-''A''[i, 1])^2+(y-''A''[i, 2])^2)-''A''[i, 3])*(sqrt((x-''A''[i, 1])^2+(y-''A''[i, 2])^2)-''A''[i, 4]), i = 1 .. 3)
NLPSolve(optimize, constraints)

share|improve this question
    
From your description, it's not clear to me whether mindistance and maxdistance are fixed or variable. I presume they're variable and your problem is a tracking problem?! Also the first two columns of $A$ are $(n_x, n_y)$, aren't they (i.e., the location of the $n$-th sensor)? Also you should perhaps call $(t_x, t_y)$ the variables of your problem to avoid confusion with the $x$ and $y$ in $A$. –  Dominique Mar 2 '13 at 16:57
    
The sensors measured distances are variable, and yes $\left(n_{x},n_{y}\right) is the first two columns of $A$. –  Skeen Mar 2 '13 at 17:32
    
What I mean is that if the unit is located at $t := (t_x, t_y)$, then both mindistance and maxdistance are known functions of $t$, is that correct? What do you know of those functions? Do you have access to their derivatives? –  Dominique Mar 2 '13 at 20:14
    
The mindistance and maxdistance are reals, returned by a function called GetApproximateDistance(t). I have no knowledge whatsoever about that function. –  Skeen Mar 2 '13 at 23:38
    
Please correct me if I'm understanding the question wrong, your constraints don't make sense. $A_{i,3}$ and $A_{i,4}$ are min/max distances, while on the left hand side you have distance-squared. You should have distance(i) on the LHS instead, just as defined in your objective function. Also, in your objective function, you have $\sum$(dist-min)(dist-max), with appropriate constraints you will always get a negative value for this function. Your minimization wouldn't make sense in this case. That aside, which option did you use in NLPSolve? –  hattoriace Mar 4 '13 at 18:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.