Path Finding with Large Graphs

[Jason Barto]

i am using Gama to build a model of London traffic. I have an ESRI shape file which contains nearly 250000 roads in it. Following the examples I've created agents using the shape file, created an edge graph and gave it weights of shape.perimeter / speedLimit. When covering a short distance, less than a kilometer or so, Gama finds what appears to be a direct path. Beyond that it seems to travel in nonsensical ways and even jump streets or appear to travel where there are no streets.

Can anyone provide advice on how to help Gama perform beat with such a large graph?

Sincerely,
Jason

[Patrick Taillandier]

Hi,

Some questions:

Which version of GAMA are you using? Are you using OSM data? Can you check the size of the environment (to be sure that you do not have a projection problem)?  Can you share with us your data (to make some test)? 

I just tested the goto action with a "medium/big" shapefile (Manilla - more than 60 000 roads) and it seems to work well. I do not have a bigger road shapefile on my computer.

cheers,

Patrick

--
You received this message because you are subscribed to the Google Groups "GAMA" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gama-platfor...@googlegroups.com.
To post to this group, send email to gama-p...@googlegroups.com.
Visit this group at http://groups.google.com/group/gama-platform.
For more options, visit https://groups.google.com/d/optout.

[Jason Barto]

Patrick,
As always thank you for your swift response. I am using an ESRI shape file but I have toyed with OSM data. Is OSM typically of a higher fidelity?

The data is projected using UTM Northing and Easting - I think that's the name of it. I will confirm the environment as you've suggested in a few hours and check back. Also I'll provide my test code (very simple at the moment) as well as the shape file as soon as I can.

Sincerely,
Jason

[Srirama Bhamidipati]

May be some screenshots of your paths? that can help !

regards,

Srirama

[Jason Barto]

Patrick / Srirama,

please find attached (as a reference) my Gama project complete with shapefile.  I've cobbled this together based on information here on the forums, the Gama wiki  and the tutorials.  

The model places a car at the first of 4 markers on the map.  The car then travels from marker 1 to 2, 2 to 3 and this goes along just fine.  However when the car attempts to travel to marker 4 from 3 it begins to travel in a manner I can't explain.  My hope is that you can tell me what is going on and where I have gone wrong.

https://drive.google.com/file/d/0B87628p2pygKUldiRVRFeFo1cW8/view?usp=sharing

Sincerely,

Jason

[Patrick Taillandier]

Hi,

I think you forgot to attach your model ;) 

I am using an ESRI shape file but I have toyed with OSM data. Is OSM typically of a higher fidelity?

A shapefile is just a format of data, not a data provider. For instance; you can find OSM data in shape file format. So it is difficult to say something about the fidelity of your data just from that.

To know the size of the environment, you can just add to the init section something like: write shape.points; (you will get the coordinates of the environment).

Cheers,

Patrick

2015-01-20 19:45 GMT+07:00 Jason Barto <jason....@gmail.com>:

Patrick / Srirama,

please find attached (as a reference) my Gama project complete with shapefile.  I've cobbled this together based on information here on the forums, the Gama wiki  and the tutorials.  

The model places a car at the first of 4 markers on the map.  The car then travels from marker 1 to 2, 2 to 3 and this goes along just fine.  However when the car attempts to travel to marker 4 from 3 it begins to travel in a manner I can't explain.  My hope is that you can tell me what is going on and where I have gone wrong.

Sincerely,

Jason

On Tuesday, January 20, 2015 at 1:22:21 AM UTC, Patrick Taillandier wrote:

[Srirama Bhamidipati]

Hi Patrick,

there is a link to google drive in his mail. The behaviour is very strange from marker 3 to marker 4. I think it is a problem with coordinate system. However, i tried many combinations and marker  4 seems to be the problem. I also tried from 4 to 3, to 2, to 1.... whenever 4 is included, there is a problem. Strange. But my feeling is that it is a problem with CRS.

regards,

Srirama

To unsubscribe from this group and stop receiving emails from it, send an email to gama-platform+unsubscribe@googlegroups.com.

[Patrick Taillandier]

Ok,

I have tested both on the release 1.6.1 and the SVN version of GAMA. I have been able to reproduce the bug on the release version but not on the SVN one, which means that I had already fixed this bug. 

So, for the moment, you can either try to install the SVN version of GAMA on your computer or wait for an update of the core of GAMA (I will see with Alexis if it is possible to produce one soon).

Some remarks about your model:

• You chose to divide the weights of the edge per the road speed limit, so it means that the car speed is already included in the weight so you should use a speed of 1 to your carTour agents is you want to keep it consistent.
  
• As you have a big shapefile of roads, you should rather put the refresh facet of the road layer to false and save the path geometry in a variable. see after:

species TourCar skills: [moving]

{

//other variables

list<geometry> trail;

//other things

reflex move when: waypoint != nil

{

// move toward the current waypoint

path the_path <- self goto [target::waypoint, on::roadNetwork, return_path::true];

list<geometry> segments <- the_path.segments;

trail <- trail + segments;

loop seg over: segments

{

// record the distance traveled

totalActualDistance <- totalActualDistance + seg.perimeter;

}

if location = waypoint

{

point acrs <- CRS_transform(startingPoint).location;

point bcrs <- CRS_transform(waypoint).location;

int travelTime <- int(time - waypointSetTime); // how long have we been traveling toward the current waypoint

write ("Completed travel from " + acrs + " to " + bcrs + " which took " + travelTime + " seconds to go " + totalActualDistance + " meters");

totalActualDistance <- 0.0;

do incrementWaypoint;

}

}

}

display city_display type: opengl refresh_every: 1

{

species TourCar aspect: base;

species Marker aspect: base;

species Road aspect: base refresh:false;

graphics "trail" {

loop t over: TourCar {

loop g over: t.trail {

draw g color: #red;

}

}

}

}

Cheers,

Patrick

[Jason Barto]

Patrick,
I have tried to install the SVN version using the Juno install instructions found here: https://code.google.com/p/gama-platform/wiki/G__InstallingSvnVersion

I am able to load a version of the model (without the to_GAMA_CRS spatial operator) if the application is run from within Eclipse.  However if I run an exported version of the Gama application, when I execute the model it seems to sit at 'Building Output' and never shows the map.  I am on OSX and have installed the SWT and other linked delta pack.  Any advice for what may be happening to the exported version vs the in-eclipse run of Gama?

Sincerely,
Jason

[Jason Barto]

This has been rectified, my thanks to everyone for their help. My Mac was trying to run the Gama.app using jdk 1.7 despite it being built and exported with 1.6. After modifying the Info.plist to force jdk 1.6 use I am now simulating traffic properly using the Svn build.

Sincerely,
Jason