JP2011018245A - Recognition device and method, program, and recording medium - Google Patents

Abstract

When performing autonomous learning in a changing environment, the node where the user is currently located is a node that is in a learned internal state or a node that is in a newly added internal state To be able to recognize properly.
A value of a variable N is set to 1, and time series information of length N is acquired in step S202. In step S203, the recognizer outputs a node sequence using the Viterbi algorithm based on the time series information, and determines in step S204 whether the node sequence is actually possible. If it is determined that the node sequence is not actually possible, it is recognized as an unknown node. On the other hand, if it is determined that the node sequence is actually possible, the entropy is calculated, and if it is determined that the value is greater than or equal to the threshold value, the value of the variable N is incremented and the time-series information is extended in the past direction. If it is determined that it is not equal to or greater than the threshold value, it is recognized as a known node.
[Selection] Figure 33

Description

  The present invention relates to a recognition apparatus and method, a program, and a recording medium, and in particular, when autonomous learning is performed in a changing environment, a node in which the node is currently located is a learned internal state. The present invention relates to a recognition apparatus and method, a program, and a recording medium that can appropriately recognize whether the node is an internal state to be newly added.

  The use of HMM (Hidden Markov Model) has been proposed as a method of learning a sensor signal observed from a target system as time series data and learning as a probabilistic model having both states and state transitions. HMM is one of the technologies widely used for speech recognition. The HMM is a state transition model defined by a state transition probability and an output probability density function in each state, and its parameters are estimated so as to maximize the likelihood. As a parameter estimation method, the Baum-Welch algorithm is widely used.

  The HMM is a model that can transition from each state to another state via a state transition probability, and modeling is performed as a process of state transition. However, in the HMM, it is usually determined only probabilistically to which state the observed sensor signal corresponds.

  Therefore, the Viterbi Algorithm is widely used as a method for determining the state transition process with the highest likelihood based on the observed sensor signal. This makes it possible to uniquely determine the state corresponding to the sensor signal at each time. In addition, even if the sensor signals observed from the system are the same in different situations, it can be handled as different state transition processes according to the difference in the time change process of the sensor signals before and after each time. . Although the problem of perceptual aliasing cannot be solved completely, it is possible to assign different states to the same sensor signal, and it is possible to model the state of the system in more detail than SOM etc. Yes (for example, see Non-Patent Document 1).

Lawrence R. Rabiner (February 1989). "A tutorial on Hidden Markov Models and selected applications in speech recognition" .Proceedings of the IEEE 77 (2): 257-286.

  By the way, in HMM learning, when the number of states and the number of state transitions increase, it becomes difficult to correctly estimate parameters. In particular, the Baum-Welch algorithm is not necessarily a method for guaranteeing that an optimal parameter can be determined. Therefore, when the number of parameters increases, it is extremely difficult to estimate an appropriate parameter. Further, when the system to be learned is unknown, it is difficult to appropriately set the structure of the state transition model and the initial values of the parameters, which also makes it difficult to estimate the parameters.

  The reason why the HMM is effectively used in the speech recognition is that the object to be handled is limited to the speech signal, and a lot of knowledge about speech is available. Furthermore, in the speech recognition, the fact that the left-to-right type structure is effective as a result of an enormous amount of research results over many years is a major factor. Therefore, it is a very difficult problem to make a large-scale HMM function as a practical model when an unknown system is targeted and information for determining the structure and initial values of the HMM in advance is not given. I can say that.

  As described above, the problem targeted by the HMM is that the sensor signal is structured, and there is no consideration regarding the action signal. The HMM has been expanded and replaced with a framework in which agents can act on the environment using action signals and influence future sensor signals. Partially observable Markov decision process POMDP).

  Model learning of this problem is a very difficult task, and what has been mainly studied so far is only a relatively small number of parameter estimates in the model given skeleton by prior knowledge, or reinforcement learning It was like driving learning in a dynamic framework. In addition, there are many problems with learning speed, convergence, and stability, so it can be said that the practicality is not necessarily high.

  Further, there are a batch learning method and an additional learning method as methods for learning the HMM. Here, the batch learning method is to generate and store a state transition probability table and an observation probability table based on 10,000 steps of transition and observation, for example, when 10,000 steps of transition and observation data are obtained. is there. On the other hand, in the additional learning method, for example, first, a state transition probability table and an observation probability table are generated and stored based on 1000-step transitions and observations. Then, change and save each value in the state transition probability table and the observation probability table based on the subsequent 1000-step transitions and observations, and so on to update the internal model data by repeatedly learning (Update).

  In conventional HMM learning, a problem occurs during learning in the additional learning method. In HMM learning, a method of preparing all data in advance and performing learning in a batch learning method is often adopted, but in such learning, learning from experience can be adapted to the environment. It is impossible in principle. In other words, in order to exhibit better performance in various real worlds, a function of performing additional learning by feeding back the operation results in the real environment is essential. However, the problem of how to mediate “learned memory structure” and “new experience” when performing additional learning is still unsolved. On the one hand, we want to quickly adapt our “new experience” and realize quick adaptation. On the other hand, there is a risk that the memory structure established so far will be destroyed.

  Conventionally, in order to perform additional learning, past learning data is separated and held, or past learning data is rehearsed from the current memory and combined with newly obtained data. Learning was going on. However, even in such a case, the separated past learning data does not reflect the “new experience”, or rehearsed past learning data is generated under the influence of the “new experience”. There was a problem. Thus, in large-scale HMM learning, it is difficult to perform additional learning to function as a practical model.

  Furthermore, for example, when the environment to be learned changes, the number of observation symbols and the number of nodes increase, and it is necessary to change the number of nodes, observation symbols, or actions when proceeding with learning. There is also. In such a case, it is necessary for the agent to autonomously recognize a change in the environment and expand the state transition probability table and the observation probability table.

  When an agent autonomously recognizes an environmental change and expands the state transition probability table and the observation probability table, it is necessary for the agent itself to recognize whether or not the environment has been newly expanded. That is, the agent must be able to recognize whether the node at which he is currently located is a learned internal state or a node to be newly added.

  The present invention has been made in view of such a situation. When autonomous learning is performed in a changing environment, is the node where the current position is a node in a learned internal state? This makes it possible to appropriately recognize whether the node is an internal state to be newly added.

  One aspect of the present invention relates to observation means for observing an observation symbol based on a sensor signal obtained from an environment, and associating the observation symbol observed over time with the time at which the observation symbol was observed Observation symbol storage means for storing the information, and recognition means for reading out information stored in the observation symbol storage means as time series information and recognizing an HMM node at the last time of the time series information, the recognition means Is a recognition device that reads and recognizes the time-series information of variable length.

  The recognizing unit recognizes a node sequence corresponding to the length of the time series information based on the time series information, and the node sequence in the environment is based on the state transition probability and the observation probability of the HMM, Read from the observed symbol storage means until it is determined that the node exists with a probability equal to or greater than a first threshold and the entropy value of the posterior probability of the node at the last time of the time series information is less than a second threshold. The length of the time series information can be extended in the past direction.

  The recognizing means recognizes a node sequence corresponding to the length of the time-series information based on the time-series information extended in the past direction, and the node sequence in the environment includes the state transition probability of the HMM and Based on the observation probability, when it is determined that the node does not exist with a probability equal to or higher than the first threshold, the node at the last time of the time series information is recognized as an unknown node in the internal state to be newly added. Is output as a recognition result, and it is determined that the node sequence exists in the environment with a probability equal to or higher than a first threshold based on the state transition probability and the observation probability of the HMM, and the last time of the time-series information If the entropy value of the posterior probability of the node at is determined to be less than a second threshold, the node at the last time of the time series information is in the learned internal state It may be output as the recognition result recognized as a known node.

  A recognition result storage means for storing the recognition result in association with the recognized time can be further provided.

  The recognizing means identifies the time when the recognition result stored in the recognition result storage means has changed from a known node to an unknown node over time, and reads the time series information read from the observation symbol storage means. By extending the length in the past direction, the output of the recognition result can be suspended when the time-series information temporally prior to the specified time is read out.

  The recognizing means includes an entropy value of the posterior probability of the node at the last time of the time series information of length N and an entropy of the posterior probability of the node at the last time of the time series information of length N + 1. A difference with a value is calculated, and the length of the time series information read from the observation symbol storage means can be extended in the past direction until the calculated difference becomes less than a third threshold.

  The recognizing means recognizes a node sequence corresponding to the length of the time-series information based on the time-series information extended in the past direction, and the node sequence in the environment includes the state transition probability of the HMM and Based on the observation probability, when it is determined that the node exists with a probability less than the first threshold, the node at the last time of the time series information is recognized as an unknown node in the internal state to be newly added. Can be.

  In the environment, when the node sequence is determined to exist with a probability equal to or higher than the first threshold based on the state transition probability and the observation probability of the HMM in the environment, the recognizing unit at the last time of the time series information When the entropy value of the posterior probability of the node is less than a second threshold, the node at the last time of the time series information is recognized as a known node in the learned internal state, and the time series information When the entropy value of the posterior probability of the node at the last time is equal to or greater than the second threshold, the output of the recognition result can be suspended.

  Action symbol storage means for specifying an action to be executed for the environment as an action symbol, and storing the action symbol obtained with the passage of time in association with the time at which the action is executed is further provided. The information having the same time length as the information stored in the observation symbol storage means can be read from the action symbol storage means and used as the time-series information.

  One aspect of the present invention is stored in an observation symbol storage unit that stores the observation symbol based on a sensor signal obtained from an environment observed with the passage of time in association with the time when the observation symbol is observed. Is a recognition method for reading out the information as variable-length time-series information and recognizing the node of the HMM at the last time of the time-series information.

  One aspect of the present invention provides a computer, an observation means for observing an observation symbol based on a sensor signal obtained from an environment, and the observation symbol that is observed as time elapses. Observation symbol storage means associated with and stored in the observation symbol storage means as time series information, recognizing means for recognizing the node of the HMM at the last time of the time series information, The recognition means is a program that functions as a recognition device that reads and recognizes the variable-length time-series information.

  In one aspect of the present invention, an observation symbol is observed based on a sensor signal obtained from an environment, and the observation symbol observed with the passage of time is associated with a time when the observation symbol is observed. The stored information is read as time-series information, the node of the HMM at the last time of the time-series information is recognized, and the variable-length time-series information is read and recognized.

  According to the present invention, when autonomous learning is performed in a changing environment, whether the node where the user is currently located is a learned internal state or an internal state to be newly added. It is possible to properly recognize whether it is a node.

It is a figure which shows the example of a maze. It is a figure which shows the example of the parts which comprise the maze of FIG. It is a figure explaining the change of the structure of a maze. It is a figure explaining the change of the structure of a maze. It is a figure explaining the change of the structure of a maze. It is a figure explaining the moving direction of a robot. It is a figure explaining normal HMM. It is a figure explaining action expansion type HMM. It is a block diagram which shows the structural example of the autonomous action learning apparatus which concerns on one embodiment of this invention. It is a figure explaining application of a split algorithm. It is a figure explaining application of a split algorithm. It is a flowchart explaining the example of a split algorithm application process. It is a figure explaining application of a forward merge algorithm. It is a figure explaining application of a forward merge algorithm. It is a flowchart explaining the example of a forward merge algorithm application process. It is a figure explaining application of a backward merge algorithm. It is a figure explaining application of a backward merge algorithm. It is a flowchart explaining the example of the application process of a backward merge algorithm. It is a table | surface which compares the likelihood of the state transition probability table and observation probability table in action expansion type HMM. It is a figure explaining the change of the learning result by imposing one state one observation restrictions and action transition restrictions. It is a figure explaining the change of the learning result by imposing one state one observation restrictions and action transition restrictions. It is a figure explaining the change of the learning result by imposing one state one observation restrictions and action transition restrictions. It is a figure explaining the change of the learning result by imposing one state one observation restrictions and action transition restrictions. It is a figure explaining the change of the learning result by imposing one state one observation restrictions and action transition restrictions. It is a figure explaining the change of the learning result by imposing one state one observation restrictions and action transition restrictions. It is a figure explaining the change of the learning result by imposing one state one observation restrictions and action transition restrictions. It is a flowchart explaining the example of an action expansion type HMM learning process. It is a figure explaining the problem at the time of performing additional learning by the conventional system. It is a figure explaining the additional learning system in this invention. It is a figure explaining the influence by the increase in the kind of observation symbol. It is a figure explaining the influence by the number of nodes increasing. It is a figure explaining the influence by the number of actions increasing. It is a flowchart explaining the example of a node recognition process. It is a flowchart explaining another example of a node recognition process. It is a flowchart explaining another example of a node recognition process. It is a flowchart explaining another example of a node recognition process. It is a figure explaining an example in case an unknown node is added. It is a figure explaining another example in case an unknown node is added. It is a figure explaining the example when the necessity of addition or deletion of a node is checked when anchoring. It is a flowchart explaining the example of an unknown node addition process. It is a flowchart explaining the example of an addition or deletion necessity check process. It is a figure explaining the area | region expanded in a state transition probability table when an unknown node is added. It is a figure explaining the example of the unknown node added. It is a figure which shows the example of the unknown node and action which are added. It is a figure which shows the example of the unknown node added, a candidate node, and an action. It is a flowchart explaining the example of the state transition probability setting process at the time of node addition. It is a flowchart explaining the example of a node reverse action pair list production | generation process. It is a flowchart explaining the example of a reverse action state transition probability setting process. It is a flowchart explaining the example of a node order action pair list production | generation process. It is a flowchart explaining the example of a forward action state transition probability setting process. It is a flowchart explaining the example of an anchoring process. And FIG. 16 is a block diagram illustrating a configuration example of a personal computer.

  Embodiments of the present invention will be described below with reference to the drawings.

  First, the action expansion type HMM will be described.

  The autonomous behavior learning apparatus of the present invention to be described later is applied to, for example, a robot that self-runs in a maze, recognizes its own position, and learns a route to a destination.

  FIG. 1 is a diagram illustrating an example of a maze. As shown in the figure, this maze is configured by combining a plurality of types of parts as shown in FIG. As shown in FIG. 2, each of the parts is configured as a rectangle having the same size, and 15 different types are prepared. For example, the part 5 is for forming a horizontal passage, and the part 10 is for forming a vertical passage. Parts 7, 11, and 13 are for configuring a T-shaped path, and part 15 is for configuring a cross road.

  The maze can also change its structure. For example, in FIG. 3, the structure of the maze changes as shown in FIG. 4 by changing two parts of the portion indicated by the dotted circle. That is, the structure of the maze can be changed so that what cannot pass through in FIG. 3 can pass through in FIG.

  Furthermore, in FIG. 4, the structure of the maze changes as shown in FIG. 5 by changing two parts of the part indicated by the dotted circle. That is, the structure of the maze can be changed so that what can pass through in FIG. 4 cannot pass through in FIG.

  The robot runs in such a maze. In this example, since the maze is two-dimensional and the direction of the passage is only horizontal or vertical, it is set so that the robot can move in four directions, up, down, left, and right.

  FIG. 6 is a diagram illustrating the moving direction of the robot. The vertical direction and horizontal direction in the figure correspond to those in FIG. 1, and it can be seen that the robot shown in the center in the figure moves in either the top, bottom, left or right direction in the figure.

  Here, the movement of the robot in a predetermined direction is referred to as an action. For example, in the example of FIG. 6, there are four actions corresponding to the four arrows in the figure.

  In addition, the robot is provided with a sensor for detecting an object, for example, and by analyzing a signal output from the sensor, it is possible to specify the type of the part where the robot is located on the maze. Has been made. That is, the robot acquires sensor signals corresponding to any of the 15 types of parts described above with reference to FIG. 2 at each position on the maze.

  In the present invention, for example, internal model data corresponding to the structure of the maze is generated based on the sensor signal at each position on the maze where the robot self-runs. Here, the maze is referred to as an environment, and a sensor signal corresponding to any of 15 types of parts is referred to as an observation symbol. In the present invention, the structure of the maze is learned using the HMM, and the internal model data described above is generated.

  In HMM learning, the state is recognized based on observations obtained from the environment. As described above, the environment is, for example, a maze, and the observation corresponds to an observation symbol specified from a sensor signal corresponding to, for example, any one of 15 types of parts. Note that the robot is appropriately referred to as an agent.

  In HMM learning, the agent recognizes the state of himself / herself based on observations obtained from the environment. The state here is a state that the agent has subjectively recognized. If the state where the agent is actually placed is observed objectively from the outside, the state may be different. For example, if the position of the robot on the two-dimensional maze is objectively observed, the position is the coordinates (x1, y1), whereas the robot itself is at the coordinates (x2, y2). May be recognized. In this way, the state subjectively recognized by the agent is expressed as a hidden state, an internal state, a state, a node, etc. in the HMM.

  In the present embodiment, each position on the maze, that is, each position of each part arranged in the maze is associated with a node (state, hidden state, internal state, state) in the HMM, An example in which observation symbols are associated with nodes will be described.

  By the way, the normal HMM is to structure the sensor signal, and there is no consideration regarding the action signal. Learning in a situation where an agent uses an action signal to perform an action on the environment so as to influence an observation symbol observed in the future is not assumed in the HMM. The solution of such a problem is called a partially observable Markov decision process (hereinafter referred to as POMDP).

  Therefore, the present invention solves the above problem by extending the HMM. That is, in the present invention, the HMM is expanded so as to consider the action signal. The HMM expanded in this way is referred to as an action expanded HMM.

  FIG. 7 is a diagram for explaining a normal HMM. As shown in the figure, the HMM learns the probability of transition (state transition) from one node to another node by the number of possible transitions. That is, a state transition probability value is set at each matrix position in the node number × node number table, and a two-dimensional table called a state transition probability table is generated. Also, the HMM learns the probability that each observation symbol is observed at a certain node. That is, an observation probability value is set at each matrix position in the node number × observation symbol number table, and a two-dimensional table called an observation probability table is generated.

  For example, in the state transition probability table of FIG. 7, each of the nodes described in the vertical direction in the figure represents a transition source node, and each of the nodes described in the horizontal direction in the figure represents a transition destination node. Therefore, for example, the numerical value described in the n-th row and m-th column of the state transition probability table represents the probability of transition from the node with index n (n-th node) to the node with index m (m-th node). Yes. Then, all the numerical values described in each row (for example, the nth row) of the state transition probability table are summed to be 1.

  Further, for example, in the numerical value described in the n-th row and the p-th column of the observation probability table of FIG. 7, the observation symbol (p-th observation symbol) of the index p is observed at the node of the index n (n-th node). Represents the probability of being. Then, the sum of all the numerical values described in each row (for example, the nth row) of the observation probability table is 1.

  FIG. 8 is a diagram for explaining an action expansion type HMM. As shown in the figure, in the action expanded HMM, a state transition probability table is generated for each action. For example, as a result of the action of upward movement, the probability of transition from one node to another node is generated as a state transition probability table for the upward movement action. Further, as a result of the action of moving downward, the probability of transition from one node to another is generated as a state transition probability table for the downward moving action. Similarly, a state transition probability table for the leftward movement action and a state transition probability table for the rightward movement action are also generated.

  For example, when the state transition probability table in FIG. 8 is viewed as a plurality of two-dimensional tables, each of the nodes described in the vertical direction in the figure represents a transition source node in each action, and in the horizontal direction in the figure. Each of the nodes described in 1 represents a transition destination node. Therefore, for example, the numerical value described in the n-th row and m-th column of the k-th state transition probability table is obtained by executing the action of index k (k-th action) from the node of index n to the node of index m. Represents the probability of transition to The sum of all the numerical values described in each row of the state transition probability table (for example, the nth row of the k-th table) is 1.

  Thus, in the action extended HMM, a two-dimensional state transition probability table is generated for each action, so to speak, a three-dimensional state transition probability table is generated.

  Note that, in the action expanded HMM, as in the case of a normal HMM, an observation probability value is set at each matrix position in the table of the number of nodes × the number of observation symbols, and a two-dimensional observation probability table is generated. .

  For example, the numerical value described in n rows and p columns of the observation probability table of FIG. 8 represents the probability that the observation symbol of index p is observed at the node of index n, as in the case of FIG. Then, the sum of all the numerical values described in each row (for example, the nth row) of the observation probability table is 1.

  Here, an example in which 15 observation symbols are obtained based on a sensor signal and a discrete observation signal is obtained has been described. However, for example, the action extended HMM can also be used when acquiring a continuous observation signal such that an almost infinite observation symbol is obtained based on a sensor signal that changes little by little.

  Further, here, an example has been described in which the agent executes any one of four actions, and executes a discrete action set. However, for example, the action extended HMM can also be used when the agent changes a moving direction little by little and executes a continuous action set in which one action is executed from among almost infinite actions.

  So far, the action expansion type HMM has been described.

  FIG. 9 is a block diagram showing a configuration example of the autonomous behavior learning apparatus 10 to which the present invention is applied. The autonomous behavior learning device 10 shown in FIG. 1 is configured as a control device for a robot that moves on a maze as shown in FIG. In this example, the autonomous behavior learning device 10 includes a sensor unit 31, a behavior output unit 32, an observation buffer 33, a learning device 34, a recognizer 35, a behavior generator 36, an internal model data storage unit 37, a recognition result buffer 38, and An action output buffer 39 is provided.

  For example, the sensor unit 31 outputs a sensor signal (or an observation signal) for observing the observation symbol described above in an environment such as a maze. The observation signal output from the sensor unit 31 is stored in the observation buffer 33 in association with the time when the observation signal is output.

