An emergence of intelligent behavior within a simple robotic agent is studied in this paper. Two control mechanisms for an agent are considered - new direction of reinforcement learning called relational reinforcement learning, and a radial basis function neural network trained by evolutionary algorithm. Relational reinforcement learning is a new interdisciplinary approach combining logical programming with traditional reinforcement learning. Radial basis function networks offer wider interpretation possibilities than commonly used multilayer perceptrons. Results are discussed on the maze exploration problem.
to design intelligent agents. Several approaches have been studied so far. In our previous work, we have been examining mainly Evolutionary robotics (ER).
The ER approach attacks the problem through a self-organization process based on artificial evo-lu-tion [13]. Robot control system is typically realized by a neural network, which provides direct mapping from robot’s sensors to effectors. Most of current applications use traditional multi-layer perceptron networks. In our approach we utilize local unit network architecture called radial basis function (RBF) network, which has competitive performance, more learning options, and (due to its local nature) better interpretation possibilities [18, 19].
This article gives summary of our experiences and
comparison to Reinforcement Learning (RL) - another
widely studied approach in Artificial Intelligence. RL
is focusing on agent, that is interacting with the
environment by its sensors and effectors. This interaction
process helps agent to learn effective behavior. These
kinds of tasks are commonly studied on miniature
mobile robots of type Khepera [
solved the task, in which group of simulated Khepera robots were asked to find “food items” randomly distributed on an arena. The control system was developed by the artificial evolution. Our work with single robot and robot teams were published in [19, 18].
Reinforcement learning is gaining increasing attention in recent years. The basic overview of the field can be found in [20]. 3
The evolutionary algorithms (EA) [13, 12] represent a stochastic search technique used to find approximate solutions to optimization and search problems. They use techniques inspired by evolutionary biology such as mutation, selection, and crossover. The EA typically works with a population of individuals representing abstract representations of feasible solutions. Each individual is assigned a fitness that is a measure of how good solution it represents. The better the solution is, the higher the fitness value it gets. The population evolves toward better solutions. The evolution starts from a population of completely random individuals and iterates in generations. In each generation, the fitness of each individual is evaluated. Individuals are stochastically selected from the current population (based on their fitness), and modified by means of operators mutation and crossover to form a new population. The new population is then used in the next iteration of the algorithm.
Feed forward neural used as robot controllers are encoded in order to use them in the evolutionary algorithm. The encoded vector is represented as a floatingpoint encoded vector of real parameters determining the network weights.
Typical evolutionary operators for this case have been used, namely the uniform crossover and the mutation which performs a slight additive change in the parameter value. The rate of these operators is quite big, ensuring exploration capabilities of an evolutionary learning. A standard roulette-wheel selection is used together with a small elitist rate parameter. Detailed discussions about fitness function are presented in the next section. 4
π∗ = argmaxπV π(s), ∀s ∈ S
(3) To simplify the notation, let’s write V ∗(s) instead
∗ of symbol V π , value function corresponding to optimal strategy π∗.
The lack of theoretical insight into EA is the most
serious problem of the previous approach. The RL is V ∗(s) = maxπV π(s) (4)
based on dynamic programming [
The general model of agent-environment interac- π.
tion is modeled through the notion of rewards. The
essential assumption of RL states, that agent is able Qπ(s, a) = r(s, a) + γV π(s′), (5)
to sense rewards coming from the environment.
Rewards evaluate taken actions, agent’s task is to maxi- where s′ is the state, in which agent occurs taking
mize them. The next assumption is that agent is work- action a in state s (s′ = δ(s, a)).
ing in discrete time steps. Symbol S will denote finite It is probably most commonly used algorithm of
discrete set of states and symbol A set of actions. In RL, mainly because of its simplicity. However,
seveach time step t, agent determines its actual state and eral improvements have been suggested to speed up
chooses one action. Therefore, agent’s life can be writ- the algorithm. In real life applications, state space is
ten as a sequence usually too big and convergence toward optimal
strategy is slow. In recent years, there have been a lot of
o0a0r0s1a1r1... (1) efforts devoted to rethinking idea of states by using
function approximators [
Formally, agent’s task is to maximize The distinction between classical RL and Relational Reinforcement Learning is the way how the Qvalues are represented. In classical Q-learning algoV π(st) = rt + γrt+1 + γ2rt+2 + ... = X γirt+i (2) rithm are Q-values stored in the table. In relational i=0 version of the algorithm, they are stored in the struc
ture called Logical decision tree [8]. In our experiwhere the quantity V π(st) [16] is called discounted ments, we have used logical decision trees as implecumulative reward. It is telling us, what reward can mented in the programs TILDE [8] from package ACEbe expected, if the agent starts in state st and follows ilProlog [9]. policy π, 0 ≤ γ < 1 is a constant that determines the relative value of delayed versus immediate rewards.
The most serious assumption of RL algorithms is 5 Evolutionary RBF Networks the Markov property, which states, that agent does not need history of previous states to make decision. The Evolutionary robotics combines two AI approaches: decision of the agent is based on the last state st only. neural networks and evolutionary algorithms. Neural When this property holds, we can use theory coming network receives input values from robot’s sensors and from the field of Markov decision processes (MDP). it outputs control signals to the wheels. This way it re
The policy π, which determines what action is cho- alizes a control system of the robot. sen in particular state, can be defined as function π : Evolutionary algorithms [13, 12] are then used to S → A, where π(st) = at. Now, the agent’s task is to train such a network. It would be difficult to utilize the find optimal strategy π∗. Optimal strategy is the one, training by traditional supervised learning algorithms that maximalizes expected reward. In MDP, single op- since they require instant feedback in each step. Here timal deterministic strategy always exists, no matter we typically can evaluate each run of a robot as a in what state has the agent started. good or bad one, but it is impossible to assess each one
Optimal strategy π∗ can now be defined as move as good or bad. Thus, the evolutionary algorithm – for each s, a do • initialize the table entry Q′(s, a) = 0 • e = 0 – do forever • e = e + 1 • i = 0 • generate a random state s0 • while not goal(si) do ∗ select an action ai and execute it ∗ receive an immediate reward ri = r(si, ai) ∗ observe the new state si+1 ∗ i = i + 1 • endwhile • for j = i − 1 to 0 do ∗ update Q (sj , aj) = rj + γ maxa′ Q′(sj+1, a′)
′ represent one of the few possibilities, how to train the network.
The RBF network [17, 15, 10], used in this work, is In case of RBF networks learning, each individual a feed-forward neural network with one hidden layer encodes one RBF network. The individual consists of of RBF units and linear output layer. The network h blocks: function is given by Eq. (7). IRBF = {B1, . . . , Bh}, (8) y(x) = ϕ k x − c k
b h fs(x) = X wjsϕ j=1 k x − cj k bj , (6) (7) where fs is the output of the s-th output unit, y is the output of a hidden unit, ϕ is an activation function,
2 typically Gaussian function ϕ(s) = e−s . where h is a number of hidden units. Each of the blocks contains parameter values of one RBF units:
Bk = {ck1, . . . , ckn, bk, wk1, . . . , wkm},
(9) where n is the number of inputs, m is the number of outputs, ck = {ck1, . . . , ckn} is the k-th unit’s centre, bk the width and wk = {wk1, . . . , wkm} the weights connecting k-th hidden unit with the output layer. The parameter values are encoded using direct floatingpoint encoding.
We use standard tournament selection, 1-point crossover and additive mutation. Additive mutation changes the values in the individual by adding small value randomly drawn from h−ǫ, ǫi.
The fitness function should reflect how good the robot is in given tasks and so it is always problem dependent. Detailed description of the fitness function is included in the experiment section.
The evolutionary algorithm is summarised in Fig. 3. 6 Experiments
It works with a population of individuals representing
abstract representations of feasible solutions. Each in- In order to compare performance and properties of
dividual is assigned a fitness that is a measure of how described algorithms, we conducted simulated
expergood solution it represents. The evolution starts from iment. Miniature robot of type e-puck[
To stimulate maze exploration, agent is rewarded, when it passes through the zone. The zone is randomly located area, which can not be sensed by an agent.
Therefore, Δj is 1, if agent passed through the zone
Without any further preprocessing of sensor’s and in j-th trial and 0 otherwise. The fitness value is then effector’s values, the state space would be too big. computed as Therefore, instead of raw sensor values, learning algorithms worked with “perceptions”. Instead of 4095 4 raw sensor values, we used only 5 perceptions(table 1). F itness = X(Sj + Δj ), (10) Effector’s values were processed in similar way: instead j=1 of 2000 values, learning algorithm chosen from values where quantity Sj is computed by summing normal[−500, −100, 200, 300, 500]. To reduce the state space ized trial gains Tk,j in each simulation step k and trial even more, we grouped pairs of sensors together and j. back sensors were not used at all.
The agent was trained in the simulated
environment of size 100 x 60 cm and tested in more complex (11)
environment of size 110 x 100 cm. We used Webots
[
First component Vk,j is computed by summing ab- Sensor Width Motor solute values of motor speed in k-th simulation step left front right left right and j-th trial, generating value between 0 and 1. The VERYNEAR NEAR VERYFAR 1.56 500 -100 second component (1 − pΔVk,j ) encourages the two FEEL NOWHERE NOWHERE 1.93 -500 500 wheels to rotate in the same direction. The last com- FNEEEALR NNEOAWRHERE NNEOAWRHERE 00..2795 550000 --550000 ponent (1 − ik,j) supports agent’s ability to avoid ob- VERYFAR NOWHERE NOWHERE 0.16 500 500 stacles. The value ik,j of the most active sensor in k-th simulation step and j-th trial provides a conservative Table 2. Rules represented by RBF units (listed values measure of how close the robot is to an object. The are original RBF network parameters after discretization). closer it is to an object, the higher the measured value in range from 0 to 1. Thus, Tk,j is in range from 0 to 1, too.
The experiment was repeated 10 times, each run lasted 200 generations (each generation corresponding to 800 simulation steps). In all cases the successful behavior was found, i.e. the evolved robot was able to explore the whole maze without crashing to the walls.
See Fig. 7 for the mean, minimal and maximal fitness over 10 runs.
Fitness function min max mean shows average number of steps from each learning episode. It can be seen that after 10000 episodes, the agent has learned the successful behavior. This number roughly corresponds to the time complexity of the GA, where 200 populations of 50 individuals also result in 10000 simulations. The fitness of the solution found by RL is slightly better than the GA-found solution, on the other hand the inner representation of the neural network is much more compact.
900 800 700 600 300 200 100 s 500 p e tS 400 0 0 1000 2000 3000 4000 Ep5i0so0d0e 6000 7000 8000 9000 10000 700 600 500 s itsen 400 F 300 200
Table 2 and Figure 8 show parameters of an evolved network with five RBF units. For the sake of clarity, the parameters listed are also discretized. We can understand them as rules providing mapping from input sensor space to motor control. However, these ‘rules’ act in accord, since the whole network computes linear sum of the five corresponding gaussians. 6.2
Reinforcement learning
relational reinforcement learning algorithm described Fig. 9. Learning curve for Reinforcement Learning agent above under the same simulated environment and iden- averaged on 10 runs. tical conditions. The performance of the Reinforcement learning agent is shown on figure 9. The graph 8. H. Blockeel and L. De Raedt. Top-down induction of first order logical decision trees. Artificial Intelligence, This article presented survey of popular approaches 101:285–297, 1998. in mobile robotics used to robot behavior synthesis. 9. H. Blockeel, L. Dehaspe, B. Demoen, G. Janssens, J. Ramon, and H. Vandecasteele. Improving the efIn our future work, we would like to design hybrid ficiency of inductive logic programming through the intelligent system, combining the advantages of these use of query packs. Journal of Artificial Intelligence approaches. This way, agent would benefit from using Research, 16:135–166. three widely studied fields: Inductive Logic Program- 10. D.S. Broomhead and D. Lowe. Multivariable funcming, Neural Networks and Reinforcement Learning. tional interpolation and adaptive networks. Complex The Reinforcement Learning has strong mathematical Systems, 2:321–355, 1988. background. On the other side, in real experiments, 11. S. Dzeroski, L. De Raedt, and K. Driessens. Relational some of the assumptions are not realistic. Neural net- reinforcement learning. Machine Learning 43, pages works are very popular in robotics, because they pro- 7–52, 2001. vide straightforward mapping from input signals to 12. D. B. Fogel. Evolutionary Computation: The Fossil output signals, several levels of adaptation and are Record. MIT-IEEE Press, 1998. 13. J. Holland. Adaptation In Natural and Artificial Sysrobust to noise. Inductive logic programming allows tems. MIT Press, reprinted edition, 1992. agent to reason about states, thus concentrating at- 14. A. Martinoli. Swarm intelligence in autonomous Coltention on the most promising parts of the state space. lective robotics: from tools to the analysis and synthesis
The experiments showed that a preprocessing plays of distributed control strategies. Lausanne: Computer rather important role in the case of robotic agent con- Science Department, EPFL, 1999. trol. In our approach we have chosen a rather strong 15. J. Moody and C. Darken. Fast learning in networks of processing of inputs and outputs, which is suitable for locally-tuned processing units. Neural Computation, RL algorithms mainly. In our future work we would 1:289–303, 1989. like to study control with less preprocessed inputs/out- 16. S. Nolfi and D. Floreano. Evolutionary Robotics — The puts which can be used mainly for the neural network Biology, Intelligence and Techology of Self-Organizing controller. Also, another immediate work is to extract Machines. The MIT Press, 2000. 17. T. Poggio and F. Girosi. A theory of networks for the most frequently used state transitions from the approximation and learning. Technical report, CamRL algorithm and interpret them as rules in a similar bridge, MA, USA, 1989. A. I. Memo No. 1140, C.B.I.P. fashion we did with the RBF network. Paper No. 31. 18. S. Sluˇsny´ and R. Neruda. Evolving homing behaviour for team of robots. Computational IntelliAcknowledgements gence, Robotics and Autonomous Systems. Palmerston North : Massey University, 2007.
This work has been supported by the Ministry of Edu- 19. S. Sluˇsny´, R. Neruda, and P. Vidnerov´a. Evolution cation of the Czech Republic under the project Center of simple behavior patterns for autonomous robotic of Applied Cybernetics No. 1M684077004 (1M0567), agent. System Science and Simulation in Engineering. - : WSEAS Press, pages 411–417, 2007.
S. Sluˇsny´ been partially supported by 20. Richard S. Sutton and Andrew G. Barto. Reinforceby the Czech Science Foundation under the contract ment Learning: An Introduction. MIT Press, Camno. 201/05/H014G. bridge, MA, 1998. 21. C. J. Watkings. Learning from Delayed Rewards. PhD thesis, Cambridge University, 1989.