Question for Friamers! ... 2D vs. 3D
Locked
Question for Friamers! ... 2D vs. 3D
 
|
So ... I've been programming a lot in NetLogo and so forth, and I've thought about the inherent differences between 2D models and 3D models (or even higher dimensions). But I haven't thought about it very deeply, and I haven't formally investigated how the properties of, say, clusters of self-organizing agents behave in a 2D environment vs. a 3D environment.
So the other day someone asked me: what are the issues, what are the differences? Fundamental or superficial? Offhand, I sort of assumed the relationship between different simulation spaces would be pretty much the same in both 2D and 3D. Sure, I assumed there would be a scaling issue, but not much else. (e.g., a 2D pred-prey model would show different numbers than a 3D pred-prey model, but the dynamics would be essentially the same.)
Is this true? Anyone ever investigate this question? Know of some good papers out there? Other resources? I'm not assuming an infinite space, if that makes a difference ... in a 2D environment I assume a torus, and imagine if I programed a 3D simulation I would use similar assumptions.
Any guidance would be greatly appreciated! I have a presentation on Friday, and I would like to be able to cover this issue. Thanks! -Ted ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
> But I haven't thought about it very deeply, and I
> haven't formally investigated how the properties of, say, clusters of > self-organizing agents behave in a 2D environment vs. a 3D environment. > > So the other day someone asked me: what are the issues, what are the > differences? Fundamental or superficial? > > Offhand, I sort of assumed the relationship between different simulation > spaces would be pretty much the same in both 2D and 3D. Sure, I assumed > there would be a scaling issue, but not much else. (e.g., a 2D pred-prey > model would show different numbers than a 3D pred-prey model, but the > dynamics would be essentially the same.) > > Is this true? It's certainly not *obviously* true, and there are sound reasons (I think) behind my off-the-cuff intuition that it's false. (However, if someone has actual *data*, that might trump intuition. Or not.) The "drunkard's walk" in 2-dimensional (flat, infinite) space is recurrent; in 3- or greater- dimensional (flat, infinite) space, it isn't. (Your self-restriction to a torus kills part of the reason that works, but not the whole thing.) More generally, the behavior of limit sets for systems of ODEs in the plane is very, very nice, because the topology of the plane is fairly nice; whereas the behavior of limit sets for sysstems of ODEs in 3- (and much more so, greater)D can be nasty beyond belief. (Well, in the presence of people who are so much into chaos, I guess I shouldn't say *nasty*. How about, complicated?) And here your finiteness assumption wouldn't help at all. I suspect that Ed Lorenz's original numerical calculations that eventually led to a solid mathematical understanding of the Lorenz attractor in 3D could, without much heavy lifting, be embedded into a 3D NetLogo model of something-or-other. For 3D pred-prey models, look for stuff by combinations of Zeeman (E.), Zeeman (M.), and Hirsch. Sorry I can't be more specific without a search I don't have the time for right now. Bye. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
|
In reply to this post by Ted Carmichael
Ted -
There are probably a lot deeper and more well supported answers, but I have two observations that might help. In 2D vs 3D force-directed (energy minimization) graph layout, there is a big difference in nodes being trapped in "local minima" in the 2D case. It is *much* less likely for a node to get trapped in a local minima in 3D. Depending on your agent model, similar effects are likely to be experienced (for better or worse). 3 is the smallest number of dimensions where an arbitrary set of nodes can by connected by an arbitrary set of edges w/o the edges crossing. This is sort of a degenerate argument and is a corrolary to the former point made. I *am* interested myself in the question of how the dimensionality of the embedding space effects the dynamics of an agent model. Around 1984 I think it was Doyne Farmer who demonstrated the equivalence between higher dimensional and lower dimensional Cellular Automata. The lower dimensional CA had to have a larger state space (and/or neighborhood) but he demonstrated (and proved) that any CA in a high D could be implemented in a lower D (all the way down to 1D of course). I think this probably could be shown to be a corrolary to the Computational Universality of the Turing Machine. I look forward to deeper and broader discussion here... - Steve ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
|
In reply to this post by Ted Carmichael
Hi Ted,
I think I have read somewhere (in Wolfram's NKS book or Ilachinski's Cellular Automata book) that Cellular Automata in 3D do not behave significantly different than those in 2D. For many abstract agent-based models, say W. Brian Arthur's El Farol Bar Model, Axelrod's Dissemination Model or Schelling's segregation model, it probably doesn't matter if the environment is 2D or 3D. A three dimensional environment certainly is important if you consider models with direct physical interaction of the agents where the dimension is part of the model, for example models about boids, swarms or flocks. -J. ----- Original Message ----- From: Ted Carmichael To: The Friday Morning Applied Complexity Coffee Group Sent: Monday, March 01, 2010 4:02 PM Subject: [FRIAM] Question for Friamers! ... 2D vs. 3D So ... I've been programming a lot in NetLogo and so forth, and I've thought about the inherent differences between 2D models and 3D models (or even higher dimensions). But I haven't thought about it very deeply, and I haven't formally investigated how the properties of, say, clusters of self-organizing agents behave in a 2D environment vs. a 3D environment. So the other day someone asked me: what are the issues, what are the differences? Fundamental or superficial? Offhand, I sort of assumed the relationship between different simulation spaces would be pretty much the same in both 2D and 3D. Sure, I assumed there would be a scaling issue, but not much else. (e.g., a 2D pred-prey model would show different numbers than a 3D pred-prey model, but the dynamics would be essentially the same.) Is this true? Anyone ever investigate this question? Know of some good papers out there? Other resources? I'm not assuming an infinite space, if that makes a difference ... in a 2D environment I assume a torus, and imagine if I programed a 3D simulation I would use similar assumptions. Any guidance would be greatly appreciated! I have a presentation on Friday, and I would like to be able to cover this issue. Thanks! -Ted ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
In reply to this post by lrudolph
Earlier today, I replied to Ted Carmichael's question:
... > > Sure, I assumed there would be a scaling issue, but not much else. > > (e.g., a 2D pred-prey model would show different numbers than a 3D > > pred-prey model, but the dynamics would be essentially the same.) > > > > Is this true? thus, in part: > For 3D pred-prey models, look for stuff by combinations of Zeeman > (E.), Zeeman (M.), and Hirsch. Sorry I can't be more specific without > a search I don't have the time for right now. Okay, http://www.ams.org/tran/2003-355-02/S0002-9947-02-03103-3/ is a good place to start. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
|
Once you get past about 10 dimensions you hit problems of "distance concentration" (as it's known in the machine learning community). Basically, all distances between pairs of points for D>10 are pretty much the same. That impacts any distance-based clustering or visualization techniques that you are trying to use.
-- R ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
|
Thus spake Robert Holmes circa 10-03-01 02:49 PM:
> Once you get past about 10 dimensions you hit problems of "distance > concentration" (as it's known in the machine learning community). Basically, > all distances between pairs of points for D>10 are pretty much the same. > That impacts any distance-based clustering or visualization techniques that > you are trying to use. Is that true for all norms? Or just the standard 2-norm? -- glen e. p. ropella, 971-222-9095, http://agent-based-modeling.com ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
|
|
On 1 Mar 2010 at 15:01, glen e. p. ropella wrote:
> Thus spake Robert Holmes circa 10-03-01 02:49 PM: > > Once you get past about 10 dimensions you hit problems of "distance > > concentration" (as it's known in the machine learning community). Basically, > > all distances between pairs of points for D>10 are pretty much the same. > > That impacts any distance-based clustering or visualization techniques that > > you are trying to use. > > Is that true for all norms? Or just the standard 2-norm? *Gotta* be possible to handpick a better norm in any given case, no? (But as you keep resampling and refining the data you might have to modify the choice of norm adaptively, which might defeat you in the end. It would help [me, at least] to have a more precise statement of what the reported phenomenon actually is. Robert? Should I just do a Google search for the conjoined phraes "distance concentration" and "machine learning", or can you speed up the process with a few more words?) ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
|
In reply to this post by Robert Holmes
Thanks for all the interesting comments, everyone.
Lee's comments mirror what someone else told me, re: the random walk. They also said that populations of agents/particles - such as in Brownian motion - tend to exhibit clusters in 2D, but not in 3D. (I would assume - but haven't explored - that particles in 3D could still cluster under the influence of attractors. Thoughts?)
Steve pointed out a couple of things that I'll have to keep in mind for future models - the local minima in 2D vs. 3D, and free edges in a >2D network structure - but I don't think apply to the current models I'm exploring. But I'm definitely going to read up on the equivalence of CA models.
Jochen raised the important point that most social science models tend to have an abstract relationship between nodes. I agree that the dimensionality probably isn't meaningful here ... with abstract concepts for the edges, I reckon each additional node would probably add another dimension to the model (if one were concerned with mapping the model to Euclidean space.)
And since I'm not using a clustering algorithm in >10D space, I won't worry about Robert's point (but it's a very cool concept. Again, I'll keep that tucked away for future reference.)
Let's look back at Jochen's comment, in regards to spatial patterns in 2D vs. 3D. (Can't seem to access Lee's link at the moment, so I'll stay away from the math for now.) I'm thinking about a pred-prey model (in 2D) similar to Ken Hawick's found here, such that the prey reproduce, forming a blob or circle. Then the predators come in, and the circle degenerates into a crescent shape. (We replicated these type of clusters and their movements in our model, although with somewhat different agents and rules.)
Since the spatial relationships matter, I assumed that a 3D model of the same agents would tend to form spheres rather than circles; and when the predators come in, they dig out a bowl shape rather than a crescent shape ... although for the same general reasons. But I'm just guessing here.
That covers the spatial effects. In terms of populations, I assumed that either the pred or the prey would be more efficient and therefore have different numbers, but that these would scale up or down, and thus show the same general dynamics (a la the Lotka-Volterra equations). If I had to guess, I would say the prey population would tend to be larger (relative to the pred population) than in the 2D model. But I wouldn't really count on that until I ran the simulation.
Does that sound about right? Has anyone played around with other spatial effects, moving from 2D to 3D? Lee - on a side note, how familiar are you with the Lotka-Volterra dynamics? Particularly with more than two populations (i.e., 3 or more strictly defined tropic levels). We've found some interesting results, but I don't yet know if they are interesting to just me, or would be to anyone.
-Ted On Mon, Mar 1, 2010 at 5:49 PM, Robert Holmes <[hidden email]> wrote: Once you get past about 10 dimensions you hit problems of "distance concentration" (as it's known in the machine learning community). Basically, all distances between pairs of points for D>10 are pretty much the same. That impacts any distance-based clustering or visualization techniques that you are trying to use. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
|
I am not sure what you want to model,
perhaps you are mixing different models here? * predator-prey or Lotka-Volterra equations describe the long-term population density over multiple generations * boids and flocking models describe the short-term spatial form of animal groups on the move In the first case you will get oscillations and periodic population patterns, in the last case you will get flocks and swarms. Probably you mean defensive swarm behavior during predatory attack: flash expansion, split, vacuole, etc? Then maybe this link about "Self-Organized Fish Schools" is interesting http://www.biolbull.org/cgi/content/full/202/3/296 A National Geographic article says "When a predator strikes a school of fish, the group is capable of scattering in patterns that make it almost impossible to track any individual. It might explode in a flash, create a kind of moving bubble around the predator, or fracture into multiple blobs, before coming back together and swimming away http://ngm.nationalgeographic.com/ngm/0707/feature5/text4.html Iain Couzin's site at Princeton has also many papers about collective motion and decision-making http://webscript.princeton.edu/~icouzin/website/ -J. ----- Original Message ----- From: Ted Carmichael To: The Friday Morning Applied Complexity Coffee Group Sent: Tuesday, March 02, 2010 1:58 AM Subject: Re: [FRIAM] Question for Friamers! ... 2D vs. 3D [..] I'm thinking about a pred-prey model (in 2D) similar to Ken Hawick's found here, such that the prey reproduce, forming a blob or circle. Then the predators come in, and the circle degenerates into a crescent shape. (We replicated these type of clusters and their movements in our model, although with somewhat different agents and rules.) Since the spatial relationships matter, I assumed that a 3D model of the same agents would tend to form spheres rather than circles; and when the predators come in, they dig out a bowl shape rather than a crescent shape ... although for the same general reasons. But I'm just guessing here. That covers the spatial effects. In terms of populations, I assumed that either the pred or the prey would be more efficient and therefore have different numbers, but that these would scale up or down, and thus show the same general dynamics (a la the Lotka-Volterra equations). If I had to guess, I would say the prey population would tend to be larger (relative to the pred population) than in the 2D model. But I wouldn't really count on that until I ran the simulation. Does that sound about right? Has anyone played around with other spatial effects, moving from 2D to 3D? Lee - on a side note, how familiar are you with the Lotka-Volterra dynamics? Particularly with more than two populations (i.e., 3 or more strictly defined tropic levels). We've found some interesting results, but I don't yet know if they are interesting to just me, or would be to anyone. -Ted ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
Administrator
|
In reply to this post by Ted Carmichael
I'd be careful assuming 2D problems having similarity with 3D problems.
An example Frank can tell you more about is the commutability of rotations. This works fine in 2D but not in 3D. In an area I'm more familiar with, polynomial time vs exponential time algorithms, there is a huge break between 2 and 3 versions. Indeed, much of the NP-Complete world has to do with the 2-3 split. - Graph 2 coloring is in P, 3 coloring is not. - 2 variable boolean clause satisfiability is in P, 3 is not. and so it goes. Even more surprising, is that k-coloring can be reduced to 3-coloring and similarly for satisfiability. Thus there is a split in difficulty between 2 & 3, and larger dimensions can be reduced to 3, but not 2. Even worse, for your computer programming, most algorithms you are using are likely reducible to these algorithm classes above. I'm only partly through the study, CS500 sent to the group earlier, but boy am I surprised by the oddities we're finding. So I'd be very careful about the 2D-3D distinction, at least in the geometric domain and the algorithmic domain. -- Owen On Mar 1, 2010, at 8:02 AM, Ted Carmichael wrote: So ... I've been programming a lot in NetLogo and so forth, and I've thought about the inherent differences between 2D models and 3D models (or even higher dimensions). But I haven't thought about it very deeply, and I haven't formally investigated how the properties of, say, clusters of self-organizing agents behave in a 2D environment vs. a 3D environment. ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
Re: Question for Friamers! ... 2D vs. 3D
|
|
In reply to this post by Jochen Fromm-4
Well, yes ... it is sort of a mix of the two. We compare the resulting spatial forms qualitatively to Hawick's clusters. But it is definitely a predator-prey model, and the oscillations match what you would expect generally from the Lotka-Volterra equations. (I say generally because of course an ABM ignores a few of the assumptions under LV. Come to think of it, I should probably look more closely at the mathematics of it. But not this week.<g>)
The interesting thing (at least, to me) is that the spatial forms emerge in our model even though we do not explicitly program the predator population to move towards each other. (In fact, they do not sense each other in any way ... their clusters form only due to indirect feedbacks.) In Hawick's model they do tend to cluster explicitly, but I think it is a much simpler mechanism than those you described (flash expansion, etc.)
Thanks for the links! I will definitely check those out. I've come across Iain Couzin's site before, but I appreciate the reminder. -Ted
On Tue, Mar 2, 2010 at 5:03 PM, Jochen Fromm <[hidden email]> wrote: I am not sure what you want to model, ============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org |
«
Return to Friam
|
1 view|%1 views
| Free forum by Nabble | Edit this page |