For example, observation symbols o _t , o _{t + 1} , o _{t + 2} ,..., O _T corresponding to observation signals acquired at times _t , _{t + 1} , _{t + 2} ,. It is stored in the observation buffer 33 as an observation symbol at each time.

  The action output unit 32 is, for example, a functional block that outputs a control signal for causing the robot to execute an action (behavior in Japanese) to be executed by the robot. The control signal output from the action output unit 32 is converted into information specifying an action corresponding to the control signal, and is stored in the action output buffer 39 in association with the time when the control signal is output. Has been made.

For example, the actions c _t , c _{t + 1} , c _{t + 2} ,..., C _T executed at the times t, t + 1, t + 2,. It is stored in the output buffer 39.

  The learning device 34 generates or updates internal model data based on the information stored in the observation buffer 33 and the behavior output buffer 39 and stores the internal model data in the internal model data storage unit 37.

  The internal model data stored in the internal model data storage unit 37 includes the above-described three-dimensional state transition probability table and two-dimensional observation probability table. Furthermore, the internal model data stored in the internal model data storage unit 37 includes a frequency variable for calculating a state transition probability and a frequency variable for calculating an observation probability, which will be described later.

  Based on the information stored in the observation buffer 33 and the action output buffer 39 and the state transition probability table and the observation probability table stored in the internal model data storage unit 37, the recognizer 35 is currently located in the robot. It is designed to recognize nodes. The recognition result output from the recognizer 35 is stored in the recognition result buffer 38 in association with the time when the recognition result is output.

  The behavior generator 36 should be executed by the robot based on the internal model data stored in the internal model data storage unit 37, the information stored in the behavior output buffer 39, and the recognition result output by the recognizer 35. Determine the action. Then, the behavior generator 36 controls the behavior output unit 32 so as to output a control signal corresponding to the determined action.

  As described above, the autonomous behavior learning apparatus 10 can automatically learn the structure of the maze by moving the robot on the maze, for example.

  Next, the learning algorithm of the action expansion type HMM in the learning device 34 in FIG. 9 will be described.

In the normal HMM, the state transition probability from the node s _i to s _j is modeled by the state transition probability table a _ij , but in the action expanded HMM, it is modeled as a _ij (c) using the action parameter c.

  A Baum-Welch algorithm is used as a learning algorithm. If the forward probability and the backward probability can be calculated, parameter estimation (expected value maximization method) based on the Baum-Welch algorithm can be performed. Therefore, calculation of these probabilities will be described below.

Here, the probability that the transition from the node s _i to s _j occurs by the action c _k belonging to the action set C = {c ₁ , c ₂ ,..., C _n } is expressed as a three-dimensional probability expression table a _ij. (k) ≡ a _ijk In this example, a discrete action set is executed.

  First, calculation of the forward probability will be described.

Time 1, at each time of · · · t-1 observation symbols corresponding to sensor signals that the agent obtains, respectively _{o 1, o 2, ···,} o t? Let's denote by ₁ . Also, the actions executed by the agent at each time of time 1, 2,..., T−1 are c ₁ , c _{2 ,.} Let's denote by ₁ . In this case, when the observation symbols corresponding to sensor signals that the agent has acquired at time t is o _t, the agent node s _j to have forward probability alpha _t (j) denotes the recurrence formula of the formula (1) be able to.

・・・（１）
ただし、b_j(o)は、ノードs_jの下で観測シンボルoが得られる観測確率である。

... (1)
Here, b _j (o) is an observation probability that the observation symbol o is obtained under the node s _j .

  Next, calculation of the backward probability will be described.

If the agent is in state i at time t, actions c _t , c _{t + 1} ,..., C _{T at} times t, t + 1, t + 2 _{,. 1} is executed, the observation symbols corresponding to sensor signals obtained at each time, each _{o t + 1, o t +} 2, ···, backward probability βt is o _T (i) has the formula (2) It can be expressed by the recurrence formula.

・・・（２）

... (2)

  By using the forward probability and the backward probability calculated in this way, it is possible to estimate the state transition probability and the observation probability.

  The estimation of the state transition probability and the observation probability when executing the discrete action set are performed as follows.

The state transition probability a _ij (k) is estimated in the M-step of the Baum-Welch algorithm. Here, the state transition probability a _ij (k) means the probability of transition to the state j by executing the action k when the agent is in the state i. In other words, the estimated value a ′ _ij (k) of the state transition probability can be obtained by calculating Expression (3).

・・・（３）

... (3)

The observation probability b _j (o) is also estimated by the M-step of the Baum-Welch algorithm. Here, the observation probability b _j (o) means establishment of acquiring a sensor signal corresponding to the observation symbol o when the agent is in the state j. That is, by calculating equation (4), an estimated value b ′ _j (o) of the observation probability can be obtained.

・・・（４）

... (4)

Equation (4) is an example of obtaining a discrete observation signal. However, when obtaining a continuous observation signal, the observation signal o _t obtained at time t is expressed as γ _t ( j) The parameters of the observation probability density function b _j (o) may be re-estimated using the weighted signal distribution. Note that γ _t (j) represents a weighting coefficient when the agent is in the state j at time t.

・・・（５）

... (5)

Normally, logarithmic concave such as Gaussian distribution or elliptical symmetrical probability density is used as a model, and the parameters of the observed probability density function b _j (o) can be re-estimated.

As a parameter of a log-concave or elliptical symmetry probability density model such as a Gaussian distribution, an average vector μ ′ j of an observation signal in a state _j and a covariance matrix U ′ _j can be used. The average vector μ ′ _j and the covariance matrix U ′ _j can be obtained by Expression (6) and Expression (7), respectively.

・・・（６）

... (6)

・・・（７）

... (7)

  Next, an example of executing a continuous action set will be described.

In the case of the continuous action, unlike the case of the discrete action, it is necessary to learn the probability ρ _k (c) that the continuous action c is output from the discrete action c _k . This is because by learning the probability ρ _k (c), the continuous action c can be labeled as if it were the discrete action c _k (corresponding to the discrete action).

  The calculation of the forward probability in the case of continuous action is performed as follows.

Time 1, at each time of · · · t-1 observation symbols corresponding to sensor signals that the agent obtains, respectively _{o 1, o 2, ···,} o t? Let's denote by ₁ . Also, discrete actions estimated from continuous actions executed by the agent at each time of time 1, 2,..., T−1 are c ₁ , c _{2 ,.} Let's denote by ₁ . In this case, when the observation symbols corresponding to sensor signals that the agent has acquired at time t is o _t, the agent node s _j to have forward probability alpha _t (j) denotes the recurrence formula of the formula (8) be able to.

・・・（８）
ただし、ρ_k(c)は、離散アクションc_kより連続アクションcの出力される確率を表す。
なお、ρ_k(c)をどのようにして求めるかについては、後述する。

... (8)
Here, ρ _k (c) represents the probability that the continuous action c is output from the discrete action c _k .
Note that how ρ _k (c) is obtained will be described later.

When the agent is in the state i at time t, the discrete actions estimated from the continuous actions executed by the agent at the times t, t + 1, t + 2,. _t , c _{t + 1} , ..., c _{T? 1,} and observation symbols corresponding to sensor signals obtained at each time, each _{o t + 1, o t +} 2, ···, a o _T backward probability [beta] t (i) is gradually formula (9) It can be expressed by a chemical formula.

・・・（９）

... (9)

  The estimation of the state transition probability and the observation probability when the continuous action set is executed is performed as follows.

The state transition probability a _ij (k) is estimated in the M-step of the Baum-Welch algorithm as in the case of the discrete action. Here, the state transition probability a _ij (k) means the probability of transition to the state j by executing the action k when the agent is in the state i. In other words, the estimated value a ′ _ij (k) of the state transition probability can be obtained by calculating Expression (10).

・・・（１０）

(10)

Since the estimation of the observation probability b _j (o) is exactly the same as in the case of the discrete action, the description is omitted here.

Next, how to obtain the probability ρ _k (c) that the continuous action c is output from the discrete action c _k will be described.

The probability ρ _k (c) can also be performed in the M-step of the Baum-Welch algorithm. That is, it can be estimated by the same method as the estimation of the observation probability in the case of continuous observation signals.

The probability ρ _k (c) may be estimated using a signal distribution obtained by weighting the action ct executed at time t by ξ _t (i, j, k) shown in Expression (11).

・・・（１１）

(11)

As with the observation probability, the probability ρ _k (c) can be estimated using a Gaussian distribution or the like as a model.

In this case, the average vector ν _k and the covariance matrix V ′ _k of the action signal generated from the discrete action c _k obtained by labeling the continuous action c are calculated by the equations (12) and (13), respectively. The action signal average vector ν _k and covariance matrix V ′ _k calculated as described above may be used as parameters of a model such as a Gaussian distribution.

・・・（１２）

(12)

・・・（１３）

(13)

  In this way, a three-dimensional state transition probability table and a two-dimensional observation probability table in the action expanded HMM can be generated by learning.

  The state transition probability and the observation probability can be obtained by the action extended type HMM learning algorithm described so far as in the case of a normal HMM.

However, if the number of states (number of nodes) is N, the number of observation symbols is M, and the number of actions is K, the number of parameters to be calculated in the three-dimensional state transition probability table and the two-dimensional observation probability table is N ^2. K + NM. As described above, in the action expansion type HMM, it is clear that the load of the learning process increases at an accelerated rate as the number of N, M, and K increases. For example, in an environment where N is about 250, M is about 15, and K is about 5, it is necessary to calculate 300,000 scale parameters. It is very difficult to properly determine so many parameters from a few samples.

  However, for example, by adding constraints to the model, it is possible to reduce the degree of freedom of parameters and stabilize learning. Next, a technique necessary for efficiently and appropriately learning an action expanded HMM that inevitably has a large scale will be described.

  In the present invention, one-state one-observation constraint and action transition constraint are imposed in learning of the action-expanded HMM.

  First, one-state one-observation constraint will be described. The one-state one-observation constraint is a constraint that, for example, the number of observation symbols observed at a certain node is limited to one in principle. Note that it is permissible to observe the same observation symbol at different nodes even under the one-state one-observation constraint.

  In action-expanded HMM learning, the representation method of events is limited by imposing one-state one-observation constraint, and as a result, the degree of freedom of parameters required for generating the state transition probability table and the observation probability table is reduced. To do.

  As one of the methods for realizing one-state one-observation constraint, for example, there is a method of adding a constraint term that makes the observation probability sparse in the objective function, as is done in the learning of the discrete observation type HMM.

For example, a method of adding a constraint term Σ _j H (b _j ) multiplied by a weight λ that makes the observation probability sparse is added to the objective function. Here, H (b _j ) is an entropy defined for the observation probability vector b _j for all observation symbols that can be observed at the node s _j . In addition to this, a method in which the difference Σ _j (|| b _j || ₁ ? || b _j || ₂ ) between the L1 norm and the L2 norm of the observation probability vector b _j is also considered as a constraint term.

Alternatively, the one-state one-observation constraint can be realized by a method other than the method of adding the constraint term Σ _j H (b _j ) obtained by multiplying the above objective function by a weight λ that makes the observation probability sparse. is there. As an example of such a method, an example in which a split algorithm is applied can be considered.

  10 and 11 are diagrams for explaining the split algorithm. In FIGS. 10 and 11, nodes are indicated by circles in the drawings, and the figure of the part described above with reference to FIG. 2 is displayed as a symbol observed at each node.

  FIG. 10 is a diagram visualizing the contents of the state transition probability table and the observation probability table obtained as a result of agent learning. The example of FIG. 10 shows an example in the case where the node S10, the node S20, and the node S30 exist. In this example, when the agent observes the crossroad part (part 15 in FIG. 2) at the node S10 with a probability of 100% and executes an action of moving to the right at the node S10, the agent has a probability of 100%. Move (transition) to S20.

  Further, at the node S20, the parts 7 and 13 in FIG. 2 are observed with a probability of 50%. When an action that moves in the right direction is executed in the node S20, the transition to the node S30 is made with a probability of 100%, and when an action that moves in the left direction is executed in the node S20, the action is made with a probability of 100%.

  Further, at the node S30, the part 5 in FIG. 2 is observed with a probability of 100%, and when the action of moving to the left in the node S30 is executed, the node 5 transitions to the node S20 with a probability of 100%.

  Note that FIG. 10 (the same applies to FIG. 11) is a visualization of the contents of the state transition probability table and the observation probability table. Actually, the state transition probability table and the observation probability table corresponding to FIG. As learned. When the split algorithm is applied to such internal model data, the contents of the state transition probability table and the observation probability table change as shown in FIG.

  FIG. 11 is a diagram visualizing the contents of the state transition probability table and the observation probability table obtained when the split algorithm is applied to the contents of the state transition probability table and the observation probability table corresponding to FIG.

  In the example of FIG. 11, there are a node S10, a node S21, a node S22, and a node S30. That is, the node S20 in FIG. 10 is divided (split) into the node S21 and the node S22 in FIG. In this example, the part 15 in FIG. 2 is observed at the node S10 with a probability of 100%, and when the action of moving to the right is executed at the node S10, the transition to the node S21 is performed with a probability of 50%. Transition to node S22.

  2 is observed at a probability of 100% in the node S21. When an action of moving to the right in the node S21 is executed, the action moves to the node S30 with a probability of 100% and an action of moving to the left is executed. Then, a transition to the node S10 is made with a probability of 100%.

  The node 13 in FIG. 2 is observed with a probability of 100%. If an action of moving to the right in the node S22 is executed, the transition to the node S30 is performed with a probability of 100%, and an action of moving to the left is executed. Transition to the node S10 with a probability of%.

  Further, at node S30, part 5 in FIG. 2 is observed with a probability of 100%. When an action of moving to the left in node S30 is executed, transition to node S21 is made with a probability of 50%, and node S22 is made with a probability of 50%. Transition to.

  Thus, by applying the split algorithm, it is possible to realize one-state one-observation constraint.

  In other words, the split algorithm is applied by applying the one-state one-observation constraint to the local optimal solution obtained by the expected value maximization method, and again by using the local optimization based on the expected value maximization method for the corrected solution. By repeating the processing, the processing for obtaining a local optimal solution that finally satisfies the one-state one-observation constraint is obtained.

  In the example described above with reference to FIGS. 10 and 11, it has been described that the observation symbol observed at each node is divided so that the observation probability is 100%. It is rare that the observation probability is 100%. This is because the one-state one-observation constraint does not always limit the number of observation symbols observed at one node to one in a strict sense. That is, the one-state one-observation constraint is such that even when there are a plurality of observation symbols observed at one node, the observation probability of one observation symbol is equal to or greater than a threshold value.

  Processing when the split algorithm is applied to the internal model data by the learning device 34 of FIG. 9 will be described with reference to the flowchart of FIG.

In step S101, the learning device 34 refers to the observation probability table stored in the internal model data storage unit 37, and searches for one node s _j whose maximum value of the observation probability b _j is equal to or less than the threshold th1.

In step S102, the learning device 34 determines whether or not a node s _j having a maximum value equal to or less than the threshold value th1 has been found as a result of the process in step S101. If it is determined that the node s _j has been found, the process proceeds to step S103.

In step S103, the learning device 34 refers to the observation probability table, and checks the observation probability of each observation symbol in the node s _j determined to be found in step S102. Then, the learning device 34 counts the number of observation symbols whose observation probability is equal to or higher than the threshold th2 at the node s _j , and lists those observation symbols.

For example, if the observation symbols of K observation probability is a threshold th2 or more are present, observation symbols _{o k (k = 1, ···} , K) are listed.

In step S104, the learning device 34 divides the node s _j into K pieces.

At this time, the observation probability in the observation probability table after the node s _j is divided and the state transition probability in the state transition probability table are set as follows.

The k-th node among the K nodes obtained as a result of dividing the node s _j is represented as s _j ^k, and each observation probability of each observation symbol observed at the node s _j ^k is an element. Let be expressed as b _j ^k .

In step S104, the learning device 34 increases the vector b _j ^k with only the observation probability with respect to the observation symbol o _k protruding (very close to 1), and the observation probability with respect to the other observation symbols is a uniform random number in a very small range. Set to be.

In addition, the state transition probability from the node s _i to the node s _j before the node s _j is divided is represented by a _ij , and the node s _i to the node s _j ^k after the node s _j is divided The state transition probability is represented by a ^k _ij .

In step S104, the learning device 34 sets the state transition probability to be a ^k _ij and the state transition probability a _ij before the division to be prorated by the ratio of the observation probabilities of the respective observation symbols before the division. .

Furthermore, the state transition probabilities from the previous node s _j to the node s _i to node s _j is divided and be represented by a _ji, from node s _j ^k after the node s _j is divided to the node s _i The state transition probability is represented by a ^k _ji .

In step S104, a state transition probability a _ji is set for each of the K state transition probabilities a ^k _ji .

  In this way, the split algorithm application process is executed.

  Next, action transition constraints will be described. The action transition constraint is a constraint on the premise that a one-state one-observation constraint is imposed.

The action transition constraint is a transition from a node s _i to a transition destination node s _j (j = 1,..., J) that can be transitioned by the same action c _k or the same action c _k to the node s _i . In the possible transition source node s _j (j = 1,..., J), a different observation symbol o _j (j = 1,..., J) should be observed. The former is called a forward constraint and the latter is called a backward constraint. That is, under the action transition constraint, it is not allowed to observe the same observation symbol at a plurality of transition destination (or transition source) nodes that can be transitioned by the same action _ck . It should be noted that even under an action transition constraint, it is allowed that a plurality of transition destination nodes that can be transitioned by the same action _ck exist as long as the nodes observe different observation symbols.

  An example of applying a forward merge algorithm and a backward merge algorithm can be considered as an example of a method for realizing an action transition constraint.

  13 and 14 are diagrams for explaining the forward merge algorithm.

  In FIG. 13 and FIG. 14, nodes are indicated by circles in the drawings, and the graphics of the parts described above with reference to FIG. 2 are displayed as symbols observed at each node.

  FIG. 13 is a diagram visualizing the contents of the state transition probability table and the observation probability table obtained as a result of agent learning. The example of FIG. 13 illustrates an example in which the node S10, the node S21, the node S22, the node S31, and the node S32 exist. In the case of this example, when the action of moving in the right direction is executed in the node S10, the transition is made to the node S21 with a probability of 50% and the transition is made to the node S22 with a probability of 50%.

  At node S21, part 5 in FIG. 2 is observed with a probability of 100%, and at node S22, part 5 in FIG. 2 is observed with a probability of 100%.

  Further, if an action moving rightward is executed in the node S21, transition to the node S31 is made with a probability of 100%, and if an action moving rightward is executed in the node S22, the action is changed to the node S32 with a probability of 100%.

  FIG. 13 (same for FIG. 14) is a visualization of the contents of the state transition probability table and the observation probability table. Actually, the state transition probability table and the observation probability table corresponding to FIG. As learned. When the forward merge algorithm is applied to such internal model data, the contents of the state transition probability table and the observation probability table change as shown in FIG.

  FIG. 14 is a diagram visualizing the contents of the state transition probability table and the observation probability table obtained when the forward merge algorithm is applied to the contents of the state transition probability table and the observation probability table corresponding to FIG.

  In the example of FIG. 14, there are a node S10, a node S20, a node S31, and a node S32. That is, the node S21 and the node S22 in FIG. 13 are merged with the node S20 in FIG. In this example, the part 5 of FIG. 2 is observed with a probability of 100% at the node S20, and when the action of moving in the right direction is executed at the node S10, the transition to the node S20 is performed with a probability of 100%.

  Further, when an action of moving in the right direction is executed in the node S20, the node transits to the node S31 with a probability of 50%, and transits to the node S32 with a probability of 50%.

  Thus, by applying the forward merge algorithm, it is possible to realize a forward constraint among the action transition constraints.

That is, under the action transition constraint, the same observation symbol is not allowed to be observed at a plurality of transition destination nodes that can be transitioned by the same action _ck , so that the nodes S21 and S22 in FIG. It is merged into 14 nodes S20. Note that if there is a node S23 that transitions by executing an action of moving to the right in the node S10, when a part other than the part 5 is observed in the node S23, the node 23 is to be merged. There is no. This is because, even under an action transition constraint, if a node observes different observation symbols, it is allowed to have a plurality of transition destination nodes that can be transitioned by the same action _ck .

  That is, a node having a similar observation probability distribution at each transition destination node that can transition when a predetermined action is executed in one node is found, and the discovered nodes are merged.

In the example described above with reference to FIG. 13 and FIG. 14, it has been described that merging is performed so that the state transition probability to a node where a predetermined observation symbol is observed is 100%. It is rare that the state transition probability is 100%. This is because the forward constraint does not allow the same observation symbol to be observed in a plurality of transition destination nodes that can be transitioned by the same action c _k in a strict sense.

  Processing when the forward merge algorithm is applied to the internal model data by the learning device 34 of FIG. 9 will be described with reference to the flowchart of FIG.

In step S121, the learning device 34 refers to the state transition probability table stored in the internal model data storage unit 37, and checks the state transition probability table of one action _ck .

In step S122, the learning device 34 identifies one transition source node s _i in the state transition probability table checked in the process of step S121, and calculates the state transition probability from the node s _i to each transition destination node. Check the element vector a _ij (k). Then, the learning device 34 lists the transition destination node s _j whose state transition probability value is equal to or greater than the threshold value.

  In step S123, the learning device 34 classifies the transition destination nodes listed in the process of step S122 for each observation symbol.

  Note that as described above, action transition constraints are based on the premise that one-state one-observation constraint is imposed, so it is possible to specify almost one observation symbol observed at the transition destination node. It is.

  In step S124, the learning device 34 merges the nodes of the same observation symbol classified in the process of step S123.

