[pgrouting-dev] Gsoc 2013
Stephen Woodbridge
woodbri at swoodbridge.com
Thu Apr 25 08:25:19 PDT 2013
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>> 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>
> <mailto:woodbri at swoodbridge.__com
> <mailto: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/%7E__amitp/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>
> <mailto:woodbri at swoodbridge.__com <mailto:woodbri at swoodbridge.com>>
> <mailto:woodbri at swoodbridge.
> <mailto:woodbri at swoodbridge.>____com
>
> <mailto:woodbri at swoodbridge.__com
> <mailto: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>
> <mailto:pgrouting-dev at lists.__osgeo.org
> <mailto: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
> <mailto: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>
> <mailto:pgrouting-dev at lists.__osgeo.org
> <mailto: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>
> <mailto:pgrouting-dev at lists.__osgeo.org
> <mailto: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>
> 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>
> 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
>
More information about the pgrouting-dev
mailing list