Cities Growth Page

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?

Groups Members

Alberto (alberto.antonioni@unil.ch)
Alex (brummera@email.arizona.edu
Bernardo (bernardo.furtado@ipea.gov.br)
Claire (lagesse.claire at gmail.com)
Diana (dianalg11@gmail.com)
Ernest Liu (yu.liu@math.uu.se)
James
Michael Kalyuzhny (michael.kalyuzhny at mail.huji.ac.il)
Morgan (morgane@mit.edu)
Rohan (rsmehta at stanford dot edu)

Meetings

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

---

done :

Thursday 12 : 6:00 pm - 7:00 pm
Monday 16 : 2:30 pm - 4:15 pm

Ongoing work

• Create a wiki page ! (Claire) [OK]

• Write the research question (Morgan) [OK]

Literature

• Find more references (Claire [OK] & Rohan [OK])
• Overview of NetLogo models libraries (Ernest)
• Overview of Aaron's model (Rohan [OK])
• Overview of Alfred's experiment model (Alex)
• Overview of Slime mold model (Michael & Ernest)

Data

• List & Upload data on the Dropbox (Claire)
• Historical Maps of Santa Fe (Alex)

Foraging perspective

• Think about the processes we want to model (Diana & Michael)
• List relevant animals to study (James, Diana & Michael)

Modelling First Step

• Think about the models which could be relevant (Ernest, Claire, Bernardo, Alberto, Morgan, Rohan)

>> Let's write a little paragraph for each model we have in mind

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...

Overviews

Slime mold

[1]

Processes

Foraging processes we want to observe

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?)

List of relevant animals

Ants
Limpets
Vultures

Models

Alberto's proposition

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

Rohan's proposition

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.

Anyone else ? :)

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

Concept Map/Table

Ants

• Cost (Ground)
• Resources (Food, Water)
• Information (Less)
• Patch
• Resources (Depleting)
• Roads (Temporary)
• Nest

Cities

• Cost (Ground)
• Resources (???)
• Info (More)
• Patch
• Resources (Continuous)
• Roads (Permanent)
• Center