That is, the node group corresponding to the observation symbol m merged in the process of step S123 is represented by s _j ^{m, l} (l = 1,..., L), and L nodes s _j ^{m, l} is merged into one node s _j ^m .

At this time, the state transition probability in the state transition probability table after the L nodes s _j ^{m, l} are merged into one node s _j ^m and the observation probability in the observation probability table are set as follows. .

The state transition probability a _ij ^m from the node s _i to the node s _j ^m is obtained and set by Expression (14).

・・・（１４）
ここで、a_ij ^m，lは、マージされる前のノードs_iから１個のノードs_j ^m，lへの状態遷移確率を表すものとする。

(14)
Here, a _ij ^{m, l} represents the state transition probability from the node s _i before merging to one node s _j ^{m, l} .

Node s state transition probability a _ji ^m from _j ^m to the node s _i ^is, a _ji ^m, simple average of ^l, or Σ _k a _kj ^m, is obtained and set as a weighted average by ^l.

The observation probability b _j ^m of the observation symbol m at the node s _j ^m after the L nodes s _j ^{m, l} are merged into one node s _j ^m is the simple average of b _j ^{m, l} or Σ _k It is obtained and set as a weighted average by a _kj ^{m, l} .

In step S124, the state transition probability a _ij ^m , the state transition probability a _ji ^m , and the observation probability b _j ^m are set in this way.

  In this way, the process of applying the forward merge algorithm is executed.

  16 and 17 are diagrams for explaining the backward merge algorithm.

  In FIG. 16 and FIG. 17, nodes are indicated by circles in the drawings, and the graphics of the parts described above with reference to FIG. 2 are displayed as symbols observed at each node.

  FIG. 16 is a diagram visualizing the contents of the state transition probability table and the observation probability table obtained as a result of agent learning. The example of FIG. 16 illustrates an example in which the node S11, the node S12, the node S21, the node S22, and the node S30 exist. In this example, when an action of moving in the right direction is executed in the node S11, the transition to the node S21 is made with a probability of 100%. When the action of moving in the right direction is executed in the node S12, the transition to the node S22 is made with a probability of 100%.

  Further, at the node S21, the part 7 in FIG. 2 is observed with a probability of 100%. At node S22, part 7 in FIG. 2 is observed with a probability of 100%.

  Further, when an action moving in the right direction is executed in the node S21, transition to the node S30 is performed with a probability of 100%, and when an action moving in the right direction is executed in the node S22, transition to the node S30 is performed with a probability of 100%.

  Note that FIG. 16 (same for FIG. 17) is a visualization of the contents of the state transition probability table and the observation probability table. Actually, the state transition probability table and the observation probability table corresponding to FIG. As learned. When the backward merge algorithm is applied to such internal model data, the contents of the state transition probability table and the observation probability table change as shown in FIG.

  FIG. 17 is a diagram visualizing the contents of the state transition probability table and the observation probability table obtained when the backward merge algorithm is applied to the contents of the state transition probability table and the observation probability table corresponding to FIG.

  In the example of FIG. 17, there are a node S11, a node S12, a node S20, and a node S30. That is, the nodes S21 and S22 in FIG. 16 are merged with the node S20 in FIG. In this example, the part 7 in FIG. 2 is observed at the node S20 with a probability of 100%.

  Further, when an action that moves in the right direction is executed in the node S11, a transition is made to the node S20 with a probability of 100%, and when an action that moves in the right direction is executed in the node S12, a transition to the node S20 is made with a probability of 100%.

  Furthermore, when an action of moving in the right direction is executed in the node S20, the transition to the node S30 is made with a probability of 100%.

  In this way, by applying the backward merge algorithm, it is possible to realize the backward constraint among the action transition constraints.

That is, under the action transition constraint, the same observation symbol is not allowed to be observed at a plurality of transition source nodes that can be transitioned by the same action _ck , so that the nodes S21 and S22 in FIG. It is merged into 17 nodes S20. If there is a node S23 that transitions to the node S30 by executing an action that moves to the right, if a part other than the part 7 is observed at the node S23, the node 23 is to be merged. There is no. This is because it is allowed that a plurality of transition source nodes that can be transitioned by the same action _ck exist as long as the nodes observe different observation symbols even under the action transition constraint.

  That is, for a single node, a node having a similar observation probability distribution at each of the transition source nodes that are transitioned by a common action is discovered, and the discovered nodes are merged.

  Processing when the backward merge algorithm is applied to the internal model data by the learning device 34 of FIG. 9 will be described with reference to the flowchart of FIG.

In step S141, the learning device 34 refers to the state transition probability table stored in the internal model data storage unit 37, and checks the state transition probability table of one action _ck .

In step S142, the learning device 34 specifies one transition destination node s _j in the state transition probability table checked in the process of step S141, and the state transition probability from each transition source node to the node s _j . Check the vector a _ij (k) whose elements are. Then, the learning unit 34, lists the transition source node s _i the value of the state transition probability is equal to or larger than the threshold value.

  In step S143, the learning device 34 classifies the transition source nodes listed in the process of step S142 for each observation symbol.

  Note that, as described above, action transition constraints are based on the premise that one-state one-observation constraint is imposed, so it is possible to specify almost one observation symbol observed at the transition source node. It is.

  In step S144, the learning device 34 merges the nodes of the same observation symbols classified in the process of step S143.

That is, the node group corresponding to the observation symbol m merged in the process of step S143 is represented by s _i ^{m, l} (l = 1,..., L), and L nodes s _i ^{m, l} is merged into one node s _i ^m .

At this time, the state transition probability in the state transition probability table and the observation probability in the observation probability table after the L nodes s _i ^{m, l} are merged into one node s _i ^m are set as follows. .

State transition probability a _ij ^m from node s _i ^m to the node s _j ^is, a _ji ^m, simple average of ^l, or Σ _k a _ki ^m, it is obtained and set as a weighted average by ^l.

The state transition probability a _ji ^m from the node s _j to the node s _i ^m is obtained and set by Σ _l a _ji ^{m, l} .

The observation probability b _i ^m of the observation symbol m at the node s _i ^m after the L nodes s _i ^{m, l} are merged into one node s _i ^m is the simple average of b _i ^{m, l} or Σ _k It is obtained and set as a weighted average by a _ki ^{m, l} .

In step S124, the state transition probability a _ij ^m , the state transition probability a _ji ^m , and the observation probability b _j ^m are set in this way.

  In this way, the backward merging algorithm application process is executed.

  By imposing the one-state one-observation constraint and the action transition constraint in this way, it is possible to reduce the load of the learning process.

  FIG. 19 is a table for comparing the likelihoods of the state transition probability table and the observation probability table in the action expanded HMM. The leftmost column in the figure represents the number of learning (number of trials). The column on the right side of the number of trials is a column of “first learning”, which describes the likelihood values of the state transition probability table and the observation probability table learned at each trial number. The column on the right side of “first learning” is the column “after split / merging”. In this column, the state transition probability table and the observation probability table obtained by performing the processing of FIG. 12, FIG. 15 and FIG. 18 on the state transition probability table and the observation probability table obtained by “first learning”. The likelihood value of the probability table is described. Further, the column on the right side of “after split / merge” is the column of “increment”. In this column, the difference between the likelihood value described in the “after split / merging” column and the likelihood value described in the “first learning” column is described.

  As shown in FIG. 19, it is understood that the likelihood is improved by performing the processes of FIGS. 12, 15, and 18. It can also be seen that the number of times that the likelihood value takes a value in the vicinity of “−60” increases by performing the processes of FIGS. 12, 15, and 18. That is, it can be said that the likelihood value is most appropriately learned in the case where learning is performed in the vicinity of “−60”. On the other hand, the likelihood described in the “first learning” column changes greatly every time learning is performed, and it is difficult to learn the given environment most appropriately even if learning is repeated. It turns out that it is.

  That is, by imposing one-state one-observation constraint and action transition constraint, it is possible to improve the learning accuracy of the action expanded HMM.

  FIGS. 20 to 26 are diagrams for explaining the change in the learning result by imposing one-state one-observation constraint and action transition constraint.

  Here, a case will be described as an example where, in the maze shown in FIG. 20, the part at the position shown by a circle in the figure is changed and the agent learns the maze changed to the structure shown in FIG. 21 as the environment. .

  FIG. 22 is a diagram in which the contents of the state transition probability table and the observation probability table of the agent who has learned the environment shown in FIGS. 20 and 21 are visualized. In the example of FIG. 22, nodes are indicated by circles in the figure, and the nodes that are transitioned by the action in the direction represented by the triangles in the figure are connected by lines. In addition, the number shown inside the circle in the figure represents the index of the node indicated by the circle. The example of FIG. 22 is a diagram visualizing the contents of the state transition probability table and the observation probability table obtained without imposing one state one observation constraint and action transition constraint.

  On the other hand, FIG. 23 shows a state transition probability table and an observation probability obtained by subjecting the state transition probability table and the observation probability table corresponding to FIG. The table contents are visualized.

  In FIG. 23, the node 28 of FIG. 22 is divided into a node 28 and a node 31. In FIG. 23, the node 17 and the node 19 in FIG. Further, in FIG. 23, the node 12 and the node 25 in FIG.

  It should be noted that in the time zone in which the agent was moving on the maze for learning, the time zone in which the maze was configured as shown in FIG. 20 and the time zone in which the maze was configured as shown in FIG. Exists. Therefore, the position of each node shown in FIG. 23 does not completely match the position of the part in FIG. 20 or FIG. For example, it can be understood that the structure of the maze can be appropriately changed by the time zone by the node 24, the node 36, the node 2, and the node 18 in FIG.

  In practice, the size of the maze is even larger. For example, the agent learns using a maze as shown in FIG. 24 as an environment. In this case, the contents of the state transition probability table and the observation probability table obtained without imposing one state one observation constraint and action transition constraint are visualized as shown in FIG. On the other hand, when the contents of the state transition probability table and the observation probability table obtained by imposing one state one observation constraint and action transition constraint are visualized, it is as shown in FIG.

  Compared with FIG. 25, FIG. 26 is close to the structure of the actual maze (FIG. 24).

  So far, the technology necessary for efficiently and appropriately learning the action-expanded HMM that inevitably has a large scale has been described.

  Next, the action expansion type HMM learning process by the learning device 34 of FIG. 9 described so far will be described with reference to the flowchart of FIG.

  In step S161, the learning device 34 acquires initial internal model data. Here, the initial internal model data is, for example, a state transition probability table and an observation probability table immediately after the robot is generated by moving on the maze. The state transition probability and the observation probability set in the state transition probability table and the observation probability table are, for example, information including a combination of an action executed by the robot at each time and an observation symbol observed as a result of executing the action. Based on.

  In step S162, the learning device 34 optimizes the internal model data acquired in the process of step S161. At this time, for example, each value of the state transition probability table and each value of the observation probability table are changed to be optimized by a maximum likelihood estimation method or the like.

  In step S163, the learning device 34 determines whether the internal model data optimized in the process of step S162 satisfies the one-state one-observation constraint and the action transition constraint described above.

  For example, even when there are a plurality of observation symbols observed at one node, if one of the observation symbols has an observation probability equal to or higher than a threshold, the one-state one-observation constraint is satisfied. In addition, for example, in a plurality of transition destination nodes that can be transitioned by the same action, when the probability that the same observation symbol is observed is equal to or less than a threshold value, the action transition constraint is satisfied.

  If it is determined in step S163 that the internal model data does not satisfy the one-state one-observation constraint and the action transition constraint described above, the process proceeds to step S164.

  In step S164, the learning device 34 changes the internal model data so as to satisfy the one-state one-observation constraint and the action transition constraint. At this time, for example, each value of the state transition probability table and each value of the observation probability table are changed by executing the processing described above with reference to FIGS. 12, 15, and 18.

  After the process of step S164, the process returns to step S162. In step S163, the processes in steps S162 to S164 are repeatedly executed until it is determined that the one-state one-observation constraint and the action transition constraint are satisfied.

  If it is determined in step S163 that the one-state one-observation constraint and the action transition constraint are satisfied, the process proceeds to step S165.

  In step S165, the learning device 34 stores the internal model data in the internal model data storage unit 37.

  In this manner, the action expansion type HMM learning process is executed.

  By the way, there are a batch learning method and an additional learning method as methods for learning the HMM. Here, the batch learning method is to generate and store a state transition probability table and an observation probability table based on 10,000 steps of transition and observation, for example, when 10,000 steps of transition and observation data are obtained. is there. On the other hand, in the additional learning method, for example, first, a state transition probability table and an observation probability table are generated and stored based on 1000-step transitions and observations. Then, change and save each value in the state transition probability table and the observation probability table based on the subsequent 1000-step transitions and observations, and so on to update the internal model data by repeatedly learning (Update).

  For example, in the case of learning of an action expansion type HMM by a robot that runs on the maze, it is required to perform learning by an additional learning method. In learning with the batch learning method, it is impossible in principle to adaptively learn changes in the structure of the maze, etc. In order to achieve better performance in a changing environment, the operation results are fed back. This is because learning by the additional learning method is essential.

  However, the problem of how to integrate “learned memory structure” and “new experience” when performing additional learning is still unsolved. On the one hand, there is a request to realize quick adaptation by quickly reflecting “new experience”, but there is also a risk of destroying the memory structure established so far.

  For example, when a robot that learns the structure of the maze as shown in FIG. 28 keeps moving for a long time within the range indicated by the circle 101 in the figure after learning once and storing the internal model data, The internal model data corresponding to the position in the range indicated by the circle 102 may be destroyed. That is, the internal model data corresponding to the position of the range indicated by the circle 102 that has been properly learned and stored may be erroneously updated. In the learning of the additional learning method, the internal model data is updated only based on newly obtained transitions and observations. Therefore, the position in the range indicated by the circle 101 is erroneously changed to the position in the range indicated by the circle 102. This is because it may be recognized as a corresponding node.

  In order to cope with such a problem, for example, conventionally, in order to perform learning by the additional learning method, the internal model data is separately held corresponding to each range of the maze. Alternatively, learning is performed by rehearsing internal model data obtained by past learning from the current memory.

  However, even if the conventional method is adopted, for example, “new experience” is not reflected in the separated past internal model data, or past internal model data that is rehearsed affects the “new experience”. There was a problem that it was received and generated. As described above, in the conventional method, it is difficult to perform additional learning to function as a practical model in large-scale HMM learning. For example, if batch learning is performed on data used for past learning and data used for new learning, an appropriate learning result can be obtained. A large storage capacity and calculation amount are required.

  Next, a technique for enabling stable learning in the additional learning method in the action expanded HMM that inevitably has a large scale will be described.

  In the present invention, the learning device 34 performs learning by the following additional learning method so that better performance can be exhibited in a changing environment and stable learning can be performed. Specifically, by calculating and storing a frequency variable for estimating a state transition probability and a frequency variable for estimating an observation probability, which will be described later, learning in the additional learning method in the action expanded HMM is stabilized. Be able to do it automatically.

  In other words, the learning by the batch learning method can be said to be a combination of learning obtained based on observation and transition obtained in a plurality of time zones. For example, as shown in FIG. 29, it is considered that transition and observation whole data DA used in batch learning learning is configured. That is, the entire data DA includes a data set D1 obtained in the first time zone, a data set D2 obtained in the second time zone, a data set D3 obtained in the third time zone,・ It is thought that it is composed of

  The estimation of the state transition probability in learning of the action expanded HMM is performed by the above-described equation (3). Here, consider a case where a plurality of data sets exist as shown in FIG.

The estimated value a ′ _ij (k) ⁽ⁿ⁾ of the state transition probability in the n-th learning data set Dn can be obtained by Expression (15).

・・・（１５）

... (15)

  Here, in the description of the estimation of the state transition probability, t∈Dn represents (t, t + 1∈Dn) by this notation unless otherwise specified. Further, it is assumed that the learning data set Dn includes information representing an action executed at each time, a node at each time, and an observation symbol at each time.

It can be said that the numerator in the equation (15) represents the frequency of transition from the node i to the node j by executing the action c _k in the learning data set Dn. On the other hand, the denominator of Expression (15) can be said to represent the frequency of transition from node i to another node by executing action _ck in learning data set Dn.

Now, a variable χ _ij (k) ⁽ⁿ⁾ representing an expression corresponding to the numerator in Expression (15) is defined as represented by Expression (16).

・・・（１６）

... (16)

  Expression (17) can be obtained from Expression (16).

・・・（１７）

... (17)

  Expression (18) is derived from Expression (17) and Expression (15).

・・・（１８）

... (18)

Thus, the estimated value of the state transition probability can be expressed using the variable χ _ij (k) ⁽ⁿ⁾ .

Here, the variable χ _ij (k) ⁽ⁿ⁾ corresponds to the numerator in the equation (15), and the frequency of transition from the node i to the node j by executing the action c _k in the learning data set Dn. Therefore, it is called a frequency variable for estimating the state transition probability.

In the present invention, when performing the learning of the additional learning method, in order to enable stable learning, the estimated value of the state transition probability is calculated using the frequency variable χ _ij (k) ⁽ⁿ⁾ described above. I will ask. That is, each time the learning device 34 performs learning based on one learning data set, the frequency variable is updated and stored in the internal model data storage unit 37 as one of the internal model data.

  In other words, when a new learning is performed, the frequency variable corresponding to the past learning data set is read, and the frequency variable is updated by adding the frequency variable obtained based on the new learning to the frequency variable. To do. Furthermore, learning of the additional learning method is performed by obtaining an estimated value of the state transition probability obtained based on the updated frequency variable. In this way, it is possible to obtain a result almost equivalent to batch learning of the learning data sets D1, D2, D3.

Next, the integration of each internal model data obtained by multiple learning will be described. That is, estimated values a ′ _ij (k) ⁽¹⁾ and a ′ _ij (k) ^{(2) of} state transition probabilities calculated based on the learning data sets D ₁ , D ₂ ,... D _n. ,... A ′ _ij (k) ⁽ⁿ⁾ ,.

In such a case, for example, a weight w _n (Σw _n = 1) is set, and the state transition probability estimated values a ′ _ij (k) ⁽¹⁾ , a ′ _ij ( k) ⁽²⁾ , ... a´ _ij (k) ⁽ⁿ⁾ , ... can be integrated.

・・・（１９）

... (19)

Equation (19) means that the estimated values of the state transition probabilities described above are multiplied by the weights w ₁ , w ₂ ,..., W _n ,. is doing.

  However, as described above, in the present invention, since the estimated value of the state transition probability obtained based on the frequency variable corresponding to the learning data set is obtained, the integration according to Expression (19) is not suitable.

  In the present invention, since the estimated value of the state transition probability obtained based on the frequency variable corresponding to the learning data set is obtained, it is necessary to perform integration in consideration of the reliability of the estimated value of each state transition probability. is there. That is, it is necessary to set the weight in consideration of the data amount (sequence length) of the learning data set.

  Further, the frequency variable corresponding to the learning data set may change depending on the value of the state transition probability that has already been set based on past learning. For example, the value of a frequency variable obtained from a learning data set in which many transitions with low state transition probabilities have occurred is inevitably small, and obtained from a learning data set in which many transitions with high state transition probabilities have occurred The value of the frequency variable is inevitably large. This is because the frequency variable is expressed by an expression corresponding to the numerator in Expression (15) as described above. Therefore, it is necessary to set the weight in consideration of the value of the frequency variable.

In the present invention, the estimated value a ′ _ij (k) of the state transition probability after integration is obtained by Expression (20).

・・・（２０）

... (20)

In this case, it is necessary to consider the weight w _n, as described above. Specifically, for the frequency variable χ _ij (k) ⁽ⁿ⁾ corresponding to the learning data set Dn having the sequence length Tn, the weight w _n is set so as to satisfy the relationship shown in Expression (21).

・・・（２１）

... (21)

In this way, for each training data set, if the frequency variable χ _ij (k) ⁽ⁿ⁾ is accumulated over all data sets while adjusting the weight according to the sequence length of the training data set, The result is almost equivalent to batch learning of data. That is, the frequency variable χ _ij (k) is obtained from the equation (22), and the estimated value of the state transition probability after integration using the frequency variable χ _ij (k) as described above with reference to the equation (20). a ′ _ij (k) is obtained.

・・・（２２）

(22)

In this way, for example, all the learning data sets can be stored without storing the state transition probability table corresponding to each of the learning data sets D ₁ , D ₂ ,... D _n. The result is almost equivalent to batch learning together. That is, the state transition probability obtained by adding the frequency variable obtained by learning the learning data set D _n to the frequency variable obtained by learning up to the learning data set D _n−1 already stored. Obtain an estimate of. Thus, learning data sets D _1, D _2, it is possible to collectively · · · D _n to obtain substantially the same results as batch learning.

  On the other hand, the estimation of the observation probability in learning of the action expanded HMM is performed by the above-described equation (4). Here, a case where a plurality of data sets exist as shown in FIG. 29 is considered.

The estimated value b ′ _j (o) ⁽ⁿ⁾ of the observation probability in the n-th learning data set Dn can be obtained by Expression (23).

・・・（２３）

(23)

  Unlike the description of the estimation of the state transition probability, here, (t, t + 1εDn) is not represented by tεDn.

Further, it is assumed that the learning data set Dn includes information representing an action executed at each time, a node at each time, and an observation symbol at each time. o _t = o indicates that the observation symbol at time t is o.

  The numerator in Expression (23) can be said to represent the frequency at which the observation symbol o is observed at the node j in the learning data set Dn. On the other hand, it can be said that the denominator of Expression (23) represents the frequency of observation of any observation symbol at node j in the learning data set Dn.

Now, a variable ω _j (o) ⁽ⁿ⁾ representing an expression corresponding to the numerator in Expression (23) is defined as represented by Expression (24).

・・・（２４）

... (24)

  Expression (25) can be obtained from Expression (24).

・・・（２５）

... (25)

  Equation (26) is derived from Equation (25) and Equation (23).

・・・（２６）

... (26)

Thus, the estimated value of the observation probability can be expressed using the variable ω _j (o) ⁽ⁿ⁾ .

Here, the variable ω _j (o) ⁽ⁿ⁾ corresponds to the numerator in the equation (23), and can be said to represent the frequency at which the observation symbol o is observed at the node j in the learning data set Dn. It will be called a frequency variable for estimating the observation probability.

In the present invention, as in the case of the state transition probability, the variable ω _j (o) ⁽ⁿ⁾ described above is used in order to enable stable learning when learning in the additional learning method. Thus, the estimated value of the observation probability is obtained. That is, each time the learning device 34 performs learning based on one learning data set, the frequency variable is updated and stored in the internal model data storage unit 37 as one of the internal model data.

  When new learning is performed, the frequency variable corresponding to the past learning data set is read, and the frequency variable is updated by adding the frequency variable obtained based on the new learning to the frequency variable. To do. Furthermore, learning of the additional learning method is performed by obtaining an estimated value of the observation probability obtained based on the updated frequency variable.

Next, the integration of each internal model data obtained by multiple learning will be described. That is, the learning data sets _{D 1, D 2, ··· D} n estimates of the observation probability is calculated based on ^{_{··· b'j (o) (1}} ), b'j (o) (2), ... Integration of b ′ _j (o) ⁽ⁿ⁾ ,.

In the integration, it is necessary to consider the weight w ′ _n for the same reason as in the case of integrating the estimated values of the state transition probabilities.

In the present invention, the estimated value b ′ _j (o) of the state transition probability after integration is obtained by equation (27).

・・・（２７）

... (27)

At this time, for the frequency variable ω _j (o) ⁽ⁿ⁾ corresponding to the learning data set Dn having the sequence length Tn, the weight w ′ _n is set so as to satisfy the relationship shown in Expression (28).

・・・（２８）

... (28)

In this way, for each training data set, if the frequency variable ω _j (o) ⁽ⁿ⁾ is accumulated over all data sets while adjusting the weight according to the sequence length of the training data set, The result is almost equivalent to batch learning of data. That is, the frequency variable ω _j (o) is obtained from the equation (29), and the estimated value b of the observation probability after integration using the frequency variable ω _j (o) as described above with reference to the equation (27). ´ _j (o) is obtained.

・・・（２９）

... (29)

In this way, for example, all of the learning data sets D ₁ , D ₂ ,... D _n . It is possible to obtain almost the same result as batch learning of learning data sets. That is, by adding the frequency variable obtained by learning the learning data set D _n to the frequency variable obtained by learning up to the learning data set D _n−1 already stored, the observation probability is calculated. Get an estimate. As a result, it is possible to obtain almost the same result as batch learning of learning data sets D ₁ , D ₂ ,... D _n .

For example, the learning data sets D ₁ , D ₂ ,... D _n are batch-learned together even if the calculation results of Expression (15) or Expression (23) are stored as they are and learning by the additional learning method is performed. Nearly equivalent results cannot be obtained. This is because the calculation result of the equation (15) or the equation (23) is calculated as a probability value and is normalized so that the total value of the probabilities of possible transitions is 1. Even if the calculation result of the equation (15) or the equation (23) is stored as it is and learning by the additional learning method is performed, a result almost the same as batch learning can be obtained. For example, it is necessary to store a table corresponding to each learning data set. For this reason, in the present invention, the frequency variable obtained by the equation corresponding to the numerator in the equation (15) or the equation (23) is stored.

  If the state transition probability and the observation probability are obtained in this way, learning by the additional learning method can be performed, and better performance can be exhibited in a changing environment, and stable learning can be performed. It becomes like this.

  In order to do so, it is not necessary to store all the internal model data corresponding to each of the past learnings. For example, the storage capacity of the internal model data storage unit 37 can be reduced. Further, as a result of learning by the additional learning method, the amount of calculation when updating the internal model data can be reduced, and it becomes possible to recognize a change in the environment more quickly.

The explanation about the additional learning method so far has described the example in the case of obtaining the discrete observation signal. When acquiring continuous observation signals, reestimate the parameters of the observation probability density function b _j (o) using the signal distribution weighted by the weighting coefficient γ _t (j) when the agent is in state j at time t. do it. At this time, it is necessary to adjust so that the weight coefficient γ _t (j) satisfies the expression (30).

・・・（３０）

... (30)

In this case, γ ′ _t (j) has a meaning equivalent to the frequency.

Then, the average vector and covariance matrix of the observed signal may be estimated using γ ′ _t (j) ≡w ′ _n γ _t (j).

Normally, logarithmic concave such as Gaussian distribution or elliptical symmetrical probability density is used as a model, and the parameters of the observed probability density function b _j (o) can be re-estimated.

As a parameter of a log-concave or elliptical symmetry probability density model such as a Gaussian distribution, an average vector μ ′ j of an observation signal in a state _j and a covariance matrix U ′ _j can be used. The average vector μ ′ _j and the covariance matrix U ′ _j can be obtained by Expression (31) and Expression (32), respectively.

・・・（３１）

... (31)

・・・（３２）

... (32)

  As described above, stability at the time of learning by the additional learning method can be ensured, but in the case of the additional learning method, the internal model data is often updated by giving a larger weight to the latest learning result. This is because the new experience is considered convenient for learning about environmental changes more appropriately.

  For example, consider a case in which 100 samples of new data are given to a learning device that has completed learning of 100,000 samples to perform learning of an additional learning method. Since the amount of newly learned data (100) is small with respect to the size of already learned (100,000), if the learning is performed as it is, the influence of new learning becomes 0.1%. In such a case, it is difficult to say that learning about changes in the environment is appropriate.

  Therefore, for example, it is convenient if a learning rate that is the degree of influence of new learning can be designated. For example, in the above example, when the learning rate is specified as 0.1 (10%), the degree of influence can be increased by 100 times without changing the amount of data to be newly learned.

  In the present invention, even when the learning rate is specified as described above, the learning stability is not impaired.

As described above, the frequency variable χ _ij (k) for estimating the state transition probability is updated as shown in Expression (33). In the equation (33), ⇒ indicates that χ _ij (k) is updated as shown on the right side.

・・・（３３）

... (33)

The frequency variable ω _j (o) for estimating the observation probability is updated as shown in Expression (34). In Expression (34), ⇒ indicates that ω _j (o) is updated as shown on the right side.

・・・（３４）

... (34)

Now, when the learning rate r (0 ≦ r ≦ 1) is specified, in the present invention, in order to calculate the frequency variable for estimating the state transition probability, the weight W _n shown in the equation (35), The weights z _i (k) ⁽ⁿ⁾ are calculated. The weight W _n and the weight z _i (k) ⁽ⁿ⁾ are respectively calculated as the weight for multiplying the frequency variable obtained based on the new learning and the weight for multiplying the already stored frequency variable. The

・・・（３５）

... (35)

  Then, the frequency variable for estimating the state transition probability is calculated by Expression (36).

・・・（３６）

... (36)

Note that the weights z _i (k) ⁽ⁿ ) in Expression (35) are weights that are set in consideration that the weight W _n increases unilaterally as learning is repeated, and are not used in actual calculations. You may do it.

Further, when the learning rate r (0 ≦ r ≦ 1) is specified, the weight W ′ _n shown in the equation (37) and the weight z _i ⁽ Calculate ⁿ⁾ . The weights W ′ _n and the weights z _i ⁽ⁿ⁾ are calculated as weights for multiplying the frequency variables obtained based on the new learning and weights for multiplying the already stored frequency variables.

・・・（３７）

... (37)

  Then, the frequency variable for estimating the state transition probability is calculated by the equation (38).

・・・（３８）

... (38)

The weight z _i ⁽ⁿ ) in the equation (37) is a weight provided in consideration of the fact that the weight W ′ _n increases unilaterally as learning is repeated, and is not used in actual calculations. May be.

  The description of the additional learning method with the specified learning rate up to this point has been given of the example in the case of acquiring discrete observation signals. Similarly, when acquiring continuous observation signals, distribution parameters may be estimated after corresponding weight conversion.

  By doing so, it is possible to prevent the learning stability from being impaired even when the learning rate is specified.

By the way, the calculation of the estimated value a′ij (k) of the state transition probability using the frequency variable can be obtained by the equation (20) as described above, but actually, the denominator Σ _j χ _ij ( When k) becomes a small value, the calculation result may be disturbed. The disturbance described above impairs the reliability of the internal model data obtained by learning, affects the subsequent recognition of the environment, and causes the agent to mistakenly recognize the environment. Furthermore, since the recognition result adversely affects the learning result of the additional learning method, it is necessary to solve this problem.

Here, N _ik = Σ _j χ _ij (k). In order to solve the problem that the calculation result is disturbed when N _ik is a small value, a penalty coefficient corresponding to the smallness of N _ik with respect to the state transition probability may be multiplied. That is, the penalty coefficient is η (N _ik ), and the estimated value a′ij (k) of the state transition probability may be obtained by Expression (39).

・・・（３９）

... (39)

  Note that the function η (x) is a monotonically increasing function that satisfies the range 0 ≦ η (x) ≦ 1 with respect to the domain 0 ≦ x.

  The function η (x) is, for example, a function represented by Expression (40).

・・・（４０）

... (40)

  Α (> 0) and β in the equation (40) are parameters that are appropriately adjusted as necessary, and may be adjusted according to the designated learning rate r, for example.

  Incidentally, as described above, in the present invention, the frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability are stored as internal model data. Then, it is necessary to perform the above-described processing for imposing the one-state one-observation constraint and the action transition constraint on the frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability.

  The process of applying the split algorithm to the frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability is performed as follows.

Here, an example in which the node s _j is divided into K nodes will be described. The k-th node among the K nodes obtained as a result of dividing the node s _j is expressed as s _j ^k, and the node s _i to the node s _j after the node s _j is divided. the state transition probability of the ^k to be represented by a ^k _ij. Further, a state transition probability from the node s _j ^k to the node s _i after the node s _j is divided is represented by a ^k _ji .

The learning device 34 obtains a frequency variable ω _j (o) for estimating the observation probability corresponding to the observation probability b _j (o) for the observation symbol o by using the equation (41).

・・・（４１）

... (41)

Also, the learning unit 34, the frequency variable chi ^k _ij for estimating a state transition probability corresponding to the state transition probability a ^k _ij is corresponding to the observation probability of each observation symbol before the division of the frequency variable chi _ij before division It is set so that it is proportionally divided by the ratio of the frequency variable ω _j (o _k ) for estimating the observation probability.

Furthermore, the learning unit 34, the frequency variable chi ^k _ji for estimating a state transition probability corresponding to the state transition probability a ^k _ji is corresponding to the observation probability of each observation symbol before the division of the frequency variable chi _ji before division It is set so that it is proportionally divided by the ratio of the frequency variable ω _j (o _k ) for estimating the observation probability.

  The process of applying the forward merge algorithm to the frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability is performed as follows.

Here, an example in which L node groups s _j ^{m, l} (l = 1,..., L) are merged into one node s _j ^m will be described. Incidentally, it expressed from node s _i after being merged state transition probability to the node s _j ^m in a _ij ^m, a state transition probability from the node s _j ^m after being merged into a node s _i at a _ji ^m I will represent it. Also, a vector whose elements are the observation probabilities of the respective observation symbols after being merged is represented by b _j ^m .

The learning device 34, a frequency variable chi _ij ^m for estimating a state transition probability corresponding to the state transition probability ^{_{a ij m Σ l χ ij m}} , determined and set by ^l. Here, χ _ij ^{m, l} is a frequency variable for estimating the state transition probability corresponding to the state transition probability from the node s _i to the node s _j ^{m, l} before being merged.

Also, the learning unit 34, a frequency variable chi _ji ^m for estimating a state transition probability corresponding to the state transition probability ^{_{a ji m Σ l χ ji m}} , determined and set by ^l. Here, χ _ji ^{m, l} is a frequency variable for estimating the state transition probability corresponding to the state transition probability from the node s _j ^{m, l} to the node s _i before merging.

Further, the learning device 34, set determined by the vector b _j ^m the vector omega _j ^m to the elements, respectively Σ _l ω _j ^m of frequency variable for estimating a corresponding state transition probability to each of the ^{elements, l} To do.

  When all the merges are completed, the learning device 34 recalculates the state transition probability and the observation probability using the corrected frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability. To do.

  The process of applying the backward merge algorithm to the frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability is performed as follows.

Here, an example in which L node groups s _j ^{m, l} (l = 1,..., L) are merged into one node s _j ^m will be described. Incidentally, it expressed from node s _i after being merged state transition probability to the node s _j ^m in a _ij ^m, a state transition probability from the node s _j ^m after being merged into a node s _i at a _ji ^m I will represent it. Also, a vector whose elements are the observation probabilities of the respective observation symbols after being merged is represented by b _j ^m .

The learning device 34, a frequency variable chi _ij ^m for estimating a state transition probability corresponding to the state transition probability ^{_{a ij m Σ l χ ij m}} , determined and set by ^l. Here, χ _ij ^{m, l} is a frequency variable for estimating the state transition probability corresponding to the state transition probability from the node s _i to the node s _j ^{m, l} before being merged.

Also, the learning unit 34, a frequency variable chi _ji ^m for estimating a state transition probability corresponding to the state transition probability ^{_{a ji m Σ l χ ji m}} , determined and set by ^l. Here, χ _ji ^{m, l} is a frequency variable for estimating the state transition probability corresponding to the state transition probability from the node s _j ^{m, l} to the node s _i before merging.

Furthermore, the learning unit 34 sets found through vector b _i ^m of the vector omega _i ^m to each element of the frequency variable for estimating an observation probability corresponding to each element Σ ^_l ω _i ^m, _l .

  When all the merges are completed, the learning device 34 recalculates the state transition probability and the observation probability using the corrected frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability. To do.

  By doing so, the above-described one-state one-observation constraint and action transition constraint are imposed on the frequency variable for estimating the state transition probability and the frequency variable for estimating the observation probability. Become.

  Up to this point, the technology for enabling stable learning in the additional learning method in the action expanded HMM that is necessarily large in scale has been described.

In the above, the example of the action extended HMM having the three-dimensional state transition probability table and the two-dimensional observation probability table as described above with reference to FIG. 8 has been described. Normally, if the number of nodes is N, the number of observation symbols is M, and the number of actions is K, the number of parameters to be calculated is N ² K + NM, and learning is performed on the assumption that the values of N, M, and K are constant. An algorithm is defined.

  However, it may be necessary to change the values of N, M, and K as learning proceeds. For example, when new parts are added to the maze where the robot moves, the number of observation symbols increases, so the value of M needs to be increased.

  Next, a description will be given of actions that can be taken when it is necessary to change the number of nodes, the number of observation symbols, or the number of actions when learning is advanced.

  FIG. 30 is a diagram for explaining the influence of an increase in the number of types of observation symbols. As shown in the figure, when the number of observation symbols increases, the row direction (horizontal direction in the drawing) of the observation probability table is expanded. That is, it is necessary to newly set an observation probability value corresponding to the region 121. In the observation probability table, there is a restriction that the total observation probability value per row of the table is 1.0.

  Further, as shown in FIG. 30, since the observation probability table is expanded in the row direction (horizontal direction in the figure), it is necessary to expand the frequency variable table for estimating the observation probability. That is, it is necessary to newly set a frequency variable value corresponding to the region 122.

  In the present invention, when it is necessary to expand the observation probability table as shown in FIG. 30, the learning device 34 performs the following processing. Here, for example, the processing of the learning device 34 when instructing the robot to expand the observation probability table as shown in FIG. 30 on the premise that the number of types of observation symbols is increased in advance by a predetermined number. explain.

Now, the index corresponding to the new observation symbol o _{M + i} is M + i, and the M + i-th column is added to the observation probability table.

  The learning device 34 sets the observation probability value to be set in the M + i-th column of the observation probability table as a non-zero element having an appropriate size. The value of this non-zero element is determined as follows.

  As shown in Equation (42), the number of observation symbols before adding a new observation symbol is M, and all observation probability values to be set in the M + i column are 1 / M.

・・・（４２）

... (42)

Alternatively, as shown in Expression (43), for each row of the observation probability table, the number of observation symbols for which the observation probability bj (•) is equal to or greater than the threshold is counted, and the number M _j is used as the number n _j. Find the observation probability value to be set in column i. Note that bj (•) represents the observation probability of each observation symbol that is equal to or greater than the threshold.

・・・（４３）

... (43)

  As shown in the equation (42) or the equation (43), the learning device 34 sets a non-zero element having an appropriate size in the M + i column of the observation probability table, and then the observation probability per row of the table. Adjust so that the sum of the values is 1.0. That is, as shown in Expression (44), each non-zero observation probability bj (•) in the observation probability table is updated. This completes the expansion of the observation probability table.

・・・（４４）

... (44)

  Further, the learning device 34 sets all observation probability values to be set to the M + i column of the frequency variable table for estimating the observation probability to 0 (zero). This completes the expansion of the frequency variable table for estimating the observation probability.

  Then, the learning device 34 performs learning by the additional learning method for the learning data set including the new observation symbol under the designation of a predetermined learning rate, and updates the internal model data. Thereby, the frequency variable for estimating the state transition probability, the frequency variable for estimating the observation probability, and each value of the observation probability table and the state transition probability table are updated.

  By doing in this way, even when a new observation symbol is observed during learning by the additional learning method, the internal model data can be appropriately updated.

  For example, when a predetermined observation symbol becomes unnecessary during learning, the observation probability table can be reduced in the column direction.

In this case, the learning device 34 deletes the k-th column from the observation probability table so that the observation probability b _j (k) at the node s _j does not exist, where k is an index corresponding to the observation symbol that is not required. To do.

Similarly, the learning device 34 deletes the k-th column from the frequency variable table for estimating the observation probability so that ω _j (k) does not exist.

  Further, the learning device 34 recalculates each value in the reduced observation probability table using the frequency variable for estimating the observation probability.

  Then, the learning device 34 performs learning in the additional learning method for the learning data set after the predetermined observation symbol is no longer necessary, under the designation of the predetermined learning rate, and updates the internal model data. Thereby, the frequency variable for estimating the state transition probability, the frequency variable for estimating the observation probability, and each value of the observation probability table and the state transition probability table are updated.

  Also, for example, when the maze where the robot moves is extended in a predetermined direction, the number of nodes increases, so the value of the number of nodes N needs to be increased.

  FIG. 31 is a diagram for explaining the influence of an increase in the number of nodes. As shown in the figure, when the number of nodes increases, the matrix direction of the state transition probability table is expanded. That is, it is necessary to newly set a state transition probability value corresponding to the inverted L-shaped region 131-1 in the first state transition probability table of FIG. Similarly, it is necessary to newly set the value of the state transition probability corresponding to the inverted L-shaped region 131-2, region 131-3,... Of the state transition probability table corresponding to each action. That is, it is necessary to newly set a value of the state transition probability by extending the state transition probability table with K actions. In the state transition probability table, there is a restriction that the total of observation probability values per row of the table is 1.0.

  Further, when the number of nodes increases, the observation probability table expands in the column direction (vertical direction in the figure). That is, it is necessary to newly set an observation probability value corresponding to the region 134. In the observation probability table, there is a restriction that the total observation probability value per row of the table is 1.0.

  Furthermore, although not shown in the figure, the frequency variable table for estimating state transition probabilities and the frequency variable table for estimating observation probabilities must be expanded in the same way to set new values. There is.

  In the present invention, when it is necessary to expand the state transition probability table and the observation probability table as shown in FIG. 31, the learning device 34 performs the following processing. Here, for example, a learning device for instructing the robot to extend the state transition probability table and the observation probability table as shown in FIG. The process 34 will be described.

Assume that the index corresponding to the new node s _{N + i} is _{N + i} , and the N + i-th row and the N + i-th column are added to the state transition probability table.

  The learning device 34 sets the state transition probability values to be set in the (N + i) th row and the (N + i) th column of the state transition probability table as small random elements.

  Similarly, the learning device 34 adds the (N + i) th row and the (N + i) th column to the frequency variable table for estimating the state transition probability, and sets the state transition probability value to be set to a minute value. Use random elements.

The learning device 34 identifies an action c _k that has been executed at the node s _{N + i} . Then, the learning device 34 sets each of the state transition probability values of the row corresponding to the node s _{N + i} of the k-th state transition probability table corresponding to the action _ck to a uniform value. However, in consideration of the actual transition result when the action _{ck is} executed, the transition probability to the transition destination state with experience may be slightly increased.

Further, as a result of executing the action c _k , the transition source node s _j that has made a transition to the node s _{N + i} is specified. Then, the learning device 34 sets each of the state transition probability values of the row corresponding to the node s _j in the kth state transition probability table corresponding to the action _ck as follows.

In the row, counting the number of transition destination node s _l where state transition probability is equal to or greater than a threshold, for the number and L. The state transition probability a _{iN + i} (k) from the node s _j to the node s _{N + i} in the k-th state transition probability table is set to 1 / L.

