In what order? Celluar Automata etc

[f95toli]

I recently read Phillip Balls excellent book "Critical Mass" where he describes a number of modes that are used in social physics. After reading the book I started thinking about a question that I never managed to answer many years ago when I did a small school project about celluar automata (I wrote a simple Pascal program which simulated a number of "animals" feeding off some constant source of food, there where also a number of predators, the animals and predators would move around on the screen and react acording to simple rules depening on what went on around them) .

Now, the question was: If you have a computer model where a number of "agents" can react to what happening around them, how do you decide in which order to process the "actions" of said agents (in a model with discrete time)?

Let me give you an example of what I mean. Start with a 4x4 matrix, e.g

1011
0100
1111
0111

the rule is that each element looks at its four neighbors and then flips to align itself with the "majority", e.g a 0 will become a 1 if the agent has 3 or more 1 as neighbors (this is just a simple Ising model).
Lets say I want to run this model, how do I decide in which order to process the elements?
Since each element is looking at its surroundings it obviously matters.

There are lots of models like this, "Game of Life" is perhaps the most famous example but there are many others.

Is it possible to prove mathematically that the order does not matter for a certain model?
The Ising model outlined above can be solved analytically and on an infinte matrix the it does not matter, you will get ferro- or anti-ferromagnetic ordering depending on the coupling. However, it is not obvious for all models.

BTW, the same problem should arise in any RTS game, does anyone know how this problem is usually solved in games?

 

[magillig]

If I understand you correctly, the problem is as soon as you calculate on element, that throws off all of the other element's calculations. To solve this problem, I would calculate each element, but do not change that element's value, instead store the calculated value into another array. Once all the elements have been calculated you can either transfer those values over to the original array, or use the second array as you did the first.

That is, from the array in your example, you would get a second array that looks like this:
0101
1011
0111
1111

 

[f95toli]

Sure, but what happens it there are two "conflicting" flips?
E.g element (2,2) is 0 and should flip since it has 3 or more neighbors that are 1. However, what happens if two of those neigbors in turn have three or more neighbors that are 0 meaning they should flip? Then element (2,2) should NOT flip.

This is not really a programming problem. As far as I can tell it is a general problems for ALL interaction models where there are discrete agent discrete timesteps.
I know that models like these are used in physics, economy, political science, safety (what is the most efficient way to evacuate a burning building) etc
From my point of view this means that UNLESS you can show that a certain model is insensitive to the order in which you process your agents, the model itself is of very limited use.
It is also a problem in any RTS but obviously that is not as important.

 

[TuxDave]

Originally posted by: f95toli
Sure, but what happens it there are two "conflicting" flips?
E.g element (2,2) is 0 and should flip since it has 3 or more neighbors that are 1. However, what happens if two of those neigbors in turn have three or more neighbors that are 0 meaning they should flip? Then element (2,2) should NOT flip.

This is not really a programming problem. As far as I can tell it is a general problems for ALL interaction models where there are discrete agent discrete timesteps.
I know that models like these are used in physics, economy, political science, safety (what is the most efficient way to evacuate a burning building) etc
From my point of view this means that UNLESS you can show that a certain model is insensitive to the order in which you process your agents, the model itself is of very limited use.
It is also a problem in any RTS but obviously that is not as important.

Then you're already choosing an order to which they should be processed. The converse of that would be that the outside should not flip because the shared common one would've flipped and that would've removed the majority.

That's why the idea of simultaneous flipping where you determine what flips given its CURRENT state and not future states gets rid of those conflicts.

 

[f95toli]

I see what you mean. However, but I am missing something that does not really solve the problem because that would mean that you might end up with a new state which does not really follow the rules, e.g a certain agent will have flipped from 0 to 1 even though only 2 neighbors are 1 in the new state (because one 1 flipped to 0). This means that the new state would have a higher "potential energy" that old which is unphysical.

In the Ising model this is really a problem since you are only interested in which state minimizes the energy, i.e you do not care how you get there.
But in some of models described in the book the path you take to the final state is what is important.

Besides, assume you have a set of rules which describe motion (let 1=occupied and 0=unoccupied) meaning the numer of ones is conserved, you will frequently run into the problem that given the current state two agent wgiven the current state wiill want to move to the same square; essentially the same problem as before.

I guess what I interested in is how you mathematically handle problems like this ?

 

[Matthias99]

