State Space Construction by Attention Control

1 Introduction

Acquisition and utilization of internal representation are key issues in realizing intelligent behaviors in comput­ er systems. They are especially difficult for robots that process noisy sensory information and interact in the re­ al world. There are two directions for the research. One requires the programmer to provide the internal repre­ sentation [10; 3]. Another direction is to develop robots with cognitive interests [6]. The purpose is not to devel­ op a robot that can execute complex tasks, but to stress the possibility that a robot may learn how to behave in the real world. Researchers in cognitive robotics [11] focus on . cognitive aspects of physical agents - agents that learn their internal representation autonomously in order to perform tasks.

Our research direction basically takes the cognitive ap­ proach. In the cognitive approach, the key issue is how the robot efficiently obtains necessary information from complicated environments through sensors. This paper proposes an approach to construct a state space with an attention control mechanism that performs nonlinear classification of sensory data. The method proposed here is rather simple as a method of pattern recognition, but it works well in the state space construction by a robot in a complicated environment. The key points of this paper are as follows:

1. The proposed method enables the construction of a state space from redundant and noisy physical sen­ sory data, such as visual data.
2. The proposed method efficiently and autonomous­ ly constructs the state space from physical sensory data by employing an attention control mechanism.

We consider, it is interesting and important to illuminate and examine the close relationship between state space construction and attention control. This paper discusses such a key issue in cognitive robotics.

The task of the robot discussed in this paper is to avoid obstacles. While moving, the robot collects data sets consisting of an action, sensor information, and a reward. Then, the robot develops empirically obtained perceivers (EOPs) [5] . EOPs statistically analyze the da­ ta sets to classify sensory patterns according to actions and rewards to obtain a proper state space for the task. In the state space construction, EOPs perform attention control. There are two types of attention control: feature selection from sensory data and continuous gaze control. Each EOP select features in the image consisting of a huge amount of pixel data. Further, the application of a combination of EOPs cmistitutes a sequence of changes in attention for gaze control. The acquisition of the se­ quence is called visual sequentialization [2]. We have confirmed that the robot can construct state spaces for avoiding obstacles in a complicated simulated world.

There are several research approaches that au­ tonomously construct state spaces and reduce its size. Nakamura's work [6; 9] deals with physical sensory da­ ta but the feature extraction is based on human intu­ itions. Mahadevan's work based on Q-learning [13] ba­ sically has trouble dealing with physical sensory inputs that have huge dimensions. Although the G algorithm [4] and UDM [7] address certain problems, they do not use complex physical sensory data. While both meth­ ods use statistics, they assume that the sensors generate information that can be directly used to represent the state space. In other words, they do not address the problem of how to construct the state space from raw sensory data. G algorithm's sensory data selection per­ forms a kind of attention control. However, difficulties arise when the robot directly deals with physical sensory data since simple pattern matching methods cannot be applied to complicated sensory data. The purpose of this paper is to propose a coherent method for constructing a state space from physical sensory inputs and to propose a means of attention control for physical sensors in state space construction.

2 State Space Construction

2.1 Process Flow

Figure 1 shows the process flow for incrementally con­ structing a state space. In the beginning, the robot does not discriminate any sensory data and it has just one state. While moving the robot collects data sets, con­ sisting of sensory data, an action, and a reward. These data sets are divided into two classes.

Here, the robot can move along plans if it has a s­ tate space whose size is sufficiently large for planning the robot motion. While constructing the state space, state transition probabilities can be computed from the data sets, and the robot can make plans for going toward goal states with standard planning methods by referring to the state transition probabilities and rewards assigned to states 1 ·

For discriminating the two classes, an EOP is obtained and the state is split in two. Then, if there are any iden­ tical states, they are coalesced. By iterating the process, a state space is incrementally constructed.

2.2 Data Collection

The data set consists of the following four components:

where State means a state of the robot when it executes an Action, acquires sensory information and receives a Reward. Sensory vector is one dimensional array of sensory inputs.

The method proposed in this paper can deal with any kind of physical sensory data. However, it is instruc­ tive to consider a vision-based robot, since visual data contains a very large of information and it is difficult to extract what is necessary for the robot to perform its task. For the analysis discussed below, 2-D vision da­ ta is simply converted into a one dimensional array, the Sensory vector.

1 Several papers [12] concerning state space construction propose to apply Q-learning to assigning Q-values (which provide an action policy) during or after constructing the state space. However, such relations between states can be directly obtained by computing state transition probabilities from the data used for constructing the state space.