The learning device 34 adjusts the total state transition probability value per row of the table to be 1.0. That is, as shown in Expression (45), each state transition probability a _j (k) in the state transition probability table is updated. Thereby, the expansion of the state transition probability table is completed.

・・・（４５）

... (45)

  Further, the learning device 34 sets all the state transition probability values to be set in the additional region of the frequency variable table for estimating the state transition probability to 0 (zero). This completes the expansion of the frequency variable table for estimating the state transition probability.

The learning device 34 sets the observation probability values to be set in the (N + i) th row and the (N + i) th column of the observation probability table as non-zero elements having appropriate sizes. The value of the non-zero element is, for example, a uniform value such as 1 / N, but the observation probability of an observation symbol that has actually been observed at the node s _{N + i} may be increased. Good.

Further, the learning device 34 sets all N + i rows corresponding to the added node s _{N + i} in the frequency variable table for estimating the observation probability to 0 (zero). This completes the expansion of the frequency variable table for estimating the observation probability.

  Then, the learning device 34 performs learning by the additional learning method for the learning data set including the new node under the designation of a predetermined learning rate, and updates the internal model data. Thereby, the frequency variable for estimating the state transition probability, the frequency variable for estimating the observation probability, and each value of the observation probability table and the state transition probability table are updated.

  Alternatively, for example, when the robot is modified so that the movable direction on the maze is expanded, the number of actions increases, so the value of the action number K needs to be increased.

  FIG. 32 is a diagram for explaining the influence due to the increase in the number of actions. As shown in the figure, when the number of actions increases, the state transition probability table expands in the depth direction. That is, for example, it is a state transition probability table corresponding to a newly added action, and it is necessary to newly set the value of the state transition probability in the third state transition probability table 141 in FIG.

  Although not shown in the figure, the frequency variable table for estimating the state transition probability needs to be similarly expanded to set a new value.

  In the present invention, when it is necessary to expand the state transition probability table as shown in FIG. 32, the learning device 34 performs the following processing. Here, for example, the processing of the learning device 34 in the case of instructing the robot to expand the state transition probability table as shown in FIG. .

Assume that an index corresponding to a new action c _{K + i} is K + i, and a K + i-th state transition probability table is added.

  The learning device 34 sets all state transition probabilities in the added K + i-th state transition probability table to 0.

  Similarly, the learning device 34 adds a K + i-th table to the frequency variable table for estimating the state transition probability, and adds the K + i-th state transition probability table. All state transition probabilities are set to zero. This completes the expansion of the frequency variable table for estimating the state transition probability.

Further, the learning device 34 identifies a node s _j that has executed a new action c _{K + i} . Then, the learning device 34 sets all the state transition probability values of the row corresponding to the node s _j in the (K + i) th state transition probability table to a uniform value. However, in consideration of the transition result when the actual action c _{K + i is} executed, the state transition probability to the transition destination node with experience may be slightly increased. Thereby, the expansion of the state transition probability table is completed.

  Then, the learning device 34 performs learning by the additional learning method for the learning data set including execution of a new action under the designation of a predetermined learning rate, and updates the internal model data. Thereby, the frequency variable for estimating the state transition probability, the frequency variable for estimating the observation probability, and each value of the observation probability table and the state transition probability table are updated.

  With the processing described above, it is possible to continue learning even when it is necessary to add the number of nodes, the number of observation symbols, and the number of actions as learning proceeds. The above-described processing is an example in the case where each table is expanded as shown in FIGS. 30 to 32 on the premise that the number of types of observation symbols is increased in advance by a predetermined number for the robot.

  However, for example, it may not be possible to know in advance that the number of observation symbols, nodes, or actions increases by a predetermined number. That is, when a change in the environment is sequentially recognized by the autonomous behavior of the agent, for example, the robot administrator cannot know in advance how many observation symbols, nodes, or actions increase. Therefore, for example, if a new maze part appears arbitrarily, a new maze is expanded, or a moving direction is newly added while the robot is moving in the maze, further consideration is required. .

  Next, for example, expansion of the state transition probability table and the observation probability table when a new maze part appears or a new maze is expanded while the robot is moving in the maze will be described. That is, an example in which the agent autonomously recognizes a change in the environment and expands the state transition probability table and the observation probability table will be described.

  When an agent autonomously recognizes an environmental change and expands the state transition probability table and the observation probability table, it is necessary for the agent itself to recognize whether or not the environment has been newly expanded. That is, the agent must be able to recognize whether the node at which he is currently located is a learned internal state or a node to be newly added. For example, when a robot is moving through a maze and the maze is newly expanded, when moving the expanded part, it is possible to recognize that it is located at a node to be newly added. Without it, it will not be able to recognize environmental changes autonomously.

  Here, a node recognition method in the autonomous behavior learning apparatus 10 will be described. Node recognition is performed by the recognizer 35 of FIG. Although details will be described later, in consideration of the fact that there is an upper limit to the length value of the time-series information and the change in the entropy value of the recognized current state probability, four methods are finally used. I will explain.

  As described above, the recognizer 35 is based on the information stored in the observation buffer 33 and the behavior output buffer 39 and the state transition probability table and the observation probability table stored in the internal model data storage unit 37. The node where the robot is located is recognized.

Further, as described above, the observation symbols o _t , o _{t + 1} , o _{t + 2} corresponding to the observation signals acquired at the times _t , _{t + 1} , _{t + 2} ,. O and _T are stored in the observation buffer 33 as observation symbols at each time. Similarly, for example, the actions c _t , c _{t + 1} , c _{t + 2} ,..., C _T executed at the times _t , _{t + 1} , _{t + 2} ,. The action is stored in the action output buffer 39 as an action.

  Here, the information input to the recognizer 35 and stored in the observation buffer 33 and the action output buffer 39 is referred to as time-series information, and the length of the time-series information is represented by a variable N. To.

  The recognition result output from the recognizer 35 is stored in the recognition result buffer 38 in association with the time when the recognition result is output.

  The recognizer 35 first sets the length N of the time series information, acquires the time series information of the length N from the observation buffer 33 and the behavior output buffer 39, and is stored in the internal model data storage unit 37. Recognition is performed based on the transition probability table and the observation probability table.

The recognizer 35 outputs a node sequence corresponding to the length N using, for example, the Viterbi algorithm. For example, when N = 3, the recognizer 35 outputs node sequences s ₁ , s ₂ , and s ₃ as recognition results. In this case, the recognizer 35 has the robot located at the node s ₁ at time t ₁ , the robot is located at the node s ₂ at time t ₂ , and the robot is located at the node s ₃ at time t ₃ . It will be recognized that it was.

  In the process of outputting the node sequence corresponding to the length N using the Viterbi algorithm, the node sequence is estimated based on the state transition probability table and the observation probability table stored in the internal model data storage unit 37. Is output. When a node sequence corresponding to the length N is output using the Viterbi algorithm, it is possible to output a plurality of node sequences including a node sequence having the most probable probability. Here, it is assumed that a node sequence having the most probable probability obtained using the Viterbi algorithm is output.

  The recognizer 35 further determines whether or not the node where the robot is currently located should be newly added, so that the node sequence output using the Viterbi algorithm is a node sequence that is actually possible. It is determined whether or not there is.

  The determination as to whether or not the output node string is a possible node string is performed as follows, for example.

  Now, the output node sequence (node sequence of length T) is represented by X, and the sequence of observation symbols specified based on the time series information (sequence of observation symbols of length T) is represented by observation sequence O. I will decide. In addition, the state transition probability table of the internal model data is represented by a matrix A. The matrix A means a state transition probability table corresponding to each action specified based on the time series information.

  The recognizer 35 determines whether or not the node sequence X and the observation sequence O satisfy Expression (46) and Expression (47).

・・・（４６）

... (46)

・・・（４７）

... (47)

Here, P (O | X) means the observation probability of each observation symbol constituting the observation series O in each node constituting the node sequence X, and can be specified based on the observation probability table. Also, Thres _trans and Thres _obs represent a threshold value indicating whether there is a transition and a threshold value indicating whether there is an observation.

  Accordingly, when it is determined that the node sequence X and the observation sequence O do not satisfy any one of the formulas (46) and (47), the recognizer 35 determines that the output node sequence is a node that can actually exist. It is determined that it is not a column. As a result, the node where the current robot is located (the node at the last time in the time-series information) can be newly added and recognized as an unknown node.

  When it is determined that the node sequence X and the observation sequence O satisfy Expression (46) and Expression (47), the recognizer 35 calculates the entropy of the current state transition probability.

  Here, the entropy is E, the posterior probability of the node Xi is P (Xi | O), and the total number of nodes existing on the current internal model data is represented by M. The posterior probability of a node (state) is a probability output by the Viterbi algorithm, and means a probability corresponding to the node at the last time of the time series information. In this case, entropy E can be expressed by equation (48).

・・・（４８）

... (48)

  For example, when the entropy value calculated by the equation (48) is compared with a predetermined threshold value and is less than the threshold value, the recognizer 35 determines that the output node sequence is a node sequence that is actually possible and It means that the situation can be identified. As a result, the node where the current robot is located (the node at the last time of the time series information) is a node that already exists in the internal model data and is recognized as a known node (learned internal state). You can make it.

  Furthermore, it is determined whether or not the number of unique nodes included in the output node sequence is equal to or greater than the threshold Thres. Only when the number is equal to or greater than Thres, the node at the last time in the time series information is a known node. May be recognized. That is, it is a threshold for guaranteeing the accuracy of recognition, and a threshold for the number of unique nodes in the recognized node string is provided. Here, the number of unique nodes means the number of nodes when only nodes having different indexes are counted.

  For example, when the index of the output node sequence is “10”, “11”, “10”, “11”, “12”, “13”, the length of the node sequence is 6, but it is unique The number of nodes is four. For example, when the agent repeats the transition between the same nodes, even if the recognition is performed based on the time-series information having the same length, the accuracy of the recognition result is low. For this reason, a threshold value for assuring the accuracy of recognition, and a threshold value for the number of unique nodes in the recognized node sequence may be provided.

  On the other hand, if the entropy value is greater than or equal to the threshold value, the output node sequence is a node sequence that can actually exist. For example, there are a plurality of candidates that cannot be uniquely identified. Means. For this reason, the recognizer 35 determines that the output node sequence should increase the length of the time-series information. Thereby, for example, the value of the length N of the time series information is incremented, and the process is repeatedly executed.

  Next, node recognition processing by the recognizer 35 will be described with reference to the flowchart of FIG. This process is an example of a first method of the node recognition process by the recognizer 35.

  In step S201, the recognizing device 35 sets the value of the variable N to 1 which is an initial value.

  In step S <b> 202, the recognizer 35 acquires time-series information of length N from the observation buffer 33 and the behavior output buffer 39.

  In step S203, the recognizer 35 outputs a node sequence using the Viterbi algorithm based on the time series information output in step S202.

  In step S204, the recognizing device 35 determines whether or not the node sequence output as a result of the processing in step S203 is a node sequence that can actually exist. At this time, as described above, it is determined whether or not the node sequence X and the observation sequence O satisfy Expression (46) and Expression (47). When the node sequence X and the observation sequence O satisfy the equations (46) and (47), it is determined in step S204 that the node sequence is a possible node sequence. On the other hand, when the node sequence X and the observation sequence O do not satisfy at least one of the equation (46) or the equation (47), it is determined in step S204 that the node sequence is not actually possible.

  If it is determined in step S204 that the node sequence is not actually possible, the process proceeds to step S208, and the recognizer 35 recognizes that the node at the last time of the time series information is an unknown node. The recognition result in step S208 is stored in the recognition result buffer 38 in association with the last time of the time series information.

  On the other hand, if it is determined in step S204 that the node sequence is actually possible, the process proceeds to step S205.

  In step S205, the recognizer 35 calculates entropy. At this time, as described above, the entropy is calculated by the equation (48).

  In step S206, the recognizer 35 compares the entropy value calculated in the process of step S205 with a predetermined threshold value, and determines whether the entropy value is equal to or greater than the threshold value.

  If it is determined in step S206 that the entropy value is greater than or equal to the threshold, the process proceeds to step S209.

  In step S209, the recognizer 35 increments the value of the variable N by 1. As a result, time-series information having a length of N + 1 is acquired in the process of step S202 executed thereafter. Note that each time the value of the variable N is incremented in step S209, the time series information acquired in step S202 is extended in the past direction.

  Thus, until it is determined in step S204 that the node sequence is not actually possible, or in step S206, it is determined that the entropy value is not greater than or equal to the threshold value, step S202 to step S206 and step S209 are performed. This process is repeatedly executed.

  If it is determined in step S206 that the entropy value is not equal to or greater than the threshold value, the process proceeds to step S207.

  In step S204, it is further determined whether or not the number of unique nodes included in the output node string is equal to or greater than the threshold value Thres. Only when the number is equal to or greater than Thres, the process proceeds to step S205 or step S208. Also good.

  Alternatively, the process proceeds to step S204 only when a node string in which the number of unique nodes is equal to or greater than the threshold value Thres is output in step S203. If the number of unique nodes is less than the threshold value Thres, the value of N is incremented. The time series information may be acquired again.

  In step S207, the recognizer 35 recognizes that the node at the last time of the time series information is a known node. At this time, the index of the node at the last time of the time series information may be output. Further, the recognition result in step S207 is stored in the recognition result buffer 38 in association with the last time of the time series information.

  In this way, the node recognition process is executed.

  By the way, in the process of FIG. 33, every time the value of the variable N is incremented, it has been described that the acquired time series information is extended in the past direction, but a transition from a known node to an unknown node has occurred. Time series information cannot be extended before the time. This is because an accurate recognition result cannot be obtained based on a node string including an unknown node that has transitioned from a known node.

  Therefore, the node sequence corresponding to the time-series information cannot include an unknown node that has transitioned from the known node, and the value of the length N of the time-series information has an upper limit. Whether or not the node is an unknown node that has transitioned from a known node can be determined based on information stored in the recognition result buffer 38.

  Next, an example of the node recognition process when considering that there is an upper limit in the value of the length N of the time series information will be described with reference to the flowchart of FIG. This process is an example of a second method of the node recognition process by the recognizer 35.

  Since the processing from step S221 to step S229 is the same as the processing from step S201 to step S209 in FIG. 33, detailed description thereof is omitted.

  In the case of the example of FIG. 34, when the value of the variable N is incremented by 1 in the process of step S229, it is determined in step S230 whether or not an unknown node transitioned from a known node is included in the node sequence. The That is, every time the value of the variable N is incremented, the acquired time series information is extended in the past direction, but if the node sequence is extended in the past direction, an unknown node that has transitioned from a known node is included. It is determined whether or not. That is, the time series information cannot be extended before the time when the transition from the known node to the unknown node occurs.

  If it is determined in step S230 that an unknown node that has changed from a known node is included, the process proceeds to step S231. If it is determined in step S230 that an unknown node that has changed from a known node is not included, the process returns to step S222.

  In step S231, the recognizer 35 holds the recognition result and commands to extend the time series information in the future direction. That is, a message or the like for instructing further execution of action to accumulate time-series information is output. At this time, the recognizer 35 outputs control information to the action generator 36 so as to further execute an action, for example.

  That is, it is impossible to recognize the node at the present time, or even if it is possible, an uncertain recognition result is obtained. Therefore, the recognizer 35 holds the recognition result and further accumulates time-series information. The command is output as follows.

  The recognition process may be executed as shown in FIG.

  By the way, in the processing described above with reference to FIGS. 33 and 34, whether or not the node sequence X and the observation sequence O are actually possible node sequences depends on whether the equation (46) and the equation (47) are satisfied. It was explained that However, it is also possible to determine whether or not the node sequence is actually possible based on the recognized change in the entropy value of the current state probability.

That is, the entropy calculated by the formula (48) based on the time series information of length _N is set to E _N, and the entropy calculated by the formula (48) based on the time series information of length N−1 is set to E _{N. −1} and ΔE = E _N −E _N−1 are calculated. Then, △ E is compared with a predetermined threshold Thres _ent, compares the number of repetitions of the comparison process with the threshold Thres _stable, may be a node is recognized based on their comparison results.

For example, △ E <is not satisfied Thres _ent, the time series information so as to be extended in the past direction, and it is further judged whether satisfy entropy is calculated △ E <Thres _ent. △ E <if they meet Thres _ent, the counter NC is counted up, NC> when satisfying Thres _stable, so that the recognition of the node is performed.

  Next, an example of node recognition processing in the case of performing recognition based on a change in entropy value of the state probability will be described with reference to the flowchart in FIG. This process is an example of a third method of the node recognition process by the recognizer 35.

  In step S251, the recognizer 35 sets the value of the variable N to 1 which is an initial value.

  In step S <b> 252, the recognizer 35 acquires time-series information of length N from the observation buffer 33 and the action output buffer 39.

  In step S253, the recognizing device 35 outputs a node sequence using the Viterbi algorithm based on the time series information output in step S202.

In step S254, the recognizer 35 calculates an entropy difference. At this time, as described above, the entropy calculated by the equation (48) based on the time-series information of length _N is E _N, and is calculated by the equation (48) based on the time-series information of length N−1. _Let E _N-1 be the entropy to be calculated, and ΔE = E _N −E _N−1 is calculated. Note that the calculation in step S254 is executed when the value of N becomes 2 or more.

In step S255, the recognizing device 35 determines whether or not the entropy difference calculated in step S254 is equal to or greater than a threshold value Thre _ent . If it is determined in step S255 that the entropy difference calculated in step S254 is not equal to or greater than the threshold, the process proceeds to step S256.

  In step S256, the recognizing device 35 increments the value of the counter NC by 1.

In step S257, the recognizing device 35 determines whether or not the value of the counter NC is equal to or greater than a threshold value Thres _stable . If it is determined in step S257 that the value of the counter NC is equal to or greater than the threshold value Thres _stable , the process proceeds to step S258.

  In step S258, the recognizing device 35 determines whether or not the node sequence output as a result of the processing in step S253 is a node sequence that can actually exist. At this time, as described above, it is determined whether or not the node sequence X and the observation sequence O satisfy Expression (46) and Expression (47). When the node sequence X and the observation sequence O satisfy the equations (46) and (47), it is determined in step S258 that the node sequence is a possible node sequence. On the other hand, when the node sequence X and the observation sequence O do not satisfy at least one of the formula (46) or the formula (47), it is determined in step S258 that the node sequence is not actually possible.

  If it is determined in step S258 that the output node sequence is not a possible node sequence, the process proceeds to step S262, and the recognizer 35 determines that the node at the last time of the time series information is an unknown node. Recognize that The recognition result in step S262 is stored in the recognition result buffer 38 in association with the last time of the time series information.

  On the other hand, if it is determined in step S258 that the output node string is a possible node string, the process proceeds to step S259.

  In step S259, the recognizer 35 calculates entropy. At this time, as described above, the entropy is calculated by the equation (48).

  In step S260, the recognizing device 35 compares the entropy value calculated in the process of step S259 with a predetermined threshold value, and determines whether or not the entropy value is equal to or greater than the threshold value.

  If it is determined in step S260 that the entropy value is greater than or equal to the threshold, the process proceeds to step S263.

  In step S263, the recognizing device 35 holds the recognition result and commands to extend the time series information in the future direction. That is, a message or the like for instructing further execution of action to accumulate time-series information is output. At this time, the recognizer 35 outputs control information to the action generator 36 so as to further execute an action, for example.

  That is, it is impossible to recognize the node at the present time, or even if it is possible, an uncertain recognition result is obtained. Therefore, the recognizer 35 holds the recognition result and further accumulates time-series information. The command is output as follows.

  On the other hand, if it is determined in step S260 that the entropy value is not equal to or greater than the threshold, the process proceeds to step S261, and the recognizer 35 recognizes that the node at the last time of the time series information is a known node. To do.

  The recognition result in step S261 is stored in the recognition result buffer 38 in association with the last time of the time series information.

  In step S258, it is further determined whether or not the number of unique nodes included in the output node string is equal to or greater than the threshold value Thres. Only when the number is equal to or greater than Thres, the process proceeds to step S259 or step S262. Also good. In this case, if it is determined in step S258 that the number of unique nodes included in the output node string is not equal to or greater than the threshold value Thres, the process may proceed to step S265. That is, the value of the variable N may be incremented by 1.

Further, in step S255, the difference between the entropy calculated in step S254, if it is determined that the threshold Thres _ent above, the processing proceeds to step S264, the value of the counter NC is set to 0.

After the process of step S264, or when it is determined in step S257 that the value of the counter NC is not greater than or equal to the threshold value Thres _stable , the process proceeds to step S265.

  In step S265, the recognizer 35 increments the value of the variable N by 1. As a result, time-series information having a length of N + 1 is acquired in the process of step S202 executed thereafter. Note that each time the value of the variable N is incremented in step S265, the time series information acquired in step S252 is extended in the past direction.

Thus, the difference between the entropy at step S255, it is determined not to be a threshold Thres _ent or more, and, in step S257 until the value of the counter NC is determined to be the threshold Thres _stable above, steps S252 to step S257, And the process of step S265 is repeatedly executed.

  In this way, the node recognition process is executed. In the case of the example of FIG. 35, it is confirmed that the entropy value has converged by the processing of step S255 and step S257, and then it is determined whether the output node sequence is a possible node sequence. did. Therefore, for example, more reliable recognition can be performed as compared with the case described above with reference to FIG.

  Also in the case of the processing of FIG. 35, the time series information cannot be extended before the time when the transition from the known node to the unknown node occurs. This is because an accurate recognition result cannot be obtained based on a node string including an unknown node that has transitioned from a known node. .

  Therefore, the node sequence corresponding to the time series information cannot include a node recognized as an unknown node transitioned from a known node, and the value of the length N of the time series information has an upper limit. There will be. Whether or not the node is an unknown node that has transitioned from a known node can be determined based on information stored in the recognition result buffer 38.

  Next, referring to the flowchart of FIG. 36, when performing recognition based on a change in the value of entropy of the state probability, node recognition processing when considering that there is an upper limit in the value of the length N of the time series information An example will be described. This process is an example of a fourth method of the node recognition process performed by the recognizer 35.

  Since the processing from step S281 to step S295 is the same as the processing from step S251 to step S265 in FIG. 35, detailed description thereof is omitted.

  In the case of the example of FIG. 36, when the value of the variable N is incremented by 1 in the process of step S295, it is determined in step S296 whether or not an unknown node transitioned from a known node is included in the node sequence. The That is, every time the value of the variable N is incremented, the acquired time series information is extended in the past direction, but if the node sequence is extended in the past direction, an unknown node that has transitioned from a known node is included. It is determined whether or not.

  If it is determined in step S296 that an unknown node that has changed from a known node is included, the process proceeds to step S293. If it is determined in step S296 that an unknown node that has changed from a known node is not included, the process returns to step S282.

  In step S293, the recognizing device 35 holds the recognition result and commands to extend the time series information in the future direction. That is, a message or the like for instructing further execution of action to accumulate time-series information is output. At this time, the recognizer 35 outputs control information to the action generator 36 so as to further execute an action, for example.

  That is, it is impossible to recognize the node at the current time, or even if it is possible, the recognition result is uncertain. Therefore, the recognizer 35 holds the recognition result and further accumulates time-series information. The command is output as follows.

  The recognition process may be executed as shown in FIG.

  With the four methods described above with reference to FIGS. 33 to 36, the robot is located on a part of the maze that has been newly added (an unknown node) or has existed before. You can recognize whether you are on the top (known node). The state transition probability and the observation probability regarding the unknown node recognized in this way are set, and the state transition probability table and the observation probability table are expanded.

  Here, an example in which recognition is performed by the action expansion type HMM has been described, but the recognition processing of FIGS. 33 to 36 can also be applied to recognition of a normal HMM.

  By the way, when an agent autonomously recognizes an environmental change and expands the state transition probability table and the observation probability table, how many unknown nodes are newly added to the state transition probability table and the observation probability table. It becomes a problem whether to include it. Next, the number of unknown nodes to be added and the timing to add will be described when autonomously recognizing environmental changes and adding unknown nodes to internal model data.

  The addition of unknown nodes to the internal model data referred to here generates a new index representing a node regarded as an unknown node, for example, adds a matrix corresponding to the index to a state transition probability table or the like. Means that.

  Let N be the time that has elapsed since the time when it was recognized that it was located at a node (an unknown node) to be newly added by the method described above with reference to FIGS. This time N can be rephrased as the length of time-series information. Here, a threshold value for guaranteeing the accuracy of recognition, and a threshold value Thres for the number of unique nodes in the recognized node sequence is provided.

  First, the agent repeats the action until the number of unique nodes included in the time-series information of length N reaches the value of Thres. That is, the action generator 36 and the action output unit 32 execute N actions, and time-series information of length N is accumulated in the observation buffer 33 and the action output buffer 39. The time-series information of length N here means time-series information of time length N after the time when it is recognized that it is located at an unknown node. Also, in the following, “Lr becomes the value of Thres” in the sense that “the number of unique nodes included in the node string of length Lr recognized based on the time-series information of length N becomes the value of Thres”. ".

  When Lr becomes equal to or greater than Thres, the recognizer 35 executes the recognition process described above with reference to FIG. 34 or FIG. 36 based on the time series information. In this case, there is an upper limit N of the length of the time series information.

  In the recognition process executed here, the node sequence output in step S223 of FIG. 34 or step S283 of FIG. 36 is S, and the length of the node sequence is Lr.

  When the node is recognized as an unknown node in step S228 of FIG. 34 or step S292 of FIG. 36, the node is regarded as an unknown node and is added to the internal model data by the learning device 34.

  Assuming that the number of nodes added after actually becoming unknown is m_add, the number of unknown nodes to be added can be expressed by Expression (49).

・・・（４９）

... (49)

  Note that m_add is a number representing the number of added nodes when an unknown node has already been added since it was first recognized that it was located at an unknown node. That is, the expression (49) is a node between the first node and the unknown node after the number of nodes added as the unknown node is subtracted after being recognized as being located at the unknown node. Indicates that

  Further, “1” added on the right side of the equation (49) is reserved because it is not determined at this time which node is connected to the node corresponding to the oldest time in the node string of length Lr. It shows that.

  This will be described in more detail with reference to FIG. In FIG. 37, a time axis t is provided in the vertical direction in the figure, and the nodes to which the agent has changed over time are indicated by circles in the figure. Also, in the figure, a dotted line in the vertical direction in the drawing is for indicating a node that is first recognized as being located at an unknown node. In this example, the node 201 is the node that is first recognized as being located at an unknown node.

  Furthermore, for the sake of simplicity, it is assumed that the number of nodes indicated by circles in the figure and the length of the time series information increase by 1 when the action is executed once, and these nodes have no particular explanation. It is assumed that all are recognized as unique nodes.

  As shown in the figure, after first recognizing that it is located at an unknown node, actions are executed one by one and time series information is accumulated. Then, after the length N of the time series information becomes equal to the threshold value Thres (in this case, Lr = N), the recognizer 35 is described above with reference to FIG. 34 or FIG. 36 based on the time series information. Perform recognition processing. In the case of this example, it is assumed that the node sequence of node 201, node 202,..., Node 211 is output, and that node 211 is recognized as an unknown node.

  Thereafter, another action is executed, and the agent transitions to the node 212. At this time, it is assumed that recognition processing based on the time series information of length Lr corresponding to the nodes 202 to 212 is executed, and the node 212 is recognized as an unknown node. At this point, unknown nodes are not yet added.

  Thereafter, another action is executed, and the agent transitions to the node 213. At this time, it is assumed that recognition processing based on the time series information of length Lr corresponding to the nodes 203 to 213 is executed, and the node 213 is recognized as an unknown node. At this point, the node 201 is added.

  As a result, in the subsequent recognition processing, the node 201 is handled as a known node.

  In this case, the length of the time-series information (the time length after the time when it is recognized that it is located at an unknown node) N is Thres + 2. In this case, the nodes 203 to 213 correspond to the node string S, and the length Lr of the node string S is Thres. Therefore, from the equation (49), the number m of nodes to be added is calculated as Thres + 2− (Thres + 0 + 1) = 1. Therefore, one node 201 that was an unknown node is newly added.

  That is, a new index matrix representing the node 201 is added to the state transition probability table of the internal model data.

  In the example described above, the nodes 211 to 213 are all recognized as unknown nodes, but it is unknown whether the node 201 is truly unknown. For example, the node 211 is determined to be an unknown node because it is determined that the node sequence of the nodes 201 to 211 is not a possible node sequence, and the node 211 is not necessarily included in the existing internal model data. This is because it is not always a node that does not exist. That is, if any of the nodes 201 to 211 does not exist in the existing internal model data, the node 211 is recognized as an unknown node.

  Therefore, even if the node 201 is regarded as an unknown node at the present time and a new index matrix representing the node 201 is added to the state transition probability table of the internal model data, etc., a result that actually overlaps with the existing index matrix Can also be. Thus, it is unknown whether or not the node 201 is an unknown node in the true sense.

  Here, for the convenience of description with reference to FIG. 37, it is described that it is unknown whether or not the node 201 is an unknown node in the true sense. However, in the example of FIG. 37, the node 201 has the true meaning. It is assumed that it was an unknown node. Therefore, the explanation that is originally added afterwards is “it is unknown whether or not the nodes 202, 203,... Were truly unknown nodes”.

  As described above, even if it is unclear whether or not the node 201 is a truly unknown node, the new index representing the node 201 is created with excessive concern about the possibility of overlapping with the existing index matrix. There is a problem if not added to the internal model data. This is because, depending on the situation of the agent, learning will not be completed forever.

  For example, if the environment maze is expanded to create a new maze room, and the agent robot is trapped in the new maze room, you can be confident that the added node was truly an unknown node. Even without it, you still have to add it.

  For this reason, it is necessary to add a predetermined number of nodes to the internal model data at a timing after the elapse of a predetermined time from when the node is first recognized as being located at an unknown node.

  Returning to FIG. After the node 201 is added to the internal model data, further actions are executed, and recognition processing is executed based on the time series information. When the recognition process based on the time series information corresponding to the nodes 212 to 221 is executed, if the nodes 221 are recognized as known nodes, the nodes 212 to 221 are all known nodes. . At this time, the node 211 is added and anchoring from the node 211 to the node 212 is performed. Anchoring is a process of setting a state transition probability between an unknown node and a known node when a transition from an unknown node to a known node is recognized. Details of anchoring will be described later.

  By the way, in the recognition processing described above with reference to FIG. 34 or FIG. 36, in step S231 or step S293, a command for holding the recognition result and extending the time-series information in the future direction may be output. In such a case, it is necessary to extend the length of the time series information in the future direction because appropriate recognition cannot be performed with the length Thres of the time series information.

  With reference to FIG. 38, an example in which a recognition result is suspended and a command for extending the time series information in the future direction is output in the recognition processing will be described in more detail. In FIG. 38, similarly to FIG. 37, the time axis t is provided in the vertical direction in the figure, and the nodes to which the agent has changed over time are indicated by circles in the figure. Also, in the figure, a dotted line in the vertical direction in the drawing is for indicating a node that is first recognized as being located at an unknown node. In this example, the node 201 is the node that is first recognized as being located at an unknown node.

  As shown in the figure, after first recognizing that it is located at an unknown node, actions are executed one by one and time series information is accumulated. Then, after the length N of the time series information becomes equal to the threshold value Thres (in this case, Lr = N), the recognizer 35 is described above with reference to FIG. 34 or FIG. 36 based on the time series information. Perform recognition processing. In the case of this example, it is assumed that the node sequence of the node 201, the node 202,..., The node 211 is output, and the nodes 201 to 211 are all recognized as unknown nodes. In this example, it is assumed that the nodes 201 to 211 are added to the internal model data.

  Thereby, in subsequent recognition processing, the nodes 201 to 211 are handled as known nodes.

  When the agent transitions to the node 221, recognition processing is executed based on the time series information of length Lr, and at this time, a command for holding the recognition result and extending the time series information in the future direction is output. And That is, at this time, the node string cannot be uniquely identified, and even if it is recognized, there are a plurality of candidates.

  In such a case, the value of the threshold value Thres is incremented by 1, a new action 1 is executed, and the length of the time-series information that is the target of recognition processing is also incremented by 1. As a result, the agent transitions to the node 222. At this point, recognition processing is executed based on the time series information of length Thres + 1, and a node string of length Lr (= Thres + 1) is obtained. It is assumed that a command to extend in the direction is output.

  Then, it is assumed that the agent has transitioned to the node 231 by incrementing the value of the threshold value Thres and further executing an action. At this point, it is assumed that the node 231 is recognized as a known node by executing recognition processing based on the time series information of length Thres + q.

  When the node 231 is recognized as a known node, the nodes 213 to 231 are all known nodes. At this time, the node 212 is added and anchoring from the node 212 to the node 213 is performed.

  However, as described above, a node that is actually a known node may be included in the added nodes that are regarded as unknown nodes. In addition, for example, even when the agent actually makes repeated transitions to the same node (for example, when the agent reciprocates between two nodes), they may be recognized as different unknown nodes.

  In this way, in order to prevent nodes that are not originally unknown nodes from being regarded as unknown nodes and being added to the internal model data, for example, when adding or The necessity of deletion is checked.

  An example in which the necessity of adding or deleting a node is checked at the time of anchoring will be described in more detail with reference to FIG. In FIG. 39, similarly to FIG. 37, a time axis t is provided in the vertical direction in the figure, and the nodes to which the agent has changed with the passage of time are indicated by circles in the figure. Also, in the figure, a dotted line in the vertical direction in the drawing is for indicating a node that is first recognized as being located at an unknown node. In this example, the node 201 is the node that is first recognized as being located at an unknown node.

  As shown in the figure, after first recognizing that it is located at an unknown node, actions are executed one by one and time series information is accumulated. Then, after the length N of the time series information becomes equal to the threshold value Thres (in this case, Lr = N), the recognizer 35 is described above with reference to FIG. 34 or FIG. 36 based on the time series information. Perform recognition processing. In the case of this example, it is assumed that the node sequence of the node 201, the node 202,..., The node 211 is output, and the nodes 201 to 211 are all recognized as unknown nodes.

  Thereafter, another action is executed, and the agent transitions to the node 212, but at this point, an unknown node is not yet added.

  Thereafter, another action is executed, and when the agent transitions to the node 213, the node 201 is added.

  In this way, it is assumed that the action is executed and the agent transitions to the node 215. At this time, it is assumed that the addition of the nodes 201 to 203 has already been performed. At this time, the nodes 201 to 203 are regarded as unknown nodes and added. For example, it is assumed that a node having a new index is added to the internal model data. Thereafter, when recognition processing based on time-series information corresponding to the nodes 205 to 215 is executed, if the node 215 is recognized as a known node, the nodes 205 to 215 are all known nodes. become.

  At this time, the necessity of deleting the node is checked. That is, the length of the time series information is extended in the past direction, and the recognition process based on the extended time series information is executed. As a result, for example, it is assumed that recognition processing based on time-series information corresponding to the nodes 203 to 215 is executed, and as a result, all of the nodes 203 to 215 are recognized as known nodes. That is, the node 203 is regarded as an unknown node and has been added. For example, a node having a new index has been added to the internal model data. Should be removed from the internal model data.

  For example, if the node 203 and the node 205 are actually nodes having the same index, and the node 204 and the node 206 are actually nodes having the same index, they are recognized as described above.

  For example, a new matrix is added to the state transition probability table or the like with the index of the node 203 as u. As a result of checking whether or not it is necessary to delete the node, the index of the node 203 is found to be f. And It is assumed that the matrix corresponding to the index f exists in the state transition probability table or the like before the agent transitions to the node 201. In this case, since the matrix corresponding to the index u and the matrix corresponding to the index f exist in an overlapping manner, the matrix corresponding to the index u needs to be deleted from the state transition probability table or the like.

  As a result, the matrix corresponding to the index u newly added as the index of the node 203 is deleted from the internal model data, and anchoring from the node 202 to the node 203 recognized as a known node is performed.

  For example, in the above example, when a new matrix is added to the state transition probability table or the like with the index of the node 202 as t, the state transition probability from the node at the index t to the node at the index f is determined by anchoring. Will be set.

  In addition, after anchoring is performed, learning of an additional learning method is performed based on time-series information accumulated so far. That is, learning based on time series information corresponding to the nodes 201 to 215 in FIG. 39 and one node on the left side of the node 201 is performed using the internal model data immediately after the anchoring as an initial value.

  As described above, anchoring is a process of setting a state transition probability between an unknown node and a known node when a transition from an unknown node to a known node is recognized. In the present invention, after the anchoring is performed, the learning of the additional learning method is performed based on the time series information accumulated so far.

  That is, learning of the additional learning method is performed based on the internal model data after the unknown node is added. Even if nodes with the same index are actually added as different unknown nodes, the learning may be merged as the same node by applying the forward merge algorithm and backward merge algorithm described above. Becomes higher.

  In addition, the number of parameters to be updated in the internal model data can be reduced as much as possible by not performing learning in the additional learning method until anchoring is performed. This is because the necessity of node deletion is checked during anchoring. Therefore, it is possible to appropriately update the internal model data while suppressing the calculation amount.

  As described above, when the necessity of node deletion is checked during anchoring, the number m of unknown nodes to be added can be expressed by Expression (50) instead of Expression (49).

・・・（５０）

... (50)

  In this case, the length of the time-series information (the time length after the time when it is recognized that it is located at an unknown node) N is 11. In this case, the nodes 203 to 215 correspond to the node string S, and the length Lr of the node string S is Thres + 2. Therefore, from the equation (50), the number m of nodes to be added is calculated as Thres + 4− (Thres + 2 + 3) = − 1. Therefore, one node 203 (a matrix corresponding to the index of the three nodes already added) is deleted.

  Here, only an example in which a node is deleted has been described, but a node may be added depending on the value of m_add. That is, if m calculated by the equation (50) or the equation (51) described later becomes a positive value, the corresponding nodes are added. Therefore, in practice, when anchoring is performed, whether or not a node needs to be added or deleted is checked.

  If the node to be deleted is recognized as a known node as a result of the recognition process, the node is not deleted.

  If the K-th node among nodes that are already regarded as unknown nodes and added is included in the node sequence S output in the recognition process, the number m of nodes to be deleted is changed to Equation (50). This can be expressed by equation (51).

・・・（５１）

