roundabout uturn avoided (Car Mode)

[Nawaz Khurshid]

Hi,

Its seems that OTP for some reason avoid Uturn on same street using roundabouts.

In attached pic(plan1.png), otp suggest a wrong path by avoiding a Uturn in roundabout. The expected path is show in blue i.e. to make Uturn from roundabout.

In attached pic (osm.png) can be seen the permission. The street (Via Bassano) is two way street

with two lanes. 

If we plan from 'Via Bassano' to 'Via San Vito', roundabout is utilized correctly(plan2.png), but not in case of traversing back on the same street.

OSM file can be downloaded from[1]

Please let us know what could be missing in our osm to allow Uturn on same street.

Thanks

Nawaz

[1] https://drive.google.com/file/d/0B9uCt_cuOhbsM1Vyempyd2VqWm8/view?usp=sharing

[Nawaz Khurshid]

I forgot to attach the pics in last email.

Sorry for the inconvenience.

Regards

Nawaz

[MikeN]

I'm not an expert in the algorithm implementation, but I'd suspect that the "U-Turn" model hasn't been implemented for Car Mode.   There is likely some logic that prevents path retrace, and that gives the results seen here.

[Nawaz Khurshid]

Thanks Mike for the reply.

If this is the case, I feel there is strong need to implement this model, since with the current implementation the only way to have you U turn is to add another parallel street, since 'OTP' is not traversing to-and-fro on same street segment, even if it is the shortest and quickest path.

Can anyone please point me to the relevant classes to debug this issue?

Regards

--
You received this message because you are subscribed to the Google Groups "OpenTripPlanner Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opentripplanner...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Laurent GRÉGOIRE]

On 27 November 2015 at 14:57, Nawaz Khurshid <nawa...@gmail.com> wrote:
> If this is the case, I feel there is strong need to implement this model,
> since with the current implementation the only way to have you U turn is to
> add another parallel street, since 'OTP' is not traversing to-and-fro on
> same street segment, even if it is the shortest and quickest path.

This is strange, this should work. AFAIK OTP does not indeed handle
car u-turn *in the middle of a street segment* (as a full navigation
device-like road planner sometimes do, for handling the case where the
current direction of travel at the time of planning is opposite to the
shortest path initial direction), but in your case it should give you
the correct path. Are you sure there is no turn-right restriction at
the round-abount exit turning on Via Bassano?

--Laurent

[Nawaz Khurshid]

Hi Laurent,

Thanks for your reply.

We don't have any turn restriction at the roundabout(Via Bassano). I have attached herewith a png(no-restriction-associated.png), showing the properties of roundabout(Via Bassano). 

It is not the only place, where this issue occur. There are other places with same issues for e.g. please see plan3.png (OTP should return plan as depicted by blue line, traversing back-and-forth on same street segment). 

I have attached also the build.config and router.config file used in build and run time phases respectively. Perhaps we are missing something in the configuration.

We are using 0.15.x version of OTP.

Please let me know in case.

Thanks

[Laurent GRÉGOIRE]

My mistake, this will not work indeed, OTP assume for car mode a
simple model (identical to walk mode), keeping a single state per
vertex. However in car routing the state at the entrance/exit of the
round-about are different (in car mode we should distinguish the
direction of travel). I did not look further into this but AFAIK the
solution would need to keep for each vertex a distinct state for each
(outgoing?) direction (=outgoing edge). Given the various combination
of turn restrictions, it may not be trivial to implement, especially
as this may have an impact on some other places as well. Perhaps
somebody did implement / looked into this before?

HTH,

--Laurent

[Laurent GRÉGOIRE]

On 30 November 2015 at 16:20, Laurent GRÉGOIRE

<laurent....@gmail.com> wrote:
> direction of travel). I did not look further into this but AFAIK the
> solution would need to keep for each vertex a distinct state for each
> (outgoing?) direction (=outgoing edge).

I looked a bit and the culprit seems here (DominanceFunction L~70):

// Are the two states arriving at a vertex from two different
directions where turn restrictions apply?
if (a.backEdge != b.getBackEdge() && (a.backEdge instanceof
StreetEdge)) {
if (!
a.getOptions().getRoutingContext().graph.getTurnRestrictions(a.backEdge).isEmpty())
{
return false;
}
}

