SEVERE: exception planning trip - NullPointerException

[mattwigway]

When I build an SF graph using this graph-builder.xml and plan a trip starting at the SFO terminal, I get:

SEVERE: exception planning trip: 
java.lang.NullPointerException
    at org.opentripplanner.routing.impl.StreetVertexIndexServiceImpl.getClosestVertex(StreetVertexIndexServiceImpl.java:244)
    at org.opentripplanner.routing.impl.StreetVertexIndexServiceImpl.getClosestVertex(StreetVertexIndexServiceImpl.java:186)

full trace.

I think it's being snapped to the restricted-access roads inside the airport, see OpenStreetMap. Starting anywhere towards the end of the long, spider-like terminals seems to cause the issue.

[mattwigway]

It looks like this might be a tiny island: see 26788101 and friends. They're stairways that connect domestic terminals to parking, and both the terminals and parking are (ignored) areas. Indeed, there's several like this. @novalis, didn't you see some of these at PDX a while back and have a function called something like depedestrianizeOrRemove in StreetUtils.java (near the bottom, IIRC)?

[novalis]

That function was removed after a conversation with the TriMet interns in #553; it was also a problem in #429. I'm still not sure what the right solution is.

[mattwigway]

Hmmm, yes, not sure what the best solution here is. At issue here is that this is not a data problem, because the ways are actually correct - it's just that they connect areas. Perhaps area routing is the solution. Or perhaps we can set a flag on ways with no connections and less than a certain number of nodes, for checking later after transit is linked (as you proposed in #429)

[novalis]

Do you think you would have time to try putting the depedestrianizeOrRemove call at the end of the transit linker, and hacking it to deal with transit vertices?

[mattwigway]

I won't really have time to work on anything for a while anyhow. My hacky thought was to disallow snapping to vertices with an edge count of 0.

On 2/28/12, David novalis Turner reply@reply.github.com wrote:

Do you think you would have time to try putting the depedestrianizeOrRemove call at the end of the transit linker, and hacking it to deal with transit vertices?

---

Reply to this email directly or view it on GitHub: https://github.com/openplans/OpenTripPlanner/issues/614#issuecomment-4232951

[novalis]

There are vertices with an edge count of zero? Yow! That's not good.

[abyrd]

Yes, there should definitely not be 0-edge vertices left in the graph after it is built. I will look into this.

[mattwigway]

Hmm, maybe I'm wrong, but that's what graph-visualizer seemed to show. You can rebuild my graph using the above graph builder, just keep in mind I ref'd a local GTFS in there where I stripped the Muni shapes. You can either just remove the Muni GTFS, or point to the unfixed one (which only seems to cause display issues, itineraries are still correct). I can confirm when I get home, but it's an OSM way which is connected only to areas.

On Wed, Feb 29, 2012 at 11:53 AM, Andrew Byrd < reply@reply.github.com

wrote:

Yes, there should definitely not be 0-edge vertices left in the graph after it is built. I will look into this.

---

Reply to this email directly or view it on GitHub:

https://github.com/openplans/OpenTripPlanner/issues/614#issuecomment-4245374

[mattwigway]

I should have been a little more specific. The problem area is at SFO (bay side, south of SF, see OSM), just north of the traffic circle. I guess there're two problems here:

1. there are vertices left over that are not connected to anything, and
2. when the planner snaps to them, it throws a NullPointerException. Perhaps 1 can be blamed on the data, but there shouldn't be an exception thrown.

[mattwigway]

OK, I've dug into this a little more. The offending vertex (or one of them) "way 26788101 from 0" does, in fact, have one outgoing and one incoming TurnEdge; the problem is, they're the same edge; i.e. there is an edge TurnEdge(< way 26788101 from 0 back (footbridge) >, < way 26788101 from 0 back (footbridge) >). Unfortunately debugging is a bit difficult since graphviz seems to be unstable after selecting this vertex. Incidentally, the latitude and longitude are 37.6178, -122.3868, which may be handy since the center of an SF graph is off the Atlantic coast due to some stray Muni stops west of Portugal.

[abyrd]

Thanks for the additional info. I happen to be working on the Bay Area currently so I have my own "improved" copy of the Muni and BART feeds. I'm also having problems with Millbrae BART being inaccessible because it's linked to platforms that are not connected to the rest of the network. Working on this right now. For the task at hand I am going to try removing the islands, but will of course pursue a better fix.

[novalis]

I added in an optional step to the graph builder, called PruneFloatingIslands; please feel free to give it a try.

[abyrd]

Thanks, will try out your patch as soon as I send off this giant batch query. The offending way 26788101 connects two areas, so pruning out islands did solve the problem temporarily. There is an underlying problem with how dead ends/loops are turn-converted though.

[mattwigway]

Hmm, yes, see what you mean at Millbrae. What there is there is a large structure above the tracks with stairs or escalators to each platform, as well as elevators. There are also two or three (depending on the time of day, I guess - I've actually never seen the SE entrance open) cross-platform connections from NB Caltrain to the westernmost BART platform (which serves both north and southbound trains, at least during the day on weekdays. I haven't been to Millbrae on a weekend in a long time).

[mattwigway]

Here's another plan where I see this, on the latest TStopLinking.

[mattwigway]

Ignore my most recent comment; that was a separate issue with an incorrectly-specified graph path.

[novalis]

I took a look at this, and I have an entirely different diagnosis. It may well be that there is more than one problem here, so the other stuff could still be relevant.