... (51)

  The | m | nodes calculated by the equation (51) are nodes to be deleted.

  In this case, the node to be anchored is the ((Lr + K) −N) th node in the node sequence S.

  After the anchoring is performed in this way, learning of the additional learning method is performed based on the time series information accumulated so far. Further, learning by the additional learning method is not executed until anchoring is performed. Therefore, a node that is regarded as an unknown node and added to the internal model data before being anchored is recognized as one of the known nodes in the subsequent recognition process, but it is recognized as a temporary known node. Will be. This is because a node that is regarded as an unknown node and added to the internal model data before being anchored may eventually be deleted. In addition, values such as state transition probabilities between nodes that are considered as unknown nodes and added to internal model data before being anchored, and other nodes may be changed by learning using the additional learning method. Because there is.

  By the way, even if you cannot be certain that the node to be added is an unknown node in the true sense, a certain number of nodes will be used at the timing after a certain amount of time has elapsed since you first recognized that you are located in an unknown node. As described above, this node must be added to the internal model data. That is, it can be said that there is an extremely high possibility that information corresponding to an index representing a node that is simply regarded as an unknown node is added to the internal model data before anchoring.

  However, if an extremely large number of nodes that are not surely unknown nodes are truly regarded as unknown nodes and added to the internal model data, erroneous recognition may occur in the recognition process. This is because a node added as an unknown node is also treated as a known node in subsequent recognition processing.

  As a result, for example, a known node that has existed before may be erroneously recognized as a node that has been added as an unknown node. This is because the recognition process is performed based on the internal model data.

  In order to suppress such erroneous recognition, a node that has been added as an unknown node may be appropriately deleted before anchoring. In this case, when the value of m shown in Expression (49) becomes smaller than 0, | m | nodes may be deleted.

  For example, consider a case where the threshold Thres value of the number of unique nodes is 7. For example, it is assumed that the node 216 (not shown) is the node that first recognized that it is located at an unknown node, and now the agent has transitioned to the node 226 (not shown). Here, it is assumed that the node 216 has already been added to the internal model data.

  As a result of performing the recognition processing based on the time series information corresponding to the nodes 219 to 226, it is assumed that the node 226 is recognized as an unknown node. At this time, the node 217 is added to the internal model data.

  Thereafter, by executing an action, the agent transitions to a node 227 (not shown). As a result of the recognition processing at this point, it is assumed that the node 227 is recognized as an unknown node. At this time, the node 218 is added to the internal model data. However, as a result of adding the node 218 to the internal model data, it is recognized that the node 220, the node 222, the node 224, and the node 226 are actually nodes having the same index as the node 218.

  In this case, in order to output a node string including the number of unique nodes equal to or greater than the threshold value Thres, the length of the time-series information has to be a length corresponding to the nodes 217 to 227.

  In such a case, the length of the time series information (nodes 216 to 227) N is 12, and the number m_add of the nodes (nodes 216 to 218) that have already been added is 3. In this case, the nodes 217 to 227 correspond to the node string S, and the length Lr of the node string S is 11. Therefore, from Expression (49), the number m of nodes to be added is calculated as 12− (11 + 3 + 1) = − 3. Accordingly, the three nodes added to the internal model data and the nodes 216 to 218 are deleted.

  In this way, if a node that has been added as an unknown node is deleted as necessary before anchoring, erroneous recognition can be suppressed.

  That is, before anchoring, a process is performed in which an unknown node is added, or a node that has been added as an unknown node is deleted as necessary. This process corresponds to step S316 in FIG.

  Also, when anchoring, a process of adding an unknown node or deleting a node that has been added as an unknown node as necessary is performed. This process corresponds to step S318 in FIG.

  Next, the unknown node addition process will be described with reference to the flowchart of FIG. This process is executed by the autonomous behavior learning device 10 when the agent autonomously recognizes a change in the environment and needs to expand the internal model data.

  In step S311, the recognizer 35 sets the value of the variable N to 1 which is an initial value.

  In step S <b> 312, the recognizing device 35 acquires time-series information of length N from the observation buffer 33 and the behavior output buffer 39.

  In step S313, the recognizing device 35 determines whether N is equal to or greater than the threshold Thres of the number of unique nodes. If it is determined that N is not yet equal to or greater than the threshold Thres, the process proceeds to step S321.

  In step 321, the value of the variable N is incremented by 1, and the process returns to step S312.

  On the other hand, if it is determined in step S313 that N is equal to or greater than the threshold value Thres, the process proceeds to step S314.

  In step S314, the recognizer 35 executes the recognition process described above with reference to FIG. 34 or FIG. However, in this case, since the time series information is acquired in the process of step S312, the recognition process is executed based on the time series information.

  In step S315, the learning device 34 determines whether or not the last node in the node sequence is recognized as an unknown node as a result of the recognition processing in step S314. If it is determined in step S315 that the node is recognized as an unknown node as a result of the recognition process, the process proceeds to step S316.

  In step S316, the learning device 34 adds or deletes a node regarded as an unknown node.

  In step S316, for example, a node is added as if the node 201 considered as an unknown node in FIG. 37 was added to the internal model data. Further, for example, as described above, in order to suppress misrecognition, a node that has been added as an unknown node is deleted before anchoring.

  On the other hand, when it is determined in step S315 that the node is not recognized as an unknown node as a result of the recognition process, the process proceeds to step S317.

  In step S317, the learning device 34 determines whether or not the last node in the node sequence is recognized as a known node as a result of the recognition processing in step S314. If it is determined in step S317 that the node is recognized as a known node as a result of the recognition process, the process proceeds to step S318.

  In step S318, the learning device 34 and the recognizing device 35 execute an addition or deletion necessity check process described later with reference to FIG. Thus, for example, as described above with reference to FIG. 39, whether or not a node needs to be deleted at the time of anchoring is checked, and if deletion is necessary, it is regarded as an unknown node and the added node is deleted. .

  In step S319, the learning device 34 performs anchoring. Thereby, for example, a state transition probability from a known node to an unknown node is set.

  On the other hand, if it is determined in step S317 that the node is not recognized as a known node as a result of the recognition process, the process proceeds to step S320.

  In step S320, the recognizing device 35 increments the value of the threshold value Thres by one.

  That is, in step S317, if it is determined that the node is not recognized as a known node as a result of the recognition process, a command to hold the recognition result and extend the time series information in the future direction is output in the recognition process. Become. For example, this is a case where the process of step S231 or the process of step S293 described above with reference to FIG. 34 or FIG. 36 is performed. In this case, for example, as described above with reference to FIG. 38, it is necessary to increment the value of the threshold Thres and extend the length of the time series information in the future direction.

  Therefore, after the process of step S320, the process proceeds to step S321.

  In this way, the unknown node addition process is executed.

  Next, a detailed example of the addition or deletion necessity check process in step S318 in FIG. 40 will be described with reference to the flowchart in FIG.

  In step S341, the recognizing device 35 acquires time-series information of length N. That is, time-series information of time length N after the time when it is recognized that it is located at an unknown node is acquired. For example, in the example of FIG. 39, time-series information having a length corresponding to the nodes 201 to 215 is acquired.

  In step S342, the recognizer 35 executes a recognition process based on time-series information of length N. At this time, the recognition process described above with reference to FIG. 34 or 36 is executed. However, in this case, since the time series information is acquired in the process of step S341, the recognition process is executed based on the time series information.

  In step S343, the learning device 34 determines whether or not the last node (the last node in time) in the node sequence is recognized as a known node as a result of the recognition processing in step S342. If it is determined in step S343 that the node is not recognized as a known node as a result of the recognition process, the process proceeds to step S344.

  In step S344, the recognizer 35 decrements the length N of the time series information by 1. In this case, the time series information is shortened from the past side. For example, in the example of FIG. 39, the time series information having the length corresponding to the nodes 201 to 215 is acquired as the time series information having the length corresponding to the nodes 202 to 215. It will be.

  As described above, in step S343, the time series information is shortened from the past side and the repeated recognition process is executed until it is determined that the node is recognized as a known node as a result of the recognition process.

  If it is determined in step S343 that the node has been recognized as a result of the recognition process, the process proceeds to step S345. For example, in the case of the example in FIG. 39, as a result of the recognition processing based on the time series information having the length corresponding to the nodes 203 to 215, it is recognized that all of the nodes 203 to 215 are known nodes. At this time, the number of nodes in the node train of the nodes 203 to 215 is specified.

  In step S345, the learning device 34 specifies the number of nodes, performs the above-described calculation with reference to the equation (50), with the specified number of nodes as the length Lr of the node sequence S.

  In step S346, the learning device 34 determines whether there is a node to be added (or deleted). If it is determined in step S346 that there is a node to be added (or deleted), the process proceeds to step S347. On the other hand, if it is determined in step S346 that there is no node to be added (or deleted), the process of step S347 is skipped.

  In step S347, the learning device 34 adds (or deletes) a node determined to be added (or deleted) in the process of step S346. For example, in the case of the example of FIG. 39, the number m of nodes to be added is calculated as Thres + 4− (Thres + 2 + 3) = − 1 from Expression (50), so one of the three nodes that have already been added. Node 203 is deleted. That is, the node 203 has been added as an unknown node. For example, a node having a new index has been added to the internal model data. However, the node 203 is originally a known node, and the node with the added index is an internal node. It is deleted from the model data.

  In this way, an addition or deletion necessity check process is executed.

  When a new situation is encountered that cannot be expressed by internal model data obtained through learning so far, it is necessary to increase the number of nodes to express the situation and solve the situation. For example, if the maze where the robot moves is extended in a predetermined direction, the number of nodes increases, so the value of the number of nodes N needs to be increased.

  In the conventional technique, when a new node is detected, the internal model data is immediately expanded on the spot, and an index representing the new node is added.

  However, in general, when a new experience is taken in, the most important issue is how the experience is related to the existing structure. For example, immediately after a new node is detected, the relationship with the existing structure is not clear enough. There are many things.

  Therefore, adding to the index internal model data representing a new node immediately may cause future misrecognition. For example, in a situation where new nodes are continuously detected, the new node can only define a relationship with the previous state, and the more such a chain continues, the more rapidly existing The ambiguity of the relationship to the structure will progress. Even if learning is performed by the additional learning method based on such internal model data, the parameters to be adjusted at the time of learning become enormous.

  Therefore, in the present invention, as described above, a predetermined number of unknown nodes are added at a predetermined timing, and learning by the additional learning method is performed based on the internal model data immediately after the anchoring. It was made to be. By doing so, for example, in a case where new nodes appear sporadically among known nodes, it is difficult environment where new nodes are continuously detected over a long period of time. In this case, it is possible to perform sufficiently effective learning.

  As described above, it is possible for the agent to autonomously recognize changes in the environment and expand the state transition probability table and the observation probability table. At that time, set the expanded area of each table. It is necessary to specify values such as state transition probability and observation probability to be performed.

  Although the example in the case of extending each table in FIGS. 30 to 32 has been described, here, the state transition probability to the node in the expanded area is estimated and set from the state transition probability already stored. The method to do is demonstrated.

  For example, as described in FIG. 31, when it is necessary to expand the state transition probability table, it has been described that it is necessary to normalize the sum of the probability values of each row of the state transition probability table to be 1. In other words, in the processing described above in the example of FIG. 31, the state transition probability from the already-known node to the known node is not considered in setting the state transition probability in the added region. However, it can be predicted that a transition from a plurality of known nodes may occur for an unknown node added to the internal model data.

  For example, when a part A in the maze is replaced with another part B, the part C adjacent to the part A and the part B are connected. In such a case, if the robot performs an action for moving from part C to part A, the possibility of moving to part B is high. Further, when the action for moving the robot from the part A to the part C is executed in the part B, the possibility of moving to the part C is high. In this example, it is necessary to newly add an HMM node corresponding to part B as an unknown node, but the state transition probability with the known node corresponding to part C should be set in consideration of the above.

  Therefore, if the state transition probability between the unknown node and the known node can be set based on the already stored state transition probability from the known node to the known node, the state transition probability is set more appropriately. It is considered possible. In other words, if the state transition probability between an unknown node and a known node can be set based on past experience, the state transition probability can be set more appropriately.

  Note that the known nodes described here include, for example, nodes that are regarded as unknown nodes and already added to the internal model data while the robot is moving in the maze.

  The state transition probability value set as described above needs to be determined in consideration of the following pattern.

That is, when a transition from node s _i to node s _j actually occurs, it is necessary to consider whether node s _i and node s _j are known nodes or newly added unknown nodes. There is.

  That is, it is necessary to consider three patterns: a transition from a known node to an unknown node, a transition from an unknown node to an unknown node, and a transition from an unknown node to a known node.

  For example, when the state transition probability table is expanded, it is necessary to set the state transition probability from the known node to the unknown node in the region 301-1 to region 301-3 shown in FIG. In addition, it is necessary to set the state transition probability from the unknown node to the unknown node in the regions 303-1 to 303-3. Furthermore, it is necessary to set the state transition probability from the unknown node to the known node in the region 302-1 to region 302-3.

  Further, as described above, since all the numerical values described in each row (for example, the nth row) of the state transition probability table are summed to be 1, the existing state is described in FIG. It is necessary to set the probability of the area again.

  For example, a case as shown in FIG. 43 will be described as an example.

  That is, as a result of executing the action corresponding to the movement in the right direction in the figure at the transition source node 321 which is a known node, the transition destination node having a high possibility of transition is determined based on the state transition probability table. Assume that node 323 was expected. However, it is assumed that the transition destination node that has transitioned as a result of executing the action corresponding to the movement in the right direction in the figure in the transition source node 321 is the node 324. In this case, the node 324 becomes an unknown node.

  43, an observation symbol corresponding to part 5 in FIG. 2 is observed at node 321, an observation symbol corresponding to part 12 in FIG. 2 is observed at node 322, and the part of FIG. 2 is observed at node 323. An observation symbol corresponding to 6 is observed.

  In FIG. 43, the signs of the nodes 321 to 324 are attached to the rectangles representing the parts of the maze, but actually, the nodes where the observation symbols corresponding to these parts are observed are shown. It is the code | symbol attached. That is, the agent can uniquely recognize the nodes 321 to 323 based on the learned internal model data, and the node 324 recognizes the internal state (node) that has not been stored so far. Will be.

  That is, when the agent moves from the node 321 in the right direction in the figure, it is expected that the agent will come out at the upward turning corner (node 322) in the drawing or the downward turning corner (node 323) in the drawing.

  However, when actually moving from the node 321 in the right direction in the figure, it came out to the crossroad (node 324). That is, at the node 324, an observation symbol corresponding to the part 15 in FIG. 2 is observed.

  For example, such a situation occurs when a part arranged at a position corresponding to the node 321 in the maze is replaced. In such a case, since the node 324 is considered as a node that did not exist in the internal model data so far, it is necessary to add at least the node 324 to the internal model data.

  In such a case, a new index corresponding to the node 324 is generated and a matrix of the state transition probability table is added. Therefore, it is necessary to set the state transition probability from the node 321 to the node 324 in the state transition probability table corresponding to the action in the right direction. However, the timing at which a new index is actually generated and the matrix of the state transition probability table is added is as described above with reference to FIGS.

  As this state transition probability, for example, a value obtained by dividing the sum of the state transition probabilities from the node 321 to the node 322 and the node 323 by 3 is set. At this time, the state transition probabilities from the node 321 to the node 322 and the node 323 may be set in proportion to the weights according to the respective state transition probabilities.

Node candidates s _j ^l (l = 1,... L) that can be shifted from a node 321 (for example, node s _i ) by an action in the right direction (for example, action k ′) are, for example, state It is only necessary to list the transition destination node s _{j for} which the transition probability a _ij (k ′) is equal to or greater than the threshold.

  In the example of FIG. 43, two nodes of the node 322 and the node 323 that can transition from the node 321 by the action in the right direction are listed as candidate nodes. In this case, the value of L is 2.

An unknown node 324 is represented by a node s _new , and the state transition probability a _inew (k ′) from each known node s _i to s _new corresponding to the action k ′ is set as 1 / L.

  In the example of FIG. 43, the state transition probability from the node 321 to the node 324 is set as 1/2.

The state transition probability a _inew (k ′) is set in any one of the regions 301-1 to 301-3 in the example of FIG.

Then, normalization is performed so that the sum of the state transition probabilities of each row of the state transition probability table corresponding to the action k ′ becomes 1. That is, each value of a row in which a non-zero value is set as the state transition probability a _inew (k ′) may be multiplied by L / (L + 1).

However, when there is no transition destination node in which the state transition probability a _ij (k ′) is equal to or greater than the threshold, normalization as described above is performed with the state transition probability a _inew (k ′) _≈1 .

  Note that the state transition probability of transitioning to the node 324 by executing an action other than the action k ′ at the node 321 may be set to a minute value close to 0, so that the state transition probability of each row of the state transition probability table There is no need to normalize the sum to be one.

  As indicated by the arrows in FIG. 44, the node 324 that is a crossroad can execute four actions in the up, down, left, and right directions to make a transition to another node. Therefore, it is also necessary to set the state transition probability from the node 324 of the state transition probability table corresponding to the action in the up / down / left / right directions to each known node. These state transition probabilities are set in any of the region 302-1 to region 302-3 in the example of FIG. If there is a transition from an unknown node to an unknown node, any of the areas 303-1 to 303-3 in the example of FIG. 42 is included in addition to the above.

  For example, the state transition probability from the node 324 to each known node in the state transition probability table corresponding to the upward action copies the state transition probability from the node 322 to each known node. This is because the node 322 has an upward turn and is the only node that can make a transition from the node 321 by an action in the right direction and can make a transition to another known node by an action in the upward direction. Note that nothing is changed for the state transition probability from the node 322 to each known node.

  Further, for example, as the state transition probability from the node 324 to each known node in the state transition probability table corresponding to the downward action, the state transition probability from the node 323 to each known node is copied. This is because the node 323 has a downward turn and is the only node that can transition from the node 321 by an action in the right direction and can transition to another known node by an action in the downward direction. Note that nothing is changed for the state transition probability from the node 323 to each known node.

  Further, the state transition probability from the node 324 to each known node in the state transition probability table corresponding to the leftward action is the state transition probability from the node 322 to each known node and the node 323 to each known node. It is a value obtained by averaging the state transition probabilities. This is because the nodes 322 and 323 are nodes that can make a transition from the node 321 by an action in the right direction and can make a transition to another known node by an action in the left direction. That is, the average value of the state transition probabilities of the node 322 and the node 323 may be used as the state transition probability from the node 324 to each known node of the state transition probability table corresponding to the leftward action. At this time, nothing is changed for the state transition probabilities from the node 322 and the node 323 to each known node.

  Further, for each state transition probability from the node 324 of the state transition probability table corresponding to the action in the right direction to each known node, for example, a uniform value is set. This is because, as shown in FIG. 45, there is no other candidate node that can make a transition to another known node by an action in the right direction.

  Furthermore, it is necessary to set a state transition probability from each known node other than the node 321 to the node 324.

  Since the node 324 is a crossroad, the transition from another node to the node 324 can occur by any action in the vertical and horizontal directions. That is, there should be a transition source node that transitions to the node 324 by an upward action, and a transition source node that transitions to the node 324 by a downward action. In addition, there should be a transition source node that transitions to the node 324 by an action in the left direction, and a transition source node that transitions to the node 324 by an action in the right direction.

  In this case, it is necessary to specify the transition source node and to specify which action is executed in each of the transition source nodes to transit to the node 324. That is, it is necessary to specify a backward transition action to an unknown node.

  First, a node similar to the node 324 is extracted in order to obtain information as a basis for estimating the transition source node. A node similar to the node 324 may be a node that is certain to some extent if, for example, the agent is in a node other than the current node 324.

  For example, consider a case where there are a plurality of parts that are similar in the structure of the maze. It is assumed that the agent is one of those parts and exists on a predetermined part. In such a case, it may actually exist on a predetermined part that is different from the part recognized by the agent. In this way, a node similar to the node recognized by the agent can be extracted.

  Similar nodes can be identified by n-step state recognition using time series information for the past n steps.

At time t, a sequence of actions for the past n steps c _{t? n} , ..., c _t? Sequence of observation symbols for ₁ and past n + 1 steps o _t? Estimating the current node using _n ,..., o _t or calculating the probability that an agent exists at each node at the current time t is referred to as “n-step state recognition”.

In n-step state recognition, first, a priori probability π _i corresponding to a node with an index i (i = 1,... N) is set by, for example, a predetermined method.

Thereafter, the recognizer 35 calculates the probability δ _tn (i) that the agent exists in each node at the time tn by the equation (52).

・・・（５２）

... (52)

  Then, the recognizer 35 calculates the probability δτ (i) that the agent exists in each node in the order of time τ = t−n + 1,... T by the recurrence formula of Formula (53).

・・・（５３）

... (53)

  Alternatively, the calculation of Expression (54) may be performed instead of Expression (53).

・・・（５４）

... (54)

The recognizer 35 further normalizes the probability δ _t (i) that the agent exists at each node at the final time t in the equation (53) or the equation (54), thereby obtaining the state probability for each node at the time t. δ ′ _t (i) is calculated by Expression (55).

・・・（５５）

... (55)

  Each node whose state probability obtained by the equation (55) is equal to or greater than a predetermined threshold is a similar node.

Incidentally, n- in the step state recognition, but a sequence of the sequence and observation symbol action past n steps worth is used, when the n is set to 0, the node observation symbol o _t is observed with probability higher than a predetermined threshold value All become similar nodes. In addition, as n is increased, the number of similar nodes usually decreases. It is assumed that the value of n in n-step state recognition is a preset value that is suitable for use in estimation performed in the present invention, for example.

  When similar nodes are obtained, actions that can be transitioned to other nodes are specified by being executed at those nodes. For example, since the node 324 is a crossroad, there is a high possibility that a node similar to the node 324 is also a crossroad. Then, a similar node can transition to another node by an up / down / left / right movement action.

  Then, by executing these actions, a known node that can transition to another node is specified. For example, even a node 322 that is a known node that can transition from the node 321 by an action in the right direction can transition to another node by executing an action in the left direction and the upward direction, respectively. Similarly, the node 323, which is a known node that can transition from the node 321 by an action in the right direction, can transition to another node by executing an action in the left direction and the downward direction, respectively.

  Then, the unknown node 324 can transition from each of the transition destination nodes that transition by executing the leftward and upward actions in the node 322, respectively, by an action that is the reverse of the leftward and upward directions. I can assume. In this case, an action (reverse direction transition action) in which the right direction and the downward direction are reversed is performed.

  In addition, the unknown node 324 can transition from each of the transition destination nodes that transition by executing the leftward and downward actions in the node 323, respectively, by an action that is the reverse of the leftward and downward directions. I can assume. In this case, an action in which the right direction and the upward direction are opposite directions (reverse direction transition action) is performed.

The backward direction transition action can be estimated as follows, for example. For example, if the transition of the action c _z from node s _a to node s _b occurs, reverse transition, that estimates the action c _{z 'for} causing the transition from node s _b to the node s _a.

In estimating the backward transition action, the recognizer 35 identifies similar nodes that are similar as described above. Each of the known nodes specified here is represented by a node s _j ^q (q = 1,... Q).

Then, the recognition device 35, for each node s _j ^q, extracts the transition source node to transition to the node s _j ^q by the action c _z. In this case, for example, the nodes s _i whose state transition probabilities a _ij ^q (z) are equal to or greater than a threshold may be listed.

Then, the recognizing device 35 determines the node s _j ^q for all combinations of (s _j ^q , s _i ^{q, l} ) (q = 1,..., Q, l = 1,..., L _q ). The average value a ^* (k) of the state transition probabilities from the node s _i ^{q, l} to the node s _i ^{q, l} is calculated by the equation (56).

・・・（５６）

... (56)

If the average value a ^* (k) of the state transition probabilities obtained in this way is selected to be equal to or greater than the threshold, and the action c _k corresponding to the a ^* (k) is specified, the backward transition The action c _z ^r ′ (r = 1,..., R) can be specified.

  Assuming that the transition source node identified in this way makes a transition to the node 324 by executing a reverse transition, the same as the case of setting the state transition probability from the node 321 to the node 324 described above. The state transition probability can be set by operation.

  Considering this, when adding a matrix corresponding to the index of a node regarded as an unknown node to the state transition probability table, it is necessary to reset all state transition probabilities in the region shown in FIG.

  That is, when a matrix corresponding to an index of a node regarded as an unknown node is added to the state transition probability table, it is necessary to specify an action that can be executed at the unknown node and a transition destination node that can be shifted by the action. is there. In this way, it is possible to specify a predetermined matrix position in the state transition probability table from the pair of the identified action and the transition destination node, and set the value of the state transition probability to be set at those positions. And normalizing each value in the row.

  In addition, when adding a matrix corresponding to the index of a node regarded as an unknown node to the state transition probability table, a transition source node that can transition to the unknown node, an action for transitioning from the transition source node to the unknown node, Need to be identified. In this way, it is possible to specify a predetermined matrix position in the state transition probability table from the pair of the identified action and the transition source node, and set the value of the state transition probability to be set at those positions. And normalizing each value in the row.

  Therefore, as described above, when the agent autonomously recognizes the environmental change and expands the state transition probability table, the process of setting the value of the state transition probability to be set in the expanded area is as follows. Finally, for example, it can be executed by the procedure shown in FIG.

  FIG. 46 is a flowchart for explaining state transition probability setting processing when a node is added. This process is executed, for example, when the agent autonomously recognizes a change in the environment and adds an unknown node to the state transition probability table or the like.

Here, it is assumed that the unknown node s _{new new} is added to the internal model data, the agent 'and the node s _i' node s _i to node prior to the transition to the node s _{new new} carries out the action c _k 'in As a result, the agent transitions to the node s _new .

  In step S401, the recognizing device 35 executes a node reverse action pair list generation process to be described later with reference to the flowchart of FIG.

  As a result, the transition source node to the unknown node is specified, and the backward transition action to the unknown node is specified.

  In step S402, the learning device 34 executes a reverse action state transition probability setting process which will be described later with reference to the flowchart of FIG.

  As a result, the state transition probability of transitioning to an unknown node is set by executing a backward transition action at the transition source node identified by the process of step S401. In addition, the value of each row of the state transition probability table is normalized according to the state transition probability newly set here.

  In step S403, the recognizing device 35 executes a node-order action pair list generation process which will be described later with reference to the flowchart of FIG.

  As a result, the transition destination node from the unknown node is specified, and the forward transition action for transitioning from the unknown node to the transition destination node is specified.

  In step S404, the learning device 34 executes a forward action state transition probability setting process which will be described later with reference to the flowchart of FIG.

  Thereby, in the unknown node, the state transition probability of transitioning to the transition destination node is set by executing the forward transition action specified by the process of step S403. In addition, the value of each row of the state transition probability table is normalized according to the state transition probability newly set here.

  Next, details of the node reverse action pair list generation processing in step S401 of FIG. 46 will be described with reference to the flowchart of FIG.

In step S421, the recognizing device 35 extracts a candidate node s _j ^l (l = 1,... L) that can be transitioned by executing the action c _k ′ at the node s _i ′. Candidate node s _j ^l may be, for example, the state transition probability a _i'j (k') list is equal to or greater than a threshold transition destination node s _j'.

  In step S422, the recognizer 35 performs n-step state recognition using time series information for the past n steps.

