How Does GAMA Calculate the Shortest Path when as_driving_graph is used ?

[hosseinab1]

Hello Team,

I'm building a very heavy model with thousands of car agents moving around. This will become CPU and RAM intensive. I like to know how does GAMA calculate the shortest path ? I'm going to pick an example: Imagine there is an origin (A) and a destination (B). Also there are 3 separate paths from A to B each have different lengths. Does GAMA calculate all of the 3 different combinations then choose the shortest one or there is a heuristic in the background that wont go through all the paths and chooses the shortest one ? If you dont mind, I like to know which algorithm / heuristics is running on the back-end. 

Also when I put this statement (compute_path(graph, target)) in my car agents (species) and the simulation step is 1 #sec what does that mean ? Is it like for every sec and every agent GAMA runs the shortest path heuristics algorithm and calculates the path ?

Is there anyway I can deactivate the shortest path algorithm to prevent mass CPU times ?

Thanks

Hossein

P.S. my background is Ops Research so feel free to give me technical advises.

[Srirama Bhamidipati]

Hi,

My first non-technical advice will be to ask you to  visit the google forums https://groups.google.com/forum/#!forum/gama-platform and use the search box at the top. :) 

Since you say you are beginner, there are plenty of beginner questions over the years, including those that you are asking here. 

To give you a head start, you can search for - shortest paths and time units, step, unit conversion etc

regards,

Srirama

[Patrick Taillandier]

Hi,

Bu default, GAMA uses the dijkstra algorithm to compute the shortest paths. It is possible to use other algorithms: A*, Floyd Warshall, Bellman. You can have a look at the graph models in the Features/Agent movement/Goto Network to see how to tune this.

The shortest path is computed only once per agent if you use the goto action (or you use the compute_path action only once). Note by default, the shortest paths computed are stored in a cache that can be used by all agents (the cache is automatically deleted if the graph is modified). If you need a lot of shortest paths computation and if your graph is not modified during the simulation, it is possible to pre-compute all the shortest paths and to load it at the beginning of the simulation.

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-platform+unsubscribe@googlegroups.com.
To post to this group, send email to gama-p...@googlegroups.com.
Visit this group at https://groups.google.com/group/gama-platform.
For more options, visit https://groups.google.com/d/optout.

[hosseinab1]

Thanks Patrick. as always you have been very helpful !

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