[pgrouting-dev] Gsoc 2013
Mukul priya
mukul2047 at gmail.com
Sat Apr 27 03:29:58 PDT 2013
Hi steve , i have edited my proposal based on our previous discussion (
added some lines about Astar) .meanwhile do suggest if there is scope of
some improvement .
Thanks
Mukul
On Thu, Apr 25, 2013 at 11:22 PM, Mukul priya <mukul2047 at gmail.com> wrote:
> 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/20130427/ccb39d3a/attachment-0001.html>
More information about the pgrouting-dev
mailing list