Criterion for judging effective parameters

[XinArkh]

Thank you for the work in advance. I have some confusions when reading the code. From path1() to path12(), all the calculated t, u, and v values are judged whether they are all positive:

if t >= 0 and u >= 0 and v >= 0:

Could you give further explanation why this criterion is applied?

[nathanlct]

In the path, I am using Gear.FORWARD or Gear.BACKWARD to specify whether the straight line/turn is going forward (positive t, u or v) or backward (negative t, u or v). In the case of going backwards, the sign of t, u or v is changed in the formula so that they are all positive in the end, hence the condition. If one of t, u or v were negative, it would not respect the path (ie it would go forward instead of backward or the opposite). Note that paths for the other directions are generated from the timeflip/reflect transforms, to test all 48 paths from the 12 implemented ones.

Hope that answers your question!

[XinArkh]

Thank you for your reply! In fact, I tried to cancel this condition before running the code. It turned out more paths appeared in the diagram. So I wonder if the code is incorrectly ignoring some possible paths? In my understanding, the code should find all possible paths and then choose the best one.

[nathanlct]

You seem right, I found a route where adding these missing paths was more optimal. Thank you for finding that! Path lengths shouldn't be negative though, according to the paper, i'll doublecheck the formula when I have some time.

[XinArkh]

In paper the total length is calculated as below for example:

L = |t| + |u| + |v|

I think the absolute value sign here implies that t, u, and v could possibly be negative.

In other cases, the authors even give explicit assumptions that the values can be negative:

As a corroboration, the algorithm implemented in OMPL library uses absolute value as well:

L = fabs(t) + fabs(u) + fabs(v)

However, I do notice that in some other resources the positive condition is mentioned:

Besides, I find that the optimal path length shown in code output is identical with or without the positive condition. (This result seems convincing)

So, I'm now confused about this positive condition too. I did not study further math of the paper to confirm it. I hope you can look into this issue at your convenience. Best wishes!

[XinArkh]

By the way, I created a new repo to study your code and made some minor modifications.

A bug found: .copy() method is a shallow copy, and does not copy the element in the list. copy.deepcopy() should be used instead.

[benjaminbecker]

@XinArkh
I created a pull request that fixes the bugs you discovered. If you have some time, you can have a look at it and see if this is in line with your findings.

[nathanlct]

Besides, I find that the optimal path length shown in code output is identical with or without the positive condition. (This result seems convincing)

@XinArkh I did a quick test and generated paths from a few dozens random points, turns out I actually found some more optimal paths when removing the positivity conditions. I do not currently have time to investigate this more in depth, but it shouldn't hurt to remove the conditions (which @benjaminbecker did, thank you!) since it is still RS paths that are generated in the end (though there might be more duplicates).

[XinArkh]

Thank you for your reply! @benjaminbecker I will see it later.
@nathanlct Did you apply deepcopy before doing the test? I believe this bug (mentioned above) also influence the output.

[benjaminbecker]

For the fix I did not use deepcopy, but I create a new list here and here.

I also wrote a test which addresses the bug introduced by using copy here and here.

[XinArkh]

@benjaminbecker I have read your repo and believe it is an elegant way to solve the problems mentioned above. I also learned some cool Pythonic coding styles from it. Thanks again!

By the way, I've noticed an interesting fact that the Length parameters in the optimal path are always positive, even though negative values are allowed to appear. Further investigations are still required on how this is ensured.

[nathanlct]

@XinArkh By length, do you mean PathElement.param? If so, seems normal to me that a length remains positive, as the sign is handled through the forwards/backwards gear.

[XinArkh]

