Does the shortest path from an initial point to a goal point, in an environment with obstacles, also gives the minimum sum of turning angles?

It doesn't seem to be obvious, but I couldn't come up with a counter example! If it is indeed true, is there a proof which states that?

Note: the shortest path means minimum sum of Euclidean distance. Additional context: I was using A* on a visibility graph to find the optimal path. Two different cost functions were used. 1. Just the Euclidean distance and 2. Euclidean distance + theta, turning angle, multiplied by some constant.

Shortest path, which also gives the minimum sum of turning angles

  • 1
    $\begingroup$ I don't think so. I was able to generate a setting in which the turning angles through the shortest path was 180 degrees, but through the longest path was less. I'll try to make an image and show you $\endgroup$ – Michael Stachowsky Dec 9 '16 at 19:06

The following image, constructed by the original poster, demonstrates that the claim is false. The shortest path (green) has a larger total turning angle than the longer path (red).

enter image description here

  • $\begingroup$ Please see this link imgur.com/a/HXR27 The green line appears to be the shortest path and it also gives the minimum sum of turning angles. Am I missing something? Also, the shortest path is aways through the vertices of the obstacle. $\endgroup$ – Saurav Dec 9 '16 at 19:20
  • $\begingroup$ I made the image imprecisely. If you move the square down so that it touches the rectangle, then I believe my turning angles are still correct. I know that the shortest path should be through the vertices, but I lack the paint skills to do it :-P $\endgroup$ – Michael Stachowsky Dec 9 '16 at 19:23
  • $\begingroup$ Great! I think that works. I shall double check and get back. $\endgroup$ – Saurav Dec 9 '16 at 19:27
  • $\begingroup$ I've edited the figure to demonstrate $\endgroup$ – Michael Stachowsky Dec 9 '16 at 19:27
  • 1
    $\begingroup$ You can use this imgur.com/a/2Zdx7 image for a clearer answer and I shall accept it. $\endgroup$ – Saurav Dec 9 '16 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.