It seems that this condition is not sufficient, in your case there is
no turn restriction but we still have to keep two states for this
particular vertex (two directions of travel). I quick and dirty fixe
(but highly inefficient) would be to replace by this code (not
tested):

if (a.backEdge != b.getBackEdge() && (a.backEdge instanceof
StreetEdge)) {
return false;
}

You can experiment with that and see if the problem comes away, before
making any fix.

HTH,

--Laurent

[Nawaz Khurshid]

Yes you are correct!

With this fix the problem is resolved and OTP give efficient plans by traversing on same street segment making U turns. Please refer to pictures from some examples.

I will make more testing in this week. Please let me know in future about the plan to push this fix on github.

Thanks...

Nawaz

[Laurent GRÉGOIRE]

On 30 November 2015 at 17:17, Nawaz Khurshid <nawa...@gmail.com> wrote:
> Yes you are correct!

Cool.

> I will make more testing in this week. Please let me know in future about
> the plan to push this fix on github.

A tentative fix:
https://github.com/laurentg/OpenTripPlanner-plannerstack/tree/car-turn-dominance

It should be more solid as we dynamically determine the set of
possible outgoing edges for each state/backEdge, handling
turn-restrictions and U-turns.

Can you test it regarding performances? If it slower than the simpler
"always return false", we could revert to a simpler version. I made a
small test here, and most of the outgoing sets are indeed differents
if the incoming directions are distincts... So I'm dubious about the
more complex code version. But anyway, we can keep the "ifDriving()"
test, it should optimize the code a bit for walk/bike modes.

HTH,

--Laurent

[Andrew Byrd]

Hi Laurent and Nawaz,

Thanks for looking into this problem. I’m concerned that removing the check for turn restrictions could produce a lot more branching and make the search much slower.

Please create a Github issue to track this issue and do a few checks on street routing speed before submitting a pull request. And as always please add or update comments in the code explaining the conditional expression (under which conditions we need multiple states at a vertex, including roundabout exits).

Andrew

[Laurent GRÉGOIRE]

On 1 December 2015 at 09:12, Andrew Byrd <and...@fastmail.net> wrote:
> Thanks for looking into this problem. I’m concerned that removing the check for turn restrictions could produce a lot more branching and make the search much slower.

Indeed it does: you now have a state per different incoming street
edge. But I'm afraid that in order to handle all the cases we need to
handle different states per direction, regardless of
turn-restrictions, as U-turn at an intersection is by default
forbidden. See newly-created issue 2177 [1].

The change make the LinkingTest::testStopsLinkedIdentically unit test
fails, it may be a side effect as returning false more often should
(apart from performance) be always better than not. Could it be
related to some other issues about path parsing removal?

As a side-node, I've noticed that the U-turn restriction does apply
for every mode of travel (StreetEdge, L300), shouldn't it be forbidden
only for car mode?

[1] https://github.com/opentripplanner/OpenTripPlanner/issues/2177

HTH,

--Laurent

[Nawaz Khurshid]

Thanks for the update! Just to add here.

--As a side-node, I've noticed that the U-turn restriction does apply

for every mode of travel (StreetEdge, L300), shouldn't it be forbidden
only for car mode?

I think this information should be read from turn restriction tags for e.g. except=bicycle. If it is empty should apply for every mode of travel.

Please correct if I am missing something.

Regards

Nawaz

[Laurent GRÉGOIRE]

On 1 December 2015 at 10:22, Nawaz Khurshid <nawa...@gmail.com> wrote:
> I think this information should be read from turn restriction tags for e.g.
> except=bicycle. If it is empty should apply for every mode of travel.

I'm not sure bikes always follow turn restriction rules :) Also the
issue is whether OSM turn-restrictions always correctly specify the
mode of travel they apply to, mapper probably simply assume "car".
Anyway, for walk mode turn restrictions probably don't apply. I guess
we should relax them at least for walk.

In theory, theory and practice are the same. In practice, they are not :)

--Laurent

[Nawaz Khurshid]

Just to update

Now while building graph, I can see a NPE[1]. Any hint?

[1]

10:51:52.601 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766805

10:51:52.601 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766800

10:51:52.623 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3851444

10:51:52.625 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766727

10:51:52.626 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766751

10:51:52.627 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766747

10:51:52.628 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766758

10:51:52.629 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766757

10:51:52.630 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766752

10:51:52.630 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766767

10:51:52.631 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766765

10:51:52.632 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766760

10:51:52.633 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766773

