FIRST is not about building robots, it is about building people; the robots are just a good way to get the people there. - JamesBrown [more]
 Chief Delphi Math Quiz 11
 CD-Media CD-Spy
 portal register members calendar search Today's Posts Mark Forums Read FAQ rules

#16
05-05-2017, 10:46 PM
 KJaget Zebravision Labs FRC #0900 Team Role: Mentor Join Date: Dec 2014 Rookie Year: 2015 Location: Cary, NC Posts: 97
Re: Math Quiz 11

Letting matlab do the work. Set up a system of equations. x(1) = point2.x, x(2) = point2.y, x(3) = point3.x, etc. This is a set of (xsrc-xdst)^2 + (ysrc-ydst)^2 - distance^2 = 0 equations derived from the list given in the OP.

Code:
```function F = distEQ(x)

F(1) = (x(1) - x(5))^2 + (x(2) - x(6))^2 - 47.8017^2;
F(2) = (x(3) - x(7))^2 + (x(4) - x(8))^2 - 69.2026^2;
F(3) = (x(7) - x(15))^2 + (x(8) - x(16))^2 - 148.492^2;
F(4) = (x(11) - x(13))^2 + (x(12) - x(14))^2 - 86.764^2;
F(5) = (x(7) - x(9))^2 + (x(8) - x(10))^2 - 63.0714^2;
F(6) = (x(1) - x(13))^2 + (x(2) - x(14))^2 - 189.528^2;
F(7) = (x(9) - x(11))^2 + (x(10) - x(12))^2 - 65.192^2;
F(8) = (x(5) - x(15))^2 + (x(6) - x(16))^2 - 147.085^2;
F(9) = (x(1) - x(3))^2 + (x(2) - x(4))^2 - 90.5207^2;
F(10) = (x(9) - x(13))^2 + (x(10) - x(14))^2 - 86.0349^2;
F(11) = (x(3) - x(15))^2 + (x(4) - x(16))^2 - 171.956^2;
F(12) = (x(5) - x(11))^2 + (x(6) - x(12))^2 - 88.8144^2;
F(13) = x(1) - 0;
F(14) = x(2) - 0;```
Save as distEQ.m

Code:
```>> fun = @distEQ;
>> x0(1:16) = 10;
>> x = fsolve(fun, x0)
x =

Columns 1 through 7:

8.7244e-20  -4.0763e-20   8.9553e+01  -1.3199e+01   3.9964e+01   2.6228e+01   3.3832e+01

Columns 8 through 14:

2.7839e+01   8.8708e+01   5.8929e+01   5.3763e+01   1.1396e+02   1.3930e+02   1.2852e+02

Columns 15 and 16:

1.0523e+02   1.5804e+02

# Convert to x,y coords for point2, 3, 4, etc.
>> xx = reshape(x,2,8)'
xx =

8.7244e-20  -4.0763e-20
8.9553e+01  -1.3199e+01
3.9964e+01   2.6228e+01
3.3832e+01   2.7839e+01
8.8708e+01   5.8929e+01
5.3763e+01   1.1396e+02
1.3930e+02   1.2852e+02
1.0523e+02   1.5804e+02

# Sanity check pt2 -> pt4 matches the initial conditions
>> sqrt(sum((xx(1,:) - xx(3,:)).^2))
ans =  47.802

# see what this run gets for 8->9 (remember index - 1)
>> sqrt(sum((xx(7,:) - xx(8,:)).^2))
ans =  45.081```
Depending on initial conditions and arbitrary values for x&y of point 2, I also get 282.56, 21.878, 290.81, and probably more (out of battery).
#17
05-06-2017, 06:19 PM
 GeeTwo Technical Director AKA: Gus Michel II FRC #3946 (Tiger Robotics) Team Role: Mentor Join Date: Jan 2014 Rookie Year: 2013 Location: Slidell, LA Posts: 4,203
Re: Math Quiz 11

I have attached a spreadsheet which goes through the calculations to solve this problem. I haven't verified everything on it yet, but I have fixed a lot of problems along the way; I'm mostly posting to show that the problem IS soluble and as a demo of the sorts of ambiguities and multiple roots that make result in multiple solutions to the system of twelve equations in twelve unknowns.

The cells highlighted in yellow are intended to be set as you investigate different values of distance 8-9, and the different ambiguities, or if you want to zoom in to a particular segment of angle 8-5-9; see the notes in the spreadsheet for details. The top graph is a layout of the eight points based on all of the constraints EXCEPT the distance 2-4, and also based on the four ambiguity states and the initial angle 8-5-9. The second plot spans a range of angles 8-5-9. By default, I have it set for the range from 0 to 2pi.

