• Advertisement
Sign in to follow this  

3D Dubins over-estimate the path cost by an extremely small fraction

This topic is 567 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

It must be floating point creep.

But how do I get rid of it without affecting the results?

sol->dist_zs_ws = std::sqrtf((2 * sol->R * PI) * (2 * sol->R * PI) + (sol->p_s.y - sol->w_s.y) * (sol->p_s.y - sol->w_s.y));
sol->dist_ws_wi = D3DXVec3Length(&(sol->w_s - sol->w_l));
sol->dist_wi_wl = 0;
sol->dist_wl_we = std::sqrtf((2 * sol->R * PI) * (2 * sol->R * PI) + (sol->w_l.y - sol->w_e.y) * (sol->w_l.y - sol->w_e.y));

The results often off by 0.001 - 0.002 which will knock off certain suitable opened node candidate by 1 to 3 places.

I have decreased the PI from 3.1416 to 3.14, but it is still off by 0.001xxx

I don't want to change it to integers because there would be a lot of ties in the end.

Thanks

Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement
I was confused by your first post because I am not familiar with the algorithm where your code is being used. But I am more confused after the second post. Do you really think your problem has anything to do with how you display numbers as text?

Share this post


Link to post
Share on other sites

SetPrecision only affects output, not how things are calculated.

Basically you can use it to print 2.4 instead of 2.400100, but it won't change the internal representation of the value.

 

EDIT: Somewhat ninjaed by Álvaro.

Edited by Lactose!

Share this post


Link to post
Share on other sites

I have decreased the PI from 3.1416 to 3.14, but it is still off by 0.001xxx

 
Using 3 digits of precision won't help.  If you've got it in a library use pi loaded directly into the register.  If that's not possible use a constant such as M_PI if it exists in your math libraries. 
 
Instead, consider what you are doing very carefully:

std::sqrtf((2 * sol->R * PI) * (2 * sol->R * PI) + (sol->p_s.y - sol->w_s.y) * (sol->p_s.y - sol->w_s.y));

 
 
I don't know your scale, but consider that floating point has roughly six decimal digits of precision.  (See FLT_DIG for your system-specific value).  Values get converted into the correct scale as yo do the math.  
 
So for example:
 
This:  123456 + 12.3456
 
needs to get the floating point alignment and so this:
   123456.
+      12.3456
 
becomes
   123456.
+  000012.3456

giving 123468.<?>, not 123468.3456 exactly, the last value becomes rounding error.

Similarly for multiplication...  

 

Your segment of this: (2 * sol->R * PI)

 

looks like this to me: 

  2

* 695700099 (radius of our sun)

* 3.14159
 

is actually this:

          2

* 695700???

*         3.14159

 

that after floating point adjustment becomes this:

  000000???

* 695700???

* 000000???.????? 

 

or, since they are carried out sequentially, becomes this:

  000000002

* 695700099

===========

          0

* 000000003.14159 

===========

          0

 
or maybe this:

  000000002

* 695700099

===========

  695700099

* 000000003.14159 

===========

  695700099

 

or maybe something else entirely.

 

Once you've lost scale and you've done a math operation that blows away your precision, all bets are off.  Maybe you got lucky and had a bit or two that happened to cover your range, or maybe you didn't.

 

 

There are some actions you can take to ensure your numbers don't get large enough to blow away your precision, but they are dependent on the operation you are doing.  
 
For one example, averaging a ton of numbers instead of summing them all into a range that exceeds precision, you can maintain both the accumulated value and a count of values accumulated so far so you never break precision.  In that case it is avg += (x/n) - (avg/n); n++;  With that slight change the values you are working with are always a fraction of the original and thus always within the source precision. Unfortunately sometimes even with that, the optimizer will think it knows better than the programmer and attempt to rewrite the math, so this type of thing needs to be verified in assembly and sometimes have specific optimizations turned off around that code.
 
In your case, you'll need to review your math and make sure it stays inside your desired precision.

Share this post


Link to post
Share on other sites

Your segment of this: (2 * sol->R * PI)



looks like this to me:

2

* 695700099 (radius of our sun)

* 3.14159


is actually this:

2

* 695700???

* 3.14159



that after floating point adjustment becomes this:

000000???

* 695700???

* 000000???.?????



or, since they are carried out sequentially, becomes this:

000000002

* 695700099

===========

0

* 000000003.14159

===========

0


What are you talking about? Your description of the loss of precision after a sum was correct, but products don't work this way at all. If floating-point products were implemented this way, nothing would work.

Share this post


Link to post
Share on other sites

Aren't these figures irritating?

But as usual, the figures on the left which are based on 2D Dubins works perfectly fine.

But on the right by 3D Dubins won't? :) Check everything else, the setups are the same

My goodness....

Tried it for 2 days already, but never give up....

Thanks everybody...

 

2D: 1.5812 3D: 1.5823
2D: 1.58114 3D: 1.5823
2D: 0.707122 3D: 0.7083
2D: 0.707437 3D: 0.708
2D: 0.707437 3D: 0.708
2D: 1.58114 3D: 1.5823
2D: 0.707437 3D: 0.708
2D: 1.58114 3D: 1.5823
2D: 0.707122 3D: 0.7083
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00011 3D: 1.001
2D: 1 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.001
2D: 1.00033 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00033 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00063 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1.00011 3D: 1.0012
2D: 1 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012
2D: 1.00002 3D: 1.0012
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00033 3D: 1.0011
2D: 1.00002 3D: 1.0012

Share this post


Link to post
Share on other sites
Try using doubles and a more correct approximation to pi (like std::atan(1.0)*4.0). If that doesn't work, then your problem is not lack of precision.

With my non-understanding [and your non-explaining] of what you are doing, that's the only advice I can give you.

Share this post


Link to post
Share on other sites

There is a strange behaviour when only swapping for the length of the 2D Dubins with the length of the 3D Dubins as the path cost.

The difference is 0.001, I confirm that this must be the case because when I swap the 2D Dubins with 3D, the pathfinder goes into the wall.

I just swap one function for the path cost from 2D to 3D. When 2D is in effect, it will search other available open space and it is very smooth.

When 3D dubins is in use, it will go into the wall, and continue on searching some other useless tiles that aren't in the correct direction until

it eventually hit the destination and start to converge.....

 

OK, I see...

The 3D Dubins library I wrote must have some bugs, because the tile size is 0.9m, anything as small as 0.001 can make a substantial difference

 

Thanks

Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites

Okay, problem solved, but I can't sample the path because I can't determine the lengths of individual segments.

 

http://www.et.byu.edu/~beard/papers/preprints/BeardMcLain__.pdf

 

 

https://github.com/unr-arl/DubinsAirplane

 

See Page 18,

Why the L isn't the sum of (No intermediate, just plain LSL turn)

sol->dist_zs_ws = std::sqrtf((2 * sol->R * PI) * (2 * sol->R * PI) + (sol->p_s.y - sol->w_s.y) * (sol->p_s.y - sol->w_s.y));
sol->dist_ws_wi = D3DXVec3Length(&(sol->w_s - sol->w_l));
sol->dist_wi_wl = 0;
sol->dist_wl_we = std::sqrtf((2 * sol->R * PI) * (2 * sol->R * PI) + (sol->w_l.y - sol->w_e.y) * (sol->w_l.y - sol->w_e.y));
Edited by lucky6969b

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement