Файл: Embedded Robotics (Thomas Braunl, 2 ed, 2006).pdf

Trajectory Planning

computation is rather time consuming, this method has been substituted by simpler drive-and-turn algorithms when participating in robot soccer tournaments.

18.6.3 Ball Kicking

After a player has successfully captured the ball, it can dribble or kick it toward the opponent’s goal. Once a position close enough to the opponent’s goal has been reached or the goal is detected by the vision system, the robot activates its kicker to shoot the ball into the goal.

The driving algorithm for the goal keeper is rather simple. The robot is started at a position of about 10cm in front of the goal. As soon as the ball is detected, it drives between the ball and goal on a circular path within the defense area. The robot follows the movement of the ball by tilting its camera up and down. If the robot reaches the corner of its goal, it remains on its position and turns on the spot to keep track of the ball. If the ball is not seen in a pre-defined number of images, the robot suspects that the ball has changed position and therefore drives back to the middle of the goal to restart its search for the ball.

Figure 18.11: CIIPS Glory versus Lucky Star (1998)

If the ball is detected in a position very close to the goalie, the robot activates its kicker to shoot the ball away.

275

18 Robot Soccer

18.7 References

ASADA, M. (Ed.) RoboCup-98: Robot Soccer World Cup II, Proceedings of the Second RoboCup Workshop, RoboCup Federation, Paris, July 1998

BALTES, J. AllBotz, in P. Stone, T. Balch, G. Kraetzschmar (Eds.), RoboCup2000: Robot Soccer World Cup IV, Springer-Verlag, Berlin, 2001a, pp. 515-518 (4)

BALTES, J. 4 Stooges, in P. Stone, T. Balch, G. Kraetzschmar (Eds.), RoboCup2000: Robot Soccer World Cup IV, Springer-Verlag, Berlin, 2001b, pp. 519-522 (4)

BRÄUNL, T. Research Relevance of Mobile Robot Competitions, IEEE Robotics and Automation Magazine, vol. 6, no. 4, Dec. 1999, pp. 32-37 (6)

BRÄUNL, T., GRAF, B. Autonomous Mobile Robots with Onboard Vision and Local Intelligence, Proceedings of Second IEEE Workshop on Perception for Mobile Agents, Fort Collins, Colorado, 1999

BRÄUNL, T., GRAF, B. Small robot agents with on-board vision and local intelligence, Advanced Robotics, vol. 14, no. 1, 2000, pp. 51-64 (14)

CHO, H., LEE, J.-J. (Eds.) Proceedings 2002 FIRA World Congress, Seoul, Korea, May 2002

FIRA, FIRA Official Website, Federation of International Robot-Soccer Association, http://www.fira.net/, 2006

KITANO, H., ASADA, M., KUNIYOSHI, Y., NODA, I., OSAWA, E. RoboCup: The Robot World Cup Initiative, Proceedings of the First International Conference on Autonomous Agents (Agent-97), Marina del Rey CA, 1997, pp. 340-347 (8)

KITANO, H., ASADA, M., NODA, I., MATSUBARA, H. RoboCup: Robot World

Cup, IEEE Robotics and Automation Magazine, vol. 5, no. 3, Sept. 1998, pp. 30-36 (7)

ROBOCUP FEDERATION, RoboCup Official Site, http://www.robocup.org, 2006

276

Figure 19.1: Individual artificial neuron

Heaviside step function, with parameter U controlling the slope of the graph (usually set to 1).

1

0.8

0.6

0.4

0.2

Figure 19.2: Sigmoidal output function

19.2 Feed-Forward Networks

A neural net is constructed from a number of interconnected neurons, which are usually arranged in layers. The outputs of one layer of neurons are connected to the inputs of the following layer. The first layer of neurons is called the “input layer”, since its inputs are connected to external data, for example sensors to the outside world. The last layer of neurons is called the “output layer”, accordingly, since its outputs are the result of the total neural network and are made available to the outside. These could be connected, for example, to robot actuators or external decision units. All neuron layers between the input layer and the output layer are called “hidden layers”, since their actions cannot be observed directly from the outside.

