Preview only show first 10 pages with watermark. For full document please download

Development Of Algorithms And An Interface For Remote Control,

Rating
Date

November 2018
Size

631.9KB
Views

1,281
Categories

Computers & electronics Computers PC/workstation barebones

Transcript

Teaching through demonstration of a RoboCup goalkeeper robot by Stoyan Hristov Georgiev 17006 Master Thesis Submitted to the University of Applied Sciences Ravensburg-Weingarten in a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.) in Mechatronics 30.04.2007 Thesis Committee: Prof. Dr. Wolfgang Ertel Prof. Dr. Holger Voos Hochschule Ravensburg-Weingarten Teaching through demonstration of a RoboCup goalkeeper robot 1 I hereby declare that this master thesis is the result of my own work. It was conducted without any external help. References and literatures that were used are clearly listed without omission at the end of this report. Weingarten April 30, 2007 ...................................... Stoyan Hristov Georgiev Teaching through demonstration of a RoboCup goalkeeper robot 2 Table of contents 1 INTRODUCTION.................................................................................................................................................... 7 1.1 1.2 1.3 1.4 2 Motivation........................................................................................................................................................... 7 RoboCup project................................................................................................................................................. 8 Project necessity..................................................................................................................................................9 Objectivities...................................................................................................................................................... 10 REMOTE ROBOT CONTROL............................................................................................................................11 2.1 General overview.............................................................................................................................................. 11 2.2 Working environment........................................................................................................................................11 2.2.1 Programming language.............................................................................................................................. 12 2.2.2 Network programming ..............................................................................................................................12 2.3 Joystick control................................................................................................................................................. 13 2.3.1 Joystick requirements.................................................................................................................................13 2.3.2 Joystick features.........................................................................................................................................13 2.3.3 Simple DirectMedia Layer.........................................................................................................................15 2.4 Data manipulation on the remote application side............................................................................................ 15 2.4.1 Data conversion......................................................................................................................................... 15 2.4.1.1 Move in X and Y direction.................................................................................................................16 2.4.1.2 Robot speed........................................................................................................................................ 17 2.4.1.3 Robot rotation.....................................................................................................................................18 2.4.1.4 Rotation speed.................................................................................................................................... 19 2.4.1.5 Kicker and arms activation.................................................................................................................19 2.4.2 Data storage and data transfer....................................................................................................................19 2.5 Data manipulation on the robot side................................................................................................................. 20 2.5.1 Distance to the ball ................................................................................................................................... 20 2.5.2 Angle to the ball.........................................................................................................................................21 2.5.3 Ball speed ..................................................................................................................................................22 2.5.4 Ball direction............................................................................................................................................. 22 2.5.5 Robot movement........................................................................................................................................23 2.6 GUI....................................................................................................................................................................24 2.6.1 Graphical application.................................................................................................................................24 2.6.1.1 QT.......................................................................................................................................................25 2.6.1.2 GTK+................................................................................................................................................. 26 2.6.1.3 X window........................................................................................................................................... 27 2.6.1.4 Motif...................................................................................................................................................28 2.6.1.5 Conclusion..........................................................................................................................................28 2.6.2 GUI functionality....................................................................................................................................... 29 2.6.2.1 Requirements......................................................................................................................................29 2.6.2.2 Features.............................................................................................................................................. 29 2.6.3 Decorator design pattern ...........................................................................................................................30 3 ROBOT TEACHING............................................................................................................................................. 31 3.1 3.2 3.3 Machine learning...............................................................................................................................................31 Teaching through demonstration.......................................................................................................................32 Decision tree learning technique....................................................................................................................... 33 Teaching through demonstration of a RoboCup goalkeeper robot 3 3.4 C4.5 – decision tree method..............................................................................................................................34 3.4.1 Description.................................................................................................................................................34 3.4.2 File formats................................................................................................................................................ 35 3.4.3 Options.......................................................................................................................................................36 3.4.4 Pruning decision trees................................................................................................................................36 3.4.5 Error rates estimation.................................................................................................................................37 3.5 Conclusion.........................................................................................................................................................37 4 PRACTICAL IMPLEMENTATION AND RESULTS.......................................................................................39 4.1 Teaching process............................................................................................................................................... 39 4.1.1 Who to teach.............................................................................................................................................. 39 4.1.2 What to teach............................................................................................................................................. 39 4.1.3 How to teach.............................................................................................................................................. 40 4.1.4 Problems.................................................................................................................................................... 41 4.2 Teaching data ................................................................................................................................................... 43 4.2.1 Data gathering............................................................................................................................................43 4.2.2 Data evaluation.......................................................................................................................................... 44 4.2.3 Data preprocessing.....................................................................................................................................45 4.3 Behaviour learning............................................................................................................................................ 46 4.3.1 Generation of a decision tree with C4.5 ....................................................................................................46 4.3.2 Manual optimization.................................................................................................................................. 47 4.3.3 Decision tree interpretation........................................................................................................................47 4.4 Teaching vs. Manual Programming ................................................................................................................. 48 4.4.1 Features of teaching through demonstration process................................................................................. 48 4.4.2 Features of manual programming process ................................................................................................ 49 4.4.3 Conclusion................................................................................................................................................. 50 5 TESTING.................................................................................................................................................................51 5.1 5.2 5.3 Application testing............................................................................................................................................ 51 Behaviour testing...............................................................................................................................................52 Conclusion.........................................................................................................................................................54 6 CONCLUSION...................................................................................................................................................... 56 7 FUTURE ISSUES................................................................................................................................................... 57 8 APPENDIX..............................................................................................................................................................58 8.1 Joystick configuration....................................................................................................................................... 58 8.2 SDL................................................................................................................................................................... 58 8.2.1 Installation................................................................................................................................................. 58 8.2.2 Configuration............................................................................................................................................. 58 8.2.2.1 Bild & Run SDL.................................................................................................................................58 8.2.2.2 Add SDL to the project...................................................................................................................... 59 9 GLOSSARY............................................................................................................................................................ 61 10 USED LITERATURE.......................................................................................................................................... 62 Teaching through demonstration of a RoboCup goalkeeper robot 4 List of figures FIGURE 1 CUNIBERT – MIDDLE SIZE LEAGUE GOALKEEPER ROBOT........................................................ 9 FIGURE 2 REMOTE JOYSTICK CONTROL (GENERAL OVERVIEW).............................................................11 FIGURE 3 JOYSTICK (MC 18)....................................................................................................................................14 FIGURE 4 JOYSTICK STICK MOVEMENT............................................................................................................ 14 FIGURE 5 ROBOT SPEED........................................................................................................................................... 18 FIGURE 6 BALL ANGLE..............................................................................................................................................21 FIGURE 7 BALL DIRECTION..................................................................................................................................... 22 FIGURE 8 X WINDOW SYSTEM – CLIENT-SERVER........................................................................................... 27 FIGURE 9 GUI FOR A ROBOT REMOTE CONTROL............................................................................................29 FIGURE 10 EXAMPLE FOR DECORATOR DESIGN PATTERN......................................................................... 30 FIGURE 11 EXAMPLE OF DECISION TREES........................................................................................................ 33 FIGURE 12 SIMPLE TEACHING BEHAVIOR......................................................................................................... 40 FIGURE 13 ROTATION PROBLEM...........................................................................................................................42 FIGURE 14 C4.5 INFLUENCE OF THE 'M' PARAMETER....................................................................................46 List of tables TABLE 1 DATA FORMAT READ FROM THE JOYSTICK .................................................................................. 15 TABLE 2 DATA FORMAT USED FOR ROBOT NAVIGATION ...........................................................................16 TABLE 3 TEACHING DATA FORMAT..................................................................................................................... 20 TABLE 4 TEACHING MOVEMENT COMMAND FORMAT................................................................................ 23 TABLE 5 C4.5 OPTIONS...............................................................................................................................................36 TABLE 6 FEATURES OF TEACHING THROUGH DEMONSTRATION PROCESS.........................................48 TABLE 7 FEATURES OF MANUAL PROGRAMMING PROCESS ..................................................................... 49 Teaching through demonstration of a RoboCup goalkeeper robot 5 Acknowledgements I give special thanks to Prof. Dr. Wolfgan Ertel for giving me the possibility to work over this project and for accepting to be my supervisor. I am grateful to Arne Usadel and Joachim Fessler for their support and helpful advises concerning the easy and unproblematic work flow over the project and for their help during the whole implementation process. I would also like to thank all members of the RoboCup team for helping me teaching the robot and gathering required test data. I would like to express my appreciation to Dilip Gadipudi for his constructive comments and suggestions concerned the final documentation. Finally I would like to express my deepest gratitude to my family for their understanding and general support, to Carmen Mack for her encouragement and support, and to all my friends in Weingarten for the great time that we spent together and for the great memories that I will keep forever. Teaching through demonstration of a RoboCup goalkeeper robot 6 1 Introduction 1.1 Motivation Nowadays the technology is far away than ever and any kind of robots and machines are used to make the life of the people easier and better. Robots could be used not only in high technology areas or for scientific purposes, but also in entertainment industry or even they could become members of the family (e.g. dog robots). Some robots could even participate in sport competitions for robots and in the near future they could even play against humans. In order to reach the robots such a level of intelligence, new and modern artificial intelligence techniques are applied. One of the possibility techniques is to teach the robots to behave properly. The topic of this master thesis is teaching through demonstration of a goalkeeper robot and includes development of algorithms and an interface for remote control, observation and teaching of the robot. • Interface – Software application or hardware device used to link two or more applications, equipments, systems or devices. It might be a convention used to allow proper interconnection or communication between two software systems. The term interface can also be used to describe the look and layout of a program on the screen for interaction with the user. • Remote control – A program or a device that has the ability to control a computer system or a device from a remote location. The term is most commonly used to refer to a remote control for the televisions or other electronics devices such as DVD or stereo systems. Most often the remote communication is done via infrared signals or radio signals. In our case under the term 'remote device' we should understand a joystick device for remote control. The remote communication is done via WLAN (Wireless local area network). • Observation – Viewing or noting a fact or an occurrence of some scientific process and taking note of anything it does. To improve the accuracy and quality of the information obtained during the observation, very often additional instruments are required, like cameras, telescopes and etc. In the scope of the project, the data regarding the environment ( e.g. location and behavior of the other objects in the football field (ball, goal) ), will be saved in an external file and later on will be used for teaching the robot. • Teaching – The ability to explain clearly certain information to others, so they can learn something new. There are different ways of teaching and to decide what teaching method to use, different issues have to be taken under consideration (e.g. who we want to teach, background knowledge, teaching environment, leaning goals, abilities to accept incoming information). In the project, under the term 'teaching' we have to understand 'teaching Teaching through demonstration of a RoboCup goalkeeper robot 7 through demonstration', where a human trainer demonstrates the correct behavior that the goalkeeper robot has to learn. • Goalkeeper robot – A robot that behaves autonomous as a goalkeeper with the main task to protect the goal. The goalkeeper is the only member of the team that can use its hands within the field, although only within the penalty area. 1.2 RoboCup project Since year 2003 Hochschule Ravensburg-Weingarten is participating in the RoboCup Project. Our current target is to develop a goalkeeper robot, for the middle size league, that should move, behave and play football autonomously. According to RoboCup regulations [RCrules] there are some specific limitations for the robots who participate in the middle size league. • Size – Each robot must possess a configuration of itself and its actuators, where the projection of the robot's shape onto the floor fits into a square of size at least 30cmX30cm and at most 50cmX50cm. • Height – At least 40cm and at most 80cm. • Weight – The maximum weight of a robot could be 40kg • Shape – Any shape is allowed as long as the size restrictions are not violated. Robots may exhibit concavities in their shape, or may dynamically change shape. • Space occupied by a robot – The area occupied by the convex hull around the projection of the robot's shape onto the floor. For measuring the space occupied by a robot could be used one of the following methods: - The smallest rectangular box enclosing the robot is determined. - The smallest circle enclosing the robot is determined. • Color – The base color of a robot's body must be black Following this RoboCup regulations our goalkeeper robot (Cunibert) has been constructed. For development of a soccer robot, there are several important key components such as good mechanical design and stability, reliable hardware and software, fast vision and object recognizable system, and last but not least intelligent behavior. Teaching through demonstration of a RoboCup goalkeeper robot 8 Figure 1 Cunibert – middle size league goalkeeper robot For all robots participating in RoboCup tournament there are additional regulations [RCrules] regarding the way they are designed: 1.3 • Safety – Do not damage other robots or objects on the playground, or pose a threat to the audience, to the referees, or human team members • Jamming – Designed and programmed such that they try to avoid interference concerning the operation of sensor systems and/or communication devices • Robustness – Physical integrity of the robot is not endangered by incidental, accidental, or intentional collisions with the ball or objects of the field, or other robots • No additional remote control – Only artificial intelligence • Robots may send arbitrary kinds and amounts of data to remote computers. However, bandwidth restrictions may apply in order to ensure safe and robust game operation. • Robots may receive data from remote computers, if the data is sent by an autonomous remote program (without any means of human interaction) • Internal communication in the robot team is allowed (e.g. via wireless communication e.g. IEEE 802.11a and/or 802.11b) • Follow the official football rules Project necessity So far the robot behavior is implemented manually by a programmer. He should evaluate alone the all possible states of the robot and should write the source code by hand. Of course, it is not possible to define correctly any single state in which the robot could be involved. To improve the robot behavior we decided to evaluate and implement a different method for development of a Teaching through demonstration of a RoboCup goalkeeper robot 9 goalkeeper behavior. The method used by us is teaching through demonstration, where a human trainer demonstrates the correct behavior that the goalkeeper robot has to learn. 1.4 Objectivities The objective of this master thesis is development of algorithms and an interface for remote control, observation and teaching through demonstration of a goalkeeper robot. There are two main objectivities that should be achieved • Remote robot control – control the robot remotely via a joystick. The data from the joystick is not sent directly to the motor controller of the robot, but rather is sent to the robot software application. The target that we want to achieve with this way of communication is to have at any single moment in the software application data concerning the robot movement. If the movement data is sent directly to the omnidrive, the main software application would not have information regarding those data. Later on, the movement data and the vision data will be stored in a file and used for the teaching of the robot. • Teaching through demonstration – It is an artificial intelligence and machine learning technique. The user demonstrates the desired behavior by dictating the agent’s actions with the help of remote control device. During the demonstration process a data for the behavior and location of the robot and the other surrounding objects is saved. Later on, the data is generalized and evaluated with the help of additional decision making program, which generate a decision tree. The produced tree is used for the implementation of the final goalkeeper behavior. In Chapter 2 we introduce how our robot is remotely controlled with a joystick. Theoretical definitions and explanations regarding the robot teaching process and some machine learning methods and teaching techniques are covered in chapter 3. Chapter 4 contains descriptions regarding the practical implementation of the teaching and learning process. Theoretical comparison between the taught and manually programmed behavior is made. Explanations regarding the testing of the main software applications on the remote control side and on the robot side are covered in chapter 5. Additionally, description of the behavior testing process is included. Chapter 6 contains a general conclusion concerned the main aspects of the Master thesis. In chapter 7, some future issues are proposed. They should be taken under consideration, when someone continues to work on this project. Teaching through demonstration of a RoboCup goalkeeper robot 10 2 2.1 Remote robot control General overview The proposed solution for remote control is based on a wireless communication between a remote computer and a robot. A joystick is connected via USB connection to a computer, on which a software application is located. The application reads data from the joystick converts the data to an appropriate format and sends it via WLAN (wireless local area network) to the robot. On the robot side another software application is located, which retrieves the incoming data from the remote computer and sends control commands for movement of the robot in a defined direction. Figure 2 Remote joystick control (general overview) 2.2 Working environment For practical implementation of the proposed solution for remote control, the working environment has to be defined and set. The operating system on the computer for remote control and on the robot side is Linux. On the robot side computer, Debian Linux is installed and configured for full support and interoperability with the used hardware (e.g. WLAN connection, USB and Firewire support, and etc.). On the computer for remote control could be installed any Linux OS (e.g. Fedora Core 4, Debian or Teaching through demonstration of a RoboCup goalkeeper robot 11 Ubunto) with WLAN connection and USB support for the joystick. Additional library is installed for manipulation of the joystick data. For the used operating system, proper programming languages have to be selected. 2.2.1 Programming language As a main programming language C++ [C++] is be used. It is a high-level programming language supporting procedural programming, data abstraction and object-oriented programming. It is developed as an enhancement of the C programming language, and since then is one of the most popular programming languages. C++ is well documented and has a large selection of literature. Additionally provide huge amount of standard libraries, including libraries for networks, GUI, threads and etc. Another reason to choose C++ as a programming language, additionally to the mentioned advantageous is that we have used C++ as a programming language for development of the main software application on the robot side. To be consistent and to avoid any possible further incapability between the existing application and the newly developed application, we decided to continue with the usage of C++ as a main programming language. In the newest software version, additionally to the main programming language, the Python [Python] programming language is used. The Python is an interpreted, interactive, object-oriented programming language and is used together with C++ i.e. the main software application on the robot side is still written in C++ and Python is used only for manipulation of the incoming vision and joystick data and for implementation of the robot behavior. In the previous software version the only used programming language was C++. 2.2.2 Network programming In C++, all network connections are seen as streams of data and can be manipulated as streams. For example, the copy of one file from one computer to another computer in the same local network is implemented as a simple stream from one computer to the other. C++ is not dealing with low level details and programming, as segmentation of TCP packets. The only thing that has to be known is the IP address of the receiver, the port which will handle all the incoming data and the transport protocol (TCP, UDP). The Socket class allows to open a socket listener on a selected port and to listen for incoming connections. When a client socket on a remote host attempts to connect to that port, the server negotiates the connection with the client and opens a regular socket between the two hosts. Hence, a socket is not a physical device, but a compound programming structure, which consists of information for an IP address, port and transport protocol (e.g. TCP or UDP). It is used for establishing point-to-point communications, between different applications on different computers in a network. Teaching through demonstration of a RoboCup goalkeeper robot 12 The three components that are necessary to establish a socket connection are an IP address, port number and transport protocol. In this case the term port represents an endpoint or "channel" for network communications. Port numbers allow different applications on the same computer to utilize network resources without interfering with each other, i.e. it is possible to run different services and applications on the same computer but on different ports. It is also possible to run two services on one port, but to use different transport protocols - TCP or UDP. Usually when sockets are used, it is recommended to use threads so that different threads are dealing with different requests for connections and the server can continue listening for new incoming connection requests. Threads allow running different parts of the program simultaneously in the same address space as the main application. 2.3 Joystick control To control the robot remotely a proper joystick has to be connected to the remote system. The joystick has to fulfill specific requirements regarding the number of used axes and buttons. After a successful connection with the remote system the data from the joystick have to be read and retransferred to the robot via wireless connection. To read properly the data from the joystick an external library (SDL chapter 2.3.3) is used. 2.3.1 Joystick requirements To fulfill the requirements for controlling the robot remotely, the joystick should have at least 3 axes and 4 buttons. Two axes are used for movement of the robot in X and Y direction (left, right, front, back, etc. ) The third axis is used for rotation of the robot (left or right). The four buttons are for the kicker, left, right and top arms. The joystick should use a standardized interface (e.g. USB) for connection and communication with the computer to which it is connected. 2.3.2 Joystick features According to the specification, the used joystick has the following features: [MC] • 7 axes and 7 buttons. • Large, clear LCD multy-data display for adjustment of programs as well as input and viewing of data. • Adjustable precision, height and spring centering force control sticks with electronic trim. • High speed CPU with 10 bit A/D converter. Teaching through demonstration of a RoboCup goalkeeper robot 13 • 9,6V battery power supply Figure 3 Joystick (MC 18) The joystick has two control sticks for control in four different axes. If the right sticks is moved on in axis 3 (up and down direction) and then released it would continue to stay in that position and will not return automatically to its neutral position. This could be useful if we would like to have continuous movement in a defined direction. If the right sticks is moved on in axis 1 (left and right direction) or the left stick is moved on in any direction and then released it will return to its neutral position. We should apply continuous pressure to the stick as long as we want an action to be performed. Figure 4 Joystick stick movement The joystick uses an USB interface for connection and communication with the computer, to which it is connected. For some Linux versions (e.g. Ubunto), it is sufficient to plug the joystick USB connection and it will be recognized automatically and ready to use. For some other Linux versions (e.g. Fedora Core 4) a manual configurations have to be done. Fully explained manual configuration is appended to the appendix. Teaching through demonstration of a RoboCup goalkeeper robot 14 2.3.3 Simple DirectMedia Layer To access and read data from the joystick a Simple Direct Media Layer (SDL) is used. The library has the following characteristics:[SDL] 2.4 • Cross platform – The current version supports Linux, Windows, BeOS, MacOS, Mac OS X, FreeBSD, OpenBSD, BSD/OS, Solaris, IRIX, and QNX.The code contains support for Windows CE, AmigaOS, Dreamcast, Atari, NetBSD, AIX, OSF/Tru64, and SymbianOS, but these are not yet officially supported. • Multimedia library – Provide low level access to audio, keyboard, mouse, joystick, CDROM, 3D hardware via OpenGL, and 2D video frame buffer in a portable manner. • Open-source and licensed under the LGPL • Written in C and has bindings with almost every programming language there is (e.g. C++, Perl, Python, Pascal etc.) • Simplicity • Huge number of third party extensions that make it easy to do more advanced functions Data manipulation on the remote application side The remote control application should first connect via wireless network to the robot application and then should send control data regarding proper behavior of the robot. In order to interpret the data correctly, it should be in a proper format. 2.4.1 Data conversion With the usage of SDL library we can read the data from the joystick, but this data could not be resend to the robot in the read format, because it is not "understandable" for the robot. The data read from the joystick is in the following format (after proper calibration). Joystick part Data format axis -32767 .. 32767 (min / max) button 0 ..1 (off / on) Table 1 Data format read from the joystick Teaching through demonstration of a RoboCup goalkeeper robot 15 The data have to be converted to the following format, which is used for robot navigation: Variable name Variable description go_to_X 1..127 - move right, 128..255 - move left go_to_Y 1..127 - move front, 128..255 - move back speed 1..100 - speed ( in %) rotation 0 - don't rotate, 1 - rotate right, 2 rotate left rotation_speed 1..100 - speed ( in %) kicker 0 - not active, 1 - active left_arm 0 - not active, 1 - active right_arm 0 - not active, 1 - active top_arm 0 - not active, 1 - active Table 2 Data format used for robot navigation 2.4.1.1 Move in X and Y direction The go_to_X and go_to_Y values define only the direction in which the robot should move, rather than the distance to which he should move. The proposed solution has been chosen, because we want to move the robot in a certain direction as long as a stop command or a different direction is defined. After calibration, the MAX X and Y position is set to 32767 and relatively the MIN position is set to -32767. If the robot has to move in X or Y direction, it expects the value to be in the range 1...255, rather than in the interval between -32767 and 32767. To convert the read X and Y position and make it understandable for the robot the following formula is used: ∣Xjoy∣ Xmax = goToX , from where we could find the "goToX" value. 127 To move the robot into the right direction the goToX value should be in the interval 0 to 127, otherwise to move it into the left direction the value should be in the interval 128 to 255 (128 + goToX ) The same formula is used for the calculation of "goToY", but appropriate data is read from the Y axis. To move the robot forward, the goToY value should be in the interval 0 to 127, otherwise to move it back the value should be in the interval 128 to 255 (128 + goToY ) Teaching through demonstration of a RoboCup goalkeeper robot 16 2.4.1.2 Robot speed The value defines the speed with which the robot would move from one point to another. The speed range is between 1 and 100%. The robot would not move at all if the speed is set to 0%. To find the correct robot speed, the following calculations have to be done. X - position read from the joystick Y - position read from the joystick Xmax, Ymax = abs(Xmax, Ymax) 100 – max speed in % speed  X 2Y 2  = 2 2 100  Xmax Ymax  , main formula for calculation of the speed The values of the X and Y are always available, because we read them directly from the joystick, but the values of Xmax or Ymax are not always available. They depend of the values of X and Y and there are three possible variants to find them. • abs(X)=abs(Y) We use the main formula for calculation of the speed, where Xmax = Ymax = 32767 • abs(X)> abs(Y) Xmax = 32767, Ymax = unknow ∣X ∣ ∣Y ∣ = Xmax , from where we could find the Ymax. Ymax After that we substitute the available values in the main speed formula • abs(X) < abs(Y) Xmax = unknow, Ymax = 32767 ∣X ∣ Xmax = , from where we could find the Xmax. ∣Y ∣ Ymax After that we substitute the available values in the main speed formula Teaching through demonstration of a RoboCup goalkeeper robot 17 Figure 5 Robot speed Due to fact that close to the neutral joystick point the controlling stick is very sensitive, it is possible any movement of the stick to change the robot movement direction. To avoid this, if the speed value is less than 10% we will truncate it to zero (0%). This action would prevent sending of unrequited data, because of unwanted or unexpected stick movements. The speed truncation would also avoid the unnecessary overload of the motor. 2.4.1.3 Robot rotation For a goalkeeper robot it is important, not only to move in the right direction, but also to look in the right direction. The kicker of the robot should look in the direction in which the ball is located. When the ball is close enough, it should be immediately kicked away from the goal. The data regarding proper rotation of the robot is read from a separate joystick axis. Depend of the sign of the read data value the robot rotates right (positive value) or left (negative value). The robot will keep on rotate until he receives a rotation command equal to 0 (do not rotate anymore). At this state of the project the robot could not move and rotate at the same time. The robot should first move to the required position and then rotate. In the next software version of the omnidrive controlling application, a simultaneous movement and rotation of the robot will be possible. Teaching through demonstration of a RoboCup goalkeeper robot 18 2.4.1.4 Rotation speed The data read from the joystick rotation axis could be used not only for defining the rotation direction, but also for defining the rotation speed. To do this, the data from the rotation axis is read and converted to an appropriate data format. Due to the fact that the robot have to rotate itself faster or slower in different playing situation, the rotation speed is important for the overall robot performance and for the fast robot reaction in different situations. The rotation speed formula is: ∣Rjoy∣ Rmax = speed , where 100 Rjoy – the value read from the rotation axis Rmax – the MAX value of the rotation axis (after proper calibration, the value should be 32767) 100 – max speed value in % speed – the actual robot speed 2.4.1.5 Kicker and arms activation According to the robot middle size league rules, the goalkeeper could use its “arms” for a limited period of time. The robot should be located in the goalkeeper field and can extend left, right or top arm for max 2 seconds. To avoid an unnecessary usage of the arms, they should be activated only if the ball is close enough to be touched. The usage of the arms should be forbidden outside of the goalkeeper field. The kicker or the arms (left, right or top) will be activated if a defined button is pressed. A button is considered as pressed, if the value read from the joystick for this button is 1. 2.4.2 Data storage and data transfer After the joystick data is read, it has to be temporary stored somewhere, because it is possible that we could read and convert joystick data faster than we could send it to the robot. In this case, a data could be lost. To prevent this, data first is stored in a vector (a template container that could be used to store similar typed objects sequentially, which can be accessed at a later point of time), from where later on is read and retransferred to the robot. The read data first is converted to a format, which would be "understandable" for the robot. The next step is to check whether the previous saved object already consist the same data that we currently want to store in the vector. If this is the case, the read and converted data from the joystick is not stored in the vector, but simply omitted. The purpose of this data checking is to prevent resent of objects that contains the same data, which could overload the traffic over the wireless network. Teaching through demonstration of a RoboCup goalkeeper robot 19 After an object is ones stored in the vector, it stays there until the send thread reads it. After that the object is resend it to the robot. Once the object is read, it will be removed from the vector and the next object will be available for manipulation. 2.5 Data manipulation on the robot side On the robot side a server is started and listens for incoming connection for remote control. The server listens on port 6000 and after a connection is accepted all received data is manipulated on the top layer of the software architecture. Then control commands are sent to the CAN controller, for further motor control. As long as the robot is controlled remotely the data regarding the behavior of the ball and the distance to the goal center is gathering by the vision system of the robot, while the actual action performed of the goalkeeper is incoming from the remote control application. We are also interesting of the location and behavior of the other robots in the field, but on the current state of the project we do not have information regarding their location or behavior. 30 lines of data are stored in a file every second. The format of the data is: Data name Description Ball distance 0 ... 9000 mm Ball angle 0 ... 360° Ball speed >= 0 m/s Ball moving direction -1 ... 360° Goal center -4000 ... 4000 mm Action Ls, Lf, Rs, Rf, S Table 3 Teaching data format ball distance, ball angle, ball speed, ball moving direction, goal center, action 1514.41582, 352, 5.028209, 175, -168.62326, Lf 1400.02876, 352, 3.700141, 175, -112.42776, Ls 1251.84418, 351, 3.540512, 176, -81.080322, S 2.5.1 Distance to the ball The value represents the absolute distance of the ball. We have X and Y coordinate of the ball and the distance is calculated according to the Pythagorean Theorem. ball distance = Xball 2Yball 2 Xball – X distance to the ball , Yball – Y distance to the ball Teaching through demonstration of a RoboCup goalkeeper robot 20 2.5.2 Angle to the ball The function returns the absolute angle at which the ball is located to the robot. The robot looking direction (kicker direction) is defined as 0°. At current state of the project the robot should move only in two directions (left and right) and should not rotate. The kicker direction should always look in the opponent team goal direction. To find the correct angle we have used the aran2(x, y) function: angle_rad = atan2( X, Y) The function returns the angle in radians and the result is between -pi and pi (i.e. -180° and 180°). The signs of the both inputs are known to the function, so it can compute the correct quadrant for the angle. As input of the function we have to pass the real sign values of the ball position, rather than the absolute values. To convert the radians angle in degrees the following formula is used. angle_degree = (int)( angle_rad * 180 / pi), where pi = 3,14159265 We would like the value of the angle to be in the range 0 to 360°, rather than between -180° and 180°. In next stage of the project we could use this value to rotate the robot in ball direction. Only if the value is positive, we could directly resend it to the CAN driver for later robot control. If the angle value is already positive, then we do not modify it, otherwise we use the following formula. angle_degree = 360 + angle_degree Figure 6 Ball angle Teaching through demonstration of a RoboCup goalkeeper robot 21 2.5.3 Ball speed The value represents the speed with which the ball is moving from on point to another. In the first version of the robot software architecture, the following formula was used for calculation of the ball speed: V = S/T [mm/frame] We need to know the distance that the ball would take for the time that the vision system would make two frames. The distance could be calculated, if we know the current ball position and the previous ball position (ball position on the previous frame). S (distance) =  Xdiff 2Ydiff 2 , where Xdiff Ydiff  is the difference between the current ball X(Y) position and the previous ball X(Y) position (ball position on the previous frame). T (time) – the time the vision system makes two frames. Currently the vision system make 30 frames per second, so the time between two frames is t = 1/30 = 0.333s. In the new robot software architecture, the ball speed is calculated in the main application, rather than in the top layer application, where the behavior of the external objects is calculated. The calculation principle is similar do already described and the value of the ball speed is used directly from there. 2.5.4 Ball direction The value defines the direction in which the ball is moving. We are assuming that the previous ball position is a center of a coordinate system and we compare the current position of the ball with that position. Figure 7 Ball direction Teaching through demonstration of a RoboCup goalkeeper robot 22 The actual Xdiff and Ydiff distance between the current ball position and the previous one is calculated as a difference between the coordinate of the current ball position and the previous ball position. With these X and Y coordinate, a defined angle can be found: Ydiff =Yball−YprevBall Xdiff = Xball− XprevBall angle=atan2 Xdiff , Ydiff  The Python function atan2(Xdiff, Ydiff), as already described and used in chapter 2.5.2, is a mathematical function that return the angle in radians and the result is between -pi and pi (i.e. -180° and 180°). The signs of both inputs are known to the function, so it can compute the correct quadrant for the angle i.e. as input of the function we have to pass the real sign values of the difference between the current ball position and the previous ball position, rather than the absolute values. According to the quadrant in which the ball is currently located, the correct ball direction angle is differently calculated. If the ball is located in I or IV quadrant, the angle value is first converted to degrees and then we can use it. Otherwise, if the ball is located in II or III quadrant, the final angle is the sum of 360° and the converted direction angle (in degrees). With this additional calculation the ball direction angle is in the range of 0 to 360°. If the Xdiff and Ydiff equal to 0 then the ball direction angle is equal to -1. We assume that 0° is always the direction in which the robot kicker is looking. At current state of the project the robot would not rotate and 0° is the opponent goal direction. 2.5.5 Robot movement The robot will behave different in depend of the location and behavior of the other objects in the field (e.g. ball, goal and other robots). In order to define the proper robot movement direction, the received data from the joystick regarding robot moving direction and speed is evaluated and converted to the required format. On the current state of the project the robot will move only in two directions (left and right) with a different speed. The following robot movement commands are defined: Abbreviation of the main movements Operation Rs Right slow Rf Right fast Ls Left slow Lf Left fast S Stop Table 4 Teaching movement command format Teaching through demonstration of a RoboCup goalkeeper robot 23 If the robot moves right with a speed higher than 50% then the movement is defined as “Rf”, otherwise is the speed is lower than 50% the movement is “Rs”. If the moving direction is left than the commands are “Lf” and “Ls”. If the robot is staying still, i.e. the speed is 0% than the movement command is set to “S”. 2.6 GUI After defining basic network communication concept and data manipulation and conversion, a graphical user interface (GUI) should be created. A GUI takes advantage of the computers graphics capabilities to make the program easier to use. For users it is easier to use graphical interfaces instead of complex command languages. Some of the basics concepts that a GUI is using are: 2.6.1 ● Pointer – A symbol that appears on the display screen and that is moved to select objects and commands. Depending on the used application the size and shape of the pointer could be different. ● Pointer device – A device, such as a mouse or trackball, which enables selection of objects on the display screen. ● Icon – Small pictures that represent commands, files, or windows. By pressing a mouse button over an icon, a command could be executed or the icon could be converted into a window. ● Window – An area of the screen where different programs and files can be displayed. The windows can be moved around the display screen, and also their shape and size can be changed. ● Menus – allowing users to execute commands by selecting a choice from a menu. Graphical application Developing applications with GUI takes time and sometimes could be a hard work. Making these applications work across different operating systems could be even more complex. Usually, applications have been developed for one platform, and then large amounts of the code have been rewritten to run the application to other platforms. Currently there are several additional libraries that could be used for development of Graphical User Interfaces. All of them have advantages and disadvantages that are evaluated and the library that best passes to our requirements is used for the development of the GUI application for remote robot control. Teaching through demonstration of a RoboCup goalkeeper robot 24 2.6.1.1 QT According to Trolltech [Qttroll], QT sets the standard for high-performance, cross-platform application development. It uses standard C++, but extends the language by providing an additional pre-processor that generates the C++ code which is necessary to implement Qt's extensions. Qt can also be used by programmers using other languages, like PHP, C, Java, and Python. It runs on all major platforms (e.g. Windows, *nix, Mac OS and etc.) and has extensive internationalization support. Some of the Qt advantages are: • single-source compatibility • multiplatform using a "write once, compile anywhere" approach • feature richness • C++ performance • availability of the source code, depending on the license • on-line documentation • technical-support • Graphical development tool As disadvantages could be consider that Qt has: three license forms - free, non-commercial and commercial (can't be used for commercial applications without paying a fee) • not been developed by open-source community • Additional to the previous mentioned advantages could be considered that for Qt exist a graphical tool (Qt Designer) for development of GUI programs. It provides the possibility to build fast and easy user interfaces with so called „drag n drop“ technique. Additionally Qt supports signals and slots mechanism for type-safe communication between widgets. Qt Designer includes a code editor which can be used to embed our own custom slots inside the already generated code. Qt Designer advantages Separate UI from coding • Easier than manual coding even for advanced developers • Qt Designer disadvantages Doesn't work well with CVS and similar tools • Can't everything be done within QT Designer • Only work for static user interfaces • When a QT application starts, only one thread is running - the initial thread. This is the only thread that is allowed to create the QApplication object call exec() on it. This is the main thread, which can create new threads. If these new threads need to communicate among themselves, they could use shared variables or wait conditions. But none of these techniques could be used to Teaching through demonstration of a RoboCup goalkeeper robot 25 communicate with the main thread, since they would lock the event loop and freeze the user interface. To communication with the main thread we have used so called custom events. It is possible to define custom event and post these events to the main thread using QApplication::postEvent(). Since postEvent() is thread safe, we could use it from any thread to post events to the main thread. 2.6.1.2 GTK+ GTK+ is a multi-platform widget toolkit for creating graphical user interfaces. GTK+ was initially created for the GNU Image Manipulation Program (GIMP), a raster graphics editor with some support for vector graphics. Advantages • • • • • • • Free software and part of the GNU Project LGPL license – could develop open software, free software, and even commercial nonfree software Object oriented application programmers interface Bindings for many other programming languages – C/C++, Perl, Python, JAVA, and etc. Could use a different theme for different looks of an application Complete widget set Full internationalization Disadvantages Not available on all platforms (compared to version 1.x) • More dependencies compared to 1.x, see below • GTK+ is based on three libraries developed by the GTK+ team: [GTK] • GLib is the low-level core library that forms the basis of GTK+ and GNOME. It provides data structure handling for C, portability wrappers, and interfaces for such runtime functionality as an event loop, threads, dynamic loading, and an object system. • Pango is a library for layout and rendering of text, with an emphasis on internationalization. It forms the core of text and font handling for GTK+-2.0. • The ATK library provides a set of interfaces for accessibility. By supporting the ATK interfaces, an application or toolkit can be used with such tools as screen readers, magnifiers, and alternative input devices. Teaching through demonstration of a RoboCup goalkeeper robot 26 2.6.1.3 X window X Window System [Xwin] is a network transparent window system which runs on a wide range of computing and graphics machines. X system servers run on computers with bitmap displays. The server distributes user input and accepts output requests from various client programs through a variety of different interposes communication channels. Although the most common case for the client programs is to be run on the same machine as the server, clients could also be run transparently from other machines (including machines with different architectures and operating systems) as well. The layout of windows on the screen is controlled by special programs called window managers. Since window managers are regular client programs, a variety of different user interfaces can be built. The X Consortium distribution comes with a window manager, which supports overlapping windows, popup menus, point-and-click or click-to-type input models, title bars, nice icons. Figure 8 X Window System – client-server The picture is taken from [Xsystem] and represents the basic working principle of the X Window System. X server takes input from a keyboard and mouse and displays to a screen. A browser and a terminal emulator run on the user's workstation, and a system updater runs on a remote server. Teaching through demonstration of a RoboCup goalkeeper robot 27 2.6.1.4 Motif Motif is a graphical widget toolkit for building graphical user interface under the X Window System on Unix and other POSIX (Portable Operating System Interface for uniX) compliant systems. It is an industrial standard as defined by IEEE 1295 specification and the basic building block of the Common Desktop Environment (CDE – proprietary desktop environment for UNIX). Before the latest desktop environments, such KDE and GNOME have become so popular, the CDE has been considered as a standard for UNIX desktops. 2.6.1.5 Conclusion Several toolkits for development of graphical user interface are described and evaluated. All of them have advantages and disadvantages which are carefully considered. For us it is important that the chosen toolkit have good performance and compatibility with C++ programming language, good documentation and graphical tool for easy development of GUI applications. One of the possible toolkits that could be used for development of GUI applications is Qt. It is developed in 1991 from a Norwegian company, called later on Trolltech. Qt is used for the development of one of the leading desktop environments for Linux - KDE. Due to the fact that the toolkit is developed from a private company rather than the open-source community it has a very good on-line documentation and technical support. It have also three license forms - free, noncommercial and commercial, which mean that the product can't be used for commercial applications without paying a fee. Other possible toolkit for development of GUI applications is GTK+. It advantage compare to Qt is that it is completely free even for commercial applications and is part of the GNU Project. GTK+ is used for the development of the GNOME environment, which is the official desktop of the GNU Project, and currently together with Qt is one of the most popular widget toolkits. Other possible solution for development of GUI is X Window System. It is not a toolkit like GTK+ or Qt, but rather a system server which run on computers with bitmap displays. The layout of windows on the screen is controlled by special programs called window managers, which supports overlapping windows, popup menus, point-and-click or click-to-type input models, title bars, nice icons. The last reviewed toolkit for development of GUI applications under X Window system on Unix is Motif. It is industry standard by IEEE 1295 and has been widely used before the Qt and Gtk have become so popular. After careful evaluation of the advantages and disadvantages of the described toolkits for development of graphical interface, we decided to use Qt for the development of our graphical application. Even though there are three license forms for different type of applications, for the scope of this project no license is required. Additionally there is a graphical tool for Qt (Qt Designer) for development of GUI programs. It provides the possibility to build easy and fast user interfaces with so called „drag n drop“ technique. Qt Designer provides the possibility to separate Teaching through demonstration of a RoboCup goalkeeper robot 28 UI from coding and is easier for manipulation and GUI development than manual coding even for advanced developers. 2.6.2 GUI functionality A simple GUI application is implemented for easier manipulation of the communication with the robot. 2.6.2.1 Requirements The application has to fulfill the following requirements: • It should provide possibilities for easy connection and disconnection with the robot - if the connection is already established and the user try to establish a connection once again, a message should be shown to remind the user that the connection is already established. The same warning message should be shown if the user tries to stop the connection and there is not an established connection with the robot. • Display system messages - critical or warning messages should be shown in red. If such a message arrives, it would be easier seen among the other system messages. The other messages should be represented in black color. 2.6.2.2 Features Figure 9 GUI for a robot remote control Teaching through demonstration of a RoboCup goalkeeper robot 29 2.6.3 Decorator design pattern While designing an user interface using graphical components, the programmer usually requires some more featured controls than APIs provide. In this case the Decorator Pattern is used. It gives the possibility to add additional functionality to a particular object and leave other similar objects unmodified. Every GUI application is a combination of a lot of objects like text fields, boarders, scrollbars, buttons, menus, etc. Instead of creating subclasses for every possible combination of features it is better to create one object, for example text field, and enhance it with required objects. In reality this is implemented with the creation of an object that implements the same interface, and contains a text field, but also contains other objects that add some behavior to the text field. This enclosing object is called a decorator. The pictures is taken from [Gamma,p175] Figure 10 Example for Decorator design pattern Teaching through demonstration of a RoboCup goalkeeper robot 30 3 Robot teaching After the system for remote robot control is successfully implemented, the next step is to teach the robot to behave as a real goalkeeper. To teach it in authentic playing situations the robot is navigated with a remote control by a human trainer. Before we continue with description of the practical implementation, we have to explain how a robot could be taught and how a machine could learn. 3.1 Machine learning Several years ago, the only way to control machines to do tasks appropriately was to program them manually or to control them remotely with remote control devices. The next level in the machine evolution process was the development of autonomous robots, which could perform tasks according input data. With the newest technologies in the area of artificial intelligence, the machines could become more intelligent than the people. Such a level of intelligence could be achieved with machine learning methods [MLearn]. The branch of computer science that studies the basis of machine intelligent behavior is called Artificial Intelligence (AI). Whit the help of AI methods we could make machines simulate aspects of human intelligence, such as learning, reasoning, vision, feeling. In other words, a machine or a computer system could be made to behave, think or learn like a human being. One of the areas covered by artificial intelligence is machine learning. Machine learning is concerned with the development of algorithms and techniques that allow computers to "learn". According to Tom Mitchell [MLearn] machine learning is: „Machine Learning is the study of computer algorithms that improve automatically through experience“ The idea is repeatedly to demonstrate how a certain task is performed and let the computer learn according to the examples. So, the computer system would be learned from experience or extract knowledge based on previous results. It is also very important the content of the data used for teaching the machine, or the correctness of showed examples. Several machine learning methods exist and some of them are: • Learning through demonstration – As the name of the considered method is showing, the learning process is performed through demonstration. A human trainer demonstrates the correct behavior that the goalkeeper robot has to learn. Teaching through demonstration of a RoboCup goalkeeper robot 31 • Reinforcement learning – The computer system or agent must learn behavior through interactions with a dynamic environment, which in return provide a reward or punishment without specify how the task is to be achieved. • Inductive learning – Represent the process of learning by example. The computer system would try to induce a general rule from a set of observe instances. • Learning by analogy – The system would try to behave correctly, based on past experience related with successful solving of similar problematic situations. According to previously done conclusions the agent would have to try to guess a possible correct solution of a current task. • Learning by experimentation – Learning a behavior via experimentation i.e. with the help of acquired correct knowledge about the required behavior the actor should learn to behave correctly. Several learning methods were discussed and all of them are having advantages and disadvantages. The target of the project is to implement the teaching through demonstration method and in the next part of the current chapter it is evaluated in details. 3.2 Teaching through demonstration In this machine learning method the learning process is performed through demonstration by a human trainer. Under demonstration we can understand a representation of correct behavior that the agent should learn. In the scope of my thesis the correct behavior that has to be learned is a behavior of a goalkeeper. During the demonstration process the agent will observe and record the demonstrated actions. To do this, the data regarding correct behavior and performance is captured, manipulated and stored on the machine side. Later on, the stored data is structured, evaluated and used for the teaching of the agent. Of great importance for the correct behavior of the agent is the content of the teaching data. As long as the teaching data is correct we could expect that the learned behavior is also correct. Possible mistakes in the teaching data could arise not only during the data processing and manipulation, but also during the teaching demonstration. Due to the fact, that such demonstration mistakes could occur, it is a must that the person who demonstrates the correct behavior is qualified enough to perform the teaching process (teaching person has to know not only what have to be taught, but also how it could be taught correctly). After the correct teaching data is properly stored, it will be evaluated and converted to machine understandable format. Some of the possible techniques for data manipulation are parallel distributed processing (neural networks) or decision tree generation. Both techniques are having Teaching through demonstration of a RoboCup goalkeeper robot 32 advantages and disadvantages, but we will continue with the evaluation and the usage of the decision tree generation technique and applications that use this technique. 3.3 Decision tree learning technique Decision tree is a graph or model for representation of all possible outcomes and the paths by which they might be reached. Decision trees are constructed and mainly used to help with making decisions. A training data is used for generation of decision trees and the format of the tree is in a top-down direction. The decision tree consists of nodes, where the root node is the trees initial state. Every node could be a decision node or a leaf node. Decision node is the node where a logical decision has to be made and where two or more branches are connected according to the result of this decision. The leaf node indicates the value of the target attribute. Figure 11 Example of decision trees Once a decision tree solution is generated from the teaching data, it is used for prediction or estimation the path to the searched solution in dependence of the initial data. The process could be controlled by starting it in the root node, taking the appropriate branch, and terminating when a leaf node is reached. Decision trees advantages: • Simple to understand and interpret – Easy to understand decision tree model even without previous knowledge, because it generate understandable rules • Robust to errors • Work with missing attribute – Decision tree methods could be used even when some training examples have unknown values • Require almost no data preparation Teaching through demonstration of a RoboCup goalkeeper robot 33 • Well performance with large data in a short time – Large amounts of data could be analyzed in a short time Decision trees disadvantages: • Possible errors in classification if we have small number of training examples. • Could be computationally expensive to generate the tree if it consist a huge amount of nodes 3.4 C4.5 – decision tree method 3.4.1 Description C4.5 is a decision tree generating algorithm, based on the ID3 algorithm (ID3 (Iterative Dichotomiser 3) is an algorithm used to generate a decision tree and is completely written in C). According to [C4.5Tut] C4.5 address the following issues not dealt with by ID3: • Avoiding overfitting the data • Determining how deeply to grow a decision tree. • Reduced error pruning. • Rule post-pruning. • Handling continuous attributes. • Choosing an appropriate attribute selection measure. • Handling training data with missing attribute values. • Handling attributes with differing costs. • Improving computational efficiency. To create a useful decision tree with C4.5, some requirements have to be fulfilled. Some of the particular induction methods embodied in the program are: [C4.5] • Attribute-value description – The analyzed data must be in a flat file – all information about one object or case must be expressible in terms of a fixed collection of properties or attributes. Each attribute may have either discrete or numeric values, but the attributes used to describe the case must not vary from one case to another. Teaching through demonstration of a RoboCup goalkeeper robot 34 • Discrete classes – This requirement has to do with the categories to which cases are assigned. A case should either do or do not belong to a particular class, and there must be far more cases than classes. • Sufficient data – The amount of data required is affected by factors such as the numbers of properties and classes and the complexity of the classification model; as these increase, more data would be needed to construct a reliable mode. • Logical classification models – The program constructs only classifiers that could be expressed as decision trees or sets of production rules. 3.4.2 File formats According to C4.5 manual page [C4.5man] the program expects to find at least two files: • filestem.names file – defining class, attribute and attribute value names. The file commences with the names of the classes, separated by commas and terminated with a period. Each name is simply a sequence of characters (string) and should not include comma, question mark or colon, unless preceded by a backslash. A period may be embedded in a name provided it is not followed by a space. Embedded spaces are also permitted but multiple white space is replaced by a single space. The rest of the file consists of a single entry for each attribute. An attribute entry begins with the attribute name followed by a colon and one of the following reserved words: • Ignore – Indicate that this attribute should not be used • Continuous – Indicate that the attribute has real values. The reserved word should be also used if the attribute has a negative values or float values • Discrete – should be followed by an integer 'n'. Indicate that the program should assemble a list of up to n possible values, or a list of all possible discrete values separated by commas The vertical bar "|" character causes the remainder of that line to be ignored. Each entry is terminated by a period which may be omitted if it is the last character of a line. • filestem.data file – contain a set of objects, each of which is described by its values of each of the attributes and its class. The data file name.data contains one line per object. Each line contains the values of the attributes in order followed by the object's class, with all entries separated by commas. Every line should not include comma, question mark or colon, unless preceded by a backslash. An unknown value of an attribute is indicated by a question mark "?". The other three files are not compulsory for the unproblematic work of the tree generation. They are used or generated in the process of data evaluation. Teaching through demonstration of a RoboCup goalkeeper robot 35 • filestem.unpruned – All trees generated in the process are saved in this file. After each tree is generated, it is pruned in an attempt to simplify it. • filestem.tree – After all trees are generated and saved in the name.unpruned file, the best pruned tree is saved in machine-readable form in the name.tree file. The best tree is selected by the program and if there are more than one tree, which is considered as best then there is more than one trial. • filestem.test – In same cases, a test data or a reserved part of the available data could be used as a test set to evaluate the classifier that is produced. If there is such a data, it should be located in filestem.test, in exactly the same format as the data file. 3.4.3 Options C4.5 program has several additional options tha could be invoked on the command line. Some of the options that are used most often are: [C4.5man] Option Description -h Show a short help regarding the possible options and their default settings -f filestem Used to specify the filestem (without extension). -u Invoked when a test file has been prepared (filestem.test) -t trees Set iterative mode with specified number of trials. -m weight Any test must have at least 'm' outcomes with a minimum number of cases. If there is a huge amount of training data than the value should be at least 10. -s Causes the values of discrete attributes to be grouped for tests -c Affects decision tree pruning. Small values cause heavier pruning than large values. Default No test set 10 2 No grouping 25,00% Table 5 C4.5 options 3.4.4 Pruning decision trees Usually the generated decision tree is very complex and additional simplification is required. The process of simplifying the decision trees by removing one or more sub trees and replacing them with leaves is called pruning. The main idea behind the pruning process is not to delete the tree in favor of a leaf, but rather to remove parts of the tree that do not contribute to classification accuracy on unseen cases. As a result we have less complex decision tree in more comprehensive format. Teaching through demonstration of a RoboCup goalkeeper robot 36 3.4.5 Error rates estimation During the process of decision tree generation and simplification it is possible to evaluate the errors rate of the tree and its sub trees. When a decision tree is created, an error rate of every tree branch is shown. The following example data (the data is taken from a real generated and used decision tree) shows the way of error representation. ball_distance <= 2544.22 : | | | | goal_center_X <= -47.834 : Rf (17.0/1.0) | | | | goal_center_X > -47.834 : S (13.0/3.0) | | | ball_distance > 2544.22 : | | | | ball_direction <= 50 : S (5.0/2.0) | | | | ball_direction > 50 : | | | | | ball_distance <= 4075.37 : Rs (12.0/3.0) | | | | | ball_distance > 4075.37 : Rf (8.0/1.0) The numbers in the brackets (N, F) represent the resubstitution error rate N – number of training cases covered by the leaf F – number of predicted errors if a set of N unseen cases were classified by the tree The sum of the predicted errors at the leaves, divided by the number of cases in the training set, provides an immediate estimate of the error rate of the pruned tree on unseen cases. At the end of the file, containing generated original and pruned decision tree, a summary of result on the training cases and a set of test cases is appended. Additionally a comparison between the data before pruning and after pruning is done (comparison of the data size and number of errors). 3.5 Conclusion In this chapter, some machine learning methods and techniques have been discussed and explained. As a general, machine learning could be compared with human learning and this is especially true for the learning through demonstration method. For this method a very important factor is the teaching skill of the teacher i.e. whether he/she could represent the information in a proper way. In our case, the person who teaches the robot has to know exactly what has to be done and how to teach the robot maximum correctly and precisely. Of course, for the good performance of the robot it is not only sufficient the good teaching methods of the teacher, but also the proper evaluation and manipulation of the teaching data. It is important the data to be saved in a proper format and sequence and later on evaluated with proper techniques (e.g. decision tree technique). The C4.5 algorithm is used for data processing Teaching through demonstration of a RoboCup goalkeeper robot 37 and conversion in a decision tree format. In such a format, the data could be easily interpreted from the robot and could be used later on for teaching. After the theoretical solution has been proposed and evaluated, the next step is to implement the teaching process practically. In the next chapter, all practical aspects of the teaching process are evaluated and considered. Teaching through demonstration of a RoboCup goalkeeper robot 38 4 4.1 Practical implementation and Results Teaching process Teaching is the ability to explain clearly certain information to others, so that they can learn something new. In the project, the teaching through demonstration method is used, where first the correct behavior is demonstrated by a human trainer that the robot has to learn. There are different ways of teaching and different issues have to be taken under consideration during the teaching process. We have to know who we want to teach, the background knowledge, teaching environment and abilities to accept incoming information. 4.1.1 Who to teach The object of our teaching interest is an autonomous electronic machine (i.e. robot) on which a computer operating system and software applications are running. The robot could be considered as a small model of a human being with a lot of limitations. The system has a camera, which performs the same function as a human eye and is used to observe the surrounding environment. Additionally, the robot has two arms which could be moved only in two directions (i.e. up and down). Because of omnidrive, the robot can rotate and move in any direction simultaneously. Part of the robot could be moved and could perform a kick, similar to a human foot kick. The running computer applications on the robot allow us to perform new scientific methods for the development of an artificial intelligent system. It could be taught autonomously to perform previously defined tasks and to take decisions autonomously depending of the situation in which it is participated. 4.1.2 What to teach Before starting any teaching process we have to make sure that the agent could „see“ and recognize the surrounding objects. It should recognize the objects with different colors, and according to that color it should recognize the type of the object. If the object is orange, it should be the ball, otherwise if the object is blue or yellow it should be one of the goals (our goal or the goal of the opposite team). In the current state of the project the location of other objects in the field, which do not have previously defined color (e.g. teammates and players from the opposite team), could not be recognized. It is highly recommended that on the field no other objects do exist with the same colors like the ball or the goals. On this case it is possible that a wrong object is recognized as a ball or goal. After having all required information for the location of the recognized objects in the filed, the teaching process can start. To teach the robot to behave completely as a goalkeeper requires a lot Teaching through demonstration of a RoboCup goalkeeper robot 39 of efforts and time and could not be completely covered in this project. That’s why a simplified goalkeeper behavior is taught. The robot moves left and right with two different speeds or stands still without moving into any directions. If the goalie is located in the middle of the goal line and the ball is moving in the goal direction right to the goalkeeper, it should move right and try to prevent the ball going into the goal. If the shot is successfully blocked or a goal is scored, the robot keeps on staying in its place or takes an optimal position in the middle of the goal. The behavior of the robot depends on its location in the goal and the behavior of the ball (location, moving direction, moving speed). Figure 12 Simple teaching behavior It is necessary to teach the robot to avoid obstacles (e.g. posts or other robots). If the robot could not recognize the location of one of the posts during the behavior execution, it could hit it with a high speed and could damage itself. The same situation could occur between the goalkeeper and some of the other robots located in the field. According to RoboCup regulations a fault could be called and in a real game, a fault could also be called if the goalkeeper uses its arms outside of the penalty area. Comparing to the behavior of a real goalkeeper, there are some differences with the behavior of our robot. For example, it could only move in left or right direction, rather than in any other direction. It moves only on a line parallel to the goal line. Additionally, in the current state of the project the robot is not taught to use its arms. 4.1.3 How to teach We already know who we want to teach and what, but how exactly to do this? There are several teaching methods, but the method on which we are concentrated on is the teaching through demonstration method. The main idea is to simulate a real game, during which the robot is navigated to behave properly. The person that controls the robot should be familiar with the football rules and with the task that we would like to achieve. Before any real robot teaching process can start, we have to make sure Teaching through demonstration of a RoboCup goalkeeper robot 40 that the teacher is qualified enough to make the lessons. He has to be familiar with the device for remote control and with the features of the robot. To minimize the robot reaction time during the teaching process and to move the robot as soon as an action is occurred, it is absolute necessary to know in advance in which direction the ball would move. 4.1.4 Problems During the robot teaching process some unexpected problems could occur. They can be generized in two groups: – Teaching problems – problems that occur during the teaching process or problems related with it. Such problems depend mainly from the qualification and analysis skills of the person who leads the teaching process. The teaching person must be qualified to perform the teaching process and must be familiar with the robot features and the usage of the remote control device. As the taught object is a computer system it is possible to behave unexpectedly (e.g. the robot could lose the connection with the remote control device and could behave unexpectedly). Due to fact that the teaching person is concentrated more on the teaching process, rather tham on the technical process, it is necessary to participate at least one more person into the teaching process. The second person is responsible for the movement of the ball in the field and kicking of the ball to the goal direction. If a third person is available, s/he is used to work with the application located on the computer for remote control and more specifically to start and stop the network communication process between the remote control computer and the robot in the right moment (i.e. to synchronize the teaching and data gathering processes). Due to the fact that the teaching and the data gathering processes would be performed simultaneously, the gathering of an unnecessary data could be reduced, because the data gathering process would not be performed longer than the teaching process. – Technical problems – problems related with the technical performance of the robot or with the overall performance of the whole system. One of the most serious technical problems, directly related to the teaching process, is the robot unexpected rotation. Sometimes the goalkeeper moves not only in into the left or right direction, but also moves and rotates simultaneously. This behavior is observed mainly if the robot battery is almost empty. Usually, the robot should move only in different directions on a line paralel to the goal line. If it rotates a little bit, than it loses the correct orientation and next movement is on a line which is not any more parallel to the goal line. In this case, a fault teaching data is saved and the whole teaching process is considered as completely wrong. Teaching through demonstration of a RoboCup goalkeeper robot 41 Figure 13 Rotation problem It is highly recommended to perform the teaching process when the robot motor battery is full. Only in this case we could expect that the robot performs as it is supposed. If the motor supply battery is half full or empty, than it could not provide enough supply and the motor may not manage to move the robot with the required speed. We can expect that the robot should move with a high speed, but in reality it moves relatively slow. Due to this, inconsistency between expected and real behavior could occur, which could be a reason for an error in the teaching process. The environment conditions could also be a reason for technical problems. If the, room in which the teaching process is taking place, is too light or dark and the system is not configured for a proper work in such an environment, the vision system of the robot could recognize some surrounding objects wrongly (e.g. could not correctly recognize the location on the ball or goals). If a second object, with the same color, like the color of the ball or one of the goals, exists in the football field (i.e. orange, blue or yellow object), the probability of wrong recognition of the right object is very high, which would be a reason for wrong data to be saved. Due to this, it is recommended all other objects with the same colors like the ball or the goals to be located outside of the robot vision area. Another possible problem could arise if one of the motor wheels is located on one of the lines marked the field (e.g. goal line, goal area line, penalty area line, touch line). According to RoboCup rules [RCrules], the maximum width of the lines could be 12,5 cm and the material is usually with a very low friction (e.g. in RoboCup labor the width of these lines is 7 cm and the material is an isolating tape). So, if one of the wheels is located on one of the lines, it could slip for a certain period of time. This could be a reason for delay in the robot action and could be considered as an incorrect teaching. Last, but not least, network communication problems could occur. Such problems are not directly related to the teaching process, but could be a reason for the robot or some of the surrounding objects (people, other robots, etc.) to be heard or damaged. If the wireless network connection is interrupted during the remote joystick control process, the robot receives no control commands any more and the last received command would be continuous executed. In this case, the robot would uncontrollable continue to move in the last direction. The person that Teaching through demonstration of a RoboCup goalkeeper robot 42 kicks the ball should observe the robot behavior and in emergency cases should switch off the motor supply. 4.2 Teaching data During the teaching process, the robot observes the behavior of the surrounding objects. The information regarded the behavior of these objects (e.g. ball and goal), together with the information for its own behavior, is saved in a file and later on is used during the learning process. But before the real learning of the robot can start, the teaching data should be evaluated and preprocessed. 4.2.1 Data gathering Data gathering is a process of gathering a required data and store it in a common place from where later on the data could be used for additional treatments (e.g. evaluation, processing, etc.). There are several steps, which describe some features of the data gathering process used from us to collect the necessary teaching data. • Keep the data simple – Gather only the required data for the relevant objects (e.g. ball, goal, own behavior). That would simplify and improve later on the data evaluation and analyzing process. • The process is done during the whole teaching process – This has some positive and negative effects on the gathered data. One positive aspect is that we have all required information for the required objects during the whole teaching process. Of course, we collect not only the correct data, but also some data that later on could be consider as a wrong taught data. • The process is performed almost in a real time – In our case the data gathering process is almost done in a real time i.e. when the data is once available then it should be saved immediately. • Use existing data – If there is already a certain amount of gathered and evaluated data, then it is recommended to use it together with the new gathered data to improve the quality and correctness of the teaching data. After some important steps in the data gathering process have been defined, it is necessary to clarify the sources from where the data would be gathered. There are two sources which are used for data collection – data coming from the remote joystick device via the wireless network and data coming from the vision system of the robot (e.g. camera or later on from sensors) • Via wireless network – The data from the remote joystick device is sent via a wireless network to the robot. On the current stage of the project the data of our interest is the Teaching through demonstration of a RoboCup goalkeeper robot 43 robot's moving direction (only left or right) and the robot speed (less than 10%, less than 50% or more than 50%). All other received data (e.g. robot rotation, arms and kicker activation, etc.) is currently unused. • Robot vision system – The system should provide data regarding the location and behavior of the surrounding objects (ball and goals). After all required data is appropriate gathered and in a correct format, it is saved in a file, from where it will be evaluated and preprocessed. 4.2.2 Data evaluation Under data evaluation we understand a process of systematic collection, analysis and determination of data, so as a result we conclude whether the data meets specified criterions or not. Some criterions used by us are: • Correct number of attributes – Verify whether we have a correct number of attributes for every line of available data. The number of attributes is six. • Correct sequence of attributes – Check whether we have a correct sequence of attributes i.e. every attribute is located on its correct place. The correct attributes sequence is ball_distance, ball_angle, ball_speed, ball_direction, goal_center_X, robot action. • Correct attributes value – Review all the data and verify whether the attributes consist of the correct data. - ball_distance – should always be a positive value. A realistic data is in the range of 0 to 9000 mm max distance at which an object could be properly recognized. - ball_angle –Positive value in the range of 0 to 360 °. - ball_speed – Always a positive value. If the ball does not move the value is equal to 0. Dimension unit is [m/s] • - ball_direction – The value is the range of -1 to 360. If the ball does not move, its value is -1. - goal_center_X – The value could be either positive or negative in the range of half of the wight of the football field (4000 mm) - robot action – The action that the robot performs (Move : Ls->left slow, Lf->left fast, Rs->right slow, Rf->right fast, S->stop ) Teaching through demonstration of a RoboCup goalkeeper robot 44 • Correct file structure – Check whether the file has a correct structure i.e. check whether the attributes are separated with correct characters. In our case the attributes are separated with a comma ( , ) and after the last attribute we do not have any character. Due to the fact that the gathering of the required data is done automatically, we can expect that all data is saved in a correct format and sequence. Nevertheless, if the gathering process is unexpectedly interrupted some of the specified criterions could not be fulfilled. After evaluating and verifying the gathered data successfully, we continue with a data preprocessing process. 4.2.3 Data preprocessing Data preprocessing describes any type of processing performed on data to prepare it for another processing procedure. Some of the preprocessing processes used from us are: • Filtering – A process of reducing a complex data structure into its simplest, most stable structure. When an incorrect data is found during the evaluation process it will be removed. If more than one row consist the same set of data, the repeated rows of data are removed, because these data could influence the final structure of the generated decision tree. At the end we have a set of rows which are unique and occur only once. Additionally, we have to select only the correct teaching data and omit all other data. The process should be done manually immediately after every training session, otherwise later on we could not recognize correct from incorrect data. Of course, it is no a guarantee that we will recognize the correct data, because the whole process is not automatic and depends of the estimation of the person performing the preprocessing process. • Relocation – After normalization and sampling of the data, the file should consist only of correct data which will be used for the teaching of the robot. Usually, the teaching of the robot is done several times and after every teaching session, the final correct data should be saved separately in a different file, from where, later on, the final learning of the robot can be done. The process of movement of the final correct data to a separate learning file could be considered as the final preprocessing process. During data preprocessing there are several potential problems which should be taken under consideration. • Selecting only the correct data – During the teaching period the system saves all required external information. After every teaching session we should manually omit the incorrect teaching data. If the session is longer, the possibility to consist of incorrect Teaching through demonstration of a RoboCup goalkeeper robot 45 data is higher. In addition, if the session is longer, than it is more difficult to recognize which data is correct and which not. 4.3 • Manual preprocessing – The preprocessing process can not be done automatically, because a person should be involved into the data review and data systematization. The programmer should decide personally which data can be considered as correct and which not, and should personally remove the incorrect data. • Time consuming – The whole preprocessing process is time consuming. Behaviour learning After the teaching data is gathered, evaluated and preprocessed we can continue with the transformation of the teaching data in appropriate format understandable for the robot. This is done with the help of C4.5 program and the output data is structured like a decision tree. 4.3.1 Generation of a decision tree with C4.5 To generate a decision tree from the behavior teaching data the following command is used: [stoiko@ertellap test1]$c4.5 -f filename -m 5 -u The 'f' option specifies the filename stem. The name should be without an extension. During the decision tree generation with C4.5 it is highly recommended to use a 'm' parameter. According to the description of this parameter, any test must have at least 'm' outcomes with a minimum number of cases. If an appropriate 'm' parameter is used, the errors during the evaluation of the test data could be reduced. In our case if m=5 then the error is minimal (error = 26.4%) Figure 14 C4.5 influence of the 'm' parameter Teaching through demonstration of a RoboCup goalkeeper robot 46 The parameter 'u' is used to check the validity of the rule sets made from the training data. The amount of data in the *.test file should be 1/3 from the data located in the *.data file. The C4.5 output file could consist of two decision trees – the first tree is a regular decision tree and the second tree is a simplified decision tree. One of the questions that could arise is, „why do we need a simplified decision tree“? During the tree pruning phase or tree simplification process some of the lower branches and nodes of the tree are removed to improve performance. 4.3.2 Manual optimization The generated decision tree with c4.5 algorithm is produced on the base of the gathered teaching data. The generated decision tree does not always represents the entire correct goalie behavior, which could be immediately used. Some additional manual optimizations can be done to improve the decision tree. A manual optimization is a process of manual corrections or improvements of the generated decision tree, done by the programmer. Some of the reasons to require an addition manual optimization could be: • Decision tree modification – After the generations of the decision tree, it is recommended to review the structure of the tree, because it could contain incorrectness or mistakes. As example, we could notice that the decision tree represents a behavior that obviously is not correct. If such problems occur, some tree branches or leafs could be manually modified or completely removed. • Append new rules – If the teaching process is more specified or covers only limited test scenarios, the decision tree could be much bounded. In this case, we could decide to append additional branches or leafs to improve the general behavior of the robot. The optimization process depends of the personal estimation of the programmer. Due to that, possible errors in the structure of the final decision tree could occur. Additionally, the optimization process is done manually, and it could happen that an unnecessary data is added or a correct data is removed. 4.3.3 Decision tree interpretation To convert the decision tree structure to a source code, which would be compiled and executed as a goalkeeper behavior, we have to interpret it properly. The interpretation process could be performed in two ways: • Manual interpretation of the decision tree – The idea behind the process of manual data interpretation is manually to convert the decision tree into a C++ or Python class, which would be used together with the already existing software. As a disadvantage can be considered that the process is time consuming if we have a huge decision tree. An addition disadvantage is that the process should be repeated manually every time when there is a new decision tree (after every teaching session). Teaching through demonstration of a RoboCup goalkeeper robot 47 • Automated interpretation of a decision tree with a parser – the decision tree would be converted into a C++ or Python class with the help of a computer program. In this case, the time for the transformation process would be reduced to minimum. There are several programs that can perform automated interpretation process. The common among these programs is that they analyze the decision tree and determine its grammatical structure with respect to a given formal grammar. Another possibility is to use C4.5 to save the output data not in a decision tree format, but directly in a C++ or Python source file. A new software application has to be written and implemented to work together with C4.5. The proposed solution for automated interpretation of a decision tree is not implemented in the project so far, but currently a programmer is working on this task and in the next software version it would be implemented. 4.4 Teaching vs. Manual Programming So far, teaching through demonstration process has been described in detail, but what are the alternatives of the robot teaching process. Do they provide better possibilities to make the robot behave as a goalkeeper? In this chapter, a short feature description and comparison between the manual programmed behavior and teaching through demonstration behavior is made. We compare an artificial intelligence method for teaching with manually programmed behavior. 4.4.1 Features of teaching through demonstration process In order to compare both techniques for implementation of a goalkeeper behavior on a robot agent, we have to evaluate the advantages and disadvantages of the teaching process (teaching through demonstration) and of the manual programmed behavior. Advantages Disadvantages Could learn more complicated behavior Complicated teaching and learning processes Learn a behavior during real playing situations Well trained teaching person to perform the teaching process is required Teaching process should be performed for a sufficient duration of time Table 6 Features of teaching through demonstration process One of the biggest advantages of the behavior learned through demonstration is that more complicated behavior could be learned. The teaching process could be done for a long period of time, during which a lot of data could be gathered regarding many different actions. These actions Teaching through demonstration of a RoboCup goalkeeper robot 48 could cover behavior cases, which are not supposed to be covered from a manually written behavior. In such a case, the robot behavior can be apparently improved. In addition to the previous mentioned advantage, we could mention that the goalkeeper behavior is learned during a real playing game or during real simulated game cases, rather than as pure theoretical cases. Except the referenced advantages, there are also several disadvantages. One is the level of complexity of teaching and learning processes. The teaching process consists of several sub processes, like data gathering, data evaluation and manipulation and learning. All processes are related to each other and if a mistake occurs somewhere, the learned behavior could be completely wrong. Additionally, the person who performs the teaching process should be qualified enough and should be familiar with the teaching technique applying on the robot and techniques used during the teaching process (e.g. safety, observation, etc.). Last but not least, the teaching session should be performed for a sufficient duration of time, which means, that the robot should be trained as long as most of the possible behavior cases are covered. 4.4.2 Features of manual programming process Advantages Disadvantages Easy to implement Hard to program complicated behavior Subdivision of complexity Could not cover all possible behavior situations Table 7 Features of manual programming process As main advantage of the manual programmed behavior the implementation can be mentioned. We have to know the location of the surrounding objects and their behavior (e.g. behavior of the ball – moving direction, speed, etc.) to calculate the behavior of the robot in certain moment. Additionally, the complexity of the behavior could be subdivided i.e. at first, a very simple behavior could be done and tested, then a different one, and in the end all existing behaviors could be done together. Despite of the advantages the manual programmed behavior has, there are also some specific disadvantages. Even though we could create many simple behaviors and test them separately, the process of put them together, to form one complex behavior, is very complicate. The process of finding the right place for every sub behavior is time consuming and requires a lot of discussions among the team members involved in the project. Teaching through demonstration of a RoboCup goalkeeper robot 49 4.4.3 Conclusion A manually implemented goalkeeper behavior provides a relatively good level of intelligence for a goalkeeper robot in the middle size soccer league. We could implement manually a behavior that could cover basic goalkeeper actions (e.g. take optimal position in the goal, protect the goal, etc.) and could perform the main task of the goalkeeper – to prevent the opposite team from scoring by defending the goal. The main problem for improving the manual goalkeeper behavior is the process of correct data evaluation regarding external objects (e.g. ball, goal, and other robots) and the correct analyzing of the current playing situation. Even human goalkeepers are not perfect in protecting the goal and many mistakes are made, because of incorrect evaluation of the game situations. No matter how intelligent and good our goalkeeper robot is, we could not expect that he could behave perfectly without any mistakes to be done. The mentioned problem with incorrect evaluation of game situations could be circumvented if we apply an artificial intelligence technique for teaching a goalkeeper behavior. The main idea is to show the robot how to behave in a current situation and later on to expect that he would perform the correct action, if he occurs in the same or similar situation. To improve the taught behavior of the robot, the teaching process should be performed for sufficient duration of time and should cover as many as possible different situations. Due to the fact that artificial intelligence techniques for the teaching of a goalkeeper behavior are used for a first time in RoboCup project in Weingarten, we decided to teach a very simple behavior. Behavior would cover movements only into the left or right direction with two different speeds and no movements in any other direction would be performed. The next step in the teaching process is to teach a real goalkeeper behavior, which could be applied in a real game, but until then, many additional tests have to be performed. In conclusion, currently a manual programmed behavior is used on the goalkeeper agent, but later on an artificial intelligence technique for teaching a goalkeeper behavior would be implemented. Teaching through demonstration of a RoboCup goalkeeper robot 50 5 Testing Software testing is a process used to identify the correctness, completeness, safety and quality of the developed software. It could be also described as a process of executing a program or system with the intention of finding errors, bugs or defects. According to some software testing guides [Testing], there are several different problems that could be found during the testing process. • Error – The deviation from actual and the expected value. • Bug – It is found in the development environment before the product is shipped to the respective customer. • Defect – It is found in the product itself after it is shipped to the respective customer. What is the reason for the errors, bugs or defects in the software? 5.1 • Miscommunication or no communication concerning the details of what an application should or should not do. As a result we could have an application that does not fulfill the previously defined requirements. • Programming errors – Errors occurred in the software application as a result of bad source code. • Requirements changing – During the software development process, new software features could be requested or complete redesign of the existing software version. As a result, the completed project work could be redone once again or thrown out. The longer a project runs, the more vulnerable is to this type of requirements changes. • Time force – When a deadline of the project is closer, the programmers work under pressure and the possibility to make mistakes is higher. Application testing During the testing process, several different tests could be performed, like black box testing, white box testing, unit testing, integration testing, regression testing, usability testing, compatibility testing and etc. After the specific system features have been taken under consideration, it was decided to perform system and functionality tests. A functionality test checks the functional requirement of the application, where the overall requirements specifications are tested with system testing. To make sure, that the software application located on the remote side fulfills the requirements for operability and robustness, the following possible weak points should be tested. Teaching through demonstration of a RoboCup goalkeeper robot 51 • Interoperability with the external joystick device and proper read and normalization of the joystick data • GUI application test – Test the toolbar and the menu item for navigation, test whether the field where the system information is shown is in a read-only mode, test whether the vertical scroll bar appear only if is required, test whether spellings of all the text displayed in the window is correct, and etc. • If the remote network is inaccessible, a proper error message should be shown on the application text field. The message should be colored in red for a better reading. If this situation occurs, neither the data manipulation nor sending thread should be started. • Prevent the user to connect/disconnect to the robot twice. If a connection with the robot is once established/broken, the user should not have the possibility to connect/disconnect once again with the robot. • If the user closes the application from the close button, all treads should be stopped properly and the application should be left safely. The application software located on the robot side should be tested for interoperability with the existing software and for functionality and proper work. 5.2 • Properly start the listening server and accept connection from the remote control application. If the remote application interrupts the communication process with the robot, the server should continue to listen for incoming remote connections. • Resend immediately the incoming remote joystick control data to the motor. The motor executes the last received command as long as a new command is received. If the incoming data is not resend immediately and properly, the motor will keep on executing the last received command and will not behave properly or even will become dangerous for the surrounding objects. • Due to the fact that the gathered vision data would be used for the teaching of the robot, it is absolutely necessary that the algorithms for data conversion are operated correctly. • Safely open and close the file that consist of the robot teaching data Behaviour testing To test a real goalkeeper behavior, we have to gather enough teaching data. Firstly, several teaching cases are performed and the data is saved in the C4.5 data file. The duration of the teaching process is around 14 seconds (pure teaching time, including only shots in the goal area) and covers typical goalkeeper performance during the penalty situations (e.g. we are performing several penalty shots and the robot should try to protect the goal). Additionally, several teaching cases are performed with duration of around 6 seconds and the data is saved in the C4.5 test file. Teaching through demonstration of a RoboCup goalkeeper robot 52 As a result of the gathered data the following decision tree is produced. The format of the decision tree is automatically generated from C4.5. ball_angle <= 321 : | ball_distance <= 1209.78 : S (102.0/7.0) | ball_distance > 1209.78 : | | ball_angle <= 4 : S (11.0) | | ball_angle > 4 : | | | ball_distance <= 2544.22 : | | | | goal_center_X <= -47.834 : Rf (17.0/1.0) | | | | goal_center_X > -47.834 : S (13.0/3.0) | | | ball_distance > 2544.22 : | | | | ball_direction <= 50 : S (5.0/2.0) | | | | ball_direction > 50 : | | | | | ball_distance <= 4075.37 : Rs (12.0/3.0) | | | | | ball_distance > 4075.37 : Rf (8.0/1.0) ball_angle > 321 : | ball_distance <= 1489.95 : S (21.0/1.0) | ball_distance > 1489.95 : | | ball_direction <= 157 : S (11.0/5.0) | | ball_direction > 157 : Lf (22.0/3.0) The initiate produced decision tree does not always represent a perfect goalkeeper behavior. We have to evaluate it and if there are some weak points we have to improve then. Due to safety reasons, we have to restrict the robot to move outside of the goalkeeper penalty area. Additionally, the robot should stand still if the ball is behind it (e.g. the ball is in the goal). According to the currently generated decision tree, if the ball does not move, the robot should also not move. The ball could move into the goal direction with a different speed and if it moves too slowly, it could be considered as not movable in many cases. For example, in 30 fps the ball can be considered as not moving in 20 random frames. As a result, the motor of the robot could receive a mixed sequence of stop and movement commands, which could be a reason for the bad performance of the robot. To circumvent the mentioned problem, we do not take under consideration that the ball is considered as not movable. We repeat the last active command, until the ball is recognized as a movable and a new command is received. This could temporary solve the problem, but could arise a new problem. The ball behavior could be wrong estimated if the ball does not move. In our teaching cases, the ball is moved in the goal direction with a constant speed during the whole way to the goal, so the proposed solution for circumventing the problem could be successfully used in the current stage of the project. The newly proposed decision tree has the following format. ball_distance>4000 : S ball_angle>90 && ball_angle<270 : S goal_center_X<-750 && goal_center_X>750 : S ball_angle <= 280 : | ball_distance <= 1000 : S (102.0/7.0) | ball_distance > 1000 : | | ball_angle <= 4 : S (11.0) Teaching through demonstration of a RoboCup goalkeeper robot 53 | | ball_angle > 4 : | | | ball_distance <= 2544.22 : | | | | goal_center_X <= -47.834 : Rf (17.0/1.0) | | | | goal_center_X > -47.834 : S (13.0/3.0) | | | ball_distance > 2544.22 : | | | | ball_direction==-1 | | | | ball_direction <= 50 : S (5.0/2.0) | | | | ball_direction > 50 : | | | | | ball_distance <= 4075.37 : Rs (12.0/3.0) | | | | | ball_distance > 4075.37 : Rf (8.0/1.0) ball_angle > 280 : | ball_distance <= 1489.95 : S (21.0/1.0) | ball_distance > 1489.95 : | | ball_direction <= 157 && ball_direction!=-1 : S | | ball_direction > 157 : Lf (22.0/3.0) | | ball_direction==-1 | | ball_direction>270 With the manually made improvements on the decision tree the robot behaves much better than with the old tree. The robot manages to block almost all shots which are coming on his left side. The percentage of the blocked shots on his right side is less than 50%, but it could increase if the robot uses his arms during the game. To increase the number of blocked shots to more than 80%, we still have to improve the already generated decision tree or have to gather more teaching data. 5.3 Conclusion The main purpose of the testing process is to execute the developed software with intention to find possible problems (e.g. errors, bugs, defects). The testing process is done only manually and no additional automated tests are performed. The system is not tested under unspecified or unexpected conditions i.e. no stress test is performed. This test could be used to stress the system and could cause certain defects to be shown, which might not be manifested during the other tests. The main reason not to perform the stress test is the specific of the remote side application. The application has a simple GUI and creates only one network connection with the robot. On the robot application, the developed software mainly manipulates data and is not appropriate for a stress test. We have tested the software applications on the remote control side and on the robot, together with the overall intelligent goalkeeper behavior. • Applications testing – The system and functionality tests performed on the remote side application are done mainly for evaluation of the proper work of the joystick and its enclosure algorithms for reading the joystick data, correct overall performance and correct system data representation. On the robot side, the software application should manipulate properly the vision data and the incoming data via the network. Teaching through demonstration of a RoboCup goalkeeper robot 54 • Behavior testing – During the behavior testing, several shot are made to the goal and the robot always recognizes the correct ball direction. The percentage of the blocked shots is relatively high, but it could increase if the robot uses his arms or if teach the robot longer. In conclusion, the software applications on the remote computer and on the robot side are working properly. The goalkeeper behaves according to the taught behavior. If we want the robot to behave almost perfectly we have to perform the teaching process longer or we have to improve manually the generated decision tree. Teaching through demonstration of a RoboCup goalkeeper robot 55 6 Conclusion In this Master thesis, teaching through demonstration of a RoboCup goalkeeper robot has been implemented. We have investigated and evaluated the theoretical possibilities for teaching of an autonomous robot and practically implemented one of the machine learning methods. Current main target of the RoboCup project in FH Ravensburg-Weingarten is to develop a mobile robot that behaves as a goalkeeper. It should not be danger for the other robots and people, and should not be controlled remotely. That means that the goalkeeper should take “decisions” during the game depending on the different playing situations. It is almost impossible to program manually a behavior that could cover all situations in which the robot could be involved. To avoid this manual programming, a machine learning solution is proposed. For the implementation of the proposed solution the following two main steps have been done. • Remote control of the robot – Control the robot remotely via a joystick, where the teaching data is transferred via wireless connection. The remote control data is sent to the software application on the robot side, rather than directly to the omnidrive of the robot. The target that we want to achieve in this way of communication is to have at any single moment in the software application data concerning the robot movement. The remote control data, together with the data that comes from the vision will be converted into a proper format and will be saved in a file for further manipulation and evaluation. • Robot teaching – the saved data from the remote control and from the vision, is evaluated and structured as decision tree with C4.5. Later on, the decision tree structure is coverted to an autonomous goalkeeper behavior. During the experiments it turned out that the human trainer has to be qualified enough to perform the teaching process. It takes a lot of time and effort for him to reach a close to optimal robot control. In conclusion, the proposed solution for autonomous teaching of a robot will be used in the RoboCup project for teaching a goalkeeper behavior. The remote robot control and the behavior teaching are tested and proved to work properly. Teaching through demonstration of a RoboCup goalkeeper robot 56 7 Future issues The practical implemented solution is proven to work correctly and properly. However, to make the goalkeeper really reliable and intelligent, several further improvements could be done. Making the learned robot behavior more complicated – currently the robot could stands still and moves only to the left and to the right with two different speeds. Later on, the robot should move in any direction with a different speed. He should also try to avoid any obstacles and try to prevent possible collisions with posts and other robots. So far, for the generations of a decision tree the, C4.5 algorithm is used. For implementation of a intelligent behavior some new decision making techniques may be used. • Neural networks – systems with very strong pattern recognition capabilities and has an interconnected group of neurons that uses a mathematical or computational model for information processing based on a connection approach to computation. The neural network is an adaptive system that changes its structure based on external or internal information that flows through the network. The next step will be first to train the robot through demonstration and then to apply reinforcement learning methods to improve the robot's behavior. Teaching through demonstration of a RoboCup goalkeeper robot 57 8 Appendix 8.1 Joystick configuration Plug in the USB joystick device. dmesg – check whether the kernel recognize the plugged device modprobe joydev If joystick driver is not installed we hav eto install it manually or use the following command. yam install joystick - for Fedora apt-get install joystick - for Debian jstest /dev/input/js0 – to test the joystick device 8.2 SDL 8.2.1 Installation Download the SDL library from http://www.libsdl.org/download.php If you use the source code installation, use the following commands Run './configure; make; make install' 8.2.2 Configuration 8.2.2.1 Bild & Run SDL • Edit the file /etc/ld.so.conf, and make sure it contains the line:/usr/local/lib • If the file contains "include ld.so.conf.d/*.conf" : just go to "/etc/ld.so.conf.d" and create a new file, which should consist a row -> /usr/local/lib, or simply add "/usr/local/lib" to the "/etc/ld.so.conf" file • As root, run /sbin/ldconfig Teaching through demonstration of a RoboCup goalkeeper robot 58 • Make sure /usr/local/bin is in the execution path: export PATH=$PATH:/usr/local/bin/ 8.2.2.2 • Add SDL to the project Console compilation Append the following line "sdl-config --cflags --libs" to the end of the cmpilation command For example: gcc -o test test.c `sdl-config --cflags --libs` • Makefiles (generated with "qmake") Add somewhere in the beginning SDL_CFLAGS := $(shell sdl-config --cflags) SDL_LDFLAGS := $(shell sdl-config --libs) At the end of the line started with "CXXFLAGS " append the following line $(SDL_CFLAGS) $(SDL_LDFLAGS) In the Build rules for $(TARGET) add at the end $(CXXFLAGS), so it should looked like $(TARGET): $(UICDECLS) $(OBJECTS) $(OBJMOC) $(LINK) $(LFLAGS) -o $(TARGET) $(OBJECTS) $(OBJMOC) $(OBJCOMP) $(LIBS) $(CXXFLAGS) • Autoconf and automake – could copy the contents of 'sdl.m4' into acinclude.m4 file, and then add the following to the configure.in file: dnl Check for SDL SDL_VERSION=1.2.0 AM_PATH_SDL($SDL_VERSION, :, AC_MSG_ERROR([*** SDL version $SDL_VERSION not found!]) ) CFLAGS="$CFLAGS $SDL_CFLAGS" LIBS="$LIBS $SDL_LIBS" • Eclipse Start a new managed make project and go to project properties. Go to the C/C++ Build menu, then the Libraries submenu (the pictures are taken from [SDLEclipse]) Teaching through demonstration of a RoboCup goalkeeper robot 59 Then paste SDL. Teaching through demonstration of a RoboCup goalkeeper robot 60 9 Glossary AI – Artificial Intelligence is a science of making machines to simulate aspects of human intelligence, such as learning, reasoning, vision, understanding speech and etc. OS – Operating System is a set of computer programs that manage the hardware and software resources of a computer. USB – Universal Serial Bus is a serial bus standard to interface devices. CAN – Controller Area Network is a differential serial bus standard for connecting electronic control units. The CAN data link layer protocol is standardized in ISO 11898-1 (2003). GUI – Graphical User Interface use graphical images, special graphical element devices (widgets) or text to represent the information and actions available to a user. SDL – Simple DirectMedia Layer is a cross-platform multimedia library designed to provide low level access to multimedia devices (e.g. audio, keyboard, mouse, joystick). GNU – an operating system which is a complete free software system, upward-compatible with Unix. The name is a recursive acronym for “GNU's Not Unix“. POSIX – Portable Operating System Interface for uniX is the collective name of a family of related standards specified by the IEEE to define the application programming interface for software compatible with Unix operating systems. KDE – K Desktop Environment is a free software project which aims to be a powerful system for an easy-to-use desktop environment GNOME – GNOME is part of the GNU operating system, and is its official desktop environment. Teaching through demonstration of a RoboCup goalkeeper robot 61 10 Used literature [Python] – http://www.python.org [RCrules] Middle Size Robot League – Rules and Regulations for 2005 http://www.idt.mdh.se/rc/Mid-Size/Documents/msl-rules-2005-20050625.pdf [QTthread] C++ GUI programming with Qt3 - Jasmin Blanchelle, Mark Summerfield, ISBN 0-13124072-2 [QTtroll] http://www.trolltech.com [GTK] www.gtk.org [Xwin] www.xfree86.org/current/X.7.html [Xsystem] http://en.wikipedia.org/wiki/X_Window_System [MC] http://www.ef-uk.net/manuals/mc-20/mc18.pdf [SDL] – http://www.libsdl.org Simple DirectMedia Layer official web site. [SDLEclipse] – http://lazyfoo.net/SDL_tutorials/lesson01/linux/eclipse/index.php configure SDL library in a Eclipse developmen environment. [MLearn] – Mitchell, Tom M. 1997. “Machine learning”, ISBN: 0-07-042807-7 [C4.5] C4.5 programs for machine learning, R. Quinlan, Morgan Kaufmann, ISBN:1-55860-238-0, 1993. [C4.5Tut] – http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html –C4.5 Tutorial [C4.5man] – Linux manual pages – „man c4.5“ [Gamma] – Design Patterns: Elements of reusable Object-Oriented Software, – Erich Gamma, Richard Helm, Year 1997, page 175, ISBN: 0201633612 [Testing] – http://softwaretestingguide.blogspot.com/ Teaching through demonstration of a RoboCup goalkeeper robot 62

Development Of Algorithms And An Interface For Remote Control,

Rating

Date

Size

Views

Categories

Share

Transcript

Forgot your password?.