[pgrouting-dev] Gsoc 2013
Mukul priya
mukul2047 at gmail.com
Thu Apr 25 10:52:49 PDT 2013
Thanks Steve will add a few lines to my proposal explaining the reason
behind opting Astar.
Mukul
On Thu, Apr 25, 2013 at 8:55 PM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:
> On 4/25/2013 11:06 AM, Mukul priya wrote:
>
>>
>>
>> How much of the network do you have to explore using each algorithm?
>>
>> This will be reduced significantly while using Astar as we will have a
>> fair bit of idea about the direction towards which we should proceed.
>>
>> How does this impact the number of grids you have to load?
>>
>> Once we have an idea about the direction towards which we should proceed
>> , only those grids will be loaded. This will result in loading of less
>> number of grids.
>>
>> How does this impact your proposal?
>> The basic motivation behind the proposal is to make shortest path
>> computation faster. Number of database querry will be reduced as we will
>> be fetching lesser number of grids. This will have a positive effect on
>> computation time.
>>
>
> Right, so in your proposal, you want to be clear that the benefit will be
> achieved using astar or another algorithm with a heuristic and not
> dijkstra. I understand that "shortest path" is a generic reference to all
> of these algorithms, but the only ones that will benefit from this approach
> will be ones with a heuristic that allow us to explore only a subset the
> overall bounding box of edges that we might otherwise use as input. So it
> is best to be clear on these points.
>
> -Steve
>
> On Thu, Apr 25, 2013 at 7:07 PM, Stephen Woodbridge
>> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.**com<woodbri at swoodbridge.com>>>
>> wrote:
>>
>> On 4/25/2013 12:26 AM, Mukul priya wrote:
>>
>> Thanks Steve ,I am familar with astar ,It uses a heuristic to
>> guide
>> itself to the destination, there was huge focus on it in our
>> game theory
>> course.
>>
>> Although do point out the advantages it has in real life road
>> network
>> and its importance to my proposal.
>>
>>
>> How much of the network do you have to explore using each algorithm?
>> How does this impact the number of grids you have to load?
>> How does this impact your proposal?
>>
>> -Steve
>>
>> On Thu, Apr 25, 2013 at 7:43 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:
>>
>> Hi Mukul,
>>
>> This is a good write up. It largely mirrors out discussion.
>> One
>> thing that needs to change in this is that dijkstra should be
>> replaced with astar.
>>
>> Are you familiar with how these are different?
>> http://theory.stanford.edu/~__**__amitp/GameProgramming/____**
>> AStarComparison.html<http://theory.stanford.edu/~____amitp/GameProgramming/____AStarComparison.html>
>> <http://theory.stanford.edu/%**7E__amitp/GameProgramming/__**
>> AStarComparison.html<http://theory.stanford.edu/%7E__amitp/GameProgramming/__AStarComparison.html>
>> >
>>
>> <http://theory.stanford.edu/%_**_7Eamitp/GameProgramming/__**
>> AStarComparison.html
>>
>> <http://theory.stanford.edu/%**7Eamitp/GameProgramming/**
>> AStarComparison.html<http://theory.stanford.edu/%7Eamitp/GameProgramming/AStarComparison.html>
>> >>
>>
>>
>> Do you see why? and specifically why it matter for this
>> project?
>>
>> -Steve
>>
>> On 4/24/2013 9:10 PM, Mukul priya wrote:
>>
>> ***Name*:Mukul Priya
>>
>> *Country:*India
>>
>> *School and degree*: International Institute Of
>> Information
>>
>> Technology-Hyderabad ,
>>
>> B.Tech + Masters in
>> computer
>> Science And
>> Engineering
>>
>> *Email*:mukul2047 at gmail.com
>> <mailto:mukul2047 at gmail.com> <mailto:mukul2047 at gmail.com
>> <mailto:mukul2047 at gmail.com>>
>> <mailto:mukul2047 at gmail.com
>> <mailto:mukul2047 at gmail.com> <mailto:mukul2047 at gmail.com
>> <mailto:mukul2047 at gmail.com>>>
>>
>>
>> *Phone*:+91 9885991061
>>
>> *OSGeo project(s*):pgRouting
>>
>> *Title:* A partitioned approach to on demand increment
>> graph
>> assembly
>> for pgRouting.
>>
>> *Describe your idea*
>> *1. Introduction*
>>
>>
>> pgRouting has been working towards providing
>> routing
>> functionality on a PostGis/PostgreSql Geo spatial
>>
>> database. It already has support for shortest path
>> algorithm
>> like
>> astar ,dijkstra , tdsp and trsp .But for a very
>>
>> large network, routing becomes time consuming.
>> Network
>> partitioning
>> is one such way which can prove to
>>
>> be helpful in improving the overall time efficiency
>> of routing
>> querries. The main idea here is to first partition
>>
>> the whole network using a Quad tree approach and
>> when the
>> shortest
>> path is computed these partitions are
>>
>> loaded on demand. hence , there is an on demand
>> incremental
>> graph
>> generation.
>>
>>
>> The project aims at designing and implementing a
>> Shortest Path
>> algorithm on an on demand incremental
>>
>> Graph using a network partitioning approach.
>>
>>
>>
>> *2. Background*
>>
>>
>> Considering the present status where pgRouting
>> has
>> support for
>> shortest path algorithm like astar etc.
>>
>> Looking at their implementation details we can
>> observe that
>> the graph
>> is configured dynamically for all
>>
>> of them before computation.My proposal will also be
>> on the
>> same track
>> and for very large networks
>>
>> where the distance between source and destination
>> can be
>> very large ,
>> the response time will be
>>
>> significantly lesser and memory wise too it will be
>> lot more
>> efficient. Presently they don't use any partitioning
>>
>> approach so it will prove to be a good addition to
>> their
>> support for
>> shortest past algorithms.
>>
>>
>> *3. The idea*
>>
>>
>> There are two major components of my idea .
>>
>>
>> *
>>
>> *Network Partitioning*
>>
>>
>> For this part we can use a quad tree approach.
>> Say , we
>> start
>> with a square and a condition like maximum
>>
>> number of nodes that can reside in a square .
>> if the
>> number of
>> nodes in the square is greater than the max
>>
>> condition we further quarter it into four
>> squares and
>> allot the
>> nodes appropriately to each of them.All these
>>
>> squares can be called grids and they all will
>> be addressed
>> uniquely using a grid cell number .Each node
>>
>> will be assigned a grid cell number based on
>> the grid
>> they are
>> lying inside.
>>
>>
>> We will have data structures to address
>> edges as
>> they can
>> remain contained in either one grid cell
>>
>> or span across a number of grid cells.the
>> idea is to
>> first flag
>> such edges and store the grid cell numbers
>>
>> of the grids that the edge crosses/intersects.
>>
>>
>> *
>>
>> *On demand graph generation and Routing.*
>>
>>
>> The idea here is to first identify the
>> grid cell
>> initially and then fetch the edges that are associated
>> with
>>
>> that grid. These are the edges that will get
>> appended
>> to the
>> present graph and the graph will keep growing
>>
>> dynamically this way. we will have appropriate
>> database
>> tables
>> addressing the above issue such that
>>
>> we are able to fetch the required edges
>> quickly using a
>> database querry.
>>
>>
>> The implementation details for the above are :
>>
>> we will first partition the whole graph using
>> the quad tree
>> approach and each node/vertex will be assigned
>>
>> a grid cell number so we can have database
>> table for the
>> assigned nodes and edges like :
>>
>> CREATE TABLE vertex{
>>
>> id Node_id \\
>> unique
>> for each
>> node.
>>
>> cell grid_cell_number; \\ the
>> grid in
>> which the
>> node lies.
>>
>> geometry;
>>
>> }
>>
>>
>> CREATE TABLE edge {
>>
>> int id ;
>>
>> Int node_a;
>>
>> int node_b; \\ the connecting nodes
>>
>> // we can have other parameters like
>> traversal cost
>> and return
>> cost.
>>
>> }
>>
>> using the tables we can then fetch the
>> edges form
>> edge table
>> using simple database querry once
>>
>> we are provided with the grid cell number very easily.
>>
>> In short the summary of the whole idea is :
>>
>>
>> Step1: Fetch the start node , get the related Grid cell
>> number.
>>
>>
>> Step 2: Increment the graph by fetching all the items
>> related to
>> that grid.
>>
>>
>> Step3 : Check for boundary nodes ( this is done while
>> we are
>> partitioning) or target node .
>>
>> Step 4: On hitting a boundary node
>>
>> {
>>
>> check if the connected grid is
>> loaded and
>> continue if
>> it is
>>
>> or we extend the graph with the new
>> grid and
>> continue
>> with the routing;
>>
>> }
>>
>> or On hitting the target Node
>>
>> {
>>
>> stop;
>>
>> }
>>
>>
>>
>> *4. Project plan*
>>
>>
>> I will have about 12 weeks to implement the
>> project. The
>> tentative
>> schedule is as follows:
>>
>> Before 17th June : Get familiar with the
>> development
>> environment
>> of pgRouting and test some demos.
>>
>> week 1-2: Discuss and Define the various data
>> structures
>> and data
>> table that will be required.Prepare the
>>
>> Overall implementation
>> architecture.
>>
>>
>> week 3-4- Discuss and Implement network
>> partitioning
>> using quad
>> tree.
>>
>> week 5-8 -Start coding for on demand graph
>> generation and
>> routing
>> using Dijkstra. In between Prepare mid-term
>>
>> report.
>>
>>
>> week 9 - Integration with pgrouting .
>>
>> week 10-12- Testing and Bug fixing. Draft Final
>> report and
>> documentation.
>>
>>
>> *
>> 5. Future ideas / How can your idea be expanded? *
>>
>>
>>
>> It can be integrated with other shortest path
>> algorithms
>> like
>> astar etc. which pgrouitng provides.For time dependent
>>
>> shortest path computation, it will greatly reduce
>> the
>> updating cost
>> as we will be updating the cost of only those edges
>>
>> that are contained in the grid cells that are
>> loaded.
>>
>> In route nearest neigbour querries can also be
>> implemented using
>> the partitioning approach.Overall we can
>>
>> expand this approach to various other algorithms.
>>
>> *Explain how your SoC task would benefit the OSGeo member
>> project and
>> more generally the OSGeo Foundation as a whole:*
>>
>>
>> The proposed idea will significantly improve the
>> performance of
>> shortest path finding algorithms.This will have a
>>
>> positive effect on the user base of pgRouting. For
>> various
>> software
>> paltforms or applications that are using this library ,
>>
>> the response time will significantly improve.
>>
>> *
>>
>> Please provide details of general computing experience:
>> *
>>
>>
>> I generally use ubuntu ( 12.04) for all my academic
>> purposes and
>> windows
>> 7 for entertainment only. I am familiar with Fedora also.
>>
>> C++ is the language that i use most ( programming
>> purposes). For
>> implementing various course projects i have used C++
>> ,python
>> ,Java and
>> matlab.
>>
>>
>> I have no experience with hardware. The only experience
>> that i
>> had with
>> networking was during my computer network course.
>>
>> *
>> Please provide details of previous GIS experience:*
>>
>>
>>
>> I am a part of "Lab for Spatial Informatics" which is
>> the only
>> lab in
>> India devoted to GIS applications and learning. I am
>> familiar
>> with and
>> have used almost all the open source GIS platforms like
>> Quantum ,
>> OpenJump, ILwis,Grass. We have our own rendering
>> platform that was
>> developed by our lab.(LSI viewer)
>>
>> *Please provide details of any previous involvement
>> with GIS
>> programming
>> and other software programming:*
>>
>>
>>
>> I am very much familiar with Gdal/OGR as i used it
>> extensively
>> while
>> implementing an outsourced project of Honeywell
>>
>> Technology . I have played a lot with ESRI shape files.
>>
>> *Please tell us why you are interested in GIS and open
>> source
>> software:*
>>
>>
>>
>> I was very impressed with google earth when it was
>> launched way
>> back in
>> 2004.GIS platforms like quantum and Openjump were
>> introduced to
>> me when
>> i was in my second year and then i joined Lab for spatial
>> informatics
>> that is in our college based on my interest in this area.
>>
>>
>> open source platforms provide an opportunity to learn .
>> The best
>> part is
>> you can always create or develop something that you are
>> interested in
>> and there are people who will always be there to help
>> you if you
>> are stuck.
>>
>> *
>>
>> Please tell us why you are interested in working for
>> OSGeo and the
>> software project you have selected:*
>>
>>
>>
>> It will be huge learning experience since i have been
>> using
>> platforms
>> like Qgis , Gdal ,PostGis etc which come under Osgeo
>>
>>
>> I chose pgrouting because the algorithms that they have
>> implemented are
>> related to my masters topic and it will be great if i
>> get an insight
>> about how these were implemented on a much larger scale.
>>
>> *Please tell us why you are interested in your specific
>> coding
>> project:*
>>
>>
>>
>> Implementing routing algorithms for real world networks
>> is
>> actually very
>> challenging.its a challenge to come up with good
>> approaches so
>> that the
>> computation cost and response time is both reduced.
>>
>> *Would your application contribute to your ongoing
>> studies/degree? If
>> so, how?*
>>
>>
>> I am pursuing my Masters and my topic is closely
>> related to my
>> proposal
>> . If the results are impressive , i might get a
>> publication in
>> this area.
>>
>>
>> *Please explain how you intend to continue being an
>> active member of
>> your project and/or OSGeo AFTER the summer is over:*
>>
>>
>>
>> I was always interested in open source programming but
>> never
>> knew where
>> to start . GSOC provides an opportunity for beginners
>> like me
>> to take a
>> dive in the area open source programming. i have other
>> ideas like
>> implementing IRNN ( In route nearest neighbour
>> querries) which
>> can be
>> implemented within pgRouting.I have other intentions like
>> working for
>> bigger projects like Quantum Gis or Grass.I will be
>> contributing
>> to the
>> community forum and will always try to improve things.
>>
>> *Do you understand this is a serious commitment,
>> equivalent to a
>> full-time paid summer internship or summer job?*
>>
>>
>>
>> Yes, I understand that this is a serious commitment and
>> will try
>> to give
>> my best and work in a professional manner.
>>
>>
>> *Do you have any known time conflicts during the
>> official coding
>> period?
>> (June 17 to Sept. 27)*
>>
>>
>>
>> No .
>>
>>
>>
>>
>>
>> On Thu, Apr 25, 2013 at 12:47 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>>>
>> <mailto:woodbri at swoodbridge.
>> <mailto:woodbri at swoodbridge.>_**___com
>>
>>
>> <mailto:woodbri at swoodbridge.__**com
>> <mailto:woodbri at swoodbridge.**com <woodbri at swoodbridge.com>>>>>
>> wrote:
>>
>> On 4/24/2013 2:34 PM, Mukul priya wrote:
>>
>> Hi Steve and Daniel ,
>>
>> I have posted my proposal on Melange Gsoc
>> system. Do
>> have a look
>> at it.
>> Waiting for feedback and suggestions.
>>
>>
>> Can you post a link to your proposal? or the text
>> of it
>> here also. I
>> can never find anything in Melange or I may not have
>> visibility to
>> it yet as I just applied as a mentor.
>>
>> Thanks,
>> -Steve
>> ______________________________**
>> _______________________
>>
>>
>> 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>
>> >>
>> <mailto:pgrouting-dev at lists.
>> <mailto:pgrouting-dev at lists.>_**___osgeo.org <http://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>
>> **>__>
>>
>>
>> <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>
>> >
>> <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/20130425/7c03f837/attachment-0001.html>
More information about the pgrouting-dev
mailing list