Latest revision as of 03:11, 30 June 2014

Summary

Do foraging animals and growing cities utilize resources in the same way? We're interested in building an agent-based model which generates a road network on a map of varying resources by following a set of simple, probabilistic rules. How do the properties of this network evolve through time? How much of city growth can be explained by resource constraints? Do simple rules of growth parallel simple rules of animal foraging behavior? This project will explore agent-based modeling, but will also present opportunities to examine the limits of modeling.

Objectives - Research Question(s)

Road networks are an integral part of city infrastructure, but the drivers of their structure and evolution are not well understood. At the most basic level, we posit that road networks are a means of searching out and transporting resources important for human activity. Other animals also exhibit this searching or foraging behavior. In this project, we will use the analogy of foraging animals to model the development of road networks in cities. Here we will ask how much of the structure of city road networks can be explained by a searching procedure like that of a foraging animal.

Our work will build on previous literature on foraging and city scaling, but will depart from this in two ways. We will develop an agent-based model that builds on simpler models of foraging in the literature but includes varied topography in the search space. We will also build on studies of the structure of city road networks by developing a mechanistic model that can be tested empirically against real city networks, both past and present. If validated, the model may have implications for understanding the development of road networks in new cities, or the expansion of existing cities.

This project involves a number of steps, not necessarily to be completed in this exact order:

1. Define essential properties of city networks, which will be used to evaluate the performance of the model.

2. Examine these properties in candidate animal foraging routes. What are the similarities and differences?

3. Develop an agent-based model of animal foraging on a landscape with varied resources and terrain, to be applied to city networks. What features of the model (e.g. network persistence) should be adapted from the foraging to the city case? What are the parallels?

4. Run the model using a relatively simple map, and evaluate the network properties determined to be important. Select a method for measuring these properties.

5. Run the model using a real-world map (for example, the city of Santa Fe), and compare the results visually to the actual map.

Guiding Questions: How do growing foraging networks and road networks compare and contrast in a simple model?

How much of real road networks and foraging networks can be explained by a simple optimality model?

Goals

1. Develop an agent-based model for foraging and road networks.
2. Run simulations and analyze results.
3. Compare and contrast two models using network analysis.
4. Test the city of Santa Fe growth for fun.

Groups Members