In step S423, the recognizer 35 extracts similar nodes that are similar to the node s _new and are known based on the processing result of step S422. Each of the known nodes specified here is represented by a node s _j ^q (q = 1,... Q). At this time, similar nodes similar to the node s _new are extracted by _performing the operations of the above-described equations (52) to (55).

  In step S424, the recognizing device 35 extracts the effective action of the similar node extracted in the process of step S423.

  Here, the effective action means an action that can be transferred to another node by being executed in each of the similar nodes.

In step S424, for example, the evaluation value E _{k for} each action is calculated by Expression (57). This calculation is performed for each action, and one evaluation value is obtained for one action.

・・・（５７）

... (57)

Here, a _jx ^q (k) (q = 1,..., Q, x = 1,..., N) is an action c _{k at the} node s _j ^q (q = 1,..., Q). Is the state transition probability when transitioning to node s _x .

  Then, the action k whose evaluation value calculated by the equation (57) is equal to or greater than the threshold value is selected and is set as a valid action candidate.

Further, for each of the selected actions k, the state transition probability a _jx ^q (k) is checked, and at least one pair of (q, x) in which the state transition probability a _jx ^q (k) is _{equal to} or greater than a threshold value. It is determined whether or not it exists. If there is no such (q, x) pair, the action k is excluded from the valid action candidates.

In this way, in step S424, the effective action c _k ^r (r = 1,..., R) is extracted.

In step S425, the recognizing device 35 extracts, from the candidate nodes s _j ^l extracted in the process of step S421, those having the action c _k ^r extracted in the process of step S424 as an effective action. That is, among the candidate nodes, nodes s _j ^ru (u = 1,..., Ur) having the same effective action as the similar nodes are extracted.

In step S425, for example, the evaluation value Elr for each of the nodes s _j ^l is calculated by the equation (58). This calculation is performed for each of the nodes s _j ^l corresponding to the case where each action c _k ^r is executed, and one evaluation value is obtained for one combination of the node and the action. Will be.

・・・（５８）

... (58)

Equation (58) is calculated for the case where the action c _k specified by the variable r is executed on the candidate node of the index j specified by the variable l. In addition, k (or c _k ), which is the action of the state transition probability on the right side of Equation (58), is specified by the variable r on the left side.

As described above, in step S425, the node having the evaluation value calculated by the equation (58) equal to or greater than the threshold is extracted as the node s _j ^ru .

In step S426, the recognizer 35 generates a pair (s _j ^ru , c _k ^r ) of the node extracted in step S425 and the valid action extracted in step S424, and the transition destination node specified from each pair Is identified.

For example, in the node s _j ^ru , the state transition probability a _jl ^ru (k) (l = 1,..., N) when the action c _k ^r is executed is checked, and the state transition probability exceeding the threshold is handled. The transition destination node s _l ^q (q = 1,... Q _ru ) is specified.

In step S427, the recognizer 35 estimates the backward transition action of the action c _k ^{r at} the node s _j ^ru . That is, an action for transitioning from the node s _l ^q to the node s _j ^ru is estimated. The backward transition action estimated at this time is c _ruq ^v (v = 1,... V _ruq ). However, when the transition destination node is the node s _i ′, this estimation is not performed.

Then, the recognizing device 35 pairs (s _l ^q , c _ruq ^v ) (l = 1,..., L, r = 1,...) With the transition destination node specified in step S426 and the backward transition action. ..., R, u = 1, ..., Ur, q = 1, ..., Qru, v = 1, ..., Vruq).

In step S428, the recognizer 35 _adds (s _i ′, c _k ′) to the pair (s _l ^q , c _ruq ^v ) generated in step S427 to eliminate duplication, and determines the transition source node to the unknown node. A pair of reverse transition actions (s _i ^x , c _k ^x ) (x = 1,..., X) is generated. Then, each of the pair of the transition source node to the unknown node and the backward transition action is listed.

  In this way, the node reverse action pair list generation process is executed.

Based on the pair obtained by the process of FIG. 47, it is assumed that the node s _i ^x has transitioned to the node s _new by executing the action c _k ^x, and the process of step S402 of FIG. 46 is executed.

  Next, a detailed example of the reverse action state transition probability setting process in step S402 in FIG. 46 will be described with reference to the flowchart in FIG.

For example, it is assumed that a transition is made from the transition source node s _i to the node s _new by the action c _k .

In step S441, the learning device 34 extracts candidate nodes that can transition from the node s _i by the action _ck . The node candidates s _j ^l (l = 1,... L) may be, for example, a list of transition destination nodes s _j whose state transition probability a _ij (k) is equal to or greater than a threshold.

  In step S442, the learning device 34 sets and normalizes the state transition probability to an unknown node.

For example, the state transition probability a _inew (k) from each candidate node s _i to s _new corresponding to the action c _k is set as 1 / L. Then, normalization is performed so that the sum of the state transition probabilities of each row of the state transition probability table corresponding to the action _ck becomes 1. That is, each value in a row in which a non-zero value is set as the state transition probability a _inew (k) is multiplied by L / (L + 1).

However, if there is no transition destination node in which the state transition probability a _ij (k) is greater than or equal to the threshold value as a result of the processing in step S411, the state transition probability a _inew (k) _{≈1 is assumed and the normality} as described above To do.

  In this way, the reverse action state transition probability setting process is executed.

  Next, a detailed example of the node order action pair list generation processing in step S403 in FIG. 46 will be described with reference to the flowchart in FIG.

In step S461, the recognizing device 35 extracts the transition destination node s _l ^q (q = 1,... Q _ru ) in the same manner as the processing in step S426 in FIG. That is, a pair of candidate nodes and valid actions is generated, and a transition destination node corresponding to each pair is specified.

In step S462, the recognizing device 35 determines the transition destination node s _l ^q (q = 1,... Q _ru ) obtained by the processing in step S461 and the action c _k ^r (for transition to the transition destination node. r = 1, ... R) is generated as a pair.

In step S463, the recognizing device 35 eliminates the pair duplication obtained in the process of step S462, and generates a pair (s _j ^y , c _k ^y ) (y = 1,..., Y). Then, each of a transition destination node and an action pair for transitioning to the transition destination node is listed.

  In this way, node order action pair list generation processing is executed.

Based on the pair obtained in the processing in FIG. 49, is assumed that the shift to the node s _j ^y by performing the action c _k ^y at the node s _{new new,} the process of step S404 of FIG. 46 is executed.

  Next, a detailed example of the forward action state transition probability setting process in step S404 in FIG. 46 will be described with reference to the flowchart in FIG.

In step S481, the learning device 34 initializes all the state transition probabilities a _newj (k) (j = 1,..., N, k = 1,..., K) with very small values.

In step S482, the learning device 34 sets a state transition probability using the pair (s _j ^y , c _k ^y ) obtained by the processing of FIG. That is, the state transition probability a _newj ^y (k) for transitioning to the node s _j ^y by executing the action c _k ^y at the node s _new is set as 1.

In step S483, the learning device 34 normalizes so as to satisfy Σ _j a _newj (k) (k = 1,..., K).

  In this way, the forward action state transition probability setting process is executed.

  In the above example, an example has been described in which an agent autonomously recognizes a change in the environment and adds an unknown node to the state transition probability table. Need to add. Regarding the update of the observation probability table in this case, for example, when it is necessary to expand the observation probability table as shown in FIG. 31, the above-described processing may be performed as the processing performed by the learning device 34. .

  Of course, the frequency variable table for estimating the state transition probability and the frequency variable table for estimating the observation probability are also updated in accordance with the processing described above with reference to FIG.

  Next, the setting of the state transition probability when anchoring will be described.

  As described above, anchoring is a process of setting a state transition probability between a node regarded as an unknown node and a known node when a transition to a known node is recognized.

In other words, when the action c _{k ′} is executed at the unknown node s _{i ′} and the state transitions to the known node s _j ′, the state transition probability a _i′j (k ′) in the state transition probability table of the internal model data. Anchoring is performed when there is no node s _j where (j = 1,..., N) is greater than or equal to the threshold. That is, when a transition from a node regarded as an unknown node to a known node is confirmed and a transition from the unknown node to a node other than the known node is difficult to occur, anchoring is performed.

In anchoring, the state transition probability from the unknown node s _{i ′} to the known node s _{j ′} by the action c _{k ′} is set. For example, as described above with reference to FIG. 46, every time a node regarded as an unknown node is added to the internal model data, the state transition probability from the unknown node to the known node is estimated and set. However, when a transition from an unknown node to a known node actually occurs, anchoring is performed.

  Here, the anchoring process will be described with reference to the flowchart of FIG. This process is, for example, a process executed as the process of step S319 in FIG.

In step S501, the learning device 34 sets the state transition probability corresponding to the transition to be anchored to 1. In the above example, the state transition probability a _i′j ′ (k ′) is 1.

In step S502, the learning device 34 normalizes each value in the state transition probability table so that Σ _j a _i′j (k ′) becomes 1.

In step S503, the recognizing device 35 estimates a backward transition action for transition from the known node s _{j ′} to the unknown node s _{i ′} . At this time, for example, the backward transition action is estimated in the same manner as described above with reference to FIG. Thereby, the backward transition action c _z ^r (r = 1,..., R) is estimated.

In step S504, the learning device 34 assumes that a transition from the known node s _{j ′} to the unknown node s _i ′ has occurred by executing each of the backward transition actions estimated in the process of step S503. To set the state transition probability. This process is the same as that described above with reference to FIG. 48, for example.

  In this way, the anchoring process is executed.

Note that, instead of the process described with reference to FIG. 51, the process described above with reference to FIG. 46 is performed on the assumption that a transition from the known node s _{j ′} to the unknown node s _i ′ has occurred. An anchoring process may be performed by setting a state transition probability.

That is, in practice, the action c _{k ′} is executed in the unknown node s _{i ′} and the transition is made to the known node s _j ′, but the backward transition action c _z ^r (r = 1,..., R) It is assumed that a transition from the known node s _{j ′} to the unknown node s _i ′ has occurred. Here, the backward transition action c _z ^r (r = 1,..., R) can be estimated in the same manner as in the process of step S503, for example.

That is, assuming that a transition from the known node s _{j ′} to the unknown node s _i ′ has occurred by the action c _z ¹ , the processing described above with reference to FIG. 46 is executed. Further, assuming that a transition from the known node s _{j ′} to the unknown node s _i ′ has occurred by the action c _z ² , the processing described above with reference to FIG. 46 is executed. Similarly, it is assumed that a transition from the known node s _{j ′} to the unknown node s _i ′ is caused by the action c _z ³ ... Action c _z ^R , respectively, and the processing described above with reference to FIG. It is.

At the time of anchoring, in this way, the action c _z ^r (r = 1,..., R) causes the unknown node s _{i ′} from the immediately preceding node s _{j ′} (actually the known node to be anchored). 46 may be executed by assuming that the process has transitioned to.

  Thus, according to the present invention, it is possible for the agent to autonomously recognize a change in the environment, and to expand the state transition probability table and the observation probability table. At that time, it is also possible to appropriately set values such as state transition probability and observation probability to be set in the expanded area of each table. Further, it is possible to set the state transition probability between the unknown node and the known node based on the state transition probability from the known node to the known node that has already been stored.

  So far, the description has been given of the actions that can be taken when it is necessary to change the number of nodes, the number of observation symbols, or the number of actions when learning is advanced.

  As described above, according to the present invention, learning using an action expanded HMM can be performed. As a result, it is possible to learn in a situation where the agent executes an action on the environment using the action signal and can influence an observation symbol observed in the future.

  Further, according to the present invention, it is possible to efficiently and appropriately learn an action expanded HMM that inevitably has a large scale. That is, a one-state one-observation constraint is imposed on the learned internal model data by applying a split algorithm, and an action transition constraint is imposed by applying a forward merge algorithm and a backward merge algorithm. As a result, an increase in the number of parameters to be calculated can be suppressed, and learning of the action extended HMM that inevitably has a large scale can be performed efficiently and appropriately.

  Furthermore, according to the present invention, it is possible to stably perform learning by the additional learning method in the action expanded HMM that inevitably has a large scale. In other words, by calculating and storing a frequency variable for estimating the state transition probability and a frequency variable for estimating the observation probability, it is possible to stably perform learning in the additional learning method in the action expanded HMM. it can.

  Further, according to the present invention, it is possible to change the number of nodes, the number of observation symbols, or the number of actions when learning is advanced.

  At this time, for example, it is possible to instruct the agent to expand the internal model data on the assumption that the number of nodes increases in advance by a predetermined number, and the agent autonomously changes the environment. It is also possible to recognize and extend the internal model data.

  In order for the agent to autonomously recognize changes in the environment and expand the internal model data, the agent should add a new node whether the node where the agent is currently located is a learned internal state Enabled to recognize whether the node is in internal state.

  In addition, a predetermined number of unknown nodes are added at a predetermined timing, and learning by the additional learning method is performed based on the internal model data immediately after the anchoring. This allows, for example, new nodes to appear sporadically among known nodes, but also in difficult environments where new nodes are continuously detected over a long period of time. It became possible to perform effective learning.

  Furthermore, when expanding the internal model data, the state transition probability between the unknown node and the known node can be set based on past experience.

  Thus, according to the present invention, efficient and stable learning can be performed when autonomous learning is performed in a changing environment.

  In the above description, the embodiment of the present invention is mainly applied to an example in which the robot moves in the maze. However, other embodiments may be used as a matter of course. For example, the action is not limited to moving an agent, and may be an action as long as it acts on the environment. Further, for example, the observation symbols are not limited to those corresponding to the shape of the maze part, but may correspond to changes in light or sound.

  The series of processes described above can be executed by hardware, or can be executed by software. When the above-described series of processing is executed by software, a program constituting the software is installed in a computer incorporated in dedicated hardware. For example, a general-purpose personal computer 700 as shown in FIG. 52 that can execute various functions by installing various programs has a program that configures the software from a network or a recording medium. Installed.

  52, a CPU (Central Processing Unit) 701 executes various processes according to a program stored in a ROM (Read Only Memory) 702 or a program loaded from a storage unit 708 to a RAM (Random Access Memory) 703. To do. The RAM 703 also appropriately stores data necessary for the CPU 701 to execute various processes.

  The CPU 701, ROM 702, and RAM 703 are connected to each other via a bus 704. An input / output interface 705 is also connected to the bus 704.

  Connected to the input / output interface 705 are an input unit 706 composed of a keyboard, a mouse, etc., a display composed of an LCD (Liquid Crystal display), an output unit 707 composed of a speaker, etc., and a storage unit 708 composed of a hard disk. Yes. The input / output interface 705 is connected to a communication unit 709 including a network interface card such as a modem or a LAN card. The communication unit 709 performs communication processing via a network including the Internet.

  A drive 710 is connected to the input / output interface 705 as necessary, and a removable medium 711 such as a magnetic disk, an optical disk, a magneto-optical disk, or a semiconductor memory is appropriately mounted. Then, the computer program read from them is installed in the storage unit 708 as necessary.

  When the above-described series of processing is executed by software, a program constituting the software is installed from a network such as the Internet or a recording medium such as a removable medium 711.

  The recording medium shown in FIG. 52 is a magnetic disk (including a floppy disk (registered trademark)) on which a program is recorded, which is distributed to distribute the program to the user separately from the apparatus main body. Removable media consisting of optical disks (including CD-ROM (compact disk-read only memory), DVD (digital versatile disk)), magneto-optical disks (including MD (mini-disk) (registered trademark)), or semiconductor memory It includes not only those configured by 711 but also those configured by a ROM 702 in which a program is recorded, a hard disk included in the storage unit 708, and the like distributed to the user in a state of being incorporated in the apparatus main body in advance.

  Note that the series of processes described above in this specification includes processes that are performed in parallel or individually even if they are not necessarily processed in time series, as well as processes that are performed in time series in the order described. Is also included.

  The embodiments of the present invention are not limited to the above-described embodiments, and various modifications can be made without departing from the scope of the present invention.

  DESCRIPTION OF SYMBOLS 10 Autonomous behavior learning apparatus, 31 sensor part, 32 action output part, 33 observation buffer, 34 learning device, 35 recognizer, 36 action generator, 37 internal model data storage part, 38 recognition result buffer, 39 action output buffer

Claims (12)

Observation means for observing observation symbols based on sensor signals obtained from the environment;
Observation symbol storage means for storing the observation symbol observed over time in association with the time when the observation symbol was observed;
Recognizing means for reading information stored in the observation symbol storage means as time series information and recognizing a node of the HMM at the last time of the time series information;
The recognition means reads and recognizes the time-series information of variable length. The recognition means is
Based on the time series information, recognize a node sequence corresponding to the length of the time series information,
Based on the state transition probability and the observation probability of the HMM, it is determined that the node string exists in the environment with a probability equal to or higher than a first threshold, and the posterior probability of the node at the last time of the time series information Until the entropy value is below the second threshold,
The recognition apparatus according to claim 1, wherein a length of the time-series information read from the observation symbol storage unit is extended in a past direction. The recognition means is
Recognizing a node sequence corresponding to the length of the time series information based on the time series information extended in the past direction,
If it is determined in the environment that the node sequence does not exist with a probability equal to or higher than the first threshold based on the state transition probability and the observation probability of the HMM, the node at the last time of the time series information is: Recognize that it is an unknown node in the internal state to be newly added, and output it as a recognition result.
Based on the state transition probability and the observation probability of the HMM, it is determined that the node string exists in the environment with a probability equal to or higher than a first threshold, and the posterior probability of the node at the last time of the time series information 3. When it is determined that the entropy value is less than a second threshold, the node at the last time of the time-series information is recognized as a known node in the learned internal state and is output as a recognition result. The recognition device described in 1. The recognition apparatus according to claim 3, further comprising a recognition result storage unit that stores the recognition result in association with the recognized time. The recognition means is
Identifying the time when the recognition result stored in the recognition result storage means changes from a known node to an unknown node over time;
When the time series information that is temporally prior to the specified time is read by extending the length of the time series information read from the observation symbol storage means in the past direction,
The recognition apparatus according to claim 4, wherein output of the recognition result is suspended. The recognition means is
The difference between the entropy value of the posterior probability of the node at the last time of the time series information of length N and the entropy value of the posterior probability of the node at the last time of the time series information of length N + 1 Calculate
The recognition apparatus according to claim 1, wherein the length of the time-series information read from the observation symbol storage unit is extended in the past direction until the calculated difference becomes less than a third threshold. The recognition means is
Recognizing a node sequence corresponding to the length of the time series information based on the time series information extended in the past direction,
When it is determined in the environment that the node sequence exists with a probability less than a first threshold based on the state transition probability and the observation probability of the HMM,
The recognition apparatus according to claim 6, wherein the node at the last time of the time-series information is recognized as an unknown node having an internal state to be newly added. The recognition means is
In the environment, when it is determined that the node string exists with a probability equal to or higher than a first threshold based on the state transition probability and the observation probability of the HMM,
When the entropy value of the posterior probability of the node at the last time of the time series information is less than a second threshold, the node at the last time of the time series information is a known node in the learned internal state. Recognize and
The recognition apparatus according to claim 7, wherein when the entropy value of the posterior probability of the node at the last time of the time-series information is equal to or greater than a second threshold, the recognition result output is suspended. Action symbol storage means for specifying an action to be executed for the environment as an action symbol, and storing the action symbol obtained with the passage of time in association with the time at which the action is executed is further provided. ,
The recognition apparatus according to claim 1, wherein information having the same time length as information stored in the observation symbol storage unit is read from the action symbol storage unit and used as the time-series information. The information stored in the observation symbol storage means for storing the observation symbol based on the sensor signal obtained from the environment observed with the passage of time in association with the time when the observation symbol was observed is variable length Read as series information,
A recognition method for recognizing an HMM node at the last time of the time-series information. Computer
Observation means for observing observation symbols based on sensor signals obtained from the environment;
Observation symbol storage means for storing the observation symbol observed over time in association with the time when the observation symbol was observed;
Recognizing means for reading information stored in the observation symbol storage means as time series information and recognizing a node of the HMM at the last time of the time series information;
The recognition means is a program that functions as a recognition device that reads and recognizes the time-series information of variable length.   A recording medium on which the program according to claim 11 is recorded.

Images