10:51:52.634 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3766770

10:51:52.636 WARN (OSMDatabase.java:932) Unable to process public transportation relation 3287567

10:51:52.637 INFO (OSMDatabase.java:350) Intersecting unconnected areas...

10:52:01.759 INFO (OSMDatabase.java:563) Created 13 virtual intersection nodes.

10:52:01.761 INFO (OpenStreetMapModule.java:199) Building street graph from OSM

10:52:40.147 INFO (OpenStreetMapModule.java:409) Building visibility graphs for walkable areas.

10:52:40.722 WARN (Graph.java:902) graph contains no agencies (yet); API request times will be interpreted as GMT.

Exception in thread "main" java.lang.NullPointerException

        at org.opentripplanner.routing.spt.DominanceFunction.betterOrEqualAndComparable(DominanceFunction.java:72)

        at org.opentripplanner.routing.spt.ShortestPathTree.add(ShortestPathTree.java:143)

        at org.opentripplanner.routing.algorithm.GenericDijkstra.getShortestPathTree(GenericDijkstra.java:119)

        at org.opentripplanner.graph_builder.module.osm.WalkableAreaBuilder.pruneAreaEdges(WalkableAreaBuilder.java:284)

        at org.opentripplanner.graph_builder.module.osm.WalkableAreaBuilder.build(WalkableAreaBuilder.java:239)

        at org.opentripplanner.graph_builder.module.osm.OpenStreetMapModule$Handler.buildWalkableAreas(OpenStreetMapModule.java:414)

        at org.opentripplanner.graph_builder.module.osm.OpenStreetMapModule$Handler.buildGraph(OpenStreetMapModule.java:268)

        at org.opentripplanner.graph_builder.module.osm.OpenStreetMapModule.buildGraph(OpenStreetMapModule.java:200)

        at org.opentripplanner.graph_builder.GraphBuilder.run(GraphBuilder.java:153)

        at org.opentripplanner.standalone.OTPMain.run(OTPMain.java:113)

        at org.opentripplanner.standalone.OTPMain.main(OTPMain.java:88)

[Laurent GRÉGOIRE]

On 1 December 2015 at 10:54, Nawaz Khurshid <nawa...@gmail.com> wrote:
> Now while building graph, I can see a NPE[1]. Any hint?

You can try with the updated version. I reverted back the more complex
computation of determining if the outgoing edges sets are different:
most of the time they are, so this optimization is probably pointless
(on top of probably causing the NPE you see).

HTH,

--Laurent

[Nawaz Khurshid]

Ok! seems fine.

[Nawaz Khurshid]

Hi Laurent,

While testing with the fix(as in thread above) related to u turn avoidance , i figure out an issue. Please refer to attached pic.

I have a u turn restriction from 'Viale Verona' to 'Via Malpensada'[see restriction-issue-dec11.png] . So the turn is avoided in the plan but some how it allows u turn even before the roundabout.

Attached herewith is the DominanceFunction.java class which is used during build phase. Also the 'osm' tile can be downloaded from [1]

Please let me know in case I am missing something.

regards

Nawaz

[1] https://drive.google.com/file/d/0B9uCt_cuOhbseDk1YzF2VVkxYUE/view?usp=sharing

[Laurent GRÉGOIRE]

Hi Nawaz,

On 11 December 2015 at 17:45, Nawaz Khurshid <nawa...@gmail.com> wrote:
> I have a u turn restriction from 'Viale Verona' to 'Via Malpensada'[see
> restriction-issue-dec11.png] . So the turn is avoided in the plan but some
> how it allows u turn even before the roundabout.

That's a bit strange. Direct U-turn is in theory forbidden in
StreetEdge::doTraverse [1], you can check if this code is indeed
working for your example when traversing the offending street.

HTH,

[1] https://github.com/opentripplanner/OpenTripPlanner/blob/master/src/main/java/org/opentripplanner/routing/edgetype/StreetEdge.java#L299

--Laurent

[Nawaz Khurshid]

Hi Laurent,

One interesting behavior that I have noticed in this regard is that If i build graph without GTFS, the problems goes away(see senza-gtfs-plan.png). Direct U turn is forbidden in this case.

However, If I build the graph using GTFS having bus on this street, the issue persist (gtfs-plan.png). I also tried deleting the osm relations for bus on this street segments but didnt work.

Perhaps this gives a hint about the issue. Attached herewith are the two graphs (with and without GTFS)