If all connections go from the outputs of one layer to the input of the next layer, and there are no connections within the same layer or connections from a later layer back to an earlier layer, then this type of network is called a “feedforward network”. Feed-forward networks (Figure 19.3) are used for the sim-

278

Feed-Forward Networks

Figure 19.3: Fully connected feed-forward network

plest types of ANNs and differ significantly from feedback networks, which we will not look further into here.

For most practical applications, a single hidden layer is sufficient, so the typical NN for our purposes has exactly three layers:

• Input layer (for example input from robot sensors)

•Hidden layer (connected to input and output layer)

•Output layer (for example output to robot actuators)

Perceptron Incidentally, the first feed-forward network proposed by Rosenblatt had only two layers, one input layer and one output layer [Rosenblatt 1962]. However, these so-called “Perceptrons” were severely limited in their computational power because of this restriction, as was soon after discovered by [Minsky, Papert 1969]. Unfortunately, this publication almost brought neural network research to a halt for several years, although the principal restriction applies only to two-layer networks, not for networks with three layers or more.

In the standard three-layer network, the input layer is usually simplified in the way that the input values are directly taken as neuron activation. No activation function is called for input neurons. The remaining questions for our standard three-layer NN type are:

•How many neurons to use in each layer?

•Which connections should be made between layer i and layer i + 1?

•How are the weights determined?

The answers to these questions are surprisingly straightforward:

•How many neurons to use in each layer?

The number of neurons in the input and output layer are determined by the application. For example, if we want to have an NN drive a robot around a maze (compare Chapter 15) with three PSD sensors as input

279

19 Neural Networks

and two motors as output, then the network should have three input neurons and two output neurons.

Unfortunately, there is no rule for the “right” number of hidden neurons. Too few hidden neurons will prevent the network from learning, since they have insufficient storage capacity. Too many hidden neurons will slow down the learning process because of extra overhead. The right number of hidden neurons depends on the “complexity” of the given problem and has to be determined through experimenting. In this example we are using six hidden neurons.

•Which connections should be made between layer i and layer i + 1?

We simply connect every output from layer i to every input at layer i + 1. This is called a “fully connected” neural network. There is no need to leave out individual connections, since the same effect can be achieved by giving this connection a weight of zero. That way we can use a much more general and uniform network structure.

•How are the weights determined?

This is the really tricky question. Apparently the whole intelligence of an NN is somehow encoded in the set of weights being used. What used to be a program (e.g. driving a robot in a straight line, but avoiding any obstacles sensed by the PSD sensors) is now reduced to a set of floating point numbers. With sufficient insight, we could just “program” an NN by specifying the correct (or let’s say working) weights. However, since this would be virtually impossible, even for networks with small complexity, we need another technique.

The standard method is supervised learning, for example through error backpropagation (see Section 19.3). The same task is repeatedly run by the NN and the outcome judged by a supervisor. Errors made by the network are backpropagated from the output layer via the hidden layer to the input layer, amending the weights of each connection.

right wheel right

Figure 19.4: Neural network for driving a mobile robot

280

Feed-Forward Networks

Evolutionary algorithms provide another method for determining the weights of a neural network. For example, a genetic algorithm (see Chapter 20) can be used to evolve an optimal set of neuron weights.

Figure 19.4 shows the experimental setup for an NN that should drive a mobile robot collision-free through a maze (for example left-wall following) with constant speed. Since we are using three sensor inputs and two motor outputs and we chose six hidden neurons, our network has 3 + 6 + 2 neurons in total. The input layer receives the sensor data from the infrared PSD distance sensors and the output layer produces driving commands for the left and right motors of a robot with differential drive steering.

Let us calculate the output of an NN for a simpler case with 2 + 4 + 1 neurons. Figure 19.5, top, shows the labelling of the neurons and connections in the three layers, Figure 19.5, bottom, shows the network with sample input values and weights. For a network with three layers, only two sets of connection weights are required:

Figure 19.5: Example neural network

281