@nathanlct Yes, what I mean is param. I did notice that you manually adjusted the gear to keep the value positive.(I mistook you for benjaminbecker and replied wrongly, sorry lol) However, what is interesting is that I found that this phenomenon still holds in my repo (where I didn't limit the sign). To be specific, I printed all possible paths and the optimal path, and every time there occurs positive and negative lengths in the former ones and only positive lengths in the latter one.

An example is shown below (p1=[-6, -7, 0], p2=[-6, 0, 3.14]):

All paths:
[[{ Steering: left  Gear: forward   Length: 1.6 }, { Steering: straight Gear: forward   Length: 5.01 }, { Steering: left    Gear: forward   Length: 1.4 }], [{ Steering: left   Gear: backward  Length: 1.54 }, { Steering: straight    Gear: backward  Length: 5.01 }, { Steering: left    Gear: backward  Length: 1.74 }], [{ Steering: right Gear: forward   Length: -1.56 }, { Steering: straight   Gear: forward   Length: 8.99 }, { Steering: right   Gear: forward   Length: -1.44 }], [{ Steering: right    Gear: backward  Length: -1.59 }, { Steering: straight   Gear: backward  Length: 8.99 }, { Steering: right   Gear: backward  Length: -1.7 }], [{ Steering: left  Gear: forward   Length: 1.84 }, { Steering: straight    Gear: forward   Length: 6.7 }, { Steering: right    Gear: forward   Length: -1.16 }], [{ Steering: left Gear: backward  Length: 1.88 }, { Steering: straight    Gear: backward  Length: 6.7 }, { Steering: right    Gear: backward  Length: -1.4 }], [{ Steering: right Gear: forward   Length: -1.3 }, { Steering: straight    Gear: forward   Length: 6.72 }, { Steering: left    Gear: forward   Length: 1.7 }], [{ Steering: right  Gear: backward  Length: -1.26 }, { Steering: straight   Gear: backward  Length: 6.72 }, { Steering: left    Gear: backward  Length: 2.02 }], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [{ Steering: left  Gear: forward   Length: -2.7 }, { Steering: right   Gear: backward  Length: 1.57 }, { Steering: straight    Gear: backward  Length: 2.6 }, { Steering: left Gear: backward  Length: 2.15 }], [{ Steering: left  Gear: backward  Length: -2.76 }, { Steering: right  Gear: forward   Length: 1.57 }, { Steering: straight    Gear: forward   Length: 2.6 }, { Steering: left Gear: forward   Length: 1.81 }], [{ Steering: right Gear: forward   Length: 0.24 }, { Steering: left    Gear: backward  Length: 1.57 }, { Steering: straight    Gear: backward  Length: 6.77 }, { Steering: right   Gear: backward  Length: -1.47 }], [{ Steering: right    Gear: backward  Length: 0.21 }, { Steering: left    Gear: forward   Length: 1.57 }, { Steering: straight    Gear: forward   Length: 6.77 }, { Steering: right   Gear: forward   Length: -1.22 }], [{ Steering: left Gear: forward   Length: 2.01 }, { Steering: straight    Gear: forward   Length: 2.6 }, { Steering: right    Gear: forward   Length: 1.57 }, { Steering: left    Gear: backward  Length: -2.56 }], [{ Steering: left Gear: backward  Length: 1.95 }, { Steering: straight    Gear: backward  Length: 2.6 }, { Steering: right    Gear: backward  Length: 1.57 }, { Steering: left    Gear: forward   Length: -2.9 }], [{ Steering: right Gear: forward   Length: -1.33 }, { Steering: straight   Gear: forward   Length: 6.77 }, { Steering: left    Gear: forward   Length: 1.57 }, { Steering: right   Gear: backward  Length: 0.1 }], [{ Steering: right  Gear: backward  Length: -1.36 }, { Steering: straight   Gear: backward  Length: 6.77 }, { Steering: left    Gear: backward  Length: 1.57 }, { Steering: right   Gear: forward   Length: 0.35 }], [{ Steering: left  Gear: forward   Length: 3.12 }, { Steering: right   Gear: backward  Length: 1.57 }, { Steering: straight    Gear: backward  Length: 4.99 }, { Steering: right   Gear: backward  Length: -1.69 }], [{ Steering: left Gear: backward  Length: -3.12 }, { Steering: right  Gear: forward   Length: 1.57 }, { Steering: straight    Gear: forward   Length: 4.99 }, { Steering: right   Gear: forward   Length: -1.45 }], [{ Steering: right    Gear: forward   Length: -0.02 }, { Steering: left   Gear: backward  Length: 1.57 }, { Steering: straight    Gear: backward  Length: 5.01 }, { Steering: left    Gear: backward  Length: 1.73 }], [{ Steering: right Gear: backward  Length: 0.02 }, { Steering: left    Gear: forward   Length: 1.57 }, { Steering: straight    Gear: forward   Length: 5.01 }, { Steering: left    Gear: forward   Length: 1.41 }], [{ Steering: left  Gear: forward   Length: 1.55 }, { Steering: straight    Gear: forward   Length: 4.99 }, { Steering: left    Gear: forward   Length: 1.57 }, { Steering: right   Gear: backward  Length: -0.12 }], [{ Steering: left Gear: backward  Length: 1.59 }, { Steering: straight    Gear: backward  Length: 4.99 }, { Steering: left    Gear: backward  Length: 1.57 }, { Steering: right   Gear: forward   Length: 0.12 }], [{ Steering: right Gear: forward   Length: -1.59 }, { Steering: straight   Gear: forward   Length: 5.01 }, { Steering: right   Gear: forward   Length: 1.57 }, { Steering: left    Gear: backward  Length: -2.98 }], [{ Steering: right    Gear: backward  Length: -1.55 }, { Steering: straight   Gear: backward  Length: 5.01 }, { Steering: right   Gear: backward  Length: 1.57 }, { Steering: left    Gear: forward   Length: 2.98 }], [{ Steering: left  Gear: forward   Length: -2.87 }, { Steering: right  Gear: backward  Length: 1.57 }, { Steering: straight    Gear: backward  Length: 2.7 }, { Steering: left Gear: backward  Length: 1.57 }, { Steering: right   Gear: forward   Length: 0.41 }], [{ Steering: left  Gear: backward  Length: -2.83 }, { Steering: right  Gear: forward   Length: 1.57 }, { Steering: straight    Gear: forward   Length: 2.7 }, { Steering: left Gear: forward   Length: 1.57 }, { Steering: right   Gear: backward  Length: 0.17 }], [{ Steering: right Gear: forward   Length: 0.27 }, { Steering: left    Gear: backward  Length: 1.57 }, { Steering: straight    Gear: backward  Length: 2.72 }, { Steering: right   Gear: backward  Length: 1.57 }, { Steering: left    Gear: forward   Length: -3.01 }], [{ Steering: right    Gear: backward  Length: 0.31 }, { Steering: left    Gear: forward   Length: 1.57 }, { Steering: straight    Gear: forward   Length: 2.72 }, { Steering: right   Gear: forward   Length: 1.57 }, { Steering: left    Gear: backward  Length: -2.69 }]]

Optimal path:
[{ Steering: right  Gear: backward  Length: 0.02 }, { Steering: left    Gear: forward   Length: 1.57 }, { Steering: straight    Gear: forward   Length: 5.01 }, { Steering: left    Gear: forward   Length: 1.41 }]

[nathanlct]

So what you're saying is that if you generate random points (without the missing deepcopy mentioned above), you never get more optimal paths by removing the >0 conditions?

[nathanlct]

@XinArkh

[XinArkh]

So what you're saying is that if you generate random points (without the missing deepcopy mentioned above), you never get more optimal paths by removing the >0 conditions?

@nathanlct I think there are slight differences. We should remove >0 condition for sure. (I guess) The key point is that timeflip() and reflect() would generate a set of derived paths related to the calculated path. I think one of these derived paths contributes to the optimal path, which has a positive length value.

[nathanlct]

@XinArkh Got it. I'll read through the paper more carefully when I get some time. In the meantime I merged @benjaminbecker's fixes, and we shouldn't be missing any optimal path by removing the conditions, worst case we get duplicates.