I did check that doTraverse() check are being taken in to account during planning but still debugging it more.

Regards

Nawaz

[GraphWithGTFS] https://drive.google.com/file/d/0B9uCt_cuOhbsal9VdnJHWnRtNVE/view?usp=sharing

[GraphWithoutGTFS]  https://drive.google.com/file/d/0B9uCt_cuOhbsMEh0U2ZWNHQwMTA/view?usp=sharing

[osm] https://drive.google.com/file/d/0B9uCt_cuOhbscDc1TjE0ZUE5NnM/view?usp=sharing

[Laurent GRÉGOIRE]

Hi Nawaz,

On 17 December 2015 at 11:34, Nawaz Khurshid <nawa...@gmail.com> wrote:
> One interesting behavior that I have noticed in this regard is that If i
> build graph without GTFS, the problems goes away(see senza-gtfs-plan.png).
> Direct U turn is forbidden in this case.

According to what you describe, it smells like a problem with stop to
street linking. It could be that some edges are used by the car
traversal to make the u-turn, or that those extra edges do have an
influence on the u-turn prevention (but the latter seems improbable as
you say in your tests). On your screenshot I can see that the u-turn
is made at the exact point where there is a stop alongside the road.
Can you make sure the stop linking edges are never used in car mode?
They should never be traversed.

Another point: on your screenshot it seems there is small discrepancy
between the road geometry OTP display and the map background (on Viale
Verona), is is due to an old OSM you use? I do not think this is a
problem but you'd better check just in case.

HTH,

--Laurent

[Nawaz Khurshid]

Hi Laurent,

You are right in the sense that appears to be problem of stop linking to road.

When I inspect the graph using visualizer it appears that a you turn is permitted from 

node(267587827) to stop link created (split 1 at link for 12_459_12) as can be seen in image.

It proves that stop linking edges are being used in car mode. I can debug further.

About the discrepancy in osm, you are right. I did modify the osm a bit to try different possibilities, however, it seems to be useless since it has nothing to do with the issue.

Please let me know in case something is unclear or missing.

Thanks a lot for very useful feedbacks.

Regards

Nawaz

[Laurent GRÉGOIRE]

On 17 December 2015 at 16:48, Nawaz Khurshid <nawa...@gmail.com> wrote:
> It proves that stop linking edges are being used in car mode. I can debug
> further.

IMHO that should not be the case here, unless you want to board
transit with a car (which in some case is permissible, for ferries for
example, but I don't think there is plan in OTP to support that, maybe
in the future?). In first approximation you can try to prevent car
using stop / street link to see if that solves your problem.

HTH,

--Laurent

[Laurent GRÉGOIRE]

Hi Nawaz,

On 21 December 2015 at 14:02, Nawaz Khurshid <nawa...@gmail.com> wrote:
> <Split 1 at linke for 12_459_12 ...> is the additional link create for GTFS
> stop I guess. Please correct me. Then osm node 267587827 is exactly the
> point where the u turn is made.

It seems the split vertices are breaking the CAR u-turn prevention
code. The code rely on the following check to prevent u-turn:

if (this.isReverseOf(backEdge) || backEdge.isReverseOf(this)) {
return null;
}

public boolean isReverseOf(Edge e) {
return (this.getFromVertex() == e.getToVertex() &&
this.getToVertex() == e.getFromVertex());
}

The problem here is that the two original street edges (reverse of
each other) are split in the middle by TWO splitters vertices during
stop linking, and the condition no longer apply: isReverseOf is false
(the from vertex of one edge is splitter A, distinct from the to
vertex which is splitter B).

So clearly the u-turn prevention code is bogus; also even w/o
splitters the code is probably not working (for some OSM data two
edges can be the "reverse" of each other but where clearly we should
allow u-turn, where the from-to nodes are identical and the ways in
the two directions are distinct).

A fix may not be trivial. We could store into the edge the set of
reverse edges during building, and properly adjust when splitting. Or
make the code that check for u-turn check for the geometry (if the
start of geometry are identical then it's a reversed edge).

I've created an issue to track this down:
https://github.com/opentripplanner/OpenTripPlanner/issues/2191

HTH,

--Laurent

[Nawaz Khurshid]

Hi Laurent,

Many thanks for your precious time and feebacks!

I will keep track of this issue and hope that it will get fix soon.

Regards

Nawaz