Re: [OSM-dev] GSoC - Travel Time Analysis (classification aproach of Speedcollector)
On Fri, Mar 26, 2010 at 5:47 PM, Nic Roets wrote: > On Fri, Mar 26, 2010 at 6:00 PM, Marcus Wolschon > wrote: >> Expected, general travel times and delays due to random events >> are 2 different problems. > > The two problems are so closely interlinked it makes sense to treat them as > one. No. One requires statistical data of all of the road-network indexed by the specific road to make predictions about the infuence of this specific piece of road compared to the average road of that kind. The second requires statistical data of popular incidents that can happen everywhere and have such a large impact that the specific road does not matter. A 5Km trafic jam on a motorway of 2 lanes getting narrowed down to 1 lane will have the same impact no matter what the name of the specific motorway is. >> That there was a car accident last week does not affect the estimate >> of how long you are likely to travel by the time you react the start of >> a segment now. > > Of course it does ! How so? There IS no car-accident now and it is unrealistic to assume that there will be by the time you get there. Don´t mistake the average travel time with the statistical expected value for a single, random drive. > You have to account for the probability that the > road is poorly designed at that spot. I don´t think that the road has anything to do with it. To account for the probability you have to 1) detect an instance of a specific type of event 2) know the probability I don´t think 1 is possible with this kind of data. And I don´t think we´ll have the number of tracks for 2 in any meaningful number of places to merit development time. (Remember, we are short of developers everywhere in this project.) >> The most likely source of information about short time traffic obstructions >> is TMC and it usually tells you the expected delay. So this needs different >> issue not be addressed now and certainly not here. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis (classification aproach of Speedcollector)
On Fri, Mar 26, 2010 at 6:00 PM, Marcus Wolschon wrote: > Expected, general travel times and delays due to random events > are 2 different problems. The two problems are so closely interlinked it makes sense to treat them as one. > That there was a car accident last week does not affect the estimate > of how long you are likely to travel by the time you react the start of > a segment now. Of course it does ! You have to account for the probability that the road is poorly designed at that spot. > The most likely source of information about short time traffic obstructions > is TMC and it usually tells you the expected delay. So this needs different > issue not be addressed now and certainly not here. > > Marcus > > ___ > dev mailing list > dev@openstreetmap.org > http://lists.openstreetmap.org/listinfo/dev > ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis (classification aproach of Speedcollector)
On Fri, Mar 26, 2010 at 12:21 PM, Aditya Vikram Thoomati wrote: > Hi, > > Good to see the talk on Travel Time Analysis i would like you to have a > look at http://www.wsdot.wa.gov/projects/completed.htm and also check out > hypercube queuing model to have an elevated idea. Your links seems to point to a site listing 403 Projects where roads in the US have been improved or repaired. > I'm not saying it's easy. A lot of trail and error adjustments will be needed. > The main point is that the router already does a lot of the work. I still think your aproach is flawed. There should be little trial and error required as you are dealing with exact meassurements to make a a prediction giving certain of these meassurements more weight then others based on how closely they resemble the situation you want to predict. You start with gpx-traces containing many location- and speed- information. You also start with a vector map. But then why divide your traces by timestamp instead of referencing your map? 2 minutes is nothing on a motorway but lets you cross a good part of a city driving a green wave on a major road. >such as road maintenance or a car crash that cause >motorists traveling in both directions to slow down to take a peek. These events should be filtered out from the start if they do not occur every day in the same place. Expected, general travel times and delays due to random events are 2 different problems. That there was a car accident last week does not affect the estimate of how long you are likely to travel by the time you react the start of a segment now. The most likely source of information about short time traffic obstructions is TMC and it usually tells you the expected delay. So this needs different issue not be addressed now and certainly not here. Marcus ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis
On Fri, Mar 26, 2010 at 11:09 AM, Eric Marsden wrote: >> "lk" == Lukas Kabrt writes: > > lk> I wrote a draft of my GSoC application. It is available on wiki [1]. I > lk> tried to define goals more precisely. Any comments are appreciated. * tool for matching GPS traces to the roads from the OSM * tool for analyzing GPS traces and estimating travel times Are you sure that dividing it this way is reasonable? Can you explain this design decision? What is the output of the first tool? Marcus ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis (classification aproach of Speedcollector)
Hi, Good to see the talk on Travel Time Analysis i would like you to have a look at http://www.wsdot.wa.gov/projects/completed.htm and also check out hypercube queuing model to have an elevated idea. Cheers, Aditya _ The world in moving pictures http://news.in.msn.com/gallery/archive.aspx___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis
> "lk" == Lukas Kabrt writes: lk> I wrote a draft of my GSoC application. It is available on wiki [1]. I lk> tried to define goals more precisely. Any comments are appreciated. Hi Lukas, Your draft looks solid to me. Some points I suggest you consider: - reuse existing libraries like osm4routing[1] for .osm parsing (week 1) - think about how you could obtain representative GPX files and filter out those that don't correspond to the vehicle type/driving pattern you are interested in (many GPX tracks in OSM are likely unrepresentative of normal driving) - perhaps consult potential consumers of your travel time - information (openrouteservice.org, navit, gosmore, etc.) to ensure that your information meets their requirements - (in a later version of your proposal) add some bibliography concerning algorithms for map matching [1] http://github.com/Tristramg/osm4routing -- Eric Marsden ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis
I wrote a draft of my GSoC application. It is available on wiki [1]. I tried to define goals more precisely. Any comments are appreciated. [1] http://wiki.openstreetmap.org/wiki/Google_Summer_of_Code/2010/Student_Applications#Draft_application:_Travel_Time_Analysis -- Lukas Kabrt ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis (classification aproach of Speedcollector)
On Fri, Mar 26, 2010 at 7:49 AM, Marcus Wolschon wrote: > On Thu, Mar 25, 2010 at 2:28 PM, Nic Roets wrote: >> Rerouting traffic based on collected track logs is essentially an >> extension to this: Take the tracklog, divide it into 2 minute >> intervals (or T seconds). > > I suggest to use the ways and segments between pairs of nodes > on ways instead of and time base. > But of cause any such design deccisions are not up to us but the > students who´s project this wil become. It´s their project. We merely > offer a problem and advising suggestions. > >> Try to filter out the cases where the >> vehicle was parked or the user was walking around. Ask the router how >> long it should take to travel from the starting point to the end >> point. If it's substantially less than T, mark the point (segment) as >> a penalty point (avoid point) > > What point? > You where talking about start to end a second ago. > The points and segments that the router returned. A simple algorithm to choose a representative point or segment somewhere in the middle can be devised. >> with an appropriate weighting. > > There is no apropriate weighting as that algorithm > does not know IF the delay even happened in that one, random point. > You are calculating the delay for a complete route No. I said break it up into short (2 minute) sections. If the penalty isn't attached to exactly the right node, there is still a reasonable chance that it will cause the router to avoid roads that may soon become blocked up. > and then suddenly assuming it´s all in single point/segment. > >> Serve >> these penalty points to clients and routing servers. Then adjust the >> penalty points according to time of day patterns etc. > > And in what way do your random "penalty-points" relate to the > completely different route of the client? > > a) > If there is a delay n one direction, there need not be such > a delay in both directions. ... My router represents all segments as two directional edges. But a good system will attach some probability to an event that cause delays in both directions, such as road maintenance or a car crash that cause motorists traveling in both directions to slow down to take a peek. I'm not saying it's easy. A lot of trail and error adjustments will be needed. The main point is that the router already does a lot of the work. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis (classification aproach of Speedcollector)
Here are the other links to my own aproach back then: submit: http://speedcollector.comyr.com/submit.php (this is for testing. It was supposed to be called by navigation software, not humans) query: http://speedcollector.comyr.com/query.php classification chosen: https://sourceforge.net/apps/mediawiki/travelingsales/index.php?title=Speedcollector#database_schema Marcus ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis (classification aproach of Speedcollector)
On Thu, Mar 25, 2010 at 2:28 PM, Nic Roets wrote: > Rerouting traffic based on collected track logs is essentially an > extension to this: Take the tracklog, divide it into 2 minute > intervals (or T seconds). I suggest to use the ways and segments between pairs of nodes on ways instead of and time base. But of cause any such design deccisions are not up to us but the students who´s project this wil become. It´s their project. We merely offer a problem and advising suggestions. > Try to filter out the cases where the > vehicle was parked or the user was walking around. Ask the router how > long it should take to travel from the starting point to the end > point. If it's substantially less than T, mark the point (segment) as > a penalty point (avoid point) What point? You where talking about start to end a second ago. > with an appropriate weighting. There is no apropriate weighting as that algorithm does not know IF the delay even happened in that one, random point. You are calculating the delay for a complete route and then suddenly assuming it´s all in single point/segment. > Serve > these penalty points to clients and routing servers. Then adjust the > penalty points according to time of day patterns etc. And in what way do your random "penalty-points" relate to the completely different route of the client? a) If there is a delay n one direction, there need not be such a delay in both directions. b) That one car had a delay does not mean that one second later others have a similar delay. You don´t even attempt to describe merging the delays meassured by multiple vehicles on the same segment. c) Your aproach is highly dependent on the metric on one particular routing engine with one set of speed parameters. You are penalising a sportscar in the midle of the night becasue a heavy truck at rush hour was slow 3 month earlier. d) Tracks are about past events. You cannot blindly compare travel times of different vehicle-classes (heavy truck, light sports car, motorbike, bicycle, slow city-hopper), drivers with completely different intensions (driving fast, efficient, mapping sideroads) and at different classes of days (weekend? start/end of local holidays?) and times (rush hour, night, evening, morning). My aproach: I proposed to collect the tracks in navigation-software in my attempts (http://sourceforge.net/apps/mediawiki/travelingsales/index.php?title=Speedcollector) to solve this issue one or two years back becasue there we know the car and chosen metric as well as the time and day. Then classify times and days into some broad classes and subclasses and a heuristic for combining different meassurements taken with different meta-info with a weighting dependent on how much they aligh with the meta info that is being asked for. If a service to collect such tracks with all these meta-information was provided, I´d be happy to add the functionality of posting tracks there to Traveling Salesman (provided the user allows it). http://sourceforge.net/apps/mediawiki/travelingsales/index.php?title=Plugin/FeedbackFastestRouteMetric Marcus ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis
On Thu, Mar 25, 2010 at 2:58 PM, John Robert Peterson wrote: > If somone were finally to solve the problem of matching up traces to ways, > we would be in a position to extend that to identifying some map errors, > such as missing ways, or changed road layouts. This has already been done. See the osmunda program that is part of gosmore. Rerouting traffic based on collected track logs is essentially an extension to this: Take the tracklog, divide it into 2 minute intervals (or T seconds). Try to filter out the cases where the vehicle was parked or the user was walking around. Ask the router how long it should take to travel from the starting point to the end point. If it's substantially less than T, mark the point (segment) as a penalty point (avoid point) with an appropriate weighting. Serve these penalty points to clients and routing servers. Then adjust the penalty points according to time of day patterns etc. ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis
If somone were finally to solve the problem of matching up traces to ways, we would be in a position to extend that to identifying some map errors, such as missing ways, or changed road layouts. how to present this information in a useful way is a diferent task, but worth keeping in mind. Could I sugest splitting your proposal into to distickt projects: track/way matcher; system to use that data for trafic flow. JR On 24 March 2010 23:12, Graham Jones wrote: > Hi Lukas, > I am glad you are interested in contgributing to OpenStreetMap. > You will see that today there has been quite a bit of discussion on this > list about collecting and analysing traffic information. I am sure you > could make a valuable contribution to such a project. > You are suggesting basing a project on the suggestion on the ideas list to > use the GPX files in the osm database. The analysis method you develop > could also be used in a more real time application if someone were to > develop a service to collect and process GPX traces. > I recommend that you have a look at our application template and start to > draft an application based on your email. The main things to develop are > the scope of the project (to judge success against), and a project > plan/timeline to convince yourself (and us) that the project is achievable. > There is a link from our ideas page to a page to store draft proposals for > comment if you would like to use it. > > Regards > > > Graham Jones > (from my phone) > > On Mar 24, 2010 10:50 PM, "Lukas Kabrt" wrote: > > Hi, > > I would like to introduce myself. My name is Lukas Kabrt and I am > student at the Czech technical university in Prague. I am maping for > about a year and I'm really enjoying it. Over the past few months I > participated in import of administrative boundaries and in import of > address points in the Czech republic. These two projects gave me a lot > of experience with handling OSM data. > > I would like to use the knowledge in the field of artificial > intelligence I gained during my studies and apply them in the world of > OSM. I read through the wiki article GSoC Project Ideas 2010 and I > like the Travel Time Analysis project [1]. > > I think this project has a great potentioal. As far as I know, routing > algorithms estimate travel time by using speed limits or curvature of > the roads. Using GPS traces from real vehicles will allow more > accurate estimation of travel time, becouse it will take into accout > other factors (traffic, condition of the road). With enought data > available it should be even possible to detect rush hours or different > traffic patterns through the week (weekdays vs. weekend) and give the > appropriate travel time estimations. > > IMO the biggest challange would be to develop an algorithm which will > match GPX traces to OSM roads. The algorithm has to deal with noisy > GPS tracks, not-everywhere-accurate OSM map and it would be nice if it > can handle low-frequency GPS tracks (e.g. 1point / min). > > Within the scope of GSoC '10 I'd like to create application, which > will take an OSM file and bunch of GPS traces, analyze them, try to > recognize traffic patterns and create the output file with estimated > travel times for road segments (something like last year's > Preprocessor to add altitude information to OSM data). If it prooves > well it can be extended further. > > [1] > http://wiki.openstreetmap.org/wiki/GSoC_Project_Ideas_2010#Travel_Time_Analysis > > -- > Lukas Kabrt > > ___ > dev mailing list > dev@openstreetmap.org > http://lists.openstreetmap.org/listinfo/dev > > > ___ > dev mailing list > dev@openstreetmap.org > http://lists.openstreetmap.org/listinfo/dev > > ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
Re: [OSM-dev] GSoC - Travel Time Analysis
Hi Lukas, I am glad you are interested in contgributing to OpenStreetMap. You will see that today there has been quite a bit of discussion on this list about collecting and analysing traffic information. I am sure you could make a valuable contribution to such a project. You are suggesting basing a project on the suggestion on the ideas list to use the GPX files in the osm database. The analysis method you develop could also be used in a more real time application if someone were to develop a service to collect and process GPX traces. I recommend that you have a look at our application template and start to draft an application based on your email. The main things to develop are the scope of the project (to judge success against), and a project plan/timeline to convince yourself (and us) that the project is achievable. There is a link from our ideas page to a page to store draft proposals for comment if you would like to use it. Regards Graham Jones (from my phone) On Mar 24, 2010 10:50 PM, "Lukas Kabrt" wrote: Hi, I would like to introduce myself. My name is Lukas Kabrt and I am student at the Czech technical university in Prague. I am maping for about a year and I'm really enjoying it. Over the past few months I participated in import of administrative boundaries and in import of address points in the Czech republic. These two projects gave me a lot of experience with handling OSM data. I would like to use the knowledge in the field of artificial intelligence I gained during my studies and apply them in the world of OSM. I read through the wiki article GSoC Project Ideas 2010 and I like the Travel Time Analysis project [1]. I think this project has a great potentioal. As far as I know, routing algorithms estimate travel time by using speed limits or curvature of the roads. Using GPS traces from real vehicles will allow more accurate estimation of travel time, becouse it will take into accout other factors (traffic, condition of the road). With enought data available it should be even possible to detect rush hours or different traffic patterns through the week (weekdays vs. weekend) and give the appropriate travel time estimations. IMO the biggest challange would be to develop an algorithm which will match GPX traces to OSM roads. The algorithm has to deal with noisy GPS tracks, not-everywhere-accurate OSM map and it would be nice if it can handle low-frequency GPS tracks (e.g. 1point / min). Within the scope of GSoC '10 I'd like to create application, which will take an OSM file and bunch of GPS traces, analyze them, try to recognize traffic patterns and create the output file with estimated travel times for road segments (something like last year's Preprocessor to add altitude information to OSM data). If it prooves well it can be extended further. [1] http://wiki.openstreetmap.org/wiki/GSoC_Project_Ideas_2010#Travel_Time_Analysis -- Lukas Kabrt ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev
[OSM-dev] GSoC - Travel Time Analysis
Hi, I would like to introduce myself. My name is Lukas Kabrt and I am student at the Czech technical university in Prague. I am maping for about a year and I'm really enjoying it. Over the past few months I participated in import of administrative boundaries and in import of address points in the Czech republic. These two projects gave me a lot of experience with handling OSM data. I would like to use the knowledge in the field of artificial intelligence I gained during my studies and apply them in the world of OSM. I read through the wiki article GSoC Project Ideas 2010 and I like the Travel Time Analysis project [1]. I think this project has a great potentioal. As far as I know, routing algorithms estimate travel time by using speed limits or curvature of the roads. Using GPS traces from real vehicles will allow more accurate estimation of travel time, becouse it will take into accout other factors (traffic, condition of the road). With enought data available it should be even possible to detect rush hours or different traffic patterns through the week (weekdays vs. weekend) and give the appropriate travel time estimations. IMO the biggest challange would be to develop an algorithm which will match GPX traces to OSM roads. The algorithm has to deal with noisy GPS tracks, not-everywhere-accurate OSM map and it would be nice if it can handle low-frequency GPS tracks (e.g. 1point / min). Within the scope of GSoC '10 I'd like to create application, which will take an OSM file and bunch of GPS traces, analyze them, try to recognize traffic patterns and create the output file with estimated travel times for road segments (something like last year's Preprocessor to add altitude information to OSM data). If it prooves well it can be extended further. [1] http://wiki.openstreetmap.org/wiki/GSoC_Project_Ideas_2010#Travel_Time_Analysis -- Lukas Kabrt ___ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/dev