Originally posted by: f95toli
I see what you mean. However, but I am missing something that does not really solve the problem because that would mean that you might end up with a new state which does not really follow the rules, e.g a certain agent will have flipped from 0 to 1 even though only 2 neighbors are 1 in the new state (because one 1 flipped to 0). This means that the new state would have a higher "potential energy" that old which is unphysical.

I'm not sure why this is a problem. Depending on the rules you define, this can create 'oscillating' systems or other unusual behavior, but it is mathematically valid. You're just talking about mathematical models here.

In the case you described (a square with three neighbors that are '1', but only one of those squares has three neighbors that are '1'), you would have something like this:

0.1.0.0.0
1.1.0.1.0.
0.1.1.0.0.
0.0.0.0.0.

then

0.0.0.0.0
0.1.1.0.0.
0.0.0.0.0.
0.0.0.0.0.

then

0.0.0.0.0
0.0.0.0.0.
0.0.0.0.0.
0.0.0.0.0.

There's nothing 'wrong' with that.

Besides, assume you have a set of rules which describe motion (let 1=occupied and 0=unoccupied) meaning the numer of ones is conserved, you will frequently run into the problem that given the current state two agent wgiven the current state wiill want to move to the same square; essentially the same problem as before.

I guess what I interested in is how you mathematically handle problems like this ?

There is no 'right' answer; your model should define rules for how to handle this.

If you are trying to model 'motion' and you have a 'collision', the two objects should either bounce off each other or stick together (depending on the elasticity of the objects involved), and may lose some net energy. Your model should include some concept of velocity and/or mass (if you want to include conservation of momentum), and rules on how objects interact when they 'collide'.

 

[f95toli]

I agree. But my point is that in most of the models I have seen they do not explicitly state the rules for what happen when there is a collision.
I have read a few books about this type of modelling and I have never seen a discussion about this.
This means that either it does not matter (and then my question is: Can you somehow prove this mathematically?) or it matters but it is assumed that if you run the models many times and randomize the initial state the effects will be "averaged out" (but again: Can you somehow prove this?).
(a third possibility is of course that they have not considered the problem)

After all. if you want to claim that a certain model can tell us something about the "general properties" of the real world (which is how these models are used in social physics) the order in which the agents react should not matter.

 

[Born2bwire]

Originally posted by: f95toli
This is not really a programming problem. As far as I can tell it is a general problems for ALL interaction models where there are discrete agent discrete timesteps.
I know that models like these are used in physics, economy, political science, safety (what is the most efficient way to evacuate a burning building) etc

In these cases, you evaluate all of the elements based upon the data from the previous time steps values. For example, if you do a finite difference time domain solution to an EM problem, you evaulate the new E fields based on the old E and H field values, advance half a time step, and then calculate the new H field based on the new E and old H field values. If you evaluate the elements in a certain order and evaluate them using the data from each updated element, then you are no longer evaluating within a single timestep. You should assume that each element will update itself at the same time within the time step. As long as you are using the data from a previous time step, then the order in which you process the elements will not matter. But if you use the updated data from the current time step, then you are violating FDTD by implying that there has to be some progression of time such that element one updates and then element two updates based upon element one's new data and any other old data.

I guess what I am trying to say is that by taking a discretized time space, by nature you are restricting any event to occur at a specific point instantaneously. So even though the new value of an element may be dependent upon the values of the surrounding elements, you are always taking the values from the previous time step. Taking values from your current time step (which is the only way for order of processing to matter) would imply that there must be a progression of time within your time step and thus you need to further discretize your problem.

 

[f95toli]

No, it is not quite the same thing. There are a few differences between a discretized PDE and the models I am describing above.

*Most PDEs are continuos both in space and time (there are a few exceptions) whereas interaction models I am refering to are truly discrete in "space" (meaning there is fixed numbers of agents) . Moreover, HOW you discretize space/time should not matter for the solution (i.e if you increase the number of grid points you get closer to the correct solution), in a model with a fixed number of agents this is not possible.

* In FEM solvers you are operating on the whole matrix at once, the grid points are not really "interacting".

* You are usually only interested in the solution, HOW you find the solution is irrelvant (it only affects how long it takes for the solution to converge) but if you are study interaction how you reach a stable state (iuf such as state exists) clearly matters (or at least you want to be sure that there are only a few stable trajectories).

*In FEM there is always a way to estimate the error, I don't think that is possible in "Interacting agents" models(?)

I guess you could think of these problems as multi-variable optimization problems, with the added condition that HOW you reach the solution might matter.

 

[Born2bwire]

Originally posted by: f95toli
No, it is not quite the same thing.

I guess you could think of these problems as multi-variable optimization problems, with the added condition that HOW you reach the solution might matter.