Alberto (alberto.antonioni@unil.ch) - modeling, networks
Alex (brummera@email.arizona.edu - spatial analysis, modeling (mathematically), santa fe map literature
Bernardo (bernardo.furtado@ipea.gov.br) - cities literature, netlogo, networks
Claire (lagesse.claire at gmail.com) - cities literature, modeling, networks
Diana (dianalg11@gmail.com) - ant literature, netlogo, network
Ernest Liu (yu.liu@math.uu.se) - modeling, netlogo, matlab
James - graph theory, algorithms, matlab, agent based modeling
Michael Kalyuzhny (michael.kalyuzhny at mail.huji.ac.il) - ants literature, empirical data on ants
Morgan (morgane@mit.edu) - modeling, spatial analysis
Rohan (rsmehta at stanford dot edu) - modeling, ants literature

Meetings

Tuesday 1 : 6:00 pm EVERYONE meets (coffee shop)
Wednesday 2 : 10:45 am - 12 pm Everyone meets (lecture hall)

done :

Saturday 28 : 6:00 pm Morgan, Rohan, Bernardo and Diana meet to resolve paper and begin presentation (coffee shop)
Sunday 29 : 6:30 pm Everyone meets (outside lecture hall) Monday 23 : 1:00 pm Morgan, Bernardo, Michael and Claire meet to refine cities lit search at 1pm (coffee shop)
Tuesday 24 : 4:15-5:00 pm James, Alex and Diana meet to discuss data processing goals (lecture hall)
Thursday 26 : 1:00 pm EVERYONE (lecture hall)
Sunday 22 : 6:00 pm (Arrive at 5:30 pm to discuss Python model) Thursday 12 : 6:00 pm - 7:00 pm
Monday 16 : 2:30 pm - 4:15 pm
Tuesday 17 : 3:00 pm - 5:00 pm
4:15 p.m. - 4:25 p.m. : Meeting with Josh
Wednesday 18 : 9:00 am - 12:00 am
Friday 20 : Claire & Alberto 6:30 pm - 8:00 pm (work on Python code)

Ongoing work

Model Development

Write documentation for and debug NetLogo Model (Ernest)

- Model output in this format: [Time step, Point 1 connected at that time step, Point 2 connected]

Work on Python Model (Alberto, Claire)

- Implement pseudocode
- Model output in this format: [Time step, Point 1 connected at that time step, Point 2 connected]

Ultimate goals for Python model:
- Complex resource and topography distributions
- Some adjustable ability to "see" around you (intelligence or information)
- Have some adjustable ability to make loops
- Have some adjustable constraint for branching angle

Data Analysis

Analysis of Networks (Alex, James, Diana)

- Use NetworkX to generate shape files for Claire
- Use NetworkX to calculate network metrics from models

QGIS (Claire, James)

- Network visualization
- Calculation of network metrics for Avignon, Paris, and empirical ant networks

Refining Project Goals

Discuss paper objectives (Morgan, Bernardo, Diana, Rohan)

- Work through remaining conceptual issues - Decide on paper content - Create skeleton presentation

Continued Literature Review

Look for network parameters from empirical data, especially for city networks (Diana, Morgan, Rohan, Bernardo)

Consider journals for paper placement (Morgan)

Begin paper introduction (Diana, Morgan, Rohan, Bernardo)

References

Bernardo

File:Quick Literature Review on Growth of Cities.pdf

Claire

Growing Artificial Societies
Turtles, Termites, and Traffic Jams
There's also "Artificial Ants" (Nicolas Monmarché) but I can't find a free article about his computation. That's a shame because I remember of a really interesting algorithm with a well done exploration / exploitation balance...

ALSO SEE PAPERS IN DROPBOX

Analysis Goals

Chosen Comparisons

We will be comparing the streets of Avignon to ant trails between nests, and the rail system of Paris to ant trails radiating from a single nest. Claire has data on both of these systems.

Notes on the Statistics of Foraging

Scale-free foraging patterns are currently a hot topic in animal movement biology. Typically, these scale-free patterns are identified through time series data - how far does the animal move before it changes direction? Are these step lengths drawn from a power law distribution?

It is unique to consider foraging in a network context. However, one might hypothesize that a network formed through a scale-free search pattern might also be scale-free. A particular kind of scale-free pattern - called a Levy walk - is extremely popular right now. It is a walk whose steps are drawn from a power law distribution with an exponent of 2. If our foraging network turns out to be scale-free, it might be interesting to look for a Levy-like pattern, and ask whether this is particularly interesting or significant in a network context.

In addition, it would be interesting to note how properties unique to foragers but not to cities (like having to return to a home or nest, or not creating permanent roads) change the shape, structure and fundamental properties of a network. As Aaron Clauset pointed out, simply being scale-free is not that interesting in and of itself. What other properties of networks might be interesting and/or informative? (Clustering... others?)

Network Analyses of Ant Foraging Trails: Relevant Measures

1. Total area foraged by the colony increases with population^(2/3) (Jun 2003)
2. The metabolic cost of foraging increases linearly with population (Jun 2003)
3. Ant networks represent a balance between total length and route factor (Buhl 2009)
4. Foraging networks are typically dendritic in form (Buhl 2009)
5. Route factor = 1.13 (Buhl 2009)
6. Trail branching angle = 49.33 + or – 29.9 degrees (Buhl 2009)
7. Are node distributions different from complete spatial randomness? (see Cook 2014)
8. Measures of centrality: betweenness, closeness (see Cook 2014)
9. Measures of robustness (see Cook 2014)
10. For ant travel networks, robustness is between 14 and 72%.

Network Analyses of Cities: Relevant Measures

1. Edge length distribution (Courtat "Hypergraphs...")
2. Degree distribution
3. Route factor (Gastner and Newman 2006B)
4. Total length (Gastner and Newman 2006B)
5. Measures of centrality: betweenness, closeness (Courtat "Centrality Maps...")
6. Measures of robustness
7. Claire has some of her own indices we might like to use...

- Diana

Exploratory Notes

Alfred's model

Alfred's paper has been added to the background reading tab in the Dropbox folder.

First of all, Alfred has not published all of his projects. There are no papers on the arbortrons (the self-assmebling dendritic trees). There is however a paper on the self-assembling electrical wire, a process which is governed by the same physical laws as the trees. So, I think the model presented in the latter work will suffice.

The model that Alfred uses to "describe" the self-assembling wires is more of a proof that begins with the principles of electromagnetism and the minimization of energy in order to "show" that the self-assembled wires are the lowest energetic state that can be formed, and thus will always be formed. It's important to point out that there is no computational/simulative component to his model. Instead, the modeling work done is to show that the configuration provided by the self-assembling wires acts so as to minimize the resistance to the flow of electrons through the sample, as well as showing that this type of configuration is the stable state of the system. This is then compared to the experimental results of observing the formation of the wires.

Unfortunately, the work done in which the self-assembling dendritic trees seek out their electromagnetic resources in such a way so as to demonstrate Levy-Walks was never published. It would be interesting to know if there was any unpublished theoretical work done for these resource searching trees in the same flavor as for the self-assembling wires.

- Alex

Slime mold

[1]

List of relevant animals

Ants
Limpets
Vultures

Modeling and Data Notes

Data

OpenStreet Maps are available to import directly into QGIS. Go to Vector -> OpenStreetMaps
Also, Metro areas of the world are available at [[2]] Bernardo

Ernest's Model

I've written down a summary of the model I made (dropbox doc 'Ernest Model'), and I'm going to implement it in NetLogo.

Alberto's Model

I think my proposition is quite similar to that by Rohan, but I am putting this here as a matter of discussion.

As a first approximation I would suggest to model the space as a grid, then eventually extend the model to continuous space.

Each position of the space has a carrying capacity C, i.e. the number of people that can fit in that position. This carrying capacity can also depend on the altitude or other parameters. For each time step a new citizen arrives in an already settled position (chosen at random, or preferentially according to the least crowded one), but she then may decide to move and to settle to another neighboring position. For instance, this migration can happen with a probability proportional to the crowdedness of the current position. The new position is chosen in an opportunistic way selecting the one that has the minimum cost for the new citizen among the four neighboring cells (of course, this is extendable).

Each position has a cost that depends on the following parameters:
the difference in the altitudes between the two cells, h
the distance from the water or another resource, d
the number of people that already occupy that area, n

The cost can be of this form (using then different normalization functions):

c=d*h + n

Other thoughts on modeling...

Here's my idea for a network model. We start out with a grid (fine, but still a grid; a continuous map may be too computationally intensive), with each cell possessing some attributes: elevation, proximity to resources, and proximity to roads. We choose a root at random (or not) and add nodes by the following process: within the field of view (an NxN square surrounding each node), choose the cell whose edge has minimum cost. The cost is determined by taking into account the following values: the effective length of the proposed edge (factoring in topography), the length of the path from the root to the proposed node, (from the Gastner and Newman paper), the proximity of the new node to the nearest resource, and the proximity of the node to existing roads (the closer it is to existing roads, the less we need to make it a node in the road network). The resource proximity part should be a function of population density: the greater the population/the smaller the resource budget of the population, the more heavily weighted this part. If the resource budget is sufficient (this will only be temporary), no node is added; we can ignore these steps since nothing happens. The foraging model will be the exact same model except roads are not built on the network; the network still exists as a set of repeated movement patterns, but there are no roads, and so the proximity-to-roads part of the cost function has weight 0. Foraging animals probably do not use their much-traveled paths to go anywhere other than the end of the path. If the resource budget situation is dire and there are no really useful cells in the field of view, there is an option to jump to a random location that is nearby but outside the field of view and add the resulting patch to the field of view. Of course, in most cases such a jump would result in fairly long proposed edges, which would be costly, but hopefully the benefit of landing near a resource outweighs the cost. The jumps can have a distance from the field of view drawn from a heavy-tailed distribution.

- Rohan

From "Foraging Theory", Stephens and Krebs, Princeton University Press, 1986

Three elements to consider when developing foraging models (or optimality models in general):
1) Decision Assumptions - Which of the organism's problems (or choices) are to be analyzed?
2) Currency Assumptions - How are various choices evaluated?
3) Constraint Assumptions - What limits the organism's feasible choices, and what limits the pay-off (currency) that may be obtained?

In terms of classic foraging models, we are interested in a patch model. This is a model in which an organism searches for a patch of food, which may regenerate, and which the organism may or may not consume completely.

"Formal models are valuable because they permit both rigorous analysis and testing. Optimization models consist of three components - decision assumptions, currency assumptions, and constraint assumptions. The decisions studied by conventional foraging models relate to prey choice and patch exploitation; the currency in these models is long-term average-rate maximization (maximum energy input per unit time); and the constraints are exclusivity of search and exploitation (you cannot search for food and consume food at the same time); sequential, random search; and the assumption of complete information (the forager behaves as if it knows the rules of the model)." - pages 11 and 12, parenthetical explanations mine