Essentially, you enter the value for distance 8-9, then try each of the 16 ambiguity states, and look for places where the actual distance between points 2 and 4 (red curve) crosses the constraint distance (green line), then trace up that angle to a value for distance 8-9 (blue curve). Ideally, you would use Newton's method or similar to determine where a crossing occurs, and zoom in on it to find more precisely where the crossing occurs. With the assumed distance 8-9 of 55.17, I found two solutions for false-false-false-true, (approx 190 and 186), two for false-true-true-false (127, 183), and a near miss on true-true-true-false (109).

I don't think I've used anything more complex than the law of cosines to do any of this. Does this answer your question, Jon Stratis?
Attached Files
 MQ11.xlsx (58.9 KB, 5 views)
__________________

If you can't find time to do it right, how are you going to find time to do it over?
If you don't pass it on, it never happened.
Robots are great, but inspiration is the reason we're here.
Friends don't let friends use master links.
#18
05-11-2017, 09:57 AM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 8,665
Re: Math Quiz 11

Math Quiz 11, Part B:

Given three points p1, p2, p3 with coordinates (1,1), (1.5,0.5), and (2.0,0.75) respectively...

... find the coordinates of the point p4 whose distance from points p1, p2, p3 is 1.477601434758372, 1.909792135285932, 2.416879392936271 respectively.

#19
05-11-2017, 10:35 AM
 Jared Russell Tried to take the year off. Failed. FRC #0254 (The Cheesy Poofs), FRC #0341 (Miss Daisy) Team Role: Engineer Join Date: Nov 2002 Rookie Year: 2001 Location: San Francisco, CA Posts: 3,247
Re: Math Quiz 11

Quote:
 Originally Posted by Ether Math Quiz 11, Part B: Given three points p1, p2, p3 with coordinates (1,1), (1.5,0.5), and (2.0,0.75) respectively... ... find the coordinates of the point p4 whose distance from points p1, p2, p3 is 1.477601434758372, 1.909792135285932, 2.416879392936271 respectively.