If you're talking about multi-variable optimization then this would be something like Powell's method or simulated annealing. I am not sure how well Powell's method handles local minima though.

* In FEM solvers you are operating on the whole matrix at once, the grid points are not really "interacting".

The field strength between gridpoints are still interacting with eachother. EM FDTD just has very simple rules to ensure boundary conditions and stability. The stability conditions allow us to look at the gridpoints as only dependent upon the previous time step without violating our rules. But the wave nature of the problem requires that the value of the field at the next time step at a given point is dependent upon the values of the fields of its neighbors. If we choose to ignore the stability condition, boundary conditions, or the rules governing the problem (in our case, Maxwell's equations) then the problem will propgate into an impossible state (i.e.--> infinite field strength). Just like your flipping agent problem.

*In FEM there is always a way to estimate the error, I don't think that is possible in "Interacting agents" models(?)

Most optimization algorithms work with minimizing the error. So if your system is working towards minimum energy, then I would probably take the error to be the amount of energy that the system has above the ground state.

I see where you're going for in all this now. I think what you need to do is to rigorously define the rules and functions to describe your problem and define how to measure your error. From here there are several iterative optimization algorithms that you could use that work towards minimizing your error. For example, the method of least squares is a common method for minimizing the error of an adaptive filter. From the error of the previous time step, we adapt our filter iteratively until we minimize the error of the output. So any number of iterative optimization algorithms, like least squares, Powell's, simulated annealing, would be suited to your purposes because you can keep track of how your problem propagates toward its solution.

 

[f95toli]

Well, the thing is I am not thinking about a particular problem (the Ising problem I outlined above is just a very simple example).
I am trying to understand some of the basic properties of this CLASS of models ("Critical Mass" by Phillip Ball is full of examples of models with interacting agents).

I know quite a lot about how to solve various PDEs (although nowadays I mainly use Femlab, or Comsol Multiphysics as it is known now, and Matlab/C/F77 only when I have to ) but frankly I have no idea how to handle this class of problems in a rigorous way (this Ising model is an exception, since it can be solved analytically in 2D).

Btw, I think you are missing one important point.
In some cases there is no "solution" as such. E.g in a simple model of the stock market each agent will try to to maximize its profit by interacting with other agents.
Now we come across the same problem: In which order should the agents trade? Does it matter? How do you define the "error" in this problem?
In this case I suspect it would be enough to simply run the model many times, randomize the initial distribution of "resources" and then assume that you can handle all of the runs as a statistical ensemble, meaning you can study "average" properties of all of these runs(in this case e.g. fluctuations). However, how do you prove mathematically that this works?

 

[Matthias99]

Originally posted by: f95toli
Btw, I think you are missing one important point.
In some cases there is no "solution" as such. E.g in a simple model of the stock market each agent will try to to maximize its profit by interacting with other agents.
Now we come across the same problem: In which order should the agents trade? Does it matter? How do you define the "error" in this problem?

The "error" depends on what it is you are trying to solve for (maximizing ROI, minimizing risk, etc.) You have to define what it is you are looking for and how to measure it before you can try to find it. In situations that do not have a clear-cut "solution", you are still often trying to minimize or maximize some quantity.

But in terms of actually doing the modelling and running simulations, you would have to define some sort of rules about how the 'market' works, trying to compromise between accuracy and complexity of the simulation. For instance, in a stock-market simulation, each agent could take turns (round-robin) offering trades to another agent (or passing), and the trade must be immediately accepted or denied. Or, depending on the sort of market you are modelling, it might make more sense for agents to put a stock or future (or whatever) 'up for grabs', and then the other agents could 'bid' on it in turn until nobody wants to top the current bid.

You can get very, very complex in modelling multi-agent systems. Game theory can often be useful in more complex situations (using techniques such as Markov modelling to analyze your simulation and look for optimal strategies).

In this case I suspect it would be enough to simply run the model many times, randomize the initial distribution of "resources" and then assume that you can handle all of the runs as a statistical ensemble, meaning you can study "average" properties of all of these runs(in this case e.g. fluctuations). However, how do you prove mathematically that this works?

If the simulation is small enough, you could potentially test every possible starting resource distribution (or whatever set of initial conditions there are), and hence reach a deterministic conclusion. If that is impractical due to time or other resource constraints, you would have to take a bunch of samples/guesses and produce results within a confidence interval, as with any other search technique. In complex, potentially unbounded searches, you often *cannot* reach a definitive conclusion without spending an intractable amount of time or effort.