Re: BUG?! Paths not actually shortest paths!?

[Andrew Byrd]

On 05/17/2013 04:07 PM, Avi Flamholz wrote:
> I checked. My test OSM file contains no restriction relations. So turn
> restrictions do not explain the violation of the triangle inequality in
> this case. Any other theories?

I was using the terms "turn restrictions" and "turn costs"
interchangeably. I should have said "turn costs" which is the more
general term: a forbidden turn is just a special case of a turn cost
where the cost is infinite. Though I mentioned the case where a turn is
disallowed, the triangle inequality also does not hold for finite turn
costs.

Imagine the simplest example: a graph G with three nodes A,B,C and two
edges AB and BC, with a finite positive turn cost from edge AB to edge
BC through node B. The shortest path from A to C necessarily includes a
turn cost that is not present in the subpaths from A to B and B to C. It
has a higher cost than the two subpaths combined.

> On the issue of double/long the problem goes like this: there is at
> lease one round-up operation on every edge transition. So if you have a
> shorter path that covers more edges it may appear longer if the duration
> difference between the two paths is small enough. I don't know whether
> or not this is actually happening, but I suspect that it is. Any ideas
> about how to check? Any reason not to simply switch to doubles and round
> at the end to avoid the loss of precision?

This is correct, there is a round-up operation on any traversal that
does not give an integer result. If two paths have exactly equal
physical lengths, slopes etc. but one has more edges, it will have a
higher cost.

I never worried about this too much since our speeds, the effects of
slopes on traversal time, etc. are all assumptions and there are so many
details we do not even model that one-second resolution seemed adequate.
Consider that every place an extra fraction of a second is inserted is
an intersection that may or may not have a stop light/sign, a curb cut,
cross traffic, a crosswalk, etc. It is true though that this could add
up to several minutes' difference over a longer path, and it's a stretch
to defend the number of edges affecting the relative cost of a path.

Does this ever actually tangibly affect routing results?

-Andrew

> On Thu, May 16, 2013 at 6:29 PM, Andrew Byrd <and...@fastmail.net
> <mailto:and...@fastmail.net>> wrote:
>
> There may be additional reasons for what you have observed, but the
> primary reason is that the triangle inequality does not hold in spaces
> with turn restrictions. There is no guarantee that the transition from
> the final edge of path AB to the initial edge of path BC is allowed. By
> breaking the path in two at B, you could avoid a turn restriction.
>
> A long and a double are both 64 bits in Java. I suppose we use longs for
> times because this is a standard representation of time (seconds since
> the epoch), and it's easier to reason about integer data types. Despite
> looking continuous floating point types are of course internally
> discrete and can misbehave.
>
> -Andrew
>
> On 05/16/2013 11:25 PM, Avi Flamholz wrote:
> > Hey David, Andrew --
> >
> > I'm seeing a bug where OTP doesn't obey the triangle inequality. Some
> > questions about this:
> >
> > 1) I've set all the reluctance terms to 1.0, so I'd expect that
> any path
> > that OTP returns is the shortest duration path in addition to
> being the
> > minimum weight path. Does this sound right to you?
> > 2) I have a test which checks the triangle inequality for a short
> path A
> > -> C in a small chunk of Manhattan (in SOHO). The graph has 70
> vertices,
> > and for all vertices B in the graph (!= A, C) I test that the path
> > A->B->C is longer or the same length as A->C if it exists at all. This
> > test fails for all traversal modes, but passes when I set all turn
> costs
> > to 0. I know that turn costs break a vanilla Dijkstra implementation,
> > but do they also break your edge-based A* search?
> > 3) I have a test where I set up a server with a map of Manhattan and
> > check the triangle inequality for a bunch of random A,B,C triples on
> > that map. (The server in question has 0 turn costs and all reluctance
> > terms set to 1.0). I still see some violations of the triangle
> > inequality, but the discrepancies are very small (1-3 seconds). Could
> > this be due to the rounding up of time to long that happens in the
> > traversal code? Why did you guys choose to represent time as a long
> > internally instead of representing it as a double and rounding at the
> > end? Saving memory?
> >
> > Thanks for any insight you have got.
> > Avi
>
>

[Andrew Byrd]

On 05/19/2013 11:13 PM, Avi Flamholz wrote:
> Andrew -- I think we are in agreement - turn costs/restrictions break
> the triangle inequality *iff* you don't continue the B->C search from
> the last edge of the A->B search. However, since I did this, the
> triangle inequality test seems to pass.

Good to know that change allows the triangle inequality test to pass and
supports this explanation. Yes, sounds like we were indeed in agreement
except for a reversal of perspective. A restriction is placed on the B-C
search that is not imposed on the A-B search, so I was thinking "The
triangle inequality does not hold in spaces with turn costs, /unless/..."

> The rounding does seem to cause weights to differ from durations by
> several seconds even when all reluctance terms are 1.0. This makes it
> harder to write high level tests of the routing code that check whether
> it preserves various invariants (e.g. weight ~= duration when
> reluctances are 1.0, etc.). Also, it seems a shame to round when you
> don't have to.

I really appreciate the kinds of tests you are adding to OTP, and in
principle I agree with this argument, especially considering that the
data types already in use can provide much higher precision. I was just
recalling that whatever precision or representation is chosen, there
will still be round-off error... we will just be able to use a smaller
epsilon in comparisons.

However, it looks like Java always uses the "round to nearest" mode in
floating point arithmetic [1], which should spread the error around and
ensure that the magnitude of the error is not a function of number of edges.

_Andrew

[1] http://docs.oracle.com/javase/specs/jls/se7/html/jls-4.html#jls-4.2.4

> On Sat, May 18, 2013 at 9:02 PM, Andrew Byrd <and...@fastmail.net