conveyal / r5

Developed to power Conveyal's web-based interface for scenario planning and land-use/transport accessibility analysis, R5 is our routing engine for multimodal (transit/bike/walk/car) networks with a particular focus on public transit
https://conveyal.com/learn
MIT License
272 stars 71 forks source link

Unsupported Operation on single point with decay function #907

Closed abyrd closed 8 months ago

abyrd commented 8 months ago

Using UI and project at https://analysis-a2ezz7l8s-conveyal.vercel.app/regions/63a95f7328b9ff8f79b276ee/analysis?projectId=63a968e7e94bbb2013007634&_shouldResolveHref=true&scenarioId=baseline

Using destinations z9 gaussian west gridded frac and logistic decay function with SD=2.

Using backend and worker from 2023-fall-release cluster branch (v6.9-10-gfbd1062).

Exception is as follows:

java.lang.UnsupportedOperationException
    at com.conveyal.r5.analyst.PointSet.getPointsInEnvelope(PointSet.java:33)
    at com.conveyal.r5.streets.LinkedPointSet.extendCostsToPoints(LinkedPointSet.java:506)
    at com.conveyal.r5.streets.LinkedPointSet.extendDistanceTableToPoints(LinkedPointSet.java:476)
    at com.conveyal.r5.streets.EgressCostTable.lambda$new$0(EgressCostTable.java:272)
    at java.base/java.util.stream.IntPipeline$1$1.accept(IntPipeline.java:180)
    at java.base/java.util.stream.Streams$RangeIntSpliterator.forEachRemaining(Streams.java:104)
    at java.base/java.util.Spliterator$OfInt.forEachRemaining(Spliterator.java:712)
    at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
    at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
    at java.base/java.util.stream.ReduceOps$ReduceTask.doLeaf(ReduceOps.java:960)
    at java.base/java.util.stream.ReduceOps$ReduceTask.doLeaf(ReduceOps.java:934)
    at java.base/java.util.stream.AbstractTask.compute(AbstractTask.java:327)
    at java.base/java.util.concurrent.CountedCompleter.exec(CountedCompleter.java:754)
    at java.base/java.util.concurrent.ForkJoinTask.doExec(ForkJoinTask.java:387)
    at java.base/java.util.concurrent.ForkJoinTask.invoke(ForkJoinTask.java:667)
    at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateParallel(ReduceOps.java:927)
    at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:233)
    at java.base/java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:682)
    at com.conveyal.r5.streets.EgressCostTable.<init>(EgressCostTable.java:331)
    at com.conveyal.r5.streets.LinkedPointSet.getEgressCostTable(LinkedPointSet.java:276)
    at com.conveyal.r5.streets.EgressCostTable.<init>(EgressCostTable.java:137)
    at com.conveyal.r5.streets.LinkedPointSet.getEgressCostTable(LinkedPointSet.java:276)
    at com.conveyal.r5.streets.LinkedPointSet.getEgressCostTable(LinkedPointSet.java:293)
    at com.conveyal.r5.profile.PerTargetPropagater.<init>(PerTargetPropagater.java:200)
    at com.conveyal.r5.analyst.TravelTimeComputer.computeTravelTimes(TravelTimeComputer.java:325)
    at com.conveyal.r5.analyst.cluster.AnalysisWorker.handleOneSinglePointTask(AnalysisWorker.java:358)
    at com.conveyal.r5.analyst.cluster.AnalysisWorker.handleAndSerializeOneSinglePointTask(AnalysisWorker.java:331)
    at com.conveyal.r5.analyst.cluster.AnalysisWorkerController.handleSinglePoint(AnalysisWorkerController.java:50)
    at spark.RouteImpl$1.handle(RouteImpl.java:72)
    at spark.http.matching.Routes.execute(Routes.java:61)
    at spark.http.matching.MatcherFilter.doFilter(MatcherFilter.java:130)
    at spark.embeddedserver.jetty.JettyHandler.doHandle(JettyHandler.java:50)
    at org.eclipse.jetty.server.session.SessionHandler.doScope(SessionHandler.java:1568)
    at org.eclipse.jetty.server.handler.ScopedHandler.handle(ScopedHandler.java:141)
    at org.eclipse.jetty.server.handler.HandlerWrapper.handle(HandlerWrapper.java:132)
    at org.eclipse.jetty.server.Server.handle(Server.java:530)
    at org.eclipse.jetty.server.HttpChannel.handle(HttpChannel.java:347)
    at org.eclipse.jetty.server.HttpConnection.onFillable(HttpConnection.java:256)
    at org.eclipse.jetty.io.AbstractConnection$ReadCallback.succeeded(AbstractConnection.java:279)
    at org.eclipse.jetty.io.FillInterest.fillable(FillInterest.java:102)
    at org.eclipse.jetty.io.ChannelEndPoint$2.run(ChannelEndPoint.java:124)
    at org.eclipse.jetty.util.thread.strategy.EatWhatYouKill.doProduce(EatWhatYouKill.java:247)
    at org.eclipse.jetty.util.thread.strategy.EatWhatYouKill.produce(EatWhatYouKill.java:140)
    at org.eclipse.jetty.util.thread.strategy.EatWhatYouKill.run(EatWhatYouKill.java:131)
    at org.eclipse.jetty.util.thread.ReservedThreadExecutor$ReservedThread.run(ReservedThreadExecutor.java:382)
    at org.eclipse.jetty.util.thread.QueuedThreadPool.runJob(QueuedThreadPool.java:708)
    at org.eclipse.jetty.util.thread.QueuedThreadPool$2.run(QueuedThreadPool.java:626)
    at java.base/java.lang.Thread.run(Thread.java:1583)

