[pgrouting-dev] Gsoc 2013 Preliminary project proposal
Mukul priya
mukul2047 at gmail.com
Sat Apr 13 20:12:36 PDT 2013
Thanks Steve for clearly mentioning the two proposals.
For Item 1 , upgrading all the algorithms will certainly require a lot of
work and since i will be having my summer vacation i don't have any issue
with it :).
For item 2 , i am looking into the idea that you have proposed , It is very
much doable , there are however some concerns of mine like
- how do we decide what should be the grid size . this can vary for
suburban area and urban area based on netwrok density.
- how do we classify the nodes lying on the junction of two or more grids .
should it be assigned to all the grids??
- how do we decide the grid that needs to be loaded in the memory ,
connectivity with the previous grid seems legit here but i guess we need to
discuss some corner cases too.
Thanks.
On Sat, Apr 13, 2013 at 6:20 AM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> On 4/11/2013 3:24 PM, Mukul priya wrote:
>
>> Hi Steve and Daniel,
>>
>>
>> You suggested extending the present algorithms such that its
>> input can take more points and not only the source and destination . i
>> think this can be implemented and i will soon come up with
>> implementation details( kind of more technical ) .
>>
>> Can you be a liitle bit more elaborate about partioning data
>> into spatial chunks or even suggest some readings . I can then come up
>> with some better ideas about implementing it.
>>
>
> This is just me thinking out loud :)
>
> Lets say we construct a grid of one degree squares, you can visualize it
> by drawing a grid over your map.
>
> Then you can associate all the nodes with the grid they fall in. We might
> also need to associate edges to the grids also and an edge the crosses over
> a grid boundary might need to be associated with two grids. This could be
> done with some simple relational tables like:
>
> node_id|grid_id or edge_d|grid_id
>
> So my idea would be to do the routing like this:
>
> 1. get the start node or edge
> 2. build the graph based on loading the items in the related grid
> 3. mark the boundary nodes (we might want to do this when we grid them)
> 4. run the algorithm until we find the target node or hit a boundary node
> 5. on hitting a boundary:
> a. we check if the connected grid is loaded and continue if it is
> b. or we extent the graph with the new grid
> 6. continue with the routing
>
> We might want to be able to dynamically change the size of the grid cell
> based on the number of items in it. This would give us better performance
> when transitioning from rural areas into urban areas where there is a
> greater density of road segments. Think of a quadtree where we split it
> based on number of entities.
>
>
> Daniel , i took a look at the oracle link that you provided but
>> there was no details about how it has been implemented , it was more
>> about how one can use it. May be a bit more search and luck might
>> take me to its implementation document :) .
>>
>
> Right, it is useful if you look at the documentation and ask why did they
> do it that way and what does it imply about how it works behind the scenes.
>
>
> The other thing that you mentioned was about contraction
>> Hierarchy . Still the nodes have to be ordered based on some criteria or
>> according to their importance . We can use natural hierarchy present in
>> the network for doing that .
>>
>
> This is not related to what you proposed. It is an algorithm that does a
> lot of precompuation, that is LOTS in capitals, but it can get results in
> milliseconds for cross country routes.
>
>
> i will be really grateful if anyone can correct me in case if
>> my thought process in not on the right lane and sorry for the late reply
>> as my academic session is in progress too .Meanwhile i am trying to
>> get fluent with git ,cmake and other tools.
>>
>
> So read over our wiki:
>
> https://github.com/pgRouting/**pgrouting/wiki<https://github.com/pgRouting/pgrouting/wiki>
>
> The way I see it at the moment there are two unrelated proposals on the
> table (I'm leaving out the contraction hierarchy):
>
> 1. multi point routing
> 2. partition JIT graph building while routing
>
> Item 1 is fairly trivial technically, I think, but if you were to upgrade
> all the algorithms to do this it would be a lot of work and a useful
> contribution to pgrouting.
>
> Item 2 is more of a design and code a new algorithm and you would probably
> want to focus on using astar or trsp algorithm to do this with. This one is
> more technically challenging and has more unknowns in it but I think it
> should be doable.
>
> If you are interested in reading about contraction hierarchies:
> https://www.google.com/#q=**contraction<https://www.google.com/#q=contraction>hierarchies
>
> Thanks,
> -Steve
>
> Thanks .
>>
>> Mukul
>>
>>
>>
>>
>> On Thu, Apr 11, 2013 at 6:47 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>>>
>> wrote:
>>
>> With pgRouting, we do most things dynamically, here is the basic flow:
>>
>> 1. Given a collection of input, points, nodes, or edges
>> map these to nodes or edges depending on algorithm.
>>
>> 2. Select the edges we need to build the graph
>>
>> 3. build the graph and solve it
>>
>> 4. return the results
>>
>> All our algorithms today only take start and end points. They could
>> be extended to take points. Each "point" (I use "point" as a generic
>> term because it might be a lat/lon, node id, edge id and offset,
>> etc) would need to be mapped to the appropriate input need for any
>> given algorithm.
>>
>> So for node based algorithms like Dijkstra,and astar it would get
>> resolved to a node. For TRSP it would get mapped to the nearest edge
>> and offset along that edge. Postgis has lots of handy tools for
>> doing this.
>>
>> -Steve
>>
>>
>> On 4/10/2013 10:50 PM, Mukul priya wrote:
>>
>> Thanks for the reply steve . i have already cloned the github
>> repository
>> and looking into various aspects of it .
>>
>> For IRNN querry implementation i think it is a good idea to sub
>> divide
>> the whole route and generate n+1 routes separately , say from S
>> to F1 ,
>> F1-F2 ,..... F(n-1)-Fn , Fn to D . i wanted to know if we have
>> that kind
>> of a data where each and every facility is mentioned on the map
>> as a
>> point (node ) . even if it is not directly connected to the road
>> network
>> we can basically treat it a pseudo node and then call the router
>> . The
>> other thing about optimization yes we can do that using spatial
>> range
>> querries suppose there are several instances of the same
>> facility that a
>> user wants to access then we can use spatial range querries to
>> locate
>> that facility which is the nearest.
>>
>>
>> On Thu, Apr 11, 2013 at 1:42 AM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>
>> >
>> <mailto:woodbri at swoodbridge.__**com
>>
>> <mailto:woodbri at swoodbridge.**com <woodbri at swoodbridge.com>>>>
>> wrote:
>>
>> On 4/10/2013 3:23 PM, Mukul priya wrote:
>>
>>
>> Hi ,
>>
>>
>> Hi Mukul,
>>
>> Thank you for your interest in pgRouting.
>>
>> I am a B.tech fourth year student at
>> IIIT-Hyderabad
>> pursuing a degree in computer science and engineering
>> and i will
>> be soon
>> pursuing a Masters Degree in the field of Spatial
>> Informatics
>> and the
>> research topic that i have been working on is *"In
>> route nearest
>> neighbour querries".*
>>
>>
>> Last year i worked on a project that was
>> funded by
>> Honeywell technology solutions and it gave me a lot of
>> insight about
>> open source programming and industrial work culture.
>>
>> I was introduced to pgrouting by *Prof. Venkatesh
>> Raghavan* who
>> visited
>>
>> our college last summer. i have also used pgrouting for
>> implementing one
>> of my Honors project.
>>
>> i have gone through the updated ideas page and i am
>> listing out
>> a topic
>> that i feel i can contribute to.
>>
>> *Idea *
>>
>> Network Partitioning
>>
>> A very simple method using which it can be done is :
>>
>> * *Existence of a natural Hierarchy*
>>
>>
>> Generally road networks are organized such
>> that there
>> is some
>> natural hierarchy for example if we look at the road
>> network of
>> USA we
>> observe that there are national highways which connect
>> multiple
>> large
>> regions , inter state roads connect places within these
>> regions
>> , multi
>> lane roads connect city areas and then there are small
>> roads to
>> connect
>> individual houses.
>>
>> so what we can do is first rank these
>> classes that
>> constitute the road network and then use the highest
>> level roads to
>> divide the road network into large regions enclosed by
>> these
>> roads. each
>> of the divided regions can further be divided again
>> using next lower
>> level road.
>>
>> so suppose we have a road network which n
>> classes of
>> different roads then we can create a tree of depth n-1
>> where the
>> root of
>> the tree will represent the entire road network and
>> children of
>> the the
>> root node will represent the area formed by
>> partitioning the
>> root using
>> the level 1 ( highest ) edges and so on . the nodes
>> will basically
>> represent a smaller part of the road network.
>>
>> The idea seems to be very naive right now
>> but if
>> anyone can
>> give some feedback whether it is achievable or not or
>> may be suggest
>> some modifications.
>>
>>
>> Yes this is the basics of how this could work. Because we
>> build our
>> graphs dynamically for each route request, we can do
>> something like
>> this today. Typically you have to feed the route request
>> and SQL
>> query that provides the edges needed to build the graph and
>> this can
>> be simply the bounding box of the start and end point of
>> the route
>> expanded slightly to allow the route move outside that
>> bounds by a
>> little if needed. A case in point are start and end points
>> that form
>> a vertical of horizontal line.
>>
>> So for the natural hierarchy, you can for a SQL query like:
>>
>> select * from edges where st_dwithin(the_geom, start_pnt,
>> radius)
>> union
>> select * from edges where st_dwithin(the_geom, end_pnt,
>> radius)
>> union
>> select * from edges
>> where st_expand(st_makeline(start___**__pnt, end_pnt),
>> pct)
>>
>>
>> and road_class < 4;
>>
>> So this gets all edges regardless of class at the start and
>> end and
>> then gets all the major roads and highways between the
>> start and end
>> points. We can dynamically select the edges that we want
>> when we
>> build the graph.
>>
>> Regardless of how you implement the routing, the problem is
>> all
>> about the data. If you have a road segment the is
>> misqualified, you
>> might end up with a network that is broken between start
>> and end.
>> This can alsoo happen if ramps are not coded correctly.
>>
>> One of the challenges we have today is that we have to be
>> able to
>> construct the whole graph in memory before we can start
>> routing.
>> This is ok for small areas but it is a problem if you want to
>> generate a route between say Miami, Florida and Seattle,
>> Washington.
>> An interesting problem would be the ability to partition
>> the data in
>> spatial chucks and only load them as the solver needed them.
>>
>> If you think about your edges sorted into say 1 degree grid
>> partitions,
>> then you load the partition for the start point and start
>> routing
>> using A* search, when you frontier get to an edge of the
>> grid you
>> are in, then you load the adjacent grid and continue, if
>> you bump
>> into another grid boundary that is not loaded yet, you
>> load, if it
>> is already loaded you continue. Anyway food for thought! :)
>>
>>
>> In route nearest neighbour querries(
>> IRNN) which
>> handle
>> querries like computation of shortest path , provided
>> that the user
>> wants to visit facilities F1 , F2 ,.....FN while he/she
>> drives
>> or walks
>> from source to destination. Network partitioning can
>> optimize these
>> computations too as the search space reduces
>> significantly once
>> we have
>> the partitions. Handling such querries have not been
>> implemented
>> yet. It
>> will be very helpful if we can have some discussion
>> about whether
>> implementing it is feasible or not.
>>
>>
>> What is we just added via support to routing? Then we could
>> do
>> something like say generate a route: Start, F1, F2, ... Fn,
>> End
>> This would allow us to build a graph one time and then
>> generate
>> multiple sub-routes with in the graph. Today if you want to
>> do that
>> you have to generate n+1 routes and build the graph n+1
>> times. We
>> could also do some preliminary optimization of the via
>> points based
>> on Euclidean distance using something like TSP before
>> calling the
>> router.
>>
>>
>>
>> It would be great if someone could give
>> a general
>> idea
>> how to go about learning more about the areas
>> mentioned with
>> respect
>> to the organization's projects.Specially suggest those
>> ideas
>> which the
>> developers think are achievable for now . I will also
>> be grateful if
>> somebody can guide me regarding the development
>> framework of
>> pgrouting
>> so that i get familiar with the whole framework in the
>> coming days.
>>
>>
>> I would clone the github repository and look at branch
>> sew-devel-2_0
>> this is our new tree structure and it has code, doc, and
>> test all
>> organized in a nice way that makes it easy to multiple
>> contributors
>> work with the tree.
>>
>> Ask questions, There is a tutorial floating around and lots
>> of
>> people that are will to help.
>>
>> -Steve
>>
>> Thank you .
>>
>> Mukul Priya
>> Lab for spatial Informatics
>> IIIT-Hyderabad
>>
>>
>> ______________________________**_____________________
>>
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> <mailto:pgrouting-dev at lists.__**osgeo.org <http://osgeo.org>
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >>
>> http://lists.osgeo.org/____**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> **>
>>
>> <http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>__>
>>
>>
>> ______________________________**_____________________
>>
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> <mailto:pgrouting-dev at lists.__**osgeo.org <http://osgeo.org>
>> <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >>
>> http://lists.osgeo.org/____**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/____mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> **>
>>
>> <http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>__>
>>
>>
>>
>>
>>
>> ______________________________**___________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**
>> osgeo.org <pgrouting-dev at lists.osgeo.org>>
>> http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>> ______________________________**___________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.**osgeo.org<pgrouting-dev at lists.osgeo.org>
>> >
>> http://lists.osgeo.org/__**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev>
>> <http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>> **>
>>
>>
>>
>>
>> ______________________________**_________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>>
> ______________________________**_________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130414/2e633e39/attachment-0001.html>
More information about the pgrouting-dev
mailing list