This is an overdetermined trilateration problem (3 constraints, 2 unknowns), which happens frequently due to measurement noise in localization systems (like GPS). As such, the solution depends on what properties you want your residual to have. For one such choice of properties, I happen to know a neat trick that solves this problem elegantly for the particular case where (# constraints) = (# unknowns + 1).

Solution here.

This method adds a free parameter to the distance measurements representing measurement error (assuming it is uniform across all measurements), which lets us solve the system of equations efficiently to find the point representing the center of the three circle-circle intersections (obtained by leaving out one constraint at a time). "h" represents the radius^2 of the circle joining those intersections (which can be imaginary, as in this case, depending on whether or not all three circles overlap or not). The fact that "h" is small in magnitude shows that the solution is very close.

It would also be reasonable to want a (perhaps weighted by distance) least squares solution, but this would require whipping out a non-linear least squares solver.
#20
05-11-2017, 10:45 AM
 Jon Stratis Mentor, LRI, MN RPC FRC #2177 (The Robettes) Team Role: Mentor Join Date: Feb 2007 Rookie Year: 2006 Location: Minnesota Posts: 4,117
Re: Math Quiz 11

Gee, that's some nice math

For part B... Is the system actually solvable? You can define each circle with the simple equation (x+a)^2 + (y+b)^2 = r^2. That leaves you with 3 equations but only 2 unknowns, which makes it really easy for there to be no solution. Of course, there's no guarantee that the circles even intersect, but we should assume they do, right? Two circles can have 2, 1, or no intersections in common, likewise three circles can have 2, 1, or 0 common intersections!

Plotting it out, it initially looks like there's an intersection point (near -0.409, 0.555) ... but zoom in and the circles just miss having a common intersection. Plug the system of equations into Wolfram Alpha, and it comes back with no solution, supporting this finding.

So, lets simplify it down to pairs of circles, see how close we actually get.

p1 + p2:
x=-0.409
y=0.5550000000000005

p1 + p3:
x=-0.4089999999999995
y=0.5549999999999989

p2 + p3:
x=-0.4089999999999999
y=-0.5550000000000041

Given how close we are... Is this just a rounding issue with your numbers Ether, or is there intentionally no solution?
Attached Thumbnails

__________________
2007 - Present: Mentor, 2177 The Robettes
LRI: North Star 2012-2016; Lake Superior 2013-2014; MN State Tournament 2013-2014, 2016-2017; Galileo 2016; Iowa 2017
2015: North Star Regional Volunteer of the Year
2016: Lake Superior WFFA
#21
05-11-2017, 11:49 AM
 KJaget Zebravision Labs FRC #0900 Team Role: Mentor Join Date: Dec 2014 Rookie Year: 2015 Location: Cary, NC Posts: 97
Re: Math Quiz 11

The solver approach also gives p4 = (-.409, .555). I modified the distEQ from my previous post and it converged pretty much immediately.

Not sure what Wolfram Alpha uses but e-15 looks an awful lot like C++'s double epsilon value, meaning it it likely hitting limits of the precision an 8-byte floating point number can handle.

Last edited by KJaget : 05-11-2017 at 11:51 AM.
#22
05-11-2017, 12:16 PM
 GeeTwo Technical Director AKA: Gus Michel II FRC #3946 (Tiger Robotics) Team Role: Mentor Join Date: Jan 2014 Rookie Year: 2013 Location: Slidell, LA Posts: 4,203
Re: Math Quiz 11

Point (-.409, .555) works out just fine in gawk (running under cygwin running under windows 7 32 bit); I suspect differences in round off.

Code:
```GeeTwo@Teal ~
\$ cat ./MQ11.gawk
#!/bin/gawk -f
BEGIN {x[1]=1; x[2]=1.5; x[3]=2.0;
y[1]=1;y[2]=0.5; y[3]=0.75;
r[1]=1.477601434758372;
r[2]=1.909792135285932;
r[3]=2.416879392936271;
tx=-.409; ty=0.555;
for (i=1; i<4; i++) {
printf "point %d: %.15f %.15f\n",
i, r[i], sqrt((tx-x[i])*(tx-x[i])+(ty-y[i])*(ty-y[i]));}
}

GeeTwo@Teal ~
\$ ./MQ11.gawk
point 1: 1.477601434758372 1.477601434758372
point 2: 1.909792135285932 1.909792135285932
point 3: 2.416879392936271 2.416879392936271```
Excel (2010, same O/S) rounds all these numbers down a digit earlier than depicted.
__________________

If you can't find time to do it right, how are you going to find time to do it over?
If you don't pass it on, it never happened.
Robots are great, but inspiration is the reason we're here.
Friends don't let friends use master links.

Last edited by GeeTwo : 05-11-2017 at 12:21 PM.
#23
05-11-2017, 12:23 PM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 8,665
Re: Math Quiz 11

Nice work Jared and Jon. Thanks for posting.

Quote:
 Originally Posted by Jared Russell This is an overdetermined trilateration problem (3 constraints, 2 unknowns), which happens frequently due to measurement noise in localization systems (like GPS). As such, the solution depends on what properties you want your residual to have. For one such choice of properties, I happen to know a neat trick that solves this problem elegantly for the particular case where (# constraints) = (# unknowns + 1). Solution here.
Or minimize the sum of the squares of the distance errors, using Maxima's COBYLA.

Quote:
 Originally Posted by Jon Stratis For part B... Is the system actually solvable?
Good question.

Technically, no, because it's overdetermined as Jared (and you) said...

... but, I purposely picked distance values that make all 3 circles have a common intersection point (to several decimal digits), so in that sense it is solvable for a unique solution.

EDIT:

Quote:
 Originally Posted by GeeTwo Point (-.409, .555) works out just fine in gawk
Hey Gus, welcome to the gawk club! It's my go-to tool for data munging and quick math stuff.

Attached Thumbnails

Last edited by Ether : 05-11-2017 at 01:16 PM.
#24
05-11-2017, 03:41 PM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 8,665
Re: Math Quiz 11

Quote:
 Originally Posted by Jared Russell It would also be reasonable to want a (perhaps weighted by distance) least squares solution, but this would require whipping out a non-linear least squares solver.
Change the p4_p3 distance from 2.416879392936271 to 2.6

Now the 3 circles no longer have a common point of intersection, so it becomes an optimization problem.

Maxima can use Powell's COBYLA algorithm to find a "best fit" value based on an objective function that the user can define.

The red boxes are the solution using equal weights for all three distance errors.

The green boxes are the solution for relative weights inversely proportional to the distance.

Attached Thumbnails

#25
05-13-2017, 01:19 PM
 Thayer McCollum I'm over here. Not over Thayer. FRC #0159 (Alpine Robotics) Team Role: Leadership Join Date: Apr 2016 Rookie Year: 2015 Location: Fort Collins Posts: 224
Re: Math Quiz 11

Quote:
 Originally Posted by Ether Change the p4_p3 distance from 2.416879392936271 to 2.6 Now the 3 circles no longer have a common point of intersection, so it becomes an optimization problem. Maxima can use Powell's COBYLA algorithm to find a "best fit" value based on an objective function that the user can define. The red boxes are the solution using equal weights for all three distance errors. The green boxes are the solution for relative weights inversely proportional to the distance.
I'm not nearly as good at math as a lot of you so maybe this doesn't work? I was trying to find an answer that minimized the error using the equal error method. I put the first three points into SolidWorks and then created three distance lines (I didn't use circles) from each point. I then created point four and three more lines connecting each distance line to point four (the error lines). Because I was trying to minimize the error using equal error I set three error lines equal to each other.

Then I didn't know what to do. SolidWorks doesn't (that I know of) have a way to set the length of a line to it's minimum acceptable value. So I just started plugging in numbers, a number larger than the minimum error would be accepted, a number smaller would make the sketch unsolvable. So I started hopping between two numbers, averaging them, getting a new domain, averaging them, etc. I did like 20 iterations of this, eventually working with numbers that were ten decimals long. Then I finally noticed something interesting, as the error became closer to the minimum value the lines became closer and closer to being co-linear.

So I scrapped dimensioning the error lines and just set each error line as co-linear with its respective distance line. This generated the final position of my point four. Which I got to be (-.50036693, .54231098) with an error length of .09102222. This was a different location than Ether's so I tried plugging in his point for equal error. When I did this the minimum error I could get was .118118 (coincidence? I think not).

Ether is a lot smarter than I am, and he actually used math so I'm assuming I just couldn't get SolidWorks to get a smaller error using his point. So what I want to know is what is the error for Ether's calculation and is it actually smaller than mine (I assume so)?
Attached Thumbnails

#26
05-13-2017, 03:42 PM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 8,665
Re: Math Quiz 11

Quote:
 Originally Posted by Thayer McCollum So what I want to know is what is the error for Ether's calculation and is it actually smaller than mine (I assume so)?
Since the 3 circles have no common point of intersection, there is no unique "correct" solution.

The answer you get depends on what you're trying to minimize and what constraints you impose.

As Jared posted earlier in this thread:
Quote:
 Originally Posted by Jared Russell the solution depends on what properties you want your residual to have
You added the constraint that the magnitude of the residuals had to be equal, so you got a different solution. Your solution is valid, given that extra constraint.

I minimized the sum of the squares of the errors (SSE), with no residual equality constraint, so my solution has a smaller SSE than yours.

Attached Thumbnails

Last edited by Ether : 05-13-2017 at 06:31 PM.
#27
05-13-2017, 04:07 PM
 Ether systems engineer (retired) no team Join Date: Nov 2009 Rookie Year: 1969 Location: US Posts: 8,665
Re: Math Quiz 11

Quote:
 Originally Posted by Ether You added the constraint that the residuals had to be equal, so you got a different solution. Your solution is valid, given that extra constraint
Here's the Maxima solution, with your added constraint (red box) that the residuals must be equal in magnitude.

The coordinates of the solution (green box) match yours, and the residuals (orange box) match yours.

Attached Thumbnails

 Thread Tools Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Announcements     User Announcements FIRST     General Forum         FIRST E-Mail Blast Archive     Rumor Mill     Career     Robot Showcase Technical     Technical Discussion     Robotics Education and Curriculum     Motors     Electrical         CAN     Programming         NI LabVIEW         C/C++         Java         Python     Control System         FRC Control System         Sensors     Pneumatics     Kit & Additional Hardware     CAD         Inventor         SolidWorks         Pro ENGINEER / Creo     IT / Communications         3D Animation and Competition         Website Design/Showcase         Videography and Photography         Computer Graphics     National Instruments LabVIEW and Data Acquisition         LabView and Data Acquisition Competition     Awards         Chairman's Award     Rules/Strategy         Scouting         You Make The Call     Team Organization         Fundraising         Starting New Teams         Finding A Team         College Teams     Championship Event     Regional Competitions     District Events     Off-Season Events     Thanks and/or Congrats     FRC Game Design     OCCRA         OCCRA Q&A         OCCRA Programming Other     Unsung FIRST Heroes     Chit-Chat         Games/Trivia             Fantasy FIRST     Car Nack's Corner     College & University Education     Dean Kamen's Inventions     FIRST-related Organizations         Western Region Robotics Forum         Southern California Regional Robotics Forum         FIRST Interactive Rural SupporT         FIRST Scouting Network         FIRSTwiki         The Blue Alliance             Video Archives     FIRST In the News...     FIRST Lego League         Lego Mindstorm Discussion     FIRST Tech Challenge     VEX         VEX Robotics Competition         VEX IQ     Televised Robotics     Math and Science         NASA Discussion ChiefDelphi.com Website     CD Forum Support     Extra Discussion Old Forum Archives     1999     2000     2001

All times are GMT -5. The time now is 11:48 PM.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.

 -- English (12 hour) -- English (24 hour) Contact Us - Chief Delphi - Rules - Archive - Top