The UnsupportedOperationException is from the base class (non-)implementation of PointSet#getPointsInEnvelope. The subclasses WebMercatorGridPointSet and FreeFormPointSet implement it, but Grid and GridTransformWrapper do not. This code path is calling an unimplemented method on a Grid. This must have worked previously because we could calculate accessibility results with decay functions during single point requests.

abyrd commented 8 months ago

The UnsupportedOperationException is indirectly caused by hitting the testing code path introduced in 9a1d114, which causes a Grid destination PointSet included in the single point request to be taken as the destinations for travel time, while subsequent code generating and recording travel times calls methods only defined on WebMercatorGridPointSet or FreeFormPointSet.

The log warnings and assertions introduced in 9a1d114 and 3b3d4ff of PR #896 caught the fact that destination PointSet objects are not always set on the destinations field of single point requests before processing (i.e. TravelTimeSurfaceTask.destinationPointSets may be null or empty). I was thrown off by the local variable destinations around TravelTimeComputer L90 which is always initialized locally (with a WebMercatorPointSet in the simple case) but that value is not reflected on the destinationPointSets field of the TravelTimeSurfaceTask object itself. In fact, single point requests only have destinationPointSets set when we're calculating accessibility. The PointSets are then expected to be ones that have defined densities, like Grid or FreeFormPointSet, not the density-less WebMercatorGridPointSet. But that local variable still gets set to a WebMercatorGridPointSet.

The fact that we can hit this code path in normal usage, and the fact that the local destinations variable is set to a different PointSet than the one on the request, implies it's possible to cause problems analogous to the one observed in the Simpson Desert tests (which led me to create this code path and assertions): a mismatch between the number of actual destination points and the number of destinations for which travel times are computed, which can fail silently if the latter is smaller than the former. The intended interface and behavior needs to be clarified, and assumptions about aligned grids need to be validated with assertions.

A check to this effect is already in place at TravelTimeReducer#checkOpportunityExtents. I will investigate why this was not being hit in the Simpson Desert tests, and whether it's being hit in single-point requests calculating accessibility (like those with decay functions).

abyrd commented 8 months ago

The check at TravelTimeReducer#checkOpportunityExtents was not being hit because it only runs when accessibility calculations are enabled, and destinations are expected to be web mercator grids. We should really be validating in every case that the size (and/or geographic position) of the targets for travel time propagation exactly match those of any destination PointSets provided on the request. I added some more assertions.

The expectations and invariants around the destinations attached to single point TravelTimeSurfaceTasks and RegionalTasks are not obvious. I added some documentation in the initial fix PR, but this should all be spelled out in more detail.

Single point tasks (TravelTimeSurfaceTasks) may or may not have attached destination PointSets. Attached PointSets are used for calculating accessibility at the same time as travel times. Travel time is always being calculated to a grid, and any attached PointSets for accessibility must exactly match that grid. To see how this is managed, see GridTransformWrapper usage in AnalysisWorkerTask#loadAndValidateDestinationPointSets.