2011.08.11 Weekly Check In - mattwigway/OpenTripPlanner GitHub Wiki
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 <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