Monday, May 8, 2006

Towards Anatomical Dissection of Massive-Multi-Agent System

[ROBOSAPIEN™(s) versus Aibo™]


We are interested in developing notion of artificial emotion for a robot inspired from biological emotions. Artificial emotions are considered as a reaction of an artificial organism to the environment, based on its internal states. The work presented here, is based on notion of Anatomical Dissection of Massive-Multi-agents System originally described Understanding Intelligence. As an extension to the Morphological paradigm, Anatomical is understood as representing the global state of Massive-Multi-Agent System as shape in geometrical space. This notion is close to the notion of phase space in physics. We propose to investigate the relation between the robot's behavior and the Anatomical representation of its current state by associating Massive-multi-agent systems to a couple the robot's sensors.


The study of Multi-agent systems has started with limited number of agents, mainly because of the capacity of computers. Since this limitation has been reduced with the advent of new technology, it is now possible to build new large scale systems. Two way can be choose to modelize agents, one is to build high complex cognitive agents, the other is to build agents with low level behaviors and to study multi-agent systems with a large number of agents. It is on that second aspect we are interested on. The research interest about the analysis and the control of such massive multi-agent systems has increased this last decade in many field of research. However methods or systems are less frequently proposed. Some approaches have been presented in order to control multi-agent systems based on "Manual tuning'', emergence based theory, or genetic algorithms. If manual tuning is suitable to control or to analyze the behavior of a couple of agents, it is almost impossible to apply it to massive-multi-agents systems. Emergence based theories describe a control from bottom (agents) to top (system). By modifying the agents' cooperative behaviors to resolve local conflicts, one expects that the system will get the proper global behavior. It seems to be difficult in some cases to associate local behavior to global behavior, especially if we consider massive multi-agents systems composed by large diversity of agents. The genetic approach was recently proposed to explore a large space of cooperative possibilities among agents. This interesting approach proposes a way to control the global behavior using fitness value. However it is difficult to understand the relationship between fitness and overall behavior that emerge from the systems.
Another approach using concept of morphology originally describe by have been proposed in order to analyze and to control and massive multi-agent systems. The underlying idea is to describe state of agent organization, by projecting the state of the agent organization in an abstract geometrical space from various measurements made at the agent level. This projection is called morphology. The main system hypothesis is to consider that the shapes representing the system's state are correlated to the system's behavior. It has been shown that using this architecture, it is possible to control the population of an organization . This approach shows the possibility to perform an analysis of organizations from top (system) to bottom (agents) in order to control global behavior.

Towards description of system state

The research field of analysis and controlling massive-multi-agent system is part of larger complex systems study, like robot control, chaotic systems in physics, biological sciences, or emergence phenomenon in social and economic sciences.
- 1 Emergent behavior systems: The study of chaos properties has been reserved for a long time to the analysis of physics and natural systems. Recently, some researches in robotics tend to use chaos model in the analysis of emergent behavior. The goal of such systems is to understand the role chaos is playing in the emergence of behaviors and what kind of control can be applied on it. This kind of research is oriented to behavior emergence from a robot on which effectors are coupled with chaotic systems. However this approach led to the necessity to be able to detect and classify these behaviors.
Another field in robotics research is exploring the dynamics of system-environment interaction, to achieve different types of locomotions. This system based on body dynamics proposes a way to build embodied adaptive behavior. The underlying idea is to build embodied reactional system in order to adapt the physical system's behavior to the modification of the environment, without any algorithmic or high level of symbolic control. The system presented is about the adaptation of a dog's locomotion state (walking, running, passing through obstacles). It shows the possibility to build fast adaptive behavior with relatively simple mechanical system based on springs. However this system, by definition, lacks of getting a way to analyze itself, and to represent its actual states. Neural network systems have been coupled to sensors in order to try to detect different states. The constraint is that it requires an a priori knowledge of possible states of the body. We think that such embodied system is interesting because it allows, like for chaotic control based systems, a large scale of possibilities of emergent behaviors. To represent internal state of such robot, one needs to consider the possibility to detect and explore new possible states that may not be predictable.
- 2 Internal states models: The emergence's study of community behavior inside an organization and the way to classify different types of homogenous behavior is closely associated to the research field of physics, chemistry, social science or economics. Some studies have been done on these fields, trying to understand and provide a control of complex organization by analyzing global behavior in order to control local behaviors. This kind of approach is particularly used in field of economic sciences.
In n more surprising field such as biological science, new approach are dealing with concept of emergence inside organizational system. These concepts appear especially in domain of emotion study. Biologists from WikiBio™ have proposed a new definition of emotions based mainly on reactive behaviors built from internal state representations. That global internal state representation of the organism is the result of the competition between different local representations with different sensitivities. The resulting emergent representation is associated to a special type of response behavior. In such concept, the internal state, and its representation highly depends about the sensor capabilities and the architecture of the body. This supposed that emotional states are unique for each body's morphology.
We think that such internal state architecture is similar to multi-agent system architecture. The state of each agent, and, in a higher level, to each organization of agents describes a representation of the current environment with different sensitivities. The global state of the organization as result of competitions and negotiations between agents and groups of agent can be associated to a specific behavior.

Description of the general approach

1 Hypothesis
The work presented in this paper is a part of a larger system originally describe in MorphoWiki™. This underlying idea of that system is based on the correlation of micro-level behavior (agents) and macro-level behavior (organization). The basic hypothesis is that the shapes of organization should be correlated to the system's behaviors. Detailed description can be found in MorphoWiki™.
2 General description
The general architecture of the system is composed by three different organizations (fig. 1) : the aspectual organization, sensitive to the external environment; the morphological organization which describe the state of aspectual environment in geometrical space; and the analysis organization that control aspectual organization using description done by the morphological organization. This analysis organization contains general trend of the system given by the system designer.

Figure 1 : The general architecture composed by the three organizations.

3 Aspectual organization
The aspectual organization, containing many Aspectual agents sensitive to different types of external environment information, represents phenomena that we want to study. The term of "Aspectual agent" comes from the original agentification methods proposed in Wikipedia.
Each aspectual agents, using information about their local environment, computes a value or a set of value that is called "aspectual vecto", as they run. This set of value describes the state of the agent, and its current activity. By definition, the aspectual vector is closely related to the structure of each agent.
4 Morphological organization
The whole collection of aspectual vector computed by aspectual agent forms what is called the aspectual landscape of the aspectual organization. The morphological organization will analyze this set of aspectual vectors in the geometrical way.
Morphological agents attempt to describe what it is happening in the aspectual organization in order to classify different possible states of the organization. In a massive context, the anatomical organization doesn't take in account the ontology previously defined for the aspectual agents, that means we do not use any semantics in the morphological space.
The anatomy analysis is only concerned by the activities and the state of the agents. Ideally the anatomy should point out structures, shapes, similarities, opposition, recurrent features···The tools used for representing anatomical morphology have no restriction and can be as well histograms, distances, network connectivity···
However in order to be able to control organization, one must consider that aspectual measure should have reciprocal. The reciprocal is a function that modifies the aspectual agent behavior according to some target value expected, so that the agents will conform to that target value.
5 Analysis organization
The purpose of the analysis organization is to correlate the overall aspectual organization's behavior to the shapes revealed by the anatomical organization.
The analysis agents use the morphological description to examine the aspectual organization and to orientate the system accordingly to some generic guidelines instructed by the designer. For example the global variable X of the system should be around value Y. This is achieved by classifying and learning the morphology: as the system runs, typical shapes are correlated to the system's behavior and categorized appropriately.
In a second step, as the system evolves in time, it should be possible to associate trajectories in the morphological space with the behavior of the system. Trajectories can be understood as successions of shapes. These properties should allow us to predict the global behavior of the aspectual organization.
Analysis organization is important in a sense it provides a kind of symbolism of the overall system state, through the aspectual and the morphological organization. By giving feedback and control to the aspectual organization, its role is to influence the aspectual organization following the designer's guidelines. It can also select appropriate shapes learned from the system's past activities, and tell the morphological agents that this particular shape would be more appropriate than the current shape.
6 Our proposal
As said previously, it has been demonstrated the property of this architecture to get self analyzed. We proposed in this paper to study the behavior of aspectual organizations when aspectual agents are linked to sensors of robot. The preliminary goal is to link agents with sensors, to build Aspectual organization regarding the physical morphology of the robot and to study what kind of morphologies we get, in order to provide a robot state analysis by analysis organization. We focus the study on the morphology, and on an architecture of aspectual organization on ROBOSAPIEN™ robot.


1 RoboSapien™ robot

The system will be applied to ROBOSAPIEN™ robot. In this section, we shortly introduce the RoboSapien architecture.
RoboSapien™ is composed by several sensors and effectors. We have implemented our example using the four legs of RoboSapien™. Each leg has three degrees of liberty called: Rotator, Elevator and Knee [fig. 2].

Figure 2: Description of the 3 degrees of liberty of RoboSapien™ leg.

The interface used for RoboSapien™, is done with the XML architecture described by WikiBot™. This library allows us to get data of position of the legs at any time. We use these data as data sensor for the position of each motor. We have set an interval of time to 10 milliseconds between sensor data request. These data are read by aspectual agents are define below.
2 Aspectual organisation
We associate to each sensor a group of agent. These groups are multi agents system itself, composed of one thousand agents. Each Multi-Agent system environment is described by the data received by one of sensors of ROBOSAPIEN™. The global architecture is illustrated on (fig. 3). That means each multi-agent system activities will describe an interpretation of one sensor state.

Figure 3: The architectural organization of aspectual groups
1 Aspectual agents
Each agent of subgroup of aspectual organization is sensitive to the data get from the sensor associated to their group. The type of sensitivity for agent can be whatever decided by the system's designer (position, average speed, acceleration, continuity of position value···). In our example, we choose to set two types of agents: one based on the position value, another one based on the last recorded speed of the motor. The sensitivity of the agent will affect what we call the ``satisfaction'' value of the agent. The agent's action will depend of that satisfaction value. The range of satisfaction value is [0,1]. For convenience, we have set the satisfaction value from 1 (satisfaction) to 0 (no satisfaction).

1. The sensitivity parameters are defined according to two criteria: tolerance and saturation. Tolerance represents a range of value in which the agent's satisfaction will be optimum. Saturation represents the degree of tolerance of the agent, if the value is outside the tolerated range. The further the value is from the range, the less will be the agent's satisfaction. These two parameters describe the satisfaction value of the agent [fig. 4].

Figure 4 : Function of satisfaction regarding the sensor value

Parameter settings of sensitivity are done randomly, so that every agent will be more or less sensitive. This allows getting a large range of sensitivity. Considering Val as the actual sensor value from sensor (position or speed), Tol as the tolerance limit value, and Sat as the coefficient of saturation, the satisfaction value S is defined by:

2. The action of the agent will be to proposed a new position or speed for the effectors, depending of what type of sensitivity they have :
  - the agent related to the position value will proposed a new value of the motor effectors position in order to keep the position as close as the range of accepted value.
  - the agent related to the speed of the motor will proposed a coefficient of speed in order to reach the value proposed by the agent related to the position. That means more fast are the changes of the position, more fast will be the proposed action. This property is a pure choice from the designer in the type of response behavior chosen for the robot. It may be defined in another way if we expect a different behavior.

Both of these propositions are also depending of the tolerance and saturation parameters of each agent. However a third parameter called Threshold is introduced to define the ``dissatisfaction'' state of the agent. This threshold defines a value of satisfaction under which the agent will decide to propose a value of rectification for the effector. The threshold value depends of effector type and is associated to all the agent of the same group. This parameter is explained in more details in section 4.2.2 .Considering the threshold value Thd of the group of the agent, the proposed value P is defined by:

In other terms, P is proportional to the value that would be proposed to reach in one step the range of accepted value (val 1) and the value that would be proposed to reach in one step the threshold of satisfaction (val 2) [fig 6].

Figure 6 : Distances from tolerated range and threshold of satisfaction.

2 Aspectual organization
We consider the aspectual architecture as a group of multi-agent systems, each of them connected to a particular sensor. For a given data received from the sensor, all agents of the group will update their satisfaction value. If the satisfaction of one agent is under a certain threshold, that agent will be set as dissatisfacted member of the group and will propose a rectification for the associated effector. The average value proposed by the group of dissatisfacted agent will be the one on which will be based the correction of the position of the effector. The threshold value is associated to each group, regarding the type of sensor. This value is important because it will set the overall sensibility of the group, and it capacity to propose value to correct the effector position. In other terms, it can be understood as the sensitivity of the response of the effector.
However we considere that one sensor state is correlated with the state of other sensor(s). Considere for example the balanced position. It cannot be defined by taking in account only one part of the body. It is the combination between the state of different parts of the body that allow to control the overall balanced position. The modifications of an effector position will affect the position of other effectors in order to keep stable position. It that case it is needed to build an architecture that allow communication and inter-dependencies between these different groups of agents. The group of dissatisfacted agent will proposed, to other connected aspectual group, a value of modification of effector in order to properly synchronize the movement of the body. This value is weighted by a coefficient of inter-dependency between connected Aspectual groups. This coefficient is set regarding the body architecture. It describes how effectors are synchronized together. Agent of connected group will agree with that value or not, depending of the actual state of the group's sensor. The agents agree with that value will proposed a modification of the effector position to their respective aspectual group. The computation of that value is done in the same way as described in 4.2.1, but based on the proposed value rather than the actual value of the sensor.
For each aspectual group, we have then two kinds of agent active agent:
  -the one dissatisfacted with the current value of the sensor
  -the one agree with the value proposed by other aspectual group
The decision for each effector position will be done by the average of value proposed by these two groups [fig 7].

Figure 7 : Overview of internal composition of two connected Aspectual groups.

These connections and interdependency coefficients between Aspectual organizations depend of the physical anatomy of the robot and of the choice of designer's system.
3 Body architecture
In this section we describe the connection set between effectors.
Effectors are describe in that way :
  - RF1, RF2, RF3 : respectivly for Right Forward Rotator, Right Forward Elevator and Right Forward Knee
  - LF1, LF2, LF3 : respectivly for Left Forward Rotator, Left Forward Elevator and Left Forward Knee
  - RB1, RB2, RB3 : respectivly for Right Back Rotator, Right Back Elevator and Right Back Knee
  - LB1, LB2, LB3 : respectivly for Left Back Rotator, Left Back Elevator and Left Back Knee
We use a simple connection rules in the example presented here. The values of interdependency coefficient are set according to opposite equivalent sensor between left and right parts of the robot (RF1 connected with LF1, RB3 connected with RB3···). All coefficients are set to 1.

The Anatomy

The Anatomy is considerate here as the shape of agents activity from an aspectual organization and its connected aspectual organization. The shapes used to describe the aspectual organization's state are normalized and mean-centered histograms representing the agents' state distribution according to their dissatisfaction or agreement state. [fig 8].

Figure 8: Example of anatomical representation of one Aspectual Organization.


We seek to develop a general method to analyze and control Massive-Multi-Agent system, and to make them self-adaptative. So far we have presented our current work based on internal state representation of a robot using part of that system. We proposed a method for connecting multi-agent systems to sensors and effectors in order to provide basic control and internal state representation of robot behavior. This internal state representation is based on notion of anatomy. In our research, the morphology is described as the shape representation of multi-agent organization in a geometrical way, with the intention of clarifying anatomical perception. A deeper understanding of such description's properties is necessary to identify correlation with agents's behavior.
In a future work, this anatomical morphology should be used to control agent's behavior, using the analysis organization. We are currently working on a more general system and look forward to use it to control robot's behavior from environmental perturbation. In order to better perceive the actions of the robot, we should focus on the development of more elaborated descriptions of anatomy.