In our model, humans cannot directly specify the robot's internal states. However, they can express their intentions to the robot through rewards. These rewards provide the robot's solely motive for learning to classi­ fy its sensory data. Thus, by referring to the rewards, the robot constructs its internal state space by itself. For reactive robotic tasks such as obstacle avoidance, the robot receives immediate rewards. For deliberative tasks such as moving toward goals, delayed rewards are used in place of immediate rewards.

2.3 Sensor Pattern Classification

Imagine that a robot with an incomplete state space moves about in a real environment in which rewards are embedded. If the robot receives different rewards when executing an action in a given state, the robot finds that the state should be appropriately divided into two states.

Let g(r) be the frequency of r E {rl(v,a,s,r) E R( v;, aJ)}, n be the number of samples in R( v;, aJ), and let Ka, Kb, Ke, and Kd be constant values, where v, a, s, and r are State, Action, and Sensory vector, and Reward, respectively. R( v;, aj) represent a set of data sets of which State and Action are v; and aj, respec­ tively. The following equations give the conditions for dividing v; (see Figure 2).

where n0 is the number of samples such that r < (), () = (a+ .8)/2, and n1 is the number of samples such that r ~ B. If several ()s are found, the longest [a, ,8] is selected. In the conditions, (3) means that rare events are neglected. ( 4) guarantees enough data to make an EOP. The method for clustering seems ad hoc. Of course, we can employ other standard clustering methods using variance. However, the clustering needed for this ap­ proach is simple and we consider the four parameters that we have employed characterize the robot behavior.

Data sets R( v;, aj) are divided by 0 through the fol­ lowing procedure for state division:

1. Take actions in the real world and collect quadruplet data (v, s, a, r) . Classify them into disparate sets

1. For each R( v;, aj) check whether v; should be divid­ ed. Terminate if no state can be divided.
2. If R(v;, aj) should be divided by the threshold 0 as shown in Figure 2, define two classes:

1. Look for an EOP which can discriminate class 0 and class 1 in EOPs already acquired. If no proper EOP is found, then make a new EOP using class 0 and class 1 (see 2.4). If the EOP cannot be construct­ ed because of the classification error, then abort to divide and go to 2.
2. Let us refer to the EOP selected at 4 as EOPk. v; is divided into new states v;o and v;1 by EO Pk. Di­ vide R( v;, a1) into R( v;0 , a1) and R( v;1 , a1) for each a1 and go to 2.

2.4 Acquisition of EOPs

Assuming that sensor patterns classes 0 and 1 are given with respect to an action, a discriminant function can be obtained in the following manner [5]: The discriminant function is a function which takes as input a sensory vectors, represented as aN-vector, and outputs a scalar value. It is represented as a sum of weighted components of a vector x.

where c is decided so that D F outputs a positive value for a sensor pattern in class 1 and a negative value for a sensor pattern in class 0. A value for w is determined to minimize the error rate [1] as follows :

where :E is a covariance matrix of class 0 and class 1. ~-t1 and ~-tO are mean vectors of class 1 and class 0, respec­ tively.

The error rates of DF are given by the following for­ mulae:

where nO and n1 are the number of data sets in class 0 and 1, respectively. mO is the number of data sets such that DF ~ 0 in class 0, and m1 is the number of data such that D F < 0 in class 1.

Here, the discriminant analysis generally takes much computational time for a large number of dimensions of the sensory data. Therefore, it is necessary to perform a kind of dimensionality reduction to reduce the size of the sensory data. However, our policy in this research ap­ proach is that the robot has no access to models based on human intuitions for segmenting features , such as lines, color regions, and so on. For this problem, our idea is to use principal component analysis (PCA) [1], which cal­ culates orthogonal dimensions of maximal variation in the data. The Hotelling (aka Karhunen-Loeve) transfor­ m is used to rotate the axes, and only those dimensions that account for most of the variation are retained. The principle components of the visual data serve as low-level quantitative features [8] and represent spatial relation­ s among pixels. Therefore, it is meaningful to refer to the principle components for analyzing vision data. Al­ though we do not consider principle component analysis is ideal for the data compression, this approach is general insofar as it can be applied to any kind of sensory data. As better methods, we can consider to apply indepen­ dent component analysis and Wavelet transform, which have interesting relations with human visual process.

The weight vector of a discriminant function repre­ sents the importance of each component of the sensory input for the classification. Thus, the weight vector de­ fines attention control for pixel (or feature) selection. Several approaches can be considered for the pixel se­ lection with referring to the weight vector. Our method employed in this paper is as follows.

Pick up the maximum and minimum values of absolute values of the weights. 'fhen, we divide the range between the maximum and minimum values into ten (this num­ ber has been empirically determined) and acquire ten threshold values (TH1 ,TH2 , ... ,THt, ... ,TH10 ). With the threshold, the weight values are modified; if the val­ ue is less than the threshold, the weight is set as 0 and the pixel is ignored. Thus, we obtain ten modified dis­ criminant functions MDF(t,s),t = 1, ... ,10.

