2011.08.11 Weekly Check In

• 13:35 <demory> well why don't we get started
• 13:35 <FrankP> hey all
• 13:35 <demory> i'll start with a quick rundown of my stuff
• 13:35 <demory> again, was out of town for much of this week
• 13:36 -!- novalis_dt [~[email protected]] has joined #opentripplanner
• 13:36 <novalis_dt> (sorry, lost connection; let me know if i missed anything)
• 13:36 <demory> no just getting started
• 13:36 <andrewbyrd> novalis_dt : nope, we just started
• 13:36 <demory> hopefully you saw the bike triangle writeup, we can discuss later
• 13:36 <novalis_dt> Saw it, but got distracted -- when I check in, we'll discuss
• 13:36 <demory> also coordinating w/ the USF folks about Sept
• 13:37 <demory> doing some more reorg/cleanup on the wiki
• 13:37 <demory> some work on the NW demo -- base network is about ready, will try building graph this afternoon
• 13:37 <demory> that's about it for me
• 13:37 <novalis_dt> Check in: I discovered this tool called FindBugs, and it has found five genuine though minor performance bugs so far, and a bunch of ugliness which I am now cleaning up
• 13:38 <novalis_dt> Which is why I have been distracted from the triangle
• 13:39 <novalis_dt> I guess I also have fixed some bugs this week.
• 13:39 <novalis_dt> (that I found on my own)
• 13:39 <novalis_dt> Or that others reported
• 13:39 <demory> findbugs looks interesting.. may need to try it on some of my other stuff
• 13:40 <demory> ok thanks
• 13:40 <FrankP> Check in: Not much to report here...been focused on TriMet stuff...only OTP related task was getting the new production server up and running (hope to be complete today/tomorrow...want to do some load testing of OTP)
• 13:40 -!- kristinann [[email protected]] has quit [Ping timeout: 260 seconds]
• 13:40 <andrewbyrd> checkin - I did most of the GraphVertex refactor earlier in the week, on a branch
• 13:41 <andrewbyrd> then addressed some related problems in graph serialization
• 13:41 <andrewbyrd> did a follow-up benchmark set using trip-banning to complement David Turner's earlier one
• 13:42 <andrewbyrd> Tried out a couple of things changing around the structure/ordering of the lowerBoundGraph
• 13:42 <andrewbyrd> and attacked a couple of bugs
• 13:43 <andrewbyrd> demory: I'm looking forward to seeing the NW demo
• 13:43 <demory> yeah me too. I should know more today about how its actually going to work
• 13:44 <demory> hey, for the GraphVertex refactor is that still in its own branch or did you merge it back in?
• 13:44 <andrewbyrd> it's still in its own branch. I should be able to merge it in with few conflicts
• 13:44 <demory> ok
• 13:45 <andrewbyrd> working on that refactor revealed several other things that I want to think through before I commit to the way things are done on the current branch
• 13:45 <novalis_dt> Can you expand on that?
• 13:47 <andrewbyrd> there was a lot of weirdness when building graphs because the current way of adding vertices (borrowed from graphserver) does not clearly distinguish between adding a vertex and fetching an existing one
• 13:47 <andrewbyrd> it also has the idea of adding an edge to a graph, whereas after the refactor an edge can only be genuinely added to a vertex (or an overlaygraph)
• 13:48 -!- kristinann [[email protected]] has joined #opentripplanner
• 13:48 <novalis_dt> Yeah, the notion was that we might want to do the create-or-use-existing thing for vertices to make it easier to handle initialization that might happen in unknown order in a single pass
• 13:49 <andrewbyrd> so for example during conversion to turn-based graph there were edges (dead ends) who were having their endpoints changed... their endpoint vertices were removed from the graph, then readded, which used to clear the edgelists but no longer does... hence edges showing up in multiple places, attached to multiple vertices
• 13:50 <novalis_dt> ok, that does sound confusing
• 13:50 <andrewbyrd> that's just an example - but it made me realize that the way the graph was built depended in some places heavily on quirks of how vertices with identical labels are handled/merged.
• 13:50 <andrewbyrd> so I wanted to think on it a bit before making it permanent
• 13:51 <FrankP> Andrew, interested in your email about weight table heuristics...is that a completely separate optimization than contraction-hierarchies, and will it work with the Bike TriAngle (whereas CH's won't)? Does using The WeightTable require a graph-builder.xml change?
• 13:51 <andrewbyrd> basically once I figured it out it was easy to fix, but I'm concerned there may be other problems of this kind hiding, that might change the graph in invisible but problematic ways
• 13:52 <andrewbyrd> FrankP: first of all, you'll notice in those results that the walk-only searches are really fast compared to transit trips.
• 13:53 <andrewbyrd> so we can apply the bike triangle to bike-only trips with no worries, I'd say.
• 13:53 <andrewbyrd> the weight tables are indeed a totally different method, which are supposed to approximate the LBG heuristic
• 13:54 <FrankP> Is the weight table ready, and should the interns be using it for their testing?
• 13:54 <andrewbyrd> for the Portland demo, worst case we use the LBG heuristic for bike+transit trips, it should be plenty fast
• 13:55 <demory> my assumption was that searches w/ the triangle enabled would involve neither heuristics or CH, is that correct?
• 13:55 <novalis_dt> demory, no, many heuristics should still be admissible.
• 13:55 <demory> oh ok
• 13:55 <novalis_dt> andrewbyrd, did you get a chance to see what would happen to the LBG if you made optimistictraverse no longer use states but instead just do pure weights?
• 13:55 <andrewbyrd> The weight table is 'ready' in the sense that it functions, but provides no real speedup in portland at this time. It was meant for huge cities anyway, and it turns out that it is not advantageous unless walk distance is constrained
• 13:56 <andrewbyrd> novalis_dt: optimisticTraverse is called on every edge only once, when a LowerBoundGraph is created. The results of all the traversals are stored in a table.
• 13:57 <novalis_dt> I thought the LBG was created on every request?
• 13:57 <novalis_dt> Or are you using a static LBG?
• 13:58 <andrewbyrd> The shortest path tree is. The graph is static in the sense that it is precalculated from the graph. That only takes a couple of seconds, and it's pretty small.
• 13:58 <andrewbyrd> I have thought about doing what you suggest as well.
• 13:59 <andrewbyrd> OptimisticTraverse probably shouldn't use states, we could define it as inherently non-path-dependent.
• 14:00 <novalis_dt> Right.
• 14:00 <novalis_dt> Ok, so Frank, does this answer your question?
• 14:00 <FrankP> Yes. But I bring this up because at one point weight tables were mentioned as being something I should use for the TriMet beta in place of CHs. Would be good to nail down the graph config for the beta sooner than later, ala https://github.com/openplans/OpenTripPlanner/issues/465
• 14:01 <andrewbyrd> I think David T started doing these benchmarks specifically to clear some of these config questions up.
• 14:01 <FrankP> Ah, very good.
• 14:02 <novalis_dt> So should we move on to the triangle?
• 14:02 <demory> ok that's a good segue into general discussion of the TriMet beta
• 14:02 <andrewbyrd> At one time I was getting noticeably better results from the Weight table, but other things have changed since then and all the methods are pretty fast in the median/average case. It's the outliers that mess things up.
• 14:03 <demory> can we talk general schedule real quick then the triangle?
• 14:03 <novalis_dt> Sure.
• 14:03 <andrewbyrd> sure
• 14:03 <demory> first, Frank: Bibiana has left for vacation right? Do you know when she returns?
• 14:04 <FrankP> looking...let
• 14:04 <FrankP> let's say Aug 22nd
• 14:04 <FrankP> better yet, Aug 23rd
• 14:05 <demory> ok thanks. i think we are going to push back the workshop follow up to the end of Aug
• 14:05 <demory> (we had originally discussed doing it next week when Kevin and I are in NYC)
• 14:05 <demory> we'll try to pin that down when he gets back next week
• 14:06 <FrankP> you might email her...she's been responding to some emails, and might want to take a break from her vacation to do a followup
• 14:06 <demory> i also don't think we ever got to a final, ranked list of must haves for Oct
• 14:06 <demory> ok thanks
• 14:07 <demory> anyway we may not have that 100% pinned down until she gets back too. but it sounds like there is enough to work on in the meantime
• 14:07 <FrankP> To quote her, "I will be working with them with your help to prioritize the requirements and identify the ones that need to be completed by the beta release, and then those that follow. At a high level, the mandatory requirements for the beta release that are not yet completed are: "
• 14:08 <FrankP> - Alerts & the Bike Preference Triangle
• 14:08 <FrankP> - Improvements to the descriptive itinerary - Bug and performance issues
• 14:09 <FrankP> This was my list of Honestly, I don't think Alerts are a must have
• 14:10 <demory> ok thanks
• 14:10 <FrankP> BTW, about alerts. Bibi did hear from Google...no firm update, but they say they'll release info on GTRTFS well before Oct 15
• 14:11 <novalis_dt> They also said they would release it before the July meeting :)
• 14:11 <FrankP> The quote, "We are on the verge of releasing the GTFS-realtime specification to the public. I will let you know as soon as we have something publicly accessible - October the 15th is definitely fine for you."
• 14:11 <demory> yeah the alerts really depends on Google's timeframe. that one's kind of a wild card for now
• 14:11 <demory> ok
• 14:12 <FrankP> Not sure they're talking 2011 or 2012 :-)
• 14:12 <demory> ha
• 14:13 <demory> for " Improvements to the descriptive itinerary - Bug and performance issues" -- DavidT was that mostly covered in #451?
• 14:13 <novalis_dt> I would like a specific list of what needs to be changed.
• 14:13 <demory> the "Various OTP bugs found by interns"
• 14:13 <novalis_dt> I have made some improvements
• 14:13 <novalis_dt> But there may well be more that could be made.
• 14:14 <FrankP> I'd say it's ongoing...but Dave's gotten the descriptive itinerary more descriptive since that email.
• 14:14 <novalis_dt> FrankP, I would prefer to have a ticket I could close.
• 14:16 <novalis_dt> That is, per each itinerary issue
• 14:16 <demory> ok should we move on to the bike triangle?
• 14:17 <FrankP> OK, I'll make sure the Interns go though me, and I'll create tickets from now on...
• 14:17 <andrewbyrd> Would you guys prefer that I spend more time on these descriptive itinerary issues too, since they are what's most visible to the end users in Portland? Or do want to handle it David T?
• 14:17 <novalis_dt> FrankP, the interns are also welcome to email me directly, and I'l ticket
• 14:17 <FrankP> OK
• 14:17 <novalis_dt> andrewbyrd, I can handle it, but I'll let you know if i get stuck on anytihng
• 14:18 <andrewbyrd> yes, don't hesitate to assign tickets to me if there end up being a bunch, and I'll shift effort in that direction
• 14:18 <novalis_dt> Cool. OK, bike triangle
• 14:19 <novalis_dt> demory, your description of the topo factor doesn't give a bonus to downhills. Is that really reasonable?
• 14:19 <andrewbyrd> My first thoughts reading about the bike triangle are: shouldn't downhill segments also be penalized ?
• 14:20 <demory> yeah i can speak to that. i wrestled with that a good bit
• 14:20 <andrewbyrd> I should look before I hit enter.
• 14:20 <novalis_dt> penalized? Don't cyclists prefer to go downhill?
• 14:20 <demory> so i originally had a penalty for uphill segments and a bonus for downhill
• 14:21 <andrewbyrd> Well, I think we agree that downhill segments should be consdered. A slight downhill is an advantage, a steep downhill is dangerous/you have to lean on the brakes
• 14:21 <demory> the problem is, say you have an edge with steep uphill followed by an equally steep downhill, i.e. so the start and end elevation are the same
• 14:21 <andrewbyrd> There are a few hills in portland I would avoid going straight down if I could go around them
• 14:22 <demory> the way i originally wrote it, the two canceled each other out, so the "cost" of that edge was 0
• 14:22 <demory> now, say you had an edge of the same length that was completely flat. its cost is also 0
• 14:22 <novalis_dt> Yeah, that's clearly wrong.
• 14:23 <demory> ..though clearly the flat edge is preferable. i suppose you could give a "partial" bonus to downhill segments
• 14:24 <novalis_dt> I guess that seems sort of pointless.
• 14:24 <andrewbyrd> You could just calculate the work required to traverse an edge. Downhill is 0, flat has a small positive value.
• 14:24 <demory> so that in the above case the flat edge still wins out. but i never really played around with that
• 14:25 <demory> honestly, i liked the results i was getting in Atlanta -- very consistent with my own experience as a cyclist -- so I just stuck with it
• 14:25 <demory> but i'm certainly open to a different approach
• 14:26 <novalis_dt> demory, the thing about the model you use is that it makes it hard to compare weights between biking and transit.
• 14:27 <novalis_dt> demory, a completely flat bike route, with T=1.0, would cost 0
• 14:27 <demory> well is it ok to only have this apply for bike only trips?
• 14:27 <andrewbyrd> I think we'd want to apply it for bike+transit
• 14:27 <novalis_dt> Yeah, I think TriMet would like that
• 14:28 <demory> yeah
• 14:28 <andrewbyrd> that's when it would get really interesting: the board/alight points and routes taken would change to avoid hills and dangerous roads for example
• 14:28 <novalis_dt> It actually makes more sense to consider downslopes when doing bike+transit routes
• 14:28 <demory> i'll need to think that through some more. my code approached bike-to-transit in a very different way
• 14:28 <andrewbyrd> novalis_dt: right
• 14:29 <novalis_dt> Because in a bike-only trip, your net elevation gain/loss over a trip is constant across all routes, meaning that downhill bonuses would be canceled out by uphill penalties. But in a bike+transit trip, this is not so
• 14:29 <andrewbyrd> This is a really interesting problem
• 14:29 <demory> yeah that makes sense
• 14:32 <demory> i need to study the current OTP code a little more before I can answer the question about bike vs transit weights
• 14:32 <novalis_dt> OK, so let's imagine an alternate plan: the topological cost of a segment is the energy it would take to ride that segment keeping speed constant.
• 14:33 <andrewbyrd> the cost of a segment is elapsed time, plus terms for all other "onerous" things that happen on that segment
• 14:33 <demory> ok. so is there any bonus for downhill? i.e. is that considered "gained" energy?
• 14:33 <andrewbyrd> so you just add work in there
• 14:34 <andrewbyrd> I assume you have to burn off that energy in the brakes at the end of every segment, since segments end at intersections
• 14:34 <novalis_dt> andrewbyrd, I've been contemplating modeling that better, since some at intersections you have a green light and just go
• 14:34 <novalis_dt> demory, well, keep in mind that on slight downhills, you actually still need to pedal to overcome the coefficient of friction...
• 14:34 <novalis_dt> (and wind resistance)
• 14:34 <andrewbyrd> right, but you still have to burn off enough energy to roll through the intersection at reasonable speed
• 14:35 <demory> well in some cases a downhill leasds directly into an uphill, and you can use the momentum to carry you partway uphill
• 14:35 <demory> if you don't have to stop that is
• 14:35 <andrewbyrd> which means wasting enough energy to return yourself to the same speed you were going at the previous intersection
• 14:36 <andrewbyrd> While we know real bikers will do these things, not returning to the same speed you went through the last intersection is usually unsafe...
• 14:36 <novalis_dt> It's all sort of a rabbit hole. We should think if the simplest thing that gives routes that cyclists like.
• 14:37 <andrewbyrd> Agreed, but I'd guess the simplest way is just to make it mostly coherent with energy expenditure.
• 14:38 <andrewbyrd> I'm also hinting here at the fact that it's probably best to make the bike terms non-negative
• 14:38 <novalis_dt> Yes, definitely.
• 14:38 <demory> also, keep in mind that you may have multiple uphill/downhill "segments" within a single edge
• 14:38 <novalis_dt> Anything negative is asking for all sorts of trouble
• 14:39 <demory> the segments are defined by the frequncy of the NED sampling, not by intersections
• 14:39 <novalis_dt> Right, we already do that.
• 14:39 <andrewbyrd> demory: I think the best policy there is to think in terms of toal rise and total fall over the segment
• 14:39 <novalis_dt> I have something that computes speed given elevation.
• 14:40 <andrewbyrd> that's how it works now right?
• 14:40 <novalis_dt> OTP?
• 14:40 <novalis_dt> OTP considers the length and slope of each segment
• 14:40 <novalis_dt> and has an insane curve that it uses based on some model that some dude put on the web
• 14:41 <novalis_dt> But this is not necessarily sensible in any way.
• 14:42 <demory> i like the energy expenditure approach, where downhill=0, flat has slight penalty, and uphill has progressively higher penalties
• 14:42 <novalis_dt> We can do that.
• 14:43 <novalis_dt> And just add it to the distance.
• 14:43 <andrewbyrd> To sum up, if we can just get the bike triangle widget values into a TraverseOptions, we can try all kinds of things easily, just by changing this or that in the traverse methods.
• 14:43 <novalis_dt> andrewbyrd, I actually think it's a separate OptimizeType
• 14:44 <novalis_dt> andrewbyrd, I'm happy to go ahead and implement it and let you worry about whatever you were already working on.
• 14:45 <andrewbyrd> I do have a long list of other stuff to work on/try, but I do find the bike optimization problem interesting.
• 14:46 <andrewbyrd> But sure, go ahead and implement it, I'm interested in seeing how hills will affect transit routing.
• 14:47 <novalis_dt> andrewbyrd, Ok, I'll do that
• 14:47 <demory> novalis_dt what specifically are you proposing implementing -- just the topographic cost factor generation?
• 14:47 <demory> b/c I can work on the front end stuff
• 14:47 <novalis_dt> I am specifically proposing implementing the entire back-end
• 14:47 <demory> ok
• 14:48 <novalis_dt> so we'll have a new OptimizeType=TRIANGLE, and then three new args for T,D, and F
• 14:48 <novalis_dt> Does that sound right?
• 14:48 <novalis_dt> Is there anything else we need?
• 14:48 <demory> right
• 14:49 <demory> that's all you need from the user
• 14:49 <demory> we haven't talked about the facility type factor
• 14:50 <novalis_dt> We actually already have that, sort of
• 14:50 <demory> i.e. safety / bike-friendliness
• 14:51 <novalis_dt> Actually, there's no sort-of: ours is, I think, more correct, at least from the perspective of safety
• 14:51 <demory> ok. i don't doubt it. my approach was admittedly pretty crude for this
• 14:52 <novalis_dt> Ok, so is that it for the meteing?
• 14:52 <demory> so it's calculated in a way that can just be added to distance and topo cost (w/ user weights)?
• 14:52 <novalis_dt> Yes.
• 14:52 <demory> alright. sounds good.
• 14:52 <novalis_dt> Um.
• 14:52 <novalis_dt> By "distance" we mean "time"
• 14:53 <demory> right
• 14:53 <novalis_dt> Actually, sort of.
• 14:53 <andrewbyrd> hmm
• 14:53 <demory> time is just a function of distance and speed right?
• 14:53 <demory> or is it more complicated than that?
• 14:53 <andrewbyrd> unless you're going up hills
• 14:53 <novalis_dt> Right...
• 14:54 <andrewbyrd> of course it's still a function of distance and speed, but speed is not constant
• 14:55 <novalis_dt> I was holding energy constant when I computed the curves.
• 14:55 <novalis_dt> It's not really fair to hold energy constant when computing speed, but hold speed constant while computing energy
• 14:56 <novalis_dt> Of course, maybe given that we're doing an affine combination it is close enough
• 14:56 <demory> so if we add topo cost and safety to time, as its currently being computed, we're effectively taking the topography into account twice, right?
• 14:56 <demory> if its also incorporated into time
• 14:57 <novalis_dt> We don't presently consider topo for safety
• 14:57 <novalis_dt> It's true that topo would be used in two of three elements
• 14:57 <novalis_dt> But it is being used differently
• 14:58 <novalis_dt> And actually in computing time we must use the topo-adjusted time in order to provide accurate multimodal routes
• 14:59 <demory> so should the "distance" factor be renamed "time"?
• 14:59 <novalis_dt> I think it should
• 14:59 <demory> my original idea with the distance factor is to give the option of computing the absolute shortest route distance-wise. but perhaps that doesn't make sense in this context
• 14:59 <novalis_dt> But maybe this doesn't make sense?
• 14:59 <andrewbyrd> I suppose what most people perceive as the "length" of their bike trip is actually the time
• 15:01 <andrewbyrd> States are currently only comparable by time and cost (weight), not distance.
• 15:01 <novalis_dt> In demory's original formulation, cost=distance
• 15:02 <demory> right. so Andrew are you saying it would be difficult to implement a purely distance-based approach?
• 15:02 <novalis_dt> I don't think it would
• 15:03 <novalis_dt> But I don't know whether that is actually useful to anyone.
• 15:03 <demory> i mean, could we try it both ways (i.e. distance or time as the first factor) and see which gives more intuitive results?
• 15:03 <novalis_dt> Sure we could. Of course, we would need a local to tell us what those are
• 15:04 <andrewbyrd> I'm saying it would be purely distance-based iff T and F were 0, right?
• 15:04 <demory> yeah. I could also set up a local deployment here and test some myself. I bike around Atlanta a lot
• 15:04 <novalis_dt> andrewbyrd, only if the route were flat
• 15:05 <demory> right
• 15:05 <demory> (^ to David T's response)
• 15:06 <demory> so, maybe we start using time as it's currently computed, since that's easiest
• 15:07 <novalis_dt> Sure.
• 15:07 <demory> but I'd be curious to see the distance-based approach as well
• 15:07 <novalis_dt> Should be not too hard.
• 15:08 <demory> and in the meantime I will start on the front-end
• 15:08 <novalis_dt> OK, awesome.
• 15:08 <novalis_dt> I will probably not get to anything other than findbugs today
• 15:08 <demory> so, anything else for the meeting?
• 15:09 <novalis_dt> Not from me
• 15:09 <andrewbyrd> Nothing else here
• 15:09 <novalis_dt> Ok, talk to you all next week.
• 15:09 <demory> ok, great. i'll upload the notes. thanks all