Diffusing Populations: Ghosts or Folks?
Simpson, Mat J., Hughes, Barry D., Landman, Kerry A., Australasian Journal of Engineering Education
In a random walk model (Hughes, 1995; Berg, 1983), an agent moves in a sequence of random steps. Such models are easy to simulate and well-suited to student projects. Students can learn important ideas in a highly intuitive context, while the subject is still an area of active mathematical research. We are interested in applications of random walk models in biological contexts, especially cell motility in tissue engineering and developmental biology (Simpson et al, 2007; Tremel et al, 2009). This kind of discrete random walk model may also be referred to as a kind of cellular automata model. We show how simulation leads to insight and suggests connections to other modelling paradigms, and then show how these connections can be derived mathematically. The procedure is in a sense the reverse of the process of discretising a partial differential equation (PDE) for numerical computation.
We consider agents occupying sites of the square lattice. The possible locations of an agent are (i, j), where i and j are integer coordinates. When attempting to move, an agent at site (i, j) will always choose one of the four target sites (i, j -1), (i, j + 1), (i -1, j) or (i + 1, j). The way the site is chosen is described in table 1. The third column gives the probability of the choice being made. To simulate this process, for each step we draw a random number S uniformly distributed in the interval o [less than or equal to] S [less than or equal to]. The fourth column in the table shows the interval in which the random number must fall for the target site to be chosen.
Here -1 [less than or equal to] [[rho].sub.x] [less than or equal to] 1 and -1 [less than or equal to] [p.sub.y] [less than or equal to] 1: these two parameters control the preferred direction of drift. For example, if 0 < [[rho].sub.x] < 1, the agent makes both left and right moves, but right moves are favoured. Elegant results are available for a single agent moving by this or other rules (Hughes, 1995) and there are many applications (Hughes, 1995; Berg, 1983). However, we shall be interested in the behaviour of crowds of agents. We consider two models which represent different extremes.
In the ghost model, agents do not interact at all. Two agents can step through each other, and there is no limit on how many agents can occupy the same site at any instant. Questions about the ghost model can be rephrased as equivalent questions for a single agent in a classical random walk process.
In the folks model, we never permit two agents to occupy the same site simultaneously. This captures an important aspect of many multi-agent systems, where volume constraints or territorial aggression lead to one agent excluding other agents from its immediate vicinity.
There are many ways to implement the ghosts and folks models. We always consider the case where there are N agents present, and we select an agent at random and deal with it, then we chose another agent and deal with it, and so on. Of course, sometimes the same agent will be chosen more than once in this process; but the average number of times that a given agent is chosen per time step will be unity. This protocol is described as random sequential update (Chowdhury et al, 2005).
When an agent is chosen, there is a probability P that it decides to attempt a move: we draw a random number R from the interval 0 [less than or equal to] R [less than or equal to] 1 and the agent attempts to move if R [less than or equal to] P, and decides not to move otherwise. The value of P can be used to control the level of activity of the agents, with small P representing minimal motility, and P = 1 representing maximal motility.
For each agent offered an opportunity to move, another random number S is drawn. Motile ghosts always accept an opportunity to move according to table 1. Motile folks, however, move according to the rules in table 1 with the additional constraint that the target site must be empty. …