Next, we check error rates of all modified discrim­ inant functions. The modified discriminant function M DF(t, s) that does not satisfy the following condition is discarded.

where emOt and em1t are error rates of the modified discriminant function and they are computed in the same way as eO and el.

For the remained discriminant functions, we evaluate performance of the threshold values by using the follow­ ing evaluation function.

where n is the total number of data sets. Then, a thresh­ old t = l that gives the minimum value of the evaluation function EF(t) is selected.

The original linear discriminant function divides the parameter space with a hyper plane based on distribu­ tion of data in the parameter space. In this case outliers significantly influence the discrimination. On t'he other hand, performance of the modified discriminant function is evaluated based on only the number of misclassified data. That is, there is a possibility that the pixel se­ lection using the modified discriminant function ignores the outliers.

By the pixel selection, the discriminant function can be represented with a small number of coefficients and fo­ cuses on important sensor components. Further, a com­ bination of modified discriminant functions realizes non­ linear discrimination as discussed later. The efficiency of this attention control method is experimentally verified in Section 3. The idea of attention control proposed here is simple but general, and it can be applied to any kinds of sensory data.

The modified discriminant function M DF(l, s) cut mi­ nor components off with a threshold value l and outputs a positive or negative value for an input data s. With M DF(l, s), we define a logical function EOP as follows:

By iterating to collect data sets and obtain EOPs the robot may generate a large number of states. In this ~ase identical states may exist. The states can be identified b; their distribution of rewards across the possible actions. Suppose the robot has two actions and each state-action pair has a distribution of rewards that it has acquired so far. If, for two states, all corresponding actions have a similar reward value, the states can be treated as i­ dentical. The identified pair of states is coalesced into a single state. The new state is represented by combining the EOPs used to represent the previous two states. In other words, by iterating the processes of identifying and coalescing states, the robot is able to perform a complex, nonlinear discrimination of an n-dimensional parameter space.

3 Experimental Results

3.1 Robot and Environment

We have developed a robot simulator and used it to veri­ fy the proposed method. The robot in the simulator has an omnidirectional vision sensor. The robot can rotate in any of 12 directions and go forward in other words it has 12 actions. The configuration df the sensor and the actions are shown in Figure 3(a) and (b). An ac­ tion ai consists of a rotation of 30 x i degrees and a forward movement of 15 pixels in the simulated envi­ ronment shown in Figure 4 with some errors (The size of the simulated environment in Figure 4 is 640 x 480 pixels). The actual direction and distance of ai follow the normal distribution whose means are 30 x i degrees :md 15 pixels, respectively. The sensor provides edge I~ages of 43 x 18 pixels as shown in Figure 3(c) at each time step; and the robot acquires edge images for the s­ tate space construction by applying Sobel edge operators 2 . _T~e acquired images are compressed by acquiring the pnnc1ple components. In this experimentation we have determined the number of the principle compon'ents with a accumulated proportion of 0.8.

3.2 Visual Sequentialization

The robot task in this experiment is obstacle avoidance. The robot receives a -1 reward when it collides with a wall and 0 otherwise. At the beginning, the robot knows nothing about the external world, it has no EOP and its internal state space consists of only one stat~ so . Figure 5 shows a state tree at a time when the robot created 9 EOPs. The combination of the EOPs represent the states. For example, state s4 is represent­ ed as EOPoEOP~EOP~EOP4, and s8 is represented as EOPoEOP~EOP~EOP7. Those two states are discrim­ inated by EOP1. In the image of the EOP, bright and dark gray areas indicate positive and negative compo­ nents of the weight vector, respectively.

2 We have tried both of intensity images and edge images. ~s t~e resu~ts, we ha_v~ ~ound that the edge images are supe­ nor m efficient acqmsitlon of EOPs to the intensity images in this simulated worlds.

The tree structure of the state space represents how the robot continuously pays its attention in order to iden­ tify the states. In Figure 5, the robot coarsely observes with EOP0 , then changes its attention to more detailed regions with EO P2 , EO P4 , and EO P7 . This behavior called visual sequentialization is how our method con­ structs the state space.

3.3 Effectiveness of Attention control

To evaluate the effectiveness of our proposed method of attention control, we have experimented in the complex outdoor environment with the reactive robot behavior for avoiding obstacles. First, we have given a fixed num­ ber of data sets for verifying effectiveness of the attention control method. With 10000 data sets collected while the robot randomly moves, the robot has constructed a state space. In Figure 6, the vertical and horizontal axes in­ dicate the error of pattern classification and the number of states, respectively. The error E is defined as:

where i, j are the IDs of state and adion, respective­ ly. nv and n are the number of acquired states and the number of all acquired data sets, respectively. For the obstacle avoidance, npii is the numbers of data sets that have a reward of 0 for an action a in a state s; and nn;i is the number of data sets that have a reward of -1. That is, the error represents the normalized number of mis­ classified data sets. In the beginning, the error is large since the number of states is small. As the number of states increases, the error is reduced.

Figure 6 shows an interesting behavior of state space construction with the attention control. In the begin­ ning, the error of the method using standard discrimi­ nant functions was smaller than the method using the attention control. Then the method using the attention control method became better at 20 states.

We analyze these phenomena as follows: In the be­ ginning, the method using attention control suffers clas­ sification error in the attention control for each EOP. However, after acquiring some total amount of EOPs, the method performs effective nonlinear state division by combining the acquired EOPs.

Another characteristic is shown in Figure 7. The ver­ tical axis indicates the number of nonzero components of weight vectors for EOPs. A small number of the nonzero components means that the robot refers a small amount of pixels in the image to distinguish the states. In oth­ er words, it saves computational time for sensory data processing. As shown in Figure 7, the method using s­ tandard discriminant functions needs more than three times of sensory data than the method using the atten­ tion control.

We have performed another experimentation in a more realistic situation. In this experimentation, the robot incrementally constructs a state space while collecting data sets and makes an EOP in a state when

1. 10 data sets for both classes, class 0 and class 1, are acquired,

1. or the number of data sets in the class that has a smaller number of data sets than the other becomes 10 % of the other.

The error of the attention control method was small­ er than the method using standard discriminant func­ tions as shown in Figure 8. In Figure 8, we could not find the similar phenomena to Figure 6, in which perfor­ mance of the two methods is reversed. In the incremen­ tal construction, nonlinearity of the sensory data space is stronger since the robot needs to move by referring to the incomplete state space. We, therefore, consider that the method not using attention control could not represent good performance in the beginning. Figure 9 shows a more impressive result. The method using the attention control was better than seven times. We con­ sider that, in the incremental state space construction, outliers are often acquired since the robot acquire data sets while randomly moving and the method of the pixel selection efficiently filters them out.

In this experimentation, we could verify the attention control method. Performance of the attention control method is better for the incremental state space con­ struction than for the state space construction with a fixed number of data sets. In the incremental state s­ pace construction, nonlinearity of the sensory data space is strong; and our method is suitable to deal with such a complex classification problem. Further, our method significantly reduces pixel data needed for the state s­ pace construction. This means how the method works well as an attention control method.

4 Discussion and Conclusion

In this paper, we have proposed a coherent method for constructing a state space using attention control from physical sensory data. In addition to the approach's co­ herency, the proposed method has the following interest­ ing point :

• It constructs a state space from a huge amount of physical sensory data.
• The EOP realizes a simple and general method of attention control.
• A combination of EOPs controls continuous changes in visual attention and represents a state.
• Attention control with the EOPs efficiently con­ structs a state space.

Finally, we discuss remaining problems and future di­ rections for our research approach. One problem is how to determine the threshold for the attention control. In this paper, we have determined the threshold based on performance of each EOP. However, an EOP influences performance of other EOPs obtained after the EOP. That is, the threshold should be adjusted by taking al­ l related EOPs in account. This threshold control is expected to construct a state space that has a more rea­ sonable abstraction hierarchy.

In this paper, the EOPs have been made under the assumption that actions are already defined, but some tasks may require more precise actions and others can be done with coarser actions. In order to change the granularity, it is necessary to detect coarse actions or to identify similar actions. It maybe possible to segment actions with a method similar to that used above for sensory data segmentation.

This paper has discussed with a single simple robot task. However, a robot needs several tasks, for example avoiding obstacles, moving toward goals, following other robots and so on. A problem is how to implement the tasks in our approach. As one of the promising solutions, we consider to employ subsumption architecture [3]. The idea is to prepare an independent state space for each robot task and connect the modules with a hierarchical network. Another solution is to develop an abstract state space where we consider a robot behavior as an action. In other words, this idea is to construct a state space for representing relations between robot behaviors. The later idea is more ideal, however it has a difficult problem of simultaneous construction of state spaces in different abstraction levels.

The method proposed in this paper obtains a state s­ pace for a given task and environment. To extend this method, we must consider how to obtain a general state space which can be used in other environments. Imagine if we place our robot in a different room and reconstruct the state space. It is expected that newly created EOP­ s will indicate the difference between the current room and the previous room, and EOPs that are commonly used indicate more general information. The final goal of our research approach is to obtain a general internal representation of a robot behaving in a class of environ­ ments.