Saturday, May 19, 2007

Identifying entities

In a previous post, I asked how one identifies groups — or really how one identifies entities in general. Here's the answer.

There are two kinds of entities: static entities and dynamic entities. (See "Putting Complex Systems to Work" for an introduction to entities. See "Emergence Explained: Abstractions" preprint/Complexity for a discussion of emergence in general.)

In both cases (static and dynamic entities) we will assume that an entity is a composite of component entities. In doing this we ignore some important questions such as what are the primitive entities?

Static entities are created when existing static entities combine to form a compound static entity in a reduced energy state according to the laws of physics. That is, the compound entity is in an energy well. Typical examples are atomic nuclei (which combine nucleons under the strong nuclear force), atoms (which combine nuclei and electrons under the electromagnetic force), molecules (which combine atoms and molecules under the electromagnetic force), and mass aggregations (which combine other masses under the gravitational force). Given any attractive primitive force, that force can be the impetus for the creation of a static entity. Of course this is a recursive process. Once an entity has been created, it can participate with other entities in the creation of still larger entities — and as the examples above show through the influence of other forces than those that created it.

Dynamic entities are a bit more subtle. They are created when entities adopt behaviors that lead them to act in particular ways and that cause them to recognize other entities as being part of the dynamic entity identified with that behavior. For any set of behaviors that characterize a dynamic entity, the entities that interact according to those behaviors become a dynamic entity.

Since this sounds a bit self-referential. Some examples will help. In the early days of agent-based modeling, flocks were modeled by defining "rules" whereby flock members adjusted their speed and direction of motion depending on the other members of the flock. Who the other members of the flock were was built into the model. The point of the model was to illustrate how simple local rules could produce "emergent" global effects.

In our definition, we are turning the "rules" upside down and using them to define what a flock consists of. In particular, a flock is any group of agents whose rules cause them to adjust their speed and direction on the basis of the other agents with which they are interacting according to those rules. Thus if one agent is adjusting its speed and direction according to a set of other agents, then the original agent along with the set of agents it observes are part of a flock. Furthermore, if any of the agents in that flock are observing still other agents not yet identified as being in the flock, then they too are included in the flock. This process of counting new agents as part of the flock continues until all the agents in the flock are adjusting their speed and direction by consulting no agents not in the flock. In this example, we start with one agent and build a flock by constructing the transitive closure of the other agents it consults according to its rules of operation.

The rules in the appendix of Emergence Explained that identify patterns in the Game of Life can be understood as simple versions of this transitive closure approach to forming agents. In the Game of Life a pattern was defined as the transitive closure of a group of on-cells that were mutually connected. As the system changed from state to state, some cells would be drawn into the pattern and others would leave.

That's basically it. The flocking rule (independently of any agent) characterizes the behavior of members of the flock. An agent who operates according to that rule along with the transitive closure of other agents it consults make up a flock. As in the game of life example, agents can enter a flock and agents can leave a flock. The flock itself persists.

This rule of entity formation allows for the existence of multiple flocks. If two flocks are sufficiently far apart, no agent in either one consults an agent in the other. Hence each one is closed, and the two form separate flocks. When the two flocks approach each other, the closure rule causes them to form a combined larger flock.

The preceding was a very simple example. We can extend it to ask about that part of the standard flocking rule that tells an agent to avoid bumping into things (like light poles).

The simplest approach is to allow the rules themselves to determine which of the things with which the agent interacts are taken to be in the flock. Thus the rule that tells an agent not to bump into fixed objects marks those fixed objects as not in the flock. The rule that tells an agent to adjust its speed and direction according to other agents marks those other agents as being in the same flock as the agent which is obeying that rule.

So the more general case is that a rule identifies other entities that it recognizes in its environment as being either part of the same larger entity or not part of the same larger entity. The transitive closure of all entities that interact according to a particular set of rules forms a group.

We do not require that all entities in a group obey the same set of rules, only that the rules determine which of the elements with which the entity interacts are in the group. For example, in a bee colony, there are a number of categories of bees: drone, worker bees, the queen bee, etc. Each of these obeys a certain set of rules. These rules identify which of the entities with which the bees interact are part of the colony. The transitive closure of all bees belonging to the colony form the colony.

This approach to defining dynamic entities can be seen as a generalization of how static entities are defined. The "behaviors/rules" we used in defining static entities are simply the laws of physics. The difference is that the laws of physics cause entities to behave in particular ways without external energy. Entities that follow behavioral rules that define groups depend on an external source of energy to allow them to follow those rules. Furthermore, entities that can be "programmed" either genetically or by learning — such as biological entities — are far more flexible in the sorts of rules that can be created for them — and therefore in the kinds of higher level entities that can be created.

No comments: