Re: [Repast-developer] Topology Notes

[Thomas R. H. <th...@sr...>]

This is a response to a conversation from quite a while ago on the list.

I've been working on refactoring the space library to give a bit more
coherence and (hopefully) swapability to the various spaces.  


I've been thinking about both the idea to base the space library be
based on metric spaces and also Gulya's idea below about a series of
"relations", which  as you point out are semantically typed edges.

First, I see a problem with conclusion in our previous discussions that
metric spaces can unify the space library.  Metric spaces only apply to
symmetric relationships, d(x,y) == d(y,x).  The network library has
complete support for asymmetric relationships: d(x,y) != d(y,x) or
d(y,x) == null.  In fact this is the most general case.  Symmetric
networks are the special case (albeit a rather substantial one). So it
seems that, at least for that part of the space library, metrics don't
apply.  Now it seems totally reasonable to unify, at least, all of the
grid type spaces, and perhaps even symmetric networks, using the metric
approach.

Gulya, Nick and I were talking about the relation stuff you came up with
yesterday.  That is a super neat way to unify the network stuff with the
spatial stuff.  I have some concerns, (I'm sure you can guess what they
are).  The first is performance, both memory and computation.  If there
is a large grid, the set of edges created by a Moore neighborhood will
be huge.  Computationally, I'm concerned about the update method in the
contexts.  If agents are moving, and constantly changing their
neighborhoods, the update method (where relations are updated) will be
extremely expensive.  My second concern is that all agents will have to
extend some base class (DefaultNode, RelNode, etc.).  This eliminates
some of the flexibility people could use to extend other classes.  This
has been a concern for both Nick and I and is one reason why we so
desparately want to use aspects.  The third concern I have has to do
with the Range operator.  I guess this falls under computational
expense, but it is a little different.  If someone needs to do a range
query, the agent would need to find the shortest path to each of the
other objects.  That would be prohibitively expensive.
I wonder, do you have any thoughts on how to get around this problem?  I
really like the design because it contains so much semantic information
and unify spatial models and network models.

Those are my thoughts at the moment.  Clearly, I haven't come to a
conclusion yet, so please anyone comment.  If you want to see the issues
I'm talking about there is a series of postings in the mailing list
called "Topology Notes".  They outline all of the things we've been
discussing.  Also, if anyone else has ideas on how to make spaces more
"switchable", please suggest.

BTW, If you've made it all the way through this epic email, I'm very
impressed.

-Tom


On Thu, 2002-11-21 at 22:52, Laszlo Gulyas wrote:
> Hi Guys,
> 
> I'm sorry for taking so long reacting, but there's so many things
> going on right now. (Not excluding selling the furniture and the car
> in preparation to moving back to Europe.) So, my schedule was and
> is a bit hectic. Fortunately, though, both Anita (my wife) and I have 
> saved up some days off, so we're gonna take off for a last vacation 
> soon. Hopefully, I get back for the last couple of days much more 
> relaxed/productive...
> 
> However, I wanted to get back to you on this before that happens.
> I think, Mike has summarized our discussion rather well. The only
> thing remained to say is about displaying these things. In principle,
> the Drawable interface works well: it basically maps an agent into
> a 2D coordinate system, plus provides a way for it to draw itself.
> This should be general enough.
> 
> Except that it kind of makes it hard for an agent to participate in
> several [switchable] 'spaces' or to display itself on different
> displays 
> of the same [possibly N-dimensional] space. Now, I don't necessarily 
> think that it is time now [just before 2.0] to blow up the whole gui
> package.
> However, I've been doing some experimentation and created my
> own ContextMapping (well, I call them contexts, but they are, kind
> of, generalized topologies) interface whose methods take an agent and
> - map it into an (X,Y) /screen/ coordinate,
> - return its Dimension,
> - draw it on the screen.
> 
> I just thought I'd share this with you. (See the attachment.) 
> Please, do not look at its performance yet! On the other hand,
> it's kind of complex, so I won't blame you not want to start
> with it right now.
> 
> - - - - - 
> 
> OK. In this model, I've taken the 'space/topology' issue a step 
> further. (?) [Don't think I'm suggesting you should start implementing
> any of this. Rather, I just want to share my crazy visions with you.]
> 
> Now I think that the bottom line of all these 'space/topology'
> issues is the concept of a Relation. It is really nothing else, but an
> Edge 
> on a network, so one nice thing about this approach is that it
> provides 
> a natural way to unify the 'grid-based' and the network models.
> 
> OK, so I call them relations, not Edges, what's the difference?
> Technically, my implementation is nothing more than providing
> ways to sort out edges according to their types. This way, I have
> general methods to say, "Give me the related nodes according to 
> relation R", R being a parameter.
> 
> My 'contexts' create and update the relations and all the Model/Agent 
> do is to query and use them, via these general methods. This way, by 
> replacing the context, you can place the agents into vastly different 
> environments, as long as they all define the same relations.
> 
> From this point of view, the topologies/spaces just define special,
> perhaps
> parametrized [with distance] 'neighborhood' or 'close-to' relations.
> Storing
> the agents on a grid internally is just an efficient way of
> implementing this.
> (Naturally, it is debatable whether the relations/edges define special
> kinds
> of topologies, or the other way around, but this time, I just went
> with the
> latter option.)
> 
> Well, let me know what do you think. Note, however, that I'll be out
> of
> town till December 3. So, don't get mad at me if I won't answer them
> immediately. (Well, that's kind of usual from me, sadly enough.)
> 
> Take care!
> 
> Gulya
> 
> PS: I can't resist to put this in here: as a long shot off the
> 'relation burble':
> this could, in fact, finally lead to the 'DB-based' simulation I've
> been
> 'visioning' for a while. I mean, if relations are a central concept in
> the
> architecture, and the model's and the agents' logic is formulated
> according
> to this, it could be possible to actually implement them by storing
> them
> in a relational DB. Then, in principle, one could do cool stuff, like 
> defining 'dynamic relationships' via joints, or creating triggers,
> etc.
> I'm not sure if it's necessarily more efficient, but wouldn't it be
> cool?! ;-) 
> [Enough of me now! :-)]
> 
> At 07:15 PM 11/15/2002 -0600, North, Michael wrote:
> 
> > Tom:
> > 
> >  
> > 
> > The topology issues that we discussed might be represented as
> > follows:
> > 
> >  
> > 
> > 1.)   An abstract Topology class or interface can be defined:
> > 
> > a.      The class has a method, getDistance(Object o1, Object o2),
> > that returns the distance between any two objects.
> > 
> > b.     The Topology class has appropriate methods to get neighbors
> > within a certain range such as getNeighbors(Object o1, double range)
> > .
> > 
> > 2.)   Three or more concrete Topology implementation classes can
> > then be defined:
> > 
> > a.      An implementation for Moore neighborhoods, von Neumann
> > neighborhoods, and hexagonal neighborhoods based on the current grid
> > implementation can be defined.  This would use the current
> > array-based grid storage and maintain backward compatibility.  Since
> > it is essentially the current implementation, it would run as fast
> > as the current code.
> > 
> > b.     An implementation for metric spaces can be defined that uses
> > trees to store objects and find neighbors.  This can be done since
> > the rules of a metric space allow tree storage.  For example see
> > http://www.vldb.org/conf/1997/P426.PDF.  Other implementations are
> > also available, especially for large lists.  For example, see
> > http://portal.acm.org/citation.cfm?id=328959&dl=ACM&coll=portal. 
> > This implementation would run slower than the current code but it
> > would still be reasonable for most problems.  The price of slower
> > execution is made up for by the added flexibility.
> > 
> > c.      An implementation for completely abstract (i.e. non-metric)
> > spaces can be defined that uses a simple list to store objects and a
> > naïve all pairs matching algorithm to find neighbors.  The algorithm
> > will simply test the distance between each object to find
> > neighbors.  This implementation will be much slower than the current
> > code for large lists but the slower execution will be made up for by
> > the increased flexibility, at least for initial testing.  Users that
> > find they need a particularly abstract notion of space are free to
> > develop optimized versions of the Topology class as they see fit.
> > 
> > 3.)   Users select the fastest concrete implementation class that
> > supports their model's notion of space.  Of course, users are also
> > free to extend or add to the existing concrete classes.
> > 
> >  
> > 
> > Mike
> > 
> >  
> > 
> >  
-- 
Tom Howe
Social Science Research Computing
University of Chicago