It looks to me like the crash is because in line 243, the call to getClosestEdges is returning null. That's happening because there are no nearby edges, because MAX_DISTANCE_FROM_STREET is 0.001 deg or ~100m. I'm not sure why that number is so small. Andrew?

[abyrd]

Thanks for catching that. The value of MAX_DISTANCE_FROM_STREET used to be 0.05 or ~5km. My new edge-finder did not use the growing-envelope trick from the original, and I had lowered the value to avoid sorting through 100km^2 of edges during every linking operation. 100m was a bit extreme, though.

I just checked in a version with an expanding envelope, but might it be better to have a search distance parameter (in meters even) -- I'll see if it affects speed much. Speaking of which, @novalis, the variant of getIntersectionAt that uses MAX_CORNER_DISTANCE, which you added in d9418ea8df3266c468011324480158e7ef939786, seems to have been wiped out by the merge in commit 0ae6e60cc9f66042ca41b538742ecb907ee55175. Is this intentional?

In any case, OTP should definitely do something more graceful than NPE when no edges are found. Also looking into that.

[abyrd]

Oh wait, that merge happened way before getIntersectionAt was modified, I was misinterpreting git blame.

[abyrd]

MAX_CORNER_DISTANCE problem fixed in 3b1e18cbee8738413ef117ce3cfea0653996e3c9

[mattwigway]

OK, yes, it looks like that's fixed the NullPointerException. Now I just get Path Not Found and the "your start or end point is not accessible when a trip is snapped to the vertex connected only to itself.

[abyrd]

Thanks for the feedback, and sorry this is taking a while -- I'm trying to finish up another project at the same time. So there are two problems here that need to be addressed for the release Thursday: disconnected islands and the incorrect turn conversion.

Even if islands are no longer a problem in Portland, there are tons of them elsewhere, and I need to filter them out of SF. @novalis doing this selectively via a separate graphbuilder makes sense, but it currently does not work because pruneFloatingIslands operates on the original graph, not the turnGraph.

We can either

1. change pruneFloatingIslands to work on the turn graph, or
2. add a boolean option to the OSM graphbuilder to prune right before turn conversion, or
3. make turn conversion also a separate graph builder process

I only mention 3 because it might be useful some day if we want to allow non-turn-based routing, multiple street data sources, etc. I am going to do (2) because it is more likely to work right away, and look at the turn conversion before exploring (1).

[novalis]

Actually, I think #1 would be better, and I'm going to go ahead and do it. I'll make sure it still works both ways.

[novalis]

(#1 is done)

[abyrd]

@mattwigway I turned off the island removal and examined the turn vertex you mentioned. In my graph it is not connected to itself - there are two turn vertices: "way 26788101 from 0" and "way 26788101 from 0 back" connected to each other in a loop. To me, this is the expected turn-conversion behavior when there is a single isolated edge in the original (non-turn) graph.

As long as these islands are not removed or marked as such (depedestrianized, etc.) a search that snaps to one of them will fail. This is just a connectivity problem with the graph, and requires either an island removal step or improved OSM data quality.

I'm going to close this issue since I no longer see searches failing in an uncontrolled way. @mattwigway, do create another ticket if you have a proposal for better island handling.

[mattwigway]

@andrewbyrd, I'm seeing a possibly-related issue with Analyst now where, with the latest OTP, I get null-pointer exceptions from the GeometryService/getNearestPedestrianStreetVertex. That may be a separate issue; it looks like the index is not getting filled (I see "spatial index size: 0" from line 55 of GeometryIndex.java). That causes getNearestPedestrianStreetVertex to return null, which makes the SPTCache load throw an NPE, so the cache throws an UncheckedExecutionException, &c. It looks like there's another error with a small search distance on line 33 of that file, which may or may not be related (I'm still trying to get my head around how the spatial index gets filled).

[mattwigway]

One thing I notice about the spatial-indexing code is that it filters for TurnVertices. Do we still have those, or do we just use StreetVertices now?

[abyrd]

TurnVertices are a subclass of StreetVertices. StreetVertices are anything on a street (i.e. non-transit), which currently includes TurnVertices and IntersectionVertices. The former represent being at the beginning of a segment on a particular street, and are connected with TurnEdges, while the latter represent being in the middle of an intersection (usually) and are linked to other IntersectionVertices with PlainStreetEdges. I will add comments to these classes. Eventually there should be a concise diagram of these relationships.

[abyrd]

I am unable to reproduce your error, my spatial index is filled. Of course getNearestPedestrianStreetVertex should not be throwing nulls unless they has some meaning and are handled, but this way of selecting search endpoints is already wrong in so many ways. For one, it is starting out facing in one direction on one street, so locations across the street can only be reached by walking down the street and back or around the block. I only did it this way because this code is a stopgap duplicating functionality in core OTP that will be shared.

[mattwigway]

OK, this was my fault; looks like my data-sources.xml got written over by a git pull. If anyone's interested, I did change SPTCache to use StreetVertexIndexServiceImpl, see https://github.com/mattwigway/opentripplanner-analyst/compare/openplans:master...mattwigway:StreetVertex I didn't rewrite other places where GeometryIndex is used.

[abyrd]

This might not work... I don't think the Dijkstra class is aware of the temporary edges that connect those vertices from StreetVertexIndexService to the main graph.

[mattwigway]

It seems to work (i.e. I do see travel times from the snapped vertices). I'm not positive it's working correctly, but it's not showing that there are no accessible locations.

[mattwigway]

Never mind, you're right. Sometimes (always?) it crashes.