Problem_Solving_with_Robotics_and_Computer_Vision

Problem solving with Robotics and Computer Vision Kyle Bonell BSc Computing with Artificial Intelligence (Industry) Session 2007/2008 The candidate confirms that the work submitted is their own and the appropriate credit has been given where reference has been made to the work of others. I understand that failure to attribute material which is obtained from another source may be considered as plagiarism. (Signature of student) Problem Solving with Lego® Mindstorms and Computer Vision Summary ________________________________________________________ The report produced here is documentation of the construction, development and evaluation of a solution produced to solve a given problem using robotics and computer vision techniques. Previous years have seen similar undergraduate projects undertaken, utilising the Lego Mindstorms robotics kit to solve a variety of problems from solving a rubrics cube (Green, 2007) to maze solving (Kevan, 2003). After deliberation, highlighted in chapter two, the problem that was decided upon for the project solution to solve was surrounding the game of football. This problem is without doubt previously the most attempted by robotic based projects; it was felt that there were still fully unexplored potential solutions or enhancements for this problem to make another project viable. Arguably the biggest of these enhancements that had not been attempted yet was to implement a second robot, or intelligent agent as referred to within artificial intelligence. The terms agent and robot are used interchangeably within this report to relate to the physical Lego Mindstorms robots created for this project. The implementation of a second robot has been listed by the project as an advanced requirement however is something the project was very keen to explore and indeed succeeding in applying. Items in the appendix have been referenced as X.1 whereby X corresponds to the appendix letter and the number is the unique identifier of the item. Referencing with X as a number relate to items included within the main chapter of this report. i Problem Solving with Lego® Mindstorms and Computer Vision Acknowledgments ________________________________________________________ I would like to thank the following people for their various contributions towards the project; Tony Cohn; for his help, ideas and overall guidance throughout the project. Mum and Dad; for allowing the dining room to be taken over in order for the development of the project and in particularly my Dad for his help in creating the extra elements needed for the environment, in particular the wooden stand which held the overhead camera. Matt; for his advice on various programming issues endured and listening to random rants throughout the project. mindsensors.com; for prompt reply to emails and the development of the Compass Sensor. ii Problem Solving with Lego® Mindstorms and Computer Vision Table of Contents ________________________________________________________ Introduction ............................................................................................................................................ 1 1.1 Aim ................................................................................................................................................ 1 1.2 Objectives...................................................................................................................................... 1 1.3 Relevance of Project towards a Computing Degree ..................................................................... 2 1.4 Report Structure ........................................................................................................................... 2 Problem Background............................................................................................................................... 4 2.1 Literature Review .......................................................................................................................... 4 2.2 Similar Previous Projects ............................................................................................................... 4 2.3 Lego Mindstorms Robotic Invention System ................................................................................ 5 2.3.1 Standard Lego Bricks .............................................................................................................. 5 2.3.2 Lego Technic Bricks ................................................................................................................ 5 2.3.3 RCX Brick ................................................................................................................................ 5 2.3.4 Infra Red communication tower ............................................................................................ 6 2.3.5 Motors.................................................................................................................................... 6 2.3.6 Light Sensor ............................................................................................................................ 6 2.3.7 Rotation Sensors .................................................................................................................... 6 2.3.8 Pressure Switches .................................................................................................................. 7 2.3.9 Third Party Sensors ................................................................................................................ 7 2.4 Robotic Command eXplorer Brick ................................................................................................. 7 2.4.1 RCX Architecture .................................................................................................................... 7 2.4.2 Sensor Ports ........................................................................................................................... 9 2.4.3 Motor Ports ............................................................................................................................ 9 2.4.4 RCX Extras ............................................................................................................................ 10 2.4.5 RCX Programming ................................................................................................................ 10 2.5 Infra Red Communication ........................................................................................................... 12 2.6 Robotic Designs and Mechanisms .............................................................................................. 12 2.6.1 Robot Locomotion................................................................................................................ 13 2.6.2 Wheel Positioning ................................................................................................................ 13 2.6.3 Wheel Drive Designs ............................................................................................................ 13 2.6.4 Localisation .......................................................................................................................... 14 2.7 Computer Vision ......................................................................................................................... 15 iii Problem Solving with Lego® Mindstorms and Computer Vision 2.7.1 LeJOS Vision System ............................................................................................................. 15 2.7.2 RoboRealm ........................................................................................................................... 16 2.7.3 OpenCV ................................................................................................................................ 16 2.8 Potential Problems...................................................................................................................... 16 2.8.1 RoboCup ............................................................................................................................... 16 2.8.2 RoboCup-Rescue .................................................................................................................. 17 2.8.3 Mathematical Puzzles .......................................................................................................... 17 Development Methodology and Planning ............................................................................................ 19 3.1 Development Methodology ........................................................................................................ 19 3.2 Planning....................................................................................................................................... 21 Design.................................................................................................................................................... 22 4.1 Chosen Problem .......................................................................................................................... 22 4.2 Computer Vision ......................................................................................................................... 22 4.3 Environment Design .................................................................................................................... 24 4.3.1 Pitch ..................................................................................................................................... 24 4.3.2 Camera ................................................................................................................................. 24 4.3.3 Infra Red Tower.................................................................................................................... 24 4.4 Robot Design ............................................................................................................................... 24 4.4.1 Locomotion and Rotation .................................................................................................... 25 4.4.2 Ball Control........................................................................................................................... 25 4.4.3 Goal Scoring ......................................................................................................................... 26 4.4.4 Collision Detection ............................................................................................................... 26 4.5 Lego Mindstorms Architecture ................................................................................................... 27 4.6 Communication ........................................................................................................................... 27 Implementation .................................................................................................................................... 28 5.1 Computer Vision ......................................................................................................................... 28 5.2 Environment Design .................................................................................................................... 30 5.2.1 Pitch ..................................................................................................................................... 30 5.2.2 Camera ................................................................................................................................. 30 5.2.3 Infra Red Tower.................................................................................................................... 30 5.3 Robot Design ............................................................................................................................... 30 5.3.1 Localisation .......................................................................................................................... 31 5.3.2 Locomotion and Rotation .................................................................................................... 34 5.3.3 Ball Control........................................................................................................................... 34 iv Problem Solving with Lego® Mindstorms and Computer Vision 5.3.4 Goal Scoring ......................................................................................................................... 35 5.3.5 Collision Detection ............................................................................................................... 35 5.4 Lego Mindstorms Architecture ................................................................................................... 36 5.5 Communication ........................................................................................................................... 37 Testing ................................................................................................................................................... 39 6.1 Test Plan ...................................................................................................................................... 39 Evaluation ............................................................................................................................................. 41 7.1 System Components ................................................................................................................... 41 7.1.1 Communication .................................................................................................................... 41 7.1.2 Locomotion .......................................................................................................................... 42 7.1.3 Rotation................................................................................................................................ 43 7.1.4 Localisation .......................................................................................................................... 43 7.1.5 Ball Finding ........................................................................................................................... 45 7.1.6 Goal Scoring ......................................................................................................................... 46 7.1.7 Collision Detection ............................................................................................................... 47 7.2 Final System ................................................................................................................................ 47 7.3 Minimum Requirements ............................................................................................................. 47 7.4 Advanced Requirements ............................................................................................................. 48 7.5 Project Schedule Evaluation ....................................................................................................... 49 Bibliography .......................................................................................................................................... 50 Appendix A – Personal Reflections ....................................................................................................... 52 A.1 Project Successes ........................................................................................................................ 52 A.2 Project Failures ........................................................................................................................... 52 A.3 Lego Mindstorms Project Advice ................................................................................................ 52 A.4 General Undergraduate Project Advice ...................................................................................... 53 Appendix B – Project Schedule ............................................................................................................. 54 Appendix C – Results ............................................................................................................................. 55 Appendix D - Figures ............................................................................................................................. 57 Appendix E – Final Solution Photographs ............................................................................................. 66 v Problem Solving with Lego® Mindstorms and Computer Vision Chapter One Introduction ________________________________________________________ This chapter highlights the aims and objectives of the project as well as linking the relevance of the task at hand towards a computing degree. The minimum and extended objectives are listed here along with more generalised objectives of the project. This chapter also details how the report aligns with the project management methodology used, detailed in chapter three. 1.1 Aim To design and build a robot utilising the Lego Mindstorms robotics kit that can complete a predefined task with relative success. In order to effectively complete the task the robot will utilise computer vision theories and methods as well as other artificial intelligence ideas and concepts. The construction of the robot will include designing both the hardware and software elements of the robot, programming the robot to perform actions required to complete the task. An example task for the robot to be able to play a version of football, a problem that has been studied for multiple projects in previous years. The robot would be required to exploit video input and possibly other sensory inputs to perform a number of football skills, such as scoring a goal. 1.2 Objectives The main objective of this project was not to develop a wholly complete, bug free solution to the given problem rather advance on work done in previous years with the Lego Mindstorms toolkit. Also investigating previously not attempted or unsuccessful computer vision elements that could be introduced into the final system was another main objective of the project. However the successfulness of the project would be based on a set of minimum requirements which were outlined before the problem upon which the solution would attempt to solve was decided. Therefore these, and the extended, requirements are generic and not constricted to any of the potential problems that could be undertaken. The minimum requirements are as follow;  Define a suitable objective or task for the robot to complete which incorporates basics of robotics and elements of computer vision.  Construct a robot which is able to complete the defined task. The robot must also be able to overcome a computer vision problem utilising video input.  Create an algorithm which enables the robot to complete its task in an efficient and effective way overcoming any limitations of the robot design wherever possible. 1 Problem Solving with Lego® Mindstorms and Computer Vision  Design and implement effective software enabling the robot to manipulate its environment in order to complete the defined task.  Design a way to evaluate the success of the robot and also to include evaluation of the robot in different environments, such as differently lit environments as this can seriously affect many computer vision problems, in order to investigate the robustness of the robot and its algorithms. Potential advancements to the minimum requirements of this project;  Build a second robot as to give the initial robot direct competition in solving the problem  Build a second robot to act as a “team mate” to the initial robot helping it complete the problem  Research possible ways in which the robot can complete the task more efficiently or successfully. 1.3 Relevance of Project towards a Computing Degree As the title of this project suggests there were two different aspects covered. The first involved the construction and programming of the actual robot. The relevance of this to a computing degree is clear throughout this project as advanced programming skills and knowledge are required to achieve the goals of this project. The second aspect focuses on utilising computer vision to help solve the problem more accurate than by merely using the Lego Mindstorms toolkit. This is again quite easily related back to the computing degree as image processing and computer vision modules play an ever increasing role in computing degrees. 1.4 Report Structure The structure of the report and how each chapter aligns with the methodology being adopted for the project, as discussed in chapter three, is detailed below. Chapter One; Outlines the aims and objectives relating to the initial inception phase by gather initial requirements. Chapter Two; Consists of a literature review of a variety of sources covering all aspects to be dealt by the project, this also relates to the inception phase acquiring research so project decisions can be made. Chapter Three; Discusses the methodologies used in similar undergraduate projects from one year previous and the methodology used for this project. Chapter Four; Divides the project up into components and outlines the possible design choices for each, this is the elaboration phase of the methodologies as design choices are reviewed. 2 Problem Solving with Lego® Mindstorms and Computer Vision Chapter Five; Illustrates the final design of the system including detailed explanations of algorithms and source code used. This chapter links to the construction phase. Chapter Six; Details what tests will be undertaken on all components individually and then on the final system as a whole. This is effectively the transition phase, as there are no end-users of the system the feedback from this phase comes in the form of the test results. Chapter Seven; Here the system is evaluated on a component by component basis, on a final solution basis and then against the initial requirements of the project. This chapter also discusses and evaluates the iterations taken over the course of the project for each component where necessary. 3 Problem Solving with Lego® Mindstorms and Computer Vision Chapter Two Problem Background ________________________________________________________ This chapter highlights the investigations undertaken for the development of the project, with a view to being able to successfully complete the aims stated in chapter one. This chapter is divided into subsection based on the different key elements of the project such as the hardware, potential software and potential theories that could be used. 2.1 Literature Review A literature review was carried out before undertaking any other aspects of the project. As this type of problem had been attempted as undergraduate projects many times before, the starting point for this review was the reports based on the relevant previous projects. Some of the information sources used within the past projects were deemed relevant and therefore in themselves were reviewed such as the book ‘Extreme Mindstorms: An Advanced Guide to Lego Mindstorms’ by Baum et al. Additional source information finding was also undertaken whereby further books, journals and web resources were found especially useful and relevant for the project. One of these resources especially valuable was the book by Ferrari et al entitled ‘Programming Lego Mindstorms with Java’. All resources used have been cited and are included within the bibliography of the report. The review aimed to answer several question before starting the project; What is Lego Mindstorms' What are the capabilities of Lego Mindstorms' What is available to program the robot' What is available to program the computer vision' What concepts will the robot require' What problems have been tackled in previous projects' What problems could be tackled by this project' 2.2 Similar Previous Projects Over the past few years multiple projects have been undertaken using Lego Mindstorms. A selection of these projects is to be analysed in this literature review and throughout the various chapters of the project. The projects that have been focused on include both projects involving Lego Mindstorms from the year previous to this project (Beattie, 2007) (Green, 2007) plus a variety of other projects using Lego Mindstorms that were highly graded (Ashmore, 2006) (Barrett, 2004) (Dodds, 2005) (Kevan, 2003). Earlier projects to these were not looked into as it was thought the 4 Problem Solving with Lego® Mindstorms and Computer Vision concepts and developments of these would have been evaluated by the projects reviewed in this report. 2.3 Lego Mindstorms Robotic Invention System The toolkit that will be utilised to solve the chosen problem will be the Lego Mindstorms Robotics Invention System. Typically aimed at children under the age of 11, this development kit can be manipulated as such to give the technology sufficient degree of complexity to warrant study and analysis of fundamental robotic and artificial intelligent concepts at a higher education level with this toolkit. The Lego Mindstorms Robotic Invention System comprises of over 700 pieces of Lego, both the standard and Technic Lego bricks. The aspects of the kit of most interest to this project are the intelligence parts. These include; the RCX brick, the Infra Red communication tower, motors and a collection of sensors (Ferrari, et al., 2002a). These significant parts of the Lego Mindstorms Robotic Invention Kit are discussed below; 2.3.1 Standard Lego Bricks The standard Lego bricks included with this project are that which gave the company producing this kit the large share of the toy industry it has today. (Lego.com, 2007) The bricks were of an actual “brick” form (Figure D.1), hence the name Lego “bricks”. These are often rectangular blocks which can be snapped together to build numerous objects, mainly structures (Figure D.2). 2.3.2 Lego Technic Bricks The Lego Technic bricks are an enhancement on the standard Lego bricks that enables the users of the product to build more complex movable parts (Figure D.3) (Technic, 2007). These bricks are of more interest to this project as the standard bricks will more than likely prove far too rigid to be able to offer a successful design. Technic bricks have been designed with movement in mind and should provide an able design solution to the problem which has been proved many times previously in a variety of different ways. Ferrari outlines and discusses numerous ways to utilise these Technic bricks to form complex design solutions. Relevant suggestions from Ferrari are discussed in section 3.3 (Ferrari, et al., 2002b). 2.3.3 RCX Brick The Robotic Command eXplorer (RCX) brick (Figure D.4) is the “brain” of any Mindstorms robots (Ferrari, et al., 2002a), being used to transfer signals to and from sensory inputs via wires and wirelessly with the infra-red communication tower (Section 2.3.4). Although the RCX brick has been designed by Lego to look like a regular brick it is actually a small computer system consisting of a 5 Problem Solving with Lego® Mindstorms and Computer Vision CPU, display, memory and peripherals. The RCX brick is split up into four architectural layers; hardware layer, system ROM Layer, firmware layer and a layer made up of user designed programs (Baum, et al., 2000). This part of the Mindstorms kit is a crucial element of the project and is therefore discussed in more detail in section 2.4. 2.3.4 Infra Red communication tower The infra red communication tower (Figure D.5) is the tool used to transfer data and allow communication between the host computer and the robot, specifically the RCX. If the extension of adding a further robot is to be included consideration needs to be taken as to how the infra red tower is going to be able to communication with both RCX bricks seeming simultaneously. This problem was highlighted in a previous project (Green, 2007) and a solution which utilised the Java communication package to open new ports for each communication was devised. This is discussed in further detail in section 2.5. 2.3.5 Motors The motor (Figure D.6) is what will drive the robot should a non static solution be implemented. The motor is sufficiently intelligent enough to be able to run a constant speed even if the power supply should alter slightly. The motor could also be utilised to control ‘arms’ if they are required by the solution such as with the Rubik cube robotic solution (Green, 2007) or with the latest attempt at a robotic footballer (Beattie, 2007). 2.3.6 Light Sensor The light sensor (Figure D.7) works by returning a value between 0 and 100 which relates to the percentage of light that the sensor is detecting. It is also able to detect Infra Red signals which may proof useful if the RoboCup problem, detailed in section 2.8.1, is undertaken in detecting the infra red emitting ball. The light sensor has also been utilised in past projects to form part of a localisation system (Barrett, 2004) by monitoring a grey-scale floor with the light sensor. 2.3.7 Rotation Sensors The rotation sensors (Figure D.8) are able to record the amount an axle has rotated. This sensor could be useful for a non-static solution in detecting the distance the robot has travelled, the current angle of the robot or, as previously used by Barrett (2004), as a method of dead reckoning self localisation. The rotation sensors come with a number of inaccuracies errors which have also been detailed by Barrett, although is still recommended as a viable solution. 6 Problem Solving with Lego® Mindstorms and Computer Vision 2.3.8 Pressure Switches Pressure switches, also known as ‘touch sensors’ (Figure D.9), are able to detect an impact or collision with another object as the sensor is pushed in. The sensor then returns a Boolean 100% voltage value to indicate a collision has been made. If multiple robots are to be implemented, these sensors could be used to detect if the robots collide. Certain movements or instruction could be then sent to the robot as to free it from its immovable state, or similarly used for collisions against the boundaries of the environment. 2.3.9 Third Party Sensors In Baum’s book ‘homebrew’ sensors for the Lego Mindstorms kit are discussed in detail with Baum going into such details of how to make sensor that can be connected to the RCX (Baum, et al., 2000). This potential meant that any type of sensor could be connected to the RCX (Barrett, 2004). Further research into this area was undertaken as to investigate if any third party sensors were available that could be useful as the creation of such a sensor was outside of scope for this project. The most interesting sensor found was a compass sensor (Figure D.10) produced by mindsensors.com. The “Compass Sensor for RCX is high precision sensor that connects to an RCX input port. This sensor measures the earth's magnetic field and reports heading angle clockwise from magnetic north.” (mindsensors.com, 2006). This could prove useful as part of a dead reckoning system in determining at which angle the robot is currently facing however the actual accuracy is undefined as no test results could be found for this sensor. 2.4 Robotic Command eXplorer Brick Further to the description of an RCX given in section 2.3.3 this section of the report details the structure of the RCX as discussed by Baum in his book ‘Extreme Mindstorms’ (Baum, et al., 2000). 2.4.1 RCX Architecture The RCX is broken down into several layers of which byte codes are sent between in order for a user to be able to control the RCX at a low level. These layers (Figure D.11) are described below; Hardware Layer The bottom layer in the RCX architecture is the hardware layer. This layer consists of a microcontroller, an LCD and memory. Also in this layer are additional electronic components; however it has been deemed that these are not relevant for discussion (Baum, et al., 2000). 7 Problem Solving with Lego® Mindstorms and Computer Vision System ROM Layer Within the microcontroller lies an area of Read Only Memory. This comes with low level software installed, known as the system ROM, to provide an interface to the hardware. Subsequently making if far simpler to manipulate the hardware as required; for example displaying a number on the LCD. However the most useful application of which the system ROM is used for is to enable a firmware to be loaded onto a separate layer within the RCX that can manipulate the system ROM (Baum, et al., 2000). Firmware Layer The system ROM enables the second piece of the software, known as the firmware, to be loaded into memory. The firmware can then be used to manipulate the system ROM software or even bypass the system ROM software and directly control the hardware layer. Unlike the permanent system ROM the firmware can be erased by simply leaving the RCX without power for a period of time. As this firmware can be loaded onto the RCX it means that different firmware software has been developed in order to allow the user different options to program the RCX (Baum, et al., 2000). The standard firmware given with the Lego Mindstorms kit is needed when developing programs for the RCX with any of the ‘official’ development environments such as RCX Code. This firmware is also for a C based programming environment, NCQ, both environments are described in section 2.4.5 (Baum, et al., 2000). Since previous projects investigated and highlighted the limitations of his software (Barrett, 2004) a new version, RIS 2.0, of the standard firmware has been released by Lego overcoming many of the limitations highlighted such as the thirty-two variable limit. However a limitation still exists within this firmware whereby the software does not provide support for the development of multi RCX communication (Green, 2007). Therefore starting a development using the standard firmware would result in a single robot solution only, not allowing the inclusion of a second robot into the solution to be explored. There are also a number of other ‘non-official’ RCX firmware software, such as BrickOS (formerly LegOS), available that have been discussed in previous projects (Dodds, 2005) (Beattie, 2007). Programmed in C, this implementation requires a deep, complex low level knowledge (Dodds, 2005). Therefore, as with the previous projects, this firmware was ruled unfeasible for use as part of the solution for this project. As a result this environment is not discussed any further in section 2.4.5. The favoured firmware of recent past projects, where the Lego Mindstorms toolkit has been used, was the LeJOS implementation (Beattie, 2007) (Green, 2007). As outlined by these projects the advantages of using this implementation of firmware outweigh the seemingly only major 8 Problem Solving with Lego® Mindstorms and Computer Vision disadvantage of using this firmware; having to overwrite the standard firmware and install the LeJOS software. This has been highlighted as a disadvantage as it may add extra, unnecessary, complications to the project; yet both Green and Beattie were able to successfully implement LeJOS into their solutions therefore it was felt this project would also be able to achieve this. Advantages of the LeJOS firmware alone, not the LeJOS programming options, these advantages are discussed in section 2.4.5, include crucially the ability to be able to communicate with multiple RCX bricks. Other advantages of this firmware include increasing the RCX brick functionality making it possible to use arrays and floating point numbers when programming the RCX (Ferrari, et al., 2002a). User Program Layer Above the firmware layer is the layer consisting of the user created programs which manipulate the firmware in order for the robot to be able to perform a set of commands. For example in the LeJOS implementation (Figure D.12) a program is created by the user in Java along with the LeJOS libraries on the host computer. This program is then compiled by the Java based LeJOS compiler which generates the binary code that can be executed on the RCX by the LeJOS firmware. This compiled, binary version of the program is then downloaded to the RCX over IR communications (section 2.5) where the program is executed by the LeJOS firmware, thus providing an interface for the features and functionality of the RCX (Baum, et al., 2000) (Solorzano, et al., 2006). 2.4.2 Sensor Ports The RCX contains three sensor ports which allow any of the sensors mention in section 2.3 to be connected to the RCX. These sensors can then be used by the RCX to understand more about its environment; an example of this is as mentioned in section 2.3.6 where the light sensor is used along with a greyscale pitch in order to help the RCX localise itself within the environment (Barrett, 2004). All sensors that can be connected to the RCX can be split into two groups; passive or active. Passive sensors include those similar to the pressure switches whereby they do not require any power from the RCX acting as a simple resistance (Baum, et al., 2000). An example of an active sensor is a light sensor whereby the sensor needs to be powered by the RCX to be able to function. The importance of this is that the RCX needs to know which type of sensor is connected to each port. Therefore within the program at some point the RCX will need to be instructed which type of sensor is connected to each port as to be able to exploit each connected sensors correctly. 2.4.3 Motor Ports Motor ports or ‘output ports’, as referred to by Baum, can theoretically provide power to any external device that can be connected to the RCX. However for the scope of this project the only 9 Problem Solving with Lego® Mindstorms and Computer Vision device necessary to connect to these ports are indeed motors. A motor can be in three modes: on, off or floating. Floating is referred to by Baum as being “in neutral when driving a car” whereby the motor is not powered however is still moving freely. When the motor port is in the ‘on’ mode, forward or reverse commands can be sent. Furthermore the power level can also be adjusted which may prove useful in this project as it could potentially give more control to the robot over movements if they are be slowed. 2.4.4 RCX Extras Also discussed in significant detail by Baum in respect to the RCX brick are various other feature of the brick such as the LCD (Figure D.13), Sound, Timing and the Datalog. As noted also by Barrett the key points to take from Baum’s discussions are; Liquid Crystal Display (LCD); The LCD display is capable of displaying “a four-digit signed number and a single-digit unsigned number” (Baum, et al., 2000). A good example of how the RCX LCD has been utilised whilst developing a solution is for debugging purposes whereby the RCX displays a series of number which relate to certain errors that occur from the user programs loaded onto the RCX. Sound; The RCX contains an onboard speaker which allows functionality for predefined “system sounds” to be played. This has been manipulated recently in order to allow more complex sounds, such as simple melodies, to be played through the RCX (Truffelli, 2006). As noted by Barrett (2004) this could potentially be used to allow communication between RCX bricks however this would be a primitive and unreliable method of communication. Timing; The firmware level of the RCX includes a system clock which provides the time in hours and minutes. Most programs require time to a much higher degree of accuracy than this therefore timers can be implemented that measure time increments by 100ms. Datalog; Another standard firmware feature of the RCX is the datalog from which a program can store a sequence of values that can be later uploaded to, for example, the host computer for analysis. 2.4.5 RCX Programming The RCX brick since its launch has been “hacked” by the robotic community so that non-standard firmware can be installed into the RAM of the brick as described previously in section 2.4.1. The usefulness of this is that different programming languages and tools can be used to develop the solution. This section considers different programming environments that exist for a Lego Mindstorms solution. 10 Problem Solving with Lego® Mindstorms and Computer Vision RCX Code RCX Code is the original programming software that comes with the Lego Mindstorms development kit. This is aimed at the tools intended audience, children under the age of 11, and is therefore very simple with a brick-like graphical user interface to blend with the Lego theme. All previous projects that have been analysed have deemed that this basic approach is not viable for a project of this scale: it is neither complex enough nor has sufficient ability to provide complex tools that will be required by the project solution. Not Quite C (NQC) NQC is a creation of David Baum, working on the standard firmware built into the RCX brick and based around programming in C, as the name of the language would suggest (Baum, et al., 2000). Running on the standard RCX firmware is a major advantage of this language although this is also a flaw, as discovered by previous projects (Ashmore, 2006): it does not allow the developer a depth of controls available through languages that don’t use the standard firmware. The main problem that Ashmore (2005) encountered with the NCQ language was the ability to create a vision system into the solution. As the vision aspect of this project was considered a key element, this language was not to be used for the development of the solution. This language had been used with a degree of success in other, earlier projects’ (Barrett, 2004) solution however these did not include any computer vision elements. LeJOS LeJOS requires the firmware on the RCX brick to be altered from the standard, implementing its own version onto the brick which takes around 17kb of the bricks RAM (Solorzano, et al., 2006). This firmware is based on a significantly trimmed Java Virtual Machine which essentially contains a Java API to allow access to RCX hardware resources. As a result the programming language used by this implementation is Java. The advantages of using this system are that the system provides “a complete, state-of-the-art language that is fast, efficient and extremely portable.” (Ferrari, et al., 2002a). The LeJOS package also includes a vision library (Griffiths, 2007) which previous projects (Ashmore, 2006) (Beattie, 2007) (Dodds, 2005) have utilised to good effect in their final solutions. This is discussed in greater detail in section 2.7.1. Further to these direct advantages more abstract advantages are gained if this implementation is used: such as the vast array of previous research has been undertaken into using this implementation alongside the Lego Mindstorms kits. An example of this research is the book by Ferrari (2000a) which describes LeJOS in significant detail. The LeJOS package also includes various example program source codes for the different libraries included which could also prove to be very helpful in the development of a solution. A further crucial abstract 11 Problem Solving with Lego® Mindstorms and Computer Vision advantage of LeJOS is that the programmer has a wider range of experience in Java over that in any of the other languages on offer in the other implementations. 2.5 Infra Red Communication The Lego Mindstorms toolkit utilises the Infra Red (IR) technology to allow communication between the host computer and potentially any number of RCX bricks. The details of how the infra red technology works has been concluded to be out of scope for a detailed discussion in this report. There is, however, some key factors of this technology that need to be considered, of which the most significant of these factors being interference. As infra red is thought of as a beam of light, the interference could potentially cause unnecessary errors if the environment is setup or located in the wrong manner; see section 3.2 for detailed design discussion on the environment. The main source of infra red interference comes from heat as this emits infra red therefore devices, such as a lamp, could potentially be disruptive to the communications in this project (Schreiner, 2000). Infra red also has a limited range and requires a direct line of sight to work effectively therefore environment designs will have to be based around these limitations. The infra red communications within the Lego Mindstorms toolkit specifically work by sending byte code messages between the sender and recipient. This is possible through the inclusion of a buffer within the RCX brick where the byte code last received is stored. A user program can query or clear, allowing a new value to be read by the buffer, at any time (Baum, et al., 2000). With the LeJOS communication package, and similar other advanced firmware, addressing can be used as to enable the use of multiple RCX bricks receiving commands from one infra red tower on a host computer. In LeJOS this is done by first ‘naming’ an RCX with a byte code in the user program that is loaded on to the RCX. This ‘naming’ is actually naming a port of which the RCX keeps open whenever the program is running on the RCX. Then when messages are sent from the host computer using the RCXLNPAdressingPort class from the josx.rcxcomm it is able to open a port with the same byte code as that assigned to the port on the RCX program enable communication only to the RCX with the given port byte code open (Solorzano, et al., 2006). 2.6 Robotic Designs and Mechanisms This section of the report is more relevant to the project if a problem is undertaken that requires the solution to be a non static solution. However it can also be related to a potential static solution as there will still be a need for some moving elements, for example a robotic arm to move static elements, pieces on a game board, around its environment. The details of the theories highlighted here will be discussed in more detail throughout chapter three. 12 Problem Solving with Lego® Mindstorms and Computer Vision 2.6.1 Robot Locomotion For a robot to become non static, a way of mobilising the robot must be devised. All previous projects with non static robots have used wheels as a means of locomotion (Ashmore, 2006) (Barrett, 2004) (Beattie, 2007) (Dodds, 2005) however there are also other possible alternative, such as tracks (Figure D.14) or legs (Figure D.15). The popularity of wheels with past projects comes as no surprise as this is seen by many to be the easiest and simplest method of locomotion to implement. This is said to be because to carry the same ‘payload’, a more complex and heavier hardware solution is required if using either of the tracks or legs locomotion design (Jones, et al., 1998). As a result of these findings in this section it is clear that is would be impractical to research tracks or legs further as this will not provide any gain in achieving an optimal solution to a problem requiring a non static robot. 2.6.2 Wheel Positioning As discussed in some detail by Ashmore (2006) there are a number of ways that the wheels can be positioned around the robot to allow locomotion which give different results. Ashmore suggests the two simplest methods are the ‘car’ and the ‘wheelchair’ (Figure D.16), although Beattie (2006) implemented a third method whereby only two wheels are used. The ‘car’ method takes its design from modern motor vehicles whereby either the front or rear wheels can be used to drive the vehicle. The front wheels are used on a pivot rack in order to enable steering of the vehicle. A front wheeled drive approach is unfeasible in a solution build with Lego Mindstorms as the parts are not available to connect a motor to the pivot system. A major limitation of the car design is the turning circle: which is limited to 80 degrees (Ashmore, 2006). The ‘wheelchair’ method uses two large rear wheels that drive the vehicle and two smaller pivot wheels towards the front of the vehicle, as with a wheelchair. The front wheels merely provide balance to the vehicle. The rear wheels are independent of each other which allow a zero turning circle, achieved when the rear wheels are spinning in opposite directions (Ashmore, 2006). A variant of the ‘wheelchair’ design was used by Beattie (2006) whereby the front wheels where simple not used and the robot balanced as such it could successfully drive on two wheels. This approach was also used in a successful robot design (Figure D.17) which entered the RoboCup Junior competition (Lund, et al., 1999). 2.6.3 Wheel Drive Designs In previous years a number of wheel drive designs have been investigated with the main options being a direct drive system and a dual differential drive system (Dodds, 2005) (Ashmore, 2006) 13 Problem Solving with Lego® Mindstorms and Computer Vision (Beattie, 2007). Of the three past projects only one (Dodds, 2005) managed to successfully implement the more complex dual differential drive system. The dual differential drive system (Figure D.18) is made up of two differentials in parallel. A differential uses two axels and a system of cogs to provide the vehicle with a drive system; one motor will power the wheels when they are spinning in the same direction and a second motor powers the wheels when they need to be spun in different directions. A disadvantage of this implementation is the lack of power provided to the drive system; at any one time, only one of the two motors is driving the robot. Due to the weight of the RCX when loaded with the batteries this proved to be a significant problem as discovered by a previous project (Beattie, 2007). The direct drive system is a much simpler system and involving one motor driving one wheel. This is how Beattie (2006) and Lund (1999) decided to implement the drive system on top of the modified ‘wheelchair’ wheel positioning design (section 2.6.2) whereby one motor would control each wheel, moving the wheel in a forward or reverse direction providing the solution with a powerful zero turning circle locomotion. 2.6.4 Localisation For a non static robot to be able to complete any task successfully either the robot or the host computer controlling the robot must be able to identify whereabouts within the environment the robot is located. Perfect localisation would consist of knowing the x, y (two dimensional coordinates) and orientation) for the robot at any point during the program. A form of the ‘dead reckoning’ has been the main method of localisation that has been explored by previous projects thus far each time finding new problems or degrees of inaccuracies for various reasons (Ashmore, 2006) (Barrett, 2004). This method requires the starting location of the robot to be known then from this starting point each movement is tracked. The x, y and values are then calculated and updated based on what movements have been recorded. Previous implementations of this method have utilised the rotation sensor which can determine x, y and to a degree of accuracy. The light sensor has also been introduced in combination with the RoboCup Junior greyscale pitch to help improve the accuracy of the dead reckoning system based on the rotation sensor (Barrett, 2004). Another method of localisation that has been used in a previous project (Dodds, 2005) is navigation by sensory input. The success of this implementation heavily relied upon the bespoke environment of which Dodds’ solution was tested and evaluated within. The method used touch sensors and ‘whiskers’ which moved along the walls of the environment. When a touch sensor no longer made 14 Problem Solving with Lego® Mindstorms and Computer Vision contact with a wall, the robot was instructed to move back towards that wall until the touch sensor was pressed again. This method would be useless for generic environments. A method which had not been successfully implemented by any of the past projects was to use a computer vision based system to localise the robot on the host computer. Ashmore (2006) attempted to use an overhead camera to locate the robot but experienced difficulties and as a result the final solution was based on a dead reckoning method as seen in previous projects to Ashmore’s. However Ashmore did implement a vision system, using a camera mounted on the robot, to locate the ball which gave sufficiently effective results for this solution to be mirrored in Beattie’s approach the following year, further details of this solution are discussed in section 4.2. Through online resource searching another project was discovered from outside the University of Leeds which also utilised computer vision, Lego Mindstorms and the LeJOS firmware, discussed in section 2.4.1 (Russell, 2005). This implementation mirrored that of which Ashmore unsuccessfully attempted to implement. Details of this are discussed in section 4.2. 2.7 Computer Vision After looking into previous projects that utilised computer vision to solve a problem, it was clear that the development of a bespoke computer vision system would not be feasible in the time scale of this project. The reasoning behind this is the creation and implementation of the actual robot is seen as the priority rather than creating a new vision system. If a vision system was to be developed from scratch the fear of the project was that it would lead away from its initial aim of creating a robotic solution. From analysis of the past project that utilised computer vision (Dodds, 2005) (Beattie, 2007) (Ashmore, 2006) it was discovered that there are already open-source vision system that are available and could be utilised by this project. 2.7.1 LeJOS Vision System LeJOS vision system is an extension to the LeJOS programming language that “provides motion detection, colour detection, light detection and interfacing with robots that use the Lego Mindstorms RCX brick, to allow Mindstorms robots to respond to what they see.” (Griffiths, 2007) This system will support most PC webcams that provides a real time video of what the camera is viewing by building upon the powerful Java media framework. This package has been utilised by various previous projects (Dodds, 2005) (Ashmore, 2006) (Beattie, 2007) with successful enough results for it to be recommended to be used in future projects. The advantage of this system is that it is integrated with the LeJOS package; improving the success of the solution by being able to directly control low level RCX commands and vision elements from within the same program. 15 Problem Solving with Lego® Mindstorms and Computer Vision 2.7.2 RoboRealm “RoboRealm® is a powerful robotic vision software application for use in computer vision, image processing, and robot vision tasks. Using an easy to use point and click interface complex image analysis and robot control becomes easy!” (RoboRealm.com, 2007) This vision system is another system that could potentially be used by the robot and is also available as freeware although has not been used in the past by any other projects that have been covered in this review. The major disadvantage of this program is the lack of resources available, such as relative examples or tutorials, and also the programmer’s lack of experience with this software. 2.7.3 OpenCV OpenCV was an option considered before the development of a new bespoke vision system was ruled out of scope of the project. OpenCV is an open source computer vision library that allows complex computer vision programs to be developed to run cross platform (Intel, 2008). 2.8 Potential Problems Potential problems that the project could aim to solve are discussed in this section of the report. The main problems covered by previous projects have been discussed and also similar potential problems that are yet been explored. 2.8.1 RoboCup RoboCup is an international project that hopes to promote the use of Artificial Intelligence, Robotics and other related fields by giving a standard problem which a variety of technologies can be used to attempt to solve. RoboCup uses football, otherwise known as soccer, as this standard problem from which innovative solution can be produced. The aim of the project is “By 2050, develop a team of fully autonomous humanoid robots that can win against the human world champion team in soccer.” (RoboCup, 2007) A possible problem that the solution robot could solve is that identified in the RoboCup competition, to successfully play a version of soccer. This problem is one that has been tackled numerous times before, with mixed results by previous year’s students. The latest two attempts at this problem have also incorporated computer vision with a camera mounted on the robot, discussed in section 4.2. Latter projects have focused on utilising only the Lego Mindstorms kit (Barrett, 2004). Although this problem has been undertaken multiple times it is still deemed viable. The work of Beattie was not extensive and only managed to create a robot that performed the very basic functions with no mention of localisation or the use of an environment. It is believed that there is still a significant 16 Problem Solving with Lego® Mindstorms and Computer Vision amount of work that could be done on this problem that has not already been attempted of achieved such as adding an additional robot. 2.8.2 RoboCup-Rescue “The intention of the RoboCupRescue project is to promote research and development in this socially significant domain at various levels involving multi-agent team work coordination, physical robotic agents for search and rescue, information infrastructures, personal digital assistants, a standard simulator and decision support systems, evaluation benchmarks for rescue strategies and robotic systems that are all integrated into a comprehensive systems in future.” (rescuesystem.org, 2007) This problem has again also been covered by a previous project (Dodds, 2005) in which the results of the project were generally of a successful nature. The robot produced from this project was able to navigate through a maze and identify a target and return to the start of the maze. The bespoke nature of this project has meant that any additions to the work done previously would first require the stage of this project to be undertaken; for example constructing the environment. Hence if this problem was to be undertaken a different perspective would have to be taken on the problem as to not merely replicate the work of the original project. 2.8.3 Mathematical Puzzles A potential problem exists in the form of mathematical puzzle, as shown in Green’s project based around the Rubik’s Cube. Other potential mathematical puzzles could be attempted as discussed below. Rubik’s Cube The Rubik’s Cube (Figure D.19) problem, as mentioned earlier, was covered in a previous project (Green, 2007). This problem works on the concept of twisting and turning a cube consisting of 3 x 3 x 3 smaller cubes with colour edges until the sides on the larger cube are all of the same colour. The solution that was created by the previous project was a static robot that was capable of working out the solution to the problem then moving and twisting the cube until it was complete. This solution involved the initial state of the cube, i.e. the starting colours of each square on each sides of the cube, to be hard coded in. Obviously a project into this area would have to build on work already done in this area as to not replicate the work of the previous project. This could be done by implementing a vision system to the initial state of the cube or to detect errors made by the solution. Towers of Hanoi 17 Problem Solving with Lego® Mindstorms and Computer Vision The Towers of Hanoi (Figure D.20) problem involves eight disks, “initially stacked in increasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs (the rightmost one in the applet below), moving only one disk at a time and never a larger one onto a smaller.” (cut-the-knot.org, 2007) This problem could be attempted in a similar way to how Green solved the Rubik’s Cube problem with a static robot that can manipulate the game until the solution is found. A potential challenge of this problem would be being able to get the robot to successfully remove and stack the discs. This problem is not seen as viable for this project as it would not require any computer vision to solve as the initial state of the disks is always the same and there is no opponent in this puzzle that can alter the state. TacTix TacTix (Figure D.21) “is a two-player game, where the players take turns removing counters from the board. The goal is to force the other player (the computer) to remove the last counter. On any turn, you may remove counters from either a single row or a single column. The counters must be on adjacent squares (for example, you could not legally remove only two corner counters). You may remove as few as 1 or as many as 4 counters on your turn.” (Math.com, 2007) This could potentially be an interesting problem to solve as it would require a static robot that uses computer vision to analyse the state of game before each of its turns and is then able to grab and remove the objects from the board. 18 Problem Solving with Lego® Mindstorms and Computer Vision Chapter Three Development Methodology and Planning ________________________________________________________ In this chapter the possibly methodologies that could be used for the development of the system are discussed. One appropriate methodology for the project is chosen and justified. This chapter also highlights the planning undertaken before the development of the project. 3.1 Development Methodology The methodologies used within the two most recent past projects (Green, 2007) (Beattie, 2007) that had been explored during the literature review in chapter two were to be analysed before a methodology was outlined. It was thought that methodologies of projects previous to these would have been considered, if not discussed, by these projects. Furthermore it was thought that the older projects would have highlighted outdated methodologies for software development that would no longer be appropriate or applicable. Within software development there is said to be two types of processes; the waterfall process and an iterative process. The waterfall process is the oldest of these processes and is shown in its design. It is a rigid model whereby one section is wholly completed before moving onto the next section. An iterative approach is rather more flexible whereby after initial plans are produced the project goes through several repetitions, or iterations, of design, implementation, testing and evaluation. Beattie’s (2007) rather vague and simplistic methodology utilised the Dynamic Systems Development Model (DSDM) (Stapleton, 1997) for software development. The theory behind this model is that of an iterative approach, this was not discussed in any depth by Beattie although leaving confusion as to how it was actually implemented. Beattie appears to have used this on parts of the solution system, e.g. vision system, were each was designed, built, tested and evaluated before moving onto the next aspect of the system. Key aspects of the methodology have been excluded by Beattie as they are not relevant to this type of project, such as the feasibility and business studies (Stapleton, 1997). These aspects are also not relevant to the project presented here. As a result of this it is considered that the use of this methodology would not be justified as efforts would be wasted completing irrelevant tasks in order to comply with the standard, unless the standard was not complied with fully as in the case of Beattie’s project. However there are better methodologies that are easier to adapt to such as the one used by Green (2007). The methodology that Green (2007) opted for was a partial implementation of the Unified Software Development Process (USDP) (Jacobsen, et al., 2000); this is also based on the iterative approach. 19 Problem Solving with Lego® Mindstorms and Computer Vision USDP therefore follows a very similar approach to the iterative stages of the DSDM model whereby each stage is designed, implemented, tested and evaluated when a decision is made whether to reiterate these stages or move onto the next section of the solution. Green’s rather more complex adaptation of a methodology also utilised the unified modelling language (UML), specifically class diagrams, which aided in describing the solution produced. The USDP methodology is far easier to tailor to a given project or organisation than the DSDM approach as it is seen as more of a framework rather than a method whereby aspects of the framework can be removed, altered or even added to the framework (Jacobsen, et al., 2000). From evaluation of the two solutions provided in previous years it became obvious that an iterative approach to software development was require for a project of this nature as constant alterations, testing and evaluation would be required for each stage of the project in order to develop a successful solution. However the more flexible USDP framework was seen as the favoured of the two methods as aspects with no relevance to the project could be ignored and, if needed, relevant aspects added. Similar to the comments made by Green (2007), the main aim of this project is that of a learning exercise therefore the intention is not to produce a fully developed, bug free product. The emphasis from the project will be on development over widespread testing, in an attempt to create a solution able to give interesting, rather than reliable or wholly accurate, results. Consequently the methodology used for this project would be a version of the USDP framework. This would be similar to that implemented by Green (2007) whereby the initial requirements were to be decided then for each component, or module as referred to by Green, required by the final solution it would be analysed, designed, constructed and tested (ADCT) before being evaluated. The evaluation of the given component would determine whether a further iteration would be required or if the component was deemed fit for purpose, at which point the next component would enter this process. Once each component within the system has been through at least one ADCT iteration, any extended requirement components would be undertaken through the same process. The final system will then be tested and an evaluation of the final system will be carried out (Figure D.22). The way in which the report matches to the methodology used is described in section 1.4. Unlike Green’s approach it is felt for this purpose of this project retrospective UML class diagrams would aid in describing some of the components that have been implemented. These would be fruitless in the design stages, as detailed knowledge of the systems is to be acquired through implementation. Use case diagrams are, like with Green’s (2007) project, deemed unnecessary for this project also as the uses of the robot are relatively simple with no ‘users’. 20 Problem Solving with Lego® Mindstorms and Computer Vision 3.2 Planning The initial project schedule (Appendix B.1) was designed in order to comply with the chosen methodology of the project, dividing the project up into sections. Time was allocated for analytical research tasks, mainly background reading, and also the production of a required deliverable, a midproject report which summarised findings so far. An allotment of time was also given to the completion of the various components of the solution that had been outlined as core elements; hardware, algorithm, software, environment and vision. A section of time was reserved for the possibility of the development and implementation of any of the project extensions highlighted within section 1.2. Testing and evaluation were amalgamated into one section before finally allocating an amount of time for the report write up. After a review of this schedule and initial analysis, several changes were implemented as a result. Therefore a new project schedule was implemented (Appendix B.2). The major changes that were implemented from the initial plan were the order in which components of the system were to be constructed. Initially it was thought that the computer vision aspect of the project should be the last component implemented however after analysis it was deemed that the vision aspect should be constructed before the implementation of any algorithm design or software implementation as these components would heavily rely upon the successfulness of the computer vision element. The time allotted for the write up was also another major change from the initial plan as the time was originally vastly under estimated it was discovered after analysis of previous similar projects in this area. Plans devised for testing various areas are discussed in chapter six. 21 Problem Solving with Lego® Mindstorms and Computer Vision Chapter Four Design ________________________________________________________ This chapter highlights possible design solutions for the final system based on what has been discovered in chapter three. The problem to be undertaken is chosen in this chapter and also certain elements of the final solution are also decided. It was decided that for the advantages discussed in the various sections of chapter two that the development of a solution should be constructed using the LeJOS firmware on the RCX. The LeJOS Java based libraries could then be used to create the user programs that reside on both the RCX and the host computer. As a result of this the most practical software choice for the computer vision element of the project was to implement a system using the LeJOS vision libraries. The advantages of this vision system are discussed in detail in section 2.7.1. 4.1 Chosen Problem The chosen problem was the most common undertaken by previous projects into Lego Mindstorms, that of a robotic footballer. Unlike some past projects the intention of this project was to not limit the project by adhering to the rules or standards of the RoboCup competition instead develop a solution that would see robots compete at a basic form of football. This gave the project more freedom to create a solution that could incorporate advancements not seen in previous projects. The robot should be initially developed as only to complete basic ‘football skills’ such as finding the ball and goal scoring. On accomplishment of these tasks a second robot shall be attempted before advanced tactics or skills. 4.2 Computer Vision As discussed in section 2.6.4 there were a number of possibilities for localisation of the robot. As one of the aims of this project was to incorporate computer vision, it was decided that this would be best incorporated into a system for localisation. Computer vision has been used by only two of the previous projects reviewed, both using a similar ‘mounted camera’ approach (Ashmore, 2006) (Beattie, 2007). The camera acted as the ‘robot’s view’ of the environment allowing the system to make the robot move appropriate to what the camera captured. The image from the camera was split into three vertical regions. If the camera detected the ball in any of the regions the robot would move towards it accordingly; centre region detected moved the robot forward, left region moved the robot left and right region moved the robot right. If 22 Problem Solving with Lego® Mindstorms and Computer Vision the robot could not detect the ball in any regions then it would rotate until it was detected. Beattie’s project did not include any means of localisation while Ashmore’s used the dead reckoning method as Barrett (2004) had done previously. This method was thought to be adequate for a one robot solution however a multi robot solution would require multiple camera feeds which the host computer being used would have struggled to process simultaneously. This solution also limited the success of the robots movement as wireless cameras were unavailable to this project meaning each robot would have to be wired to the host computer. A second computer vision implementation that was decided to be more appropriate for the initial design was to use a similar method to that discussed by Ashmore (2006) and implemented by Russell (2005) that uses a top down view of the environment to track the agents and the ball. The design used by Ashmore and Russell was to highlight two points on the roof of the robot, either via LEDs (Ashmore, 2006) or coloured circles (Russell, 2005), which the system could detect. Once the system had detected the identifiers of the robot it would be relatively easily for an x, y co-ordinate to be determined providing one of the identifiers covered the centre of the robot. The value of the robot would be more difficult to acquire and requires a second identifier at the front of the robot. Once the system has detected both points the angle of the robot can be determined from the angle of point 1 to point 2 (Figure D.23). Ashmore attempted this solution but found large problems with the code that was being used and was unable to rectify the problem. However Russell, likely to have more resources available, was able to create a new vision system based upon the LeJOS libraries and Java. It would have been more than useful if Russell’s code could have been utilised to create a solution for this project however it had been coded in a very specific manner using NetBeans which could not be loaded up on the project host computer. Furthermore in Russell’s report, image processing is talked about to be quite a slow down of the system as the methods used involved complex image processing which meant analysing the whole image several times when attempting to locate the robot. This would have resulted in dramatically reduced performance of the robot, as Russell notes (Russell, 2005). Instead of this approach an original idea was devised whereby the accuracy of the x, y co-ordinates of the robot would be considerably lowered yet would increase performance of the system in comparison to that of Russell’s solution. In place of finding the x, y co-ordinates the environment was to be split up into equal regions (Figure D.24) enabling the system to detect and label an agent or the ball as to be in one of these regions. The  value, the more complex localisation value to find, of the agent is to be determined by placing an isosceles triangle on the roof of the robot. The system 23 Problem Solving with Lego® Mindstorms and Computer Vision will be able to detect the triangle shape and calculate the direction of the agent from the way the triangle is pointing (Figure D.25). 4.3 Environment Design As the intention of the project was to use a top down camera on the whole of the environment it was important for the best results possible that this environment was as ‘clean’ as possible. By this it is meant that no unnecessary noise was present in the background that could affect the performance of the vision element of the solution. To minimise noise in the environment the floor of the pitch was coloured white and also the black walls of the RoboCup Junior pitch were covered with white paper. As a result what the camera saw without any agents or ball in the environment was a virtually completely white image. This meant that the colour of the agents, or rather the piece of coloured card place on top of the agents, and the ball would stand out far easier from the background improving the effectiveness of the solution. 4.3.1 Pitch As a standard RoboCup pitch was available from a previous projects RoboCup project it would have been senseless to create a new pitch for the purpose of this project. It was necessary to create a stand for the camera to be attached to that would give a stable overhead view of the pitch for the image processing to be as accurate as possible. 4.3.2 Camera The camera used was a 1.3 mega pixel USB web camera that could be clipped on to the overhead stand that had been constructed for the purpose of this project. The quality of this camera would be sufficient for the image processing required by the system. 4.3.3 Infra Red Tower The infra red tower which would provide communication between the host computer and the RCX bricks should also be mounted onto the stand to provide the required, by the infra red technology, line of sight wherever the robots are within the environment. However as the stand was forced to be of such a height as to enable the camera to view the whole environment the infra red range should be set to long or high to limit the amount of communications lost between the two locations. 4.4 Robot Design As mentioned in section 4.3.3 the infra red tower was to be mounted above the environment in order to allow infra red signals to be sent across the entirety of the environment. This meant that 24 Problem Solving with Lego® Mindstorms and Computer Vision the robot would needed be designed with this in mind; pointing the infra red port on the RCX upwards as to limit the amount of communication failures. Beattie’s (2006) solution adhered to this design constraint and elements of this design could be exploited. Although Beattie’s solution involved an onboard camera which would not be required by this project hence the design will need to be significantly altered. Lund’s (1999) design was deemed to be an effective solution, although the RCX on this design was laid down rather than pointing upwards as required. Therefore a cross between the two solutions was developed whereby the robot is able to have an upright mounted RCX brick while is sufficiently small enough to be able to successfully navigate within the environment. 4.4.1 Locomotion and Rotation As discussed in section 2.6.2 there were three main types of design choices to consider in regards to locomotion as wheels were seen as the only method of locomotion these choices revolved around the positioning of the wheels. The ‘car’ method discussed was ruled out due to the poor turning circle and the wheelchair method required extra, seemingly unnecessary, wheels. Hence the method that was chosen was that seen in both Beattie’s (2007) and Lund’s (1999) robot design. This involved using only two wheels which allowed a zero turning circle. Although the dual differential drive (DDD) system (section 2.6.3) would provide more accuracy in driving the robot, it was considered that as the localisation system would not be linked to the drive system, unlike previous projects, that the added complexity of the DDD design accompanied with the power issues highlighted in past years, that this would not be the best drive implementation (Ashmore, 2006) (Barrett, 2004) (Beattie, 2007) (Dodds, 2005). Consequently a simpler direct drive design, discussed in section 2.6.3, was to be used. This would involve one motor to one wheel whereby any driving inaccuracies could be resolved by first altering the power of each motor, for example if the robot pulled to the left the motor controlling the left wheel could be assigned more power. Driving inaccuracy could also be altered by the localisation system which could repeatedly tell the robot different instructions if it went off course. For example if the robot veered left when it was meant to be driving in a straight line the localisation system would recognise this and instruct the robot to turn right x degrees to correct this. 4.4.2 Ball Control Similar projects have developed a solution that includes a ‘grabbing’ mechanism whereby motorised arms are used to gain control of the ball (Beattie, 2007). This mechanism however would not be suitable for a game of robotic football where there is more than one robot playing as it would not 25 Problem Solving with Lego® Mindstorms and Computer Vision provide the opportunity for the opponent to intercept the ball without a further complicated design, such as a scoop that would lift the ball from the grasp of the motorised arms. Instead a heavier ball would be used compared to that of the ball in Beattie’s project as to overcome the main issue with a non-motorised solution of the ball bouncing off far too easily. Therefore rather than ‘ball control’ the robots would merely push the ball along by a small bumper, as seen in Lund’s (1999) design (Figure D.17) which would in fact more resemble real world football as player do not ‘grab’ hold of the ball and move with it but kick, or ‘push’, the ball along the field towards the goal. As a result of this design choice there would be no need to implement a complex kicking system as seen in Barrett’s (2004) solution whereby a series of cogs, pulleys and bricks are connected to a motor in order to form a moving barrier which when activated would propel the ball, as if the robot had kicked the ball. 4.4.3 Goal Scoring As the design of the robot was not to include any form of ‘kicking’ action, goal scoring would be achieved be effectively ‘dribbling’ the ball into the opponents net. To do this the vision aspect of the solution system would be able to identify which regions the ball and robot are located. The host computer would then be able to identify the ideal path for the robot to take in order to reach the ball and then tell the robot what moves to perform in order to push the ball towards the goal (Figure D.26). 4.4.4 Collision Detection As to prevent for the robot from becoming trapped against any part of the environment or another agent, a form of collision detection needs to be implemented. Past projects have used the touch sensor in corporation with a ‘bumper’ style design, to identify when the robot has made contact with another element within the environment (Barrett, 2004). When a collision was detected the robot was told to cease what it was currently doing, reverse for a short period then resume what it was originally doing. For this project it would be more practical to use the computer vision system to detect when the robot has not moved from its current ‘region’, see section 4.2. Based on its current location and orientation an intelligent move could then be made that will move the robot away from the obstruction. The system will be able to make a decision as to what is obstructing the robot has it will have knowledge of where all agents are within the environment and the environment boundaries. If either is close to the robot it would be safe for the system to assume this is what has 26 Problem Solving with Lego® Mindstorms and Computer Vision caused the robot to become ‘trapped’ and send a set of commands to the robot that would ‘free’ the robot from the obstacle. 4.5 Lego Mindstorms Architecture In Barrett’s (2004) report a modelling language was devised which highlighted the design of the solution robot for that project. This section was thought of as a useful way to present the detail of how the robot will be connected together with the Lego Mindstorms intelligent parts and has therefore been used to demonstrate the intended design for the robot to be employed here. Figure 4.1 shows how the modelling language introduced by Barrett is applied to the design introduced in this chapter. The legend for this modelling language is included in the appendix (Figure D.27). Figure 4.1 Figure 4.5.1 shows the simplicity of the design on the Lego Mindstorms side of the initial design ideas. It was intended that the computer vision aspect of the solution would be able to achieve the results without the Lego Mindstorms sensors that previous projects have required. By using this approach it is hoped that the accuracy and reliability of the solution would be superior to that of a solution that relies upon these sensors in anyway. 4.6 Communication As described in section 2.5 the infra red communication is the only method of communication between the RCX and the host computer with the version of Lego Mindstorms being used for this project which has the potential to be one of the biggest limitations. As mention previously in section 4.2 the environment has been designed to limit the failures of this communication protocol. However further measures can be taken to increase the reliability of the communications such as time delays which ensures that the sender of the original message is ready to receive a reply from the recipient. A time delay of 50ms between sending messages will prevent the IR port from reading a reflection of the first message and a time delay of 200ms before the recipient sends a response will ensure the sender is ready to receive (Barrett, 2004). As it the intention of the project to implement a multi RCX solution it will be necessary to use port address, see section 2.5, whereby each RCX is given an address and each message sent from the host computer contains one of these addresses. Each message is then only read by the RCX the message is intended for which results in the host computer being able to control multiple RCX bricks. 27 Problem Solving with Lego® Mindstorms and Computer Vision Chapter Five Implementation ________________________________________________________ This chapter describes the details of how the final system was implemented including various code snippets and diagrams where necessary to help explain various aspect of the solution. Within this chapter elements of the LeJOS libraries, particularly the vision libraries (Griffiths, 2007), are frequently mentioned; all of which are reference to the LeJOS API (Solorzano, et al., 2006) as such each citation will not be noted. 5.1 Computer Vision The initial design of the computer vision aspect, as discussed in section 4.2, was to exploit the LeJOS vision libraries, josx.vision package, in order to create a full localisation system. However the implementation of this designed proved to be more cumbersome than first thought. The limitations of the LeJOS vision libraries proved it impossible to create a system resembling the one described in the initial design. The problem that was encountered in trying to implement the original design was that the vision libraries offered no means of detecting shapes. This meant that either the design of the computer vision solution would have to change or the vision software being used would have to be changed. Investigations into using different vision software (section 2.7) proved to be unsuccessful as time constrictions into these investigations could not allow for the developer to acquire new skills required to be able to create a successful solution in the alternate software. Therefore it was the design would have to be changed in order to create a successful localisation system. The idea of using a grid of regions over the environment (Figure D.24) to determine an approximate two dimensional co-ordinate position of the agent was kept however the orientation of the robot would no longer be determined by the vision system but by sensors as seen in previous projects reviewed (Barrett, 2004) (Ashmore, 2006). The orientation aspect of the localisation system is discussed in section 5.3.1 as this is no longer covered by the computer vision aspect of the project. As mentioned in section 4.2, the ‘grid’ concept was to be kept in the solution as this was still regarded as the best solution. The grid was implemented by utilising the Region and Vision classes within the josx.vision LeJOS package. A new instance of the Vision class is created which loads elements from the Java Media Framework (JMF) needed to create a frame whereby the image from the selected source. In the case of this project it is the USB web camera, which is displayed at the given resolution. The details of the display such as the resolution, or size, of the image and the image 28 Problem Solving with Lego® Mindstorms and Computer Vision source are specified in a ‘video.properties’ file which is loaded by the JMF to create the live image within the frame. The addRectRegion method from the Vision package is the called inside a for-loop which creates instances of the Region class (Snippet 5.1). These regions are created with dimensions of 40 x 60 as to fill the image with equal regions of 4 rows of 8 regions. If the number of regions were any smaller the accuracy of the localisation would have suffered dramatically. Whereas increasing the number of regions would have not drastically improved the success of the agents, as found by Beattie (2007). Furthermore the higher numbers of regions that are created the higher the demands are on the host computer and may result in a slow down of processing the live image feed and subsequently the reactions of the agents. // Vision.addRectRegion(Region Number, x Position, y Position, height, width) int reg = 1; for (int row=1; row 500ms) //wait 500ms from last detection if (robot colour detected) if (detected region = last known position of robot) sinceMove++ else sinceMove = 0 if (sinceMove < 10) makeMove() else //robot has not moved for 5 seconds and deemed trapped if (robot current row == 1) move robot backwards move robot right 45 else if (robot current row == 2 or 3) move robot backwards else if (robot current row == 4) move robot backwards move robot left 45 Snippet 5.4 5.4 Lego Mindstorms Architecture As mentioned in section 4.2 the design of the robot was altered significantly due to the limitations of the chosen vision solution software. No longer could the vision system be solely relied upon to provide a comprehensive localisation system but now hardware sensors must be used, as discussed in section 5.3.1. The new design has been drawn out (Figure 5.2) in the modelling language devised by Barrett (2004) as the original designs were in section 4.5. Figure 5.2 36 Problem Solving with Lego® Mindstorms and Computer Vision 5.5 Communication For successful communication between the host computer and each RCX implemented in the final solution, as mentioned in section 4.6, addressing will be required. Addressing communications add bytes to a packet relating to the source and destination addresses. Before the packet can be sent a communication line needs to be open between the host and the destination RCX. To successfully achieve this, to eliminate the possibly of the message arriving at the wrong RCX, infra red communications are first ceased. A new communication line is then initiated from the host computer; the RCX has a constant for loop which listens for new communications (Snippet 5). //Open the port for remote commands - RCXLNPAddressingPort(source, destination); RCXLNPAddressingPort port = new RCXLNPAddressingPort((byte) 0x10, (byte) 0x20); InputStream is = port.getInputStream(); OutputStream os = port.getOutputStream(); final DataInputStream in = new DataInputStream(is); final DataOutputStream out = new DataOutputStream(os); for(;;) { //Constantly look for incoming byte int op = in.readByte();//read the byte if (op == METHOD_JOSX_VISION_RCX_TURN_RIGHT_I) { //if incoming byte matches rn.rotate(0 - in.readFloat()); }//perform actions } Snippet 5 As this loop is required wherever communications are to be received the port needs to remain open as to be able to receiver the communications whenever they are being sent. As a result of this it was not feasible to have two way communications between the host computer and the RCX, due to the fact the host computer could not be dedicated to one sender. It was also found that even when the host computer was dedicated to one sender, outgoing communications errors would occur far more frequently. As a result, mentioned previously, communications were restricted to one way communications from the host computer to either RCX bricks. The following class diagram illustrates (Figure 5.3, Legend - Figure D.32) how communication lines were first set up and then how the message was passed to the RCX brick. The LNPAddressingHandler, LNPIntegrityHandler and LNPHandler class stack is where the packet is created which is sent via infra red. LNPAddressingHandler adds source and destination bytes to the packet to enable the packet to reach the correct destination; LNPIntegrityHandler adds a simple checksum to the packet in order to maintain the integrity of the packet to limit the possibility of corrupt packets effecting the performance of the system; LNPHandler is the class upon which bundles the whole packet together into the correct Lego Network Protocol (LNP) standard to be sent via the infra red USB communication tower. Included within the LeJOS firmware written to the RCX, see section 2.4.1, are 37 Problem Solving with Lego® Mindstorms and Computer Vision the same classes which can also receive and read packets of data sent in the LNP standard (Solorzano, et al., 2006). Host Computer josx.vision FindRobot.Java Commands: RCX.turnRight(Angle : int, Robot : byte) RCX.Java Commands: RCXRemote.start(Robot : byte) RCXRemote.out.writeByte(Angle : int) josx.rcxcomm RCXRemote.Java public static variables: out: DataOutputStream Methods: start(Robot : byte) josx.rcxcomm RCXOutputStream.Java Commands: write(Angle : int) josx.rcxcomm RCXLNPAddressingPort.Java private variables: rcxout : RCXOutputStream Commands: RCXLNPAddressingPort(Sourc e : byte, Destination : byte) getOutputStream() josx.rcxcomm LNPAddressingHandler.Java LNPIntegrityHandler.Java LNPHandler.Java josx.rcxcomm Tower.Java Commands: write(SendPacket : byte, Length : byte) Java.io DataOutputStream.Java Commands: writeByte(Angle : int) RCX Brick sends Infra Red Link sends Figure 5.3 38 Problem Solving with Lego® Mindstorms and Computer Vision Chapter Six Testing ________________________________________________________ In this chapter the tests carried out from previous projects are discussed along with details of the tests to be carried out by this project. These tests results, listed in appendix C, will be used as the main component for evaluation. 6.1 Test Plan From the previous projects that have been analysed in chapter two the most relevant with regards to the testing stage are projects that have attempted the same, or very similar, robotic footballer problem (Barrett, 2004) (Ashmore, 2006) (Beattie, 2007). However none of these previous projects had been able to implement various things achieved by this project such as the implementation of a second robot or the use of computer vision for localisation via an overhead camera. Ashmore’s project failed to produce any results which were directly comparable to the objectives of this project. These results focused on the accuracy of the turning circle and not completing football skills. Results gained from Beattie’s experiment were all of qualitative; meaning comparison of the result achieved in this project to Beattie’s would add little value to the evaluation. The remaining project (Barrett, 2004) produced quantitative, comparable, results although these had more focus on the dead reckoning methods used for localisation. It was also deemed that undertaking these tests and comparing results with those acquired by Barrett’s project would also add little value. As a result of the findings above a separate test plan was devised specific to this project consisting of both qualitative and quantitative result yielding tests. For each test a small program was run which would send the command(s) to the robot in order to complete the test. For example, “Can each robot run in a straight line” a small program was written which sent a command to the robot to rotate both motors forwards for five seconds. The results of these tests are included in appendix C, the list of tests carried out and to which component this test relates to are given below (Table 6.1), details of these tests are discussed in the evaluation chapter, seven. 39 Problem Solving with Lego® Mindstorms and Computer Vision Component Communication Locomotion Rotation Vision Tests Can the host computer successfully communicate with each robot when each robot is in a variety of positions within the environment' Can each robot run in a straight line' Can each robot turn 45 accurately' Can each robot turn 90 accurately' Can each robot turn 180 accurately' Can each robot turn 360 accurately' Can the ball be detected consistently at various points throughout the environment in different lighting conditions' Can each robot be detected consistently at various points throughout the environment in different lighting conditions' Can each robot navigate to the ball when the ball is in a variety of positions' Can each robot score a goal' Can each robot be freed should it become trapped against the walls' Which robot is the first to find the ball when pitted against each other' Which robot is the first to score when pitted against each other' Table 6.1 Ball finding/control Goal Scoring Collision Detection Final System 40 Problem Solving with Lego® Mindstorms and Computer Vision Chapter Seven Evaluation ________________________________________________________ In this chapter a comprehensive review of each iteration of analysis, design, construction and testing on each component and the final solution were subjected to evaluation. The final solution is also related back to the minimum and advanced requirements as highlighted in chapter one, discussing how each requirement has been addressed. 7.1 System Components In this section of the report the details and evaluation of each iteration of ADCT undertaken for each component of the system are discussed. 7.1.1 Communication Iteration One Although not documented previously this first iteration of the communication component was developed to merely work to the minimum requirements. This was therefore based on a solution that only allowed communication between the host computer and one RCX. Addressing communication as described throughout this project was not used, merely the primitive form whereby the message sender sends to any listening connection. This implementation was acceptable for the minimum requirements however when it became obvious the implementation of a second robot was possible the second iteration was developed. Iteration Two The second implementation adopted the LeJOS communication addressing package and allowed communication to a specific RCX brick. Originally the addressing communication was set up with all three nodes involved, host computer and both RCX bricks, to be constantly listening for communications as to allow messages to be sent two ways on each node. This proved to cause terminal errors which lead to the RCX brick needing to be reset. This was by no means an ideal resolution to this problem. The problem lied with the host computer clogging up the communication lines by needing to keep open the infra red tower in order to listen for message being sent from the RCX bricks. As mentioned previously this was therefore dropped and local variables were used rather than polling the values from the robots. Iteration Three 41 Problem Solving with Lego® Mindstorms and Computer Vision Within iteration three the addressing communication design was altered as to not to allow two way communications, merely one. One way messaging between host computer and RCX worked extremely well, no instructions were sent to the wrong RCX and the positioning of the infra red tower and the infra red port on the RCX ensured a high communications success rate. The high success rate is shown in the results of the testing for this component where 10 test packets successfully reached the correct RCX when each was placed in various locations on the pitch. 7.1.2 Locomotion The locomotion of the robot was crucial as the accuracy of an agent’s drive abilities would have a direct relation to the success of the final system; if an agent cannot move in a straight line then the current orientation value held by the system will be inaccurate. The system value for the orientation of the robot will be, for example, 0 when in fact because the robot has veered off, its actual orientation may be 10. These problems were more prevalent with the robot using the rotation sensors for reasons stated in section 7.1.4. Iteration One Initial designs used a direct drive, one motor drives one wheel, implementation with each motor being supplied with the same power. These motor were positioned at the back of the robot underneath the RCX brick. As a result of this, the weight distribution on the robot lead to unsteady movement because of the two wheel implementation, discussed in 5.3.2. The robot also veered severely, over 45, which was unacceptable. Iteration Two The motors were moved to the front of the robot to give a more even weight distribution which aided the problem of unsteady movement. Smooth plates were also added to the underside of the robot in central locations at the front and back which enabled the robot to run over the ground with rather more ease than an entirely Lego brick underneath. After the alterations of the second iteration, the robot was still somewhat unsteady and veered to the left slightly less, around 25, which was still inadequate. Iteration Three As it was felt the hardware design had been altered to its optimal design, the software side was altered. The specific alterations were to adjust the power levels the motors were set to. It was established lowering the power levels from 6 to 3 improved the stability of the robot and the movements were not as erratic. The motor power for each wheel on each robot were then tweaked and constantly reviewed within ±0.5 of 3 to improve the accuracy of the drive. After several ‘trial 42 Problem Solving with Lego® Mindstorms and Computer Vision and error’ iterations of this process, adjusting the values for each motor slightly then testing, a combination was eventually devised which would allow the robot to move in a straight line with a minimal degree of inaccuracy, as results C.2 show; 5 at worst. Although not perfect this was thought to be a satisfactory solution for this system. These inaccuracies were deemed unavoidable as it was down to flaws with the Lego Mindstorms toolkit. These may have occurred due to the ‘wear and tear’ of the kits over the numerous years they have been used or simply fundamental limitations of the kit. An example of a flaw highlighted by this problem is that different motors spun at different speeds which resulted in the robot veering from a straight line. 7.1.3 Rotation Iteration One As a result of the wheel positioning, each robot had a 0 turning circle which worked extremely well. This solution allowed the robot to be easily redirected and ensured the speed of the final solution was not compromised. The robot was able to spin 360 in approximately 1 second. Further iterations of this component were not required. 7.1.4 Localisation The localisation of the robot is arguably the key component of this system as the success of any advanced tactics to be implemented, such as goal scoring, would depend upon the reliability of this component. The localisation component is considered to include three sub-components which are evaluated individually. Vision Software Iteration One As mentioned in the implementation, the original iteration, utilising shape detection to detect orientation, was not feasible as the LeJOS vision libraries were not powerful enough for the kind of image processing required without additional Java libraries. This was therefore not undertaken, due to time limitations on the project. Iteration Two The second iteration excluded any means of calculating the orientation of the agents, focusing on determining a relative x, y position. The way in which this was done is discussed in the implementation (Section 5.1). Coloured card was placed onto of the agents, purple for robot one and red for robot two, and a green ball was used. In the first iteration of design one sample of the colours of these elements were taken, again detail discussed in section 5.1. Using only one sample 43 Problem Solving with Lego® Mindstorms and Computer Vision meant the system was somewhat unreliable in detecting the colours, even when the difference threshold was set at a high value (7). This was as a result of the light variations at the different areas of the pitch drastically affecting the colours of the elements. Typically the system would only be able to detect the robot at certain areas of the pitch and not others, this was obviously not desired. Iteration Three The third iteration developed the design to use five colours for each element, agents or ball, from samples taken at different areas of the pitch. This drastically improved the reliability of the vision system in detecting the elements across the environment; shown in the test result where the environment was brightly lit. The darker environment did not favour the system as the reliability dropped dramatically, even after recalibration of the colours with the system in the darker conditions. This was likely to be due to the fact that in darker conditions the quality of the images the camera captures is significantly less than in well lit conditions, as with any other digital camera. The effect of shadows would have also been a factor in the unreliability especially in dim lighting conditions as the light source may only be coming from one angle onto the environment. In brightly lit conditions light was coming from a variety of angles, including directly above, which reduced the amount of shadow. Rotation Sensor Iteration One The rotation sensor was utilised for determining the robots orientation through the use of the RotationNavigator class as discussed in section 5.3.1. This solution did not require more than one ‘full’ iteration as the class used was comparatively comprehensive and worked well from the offset. Initial set up required some elements of ‘trail and error’ iterations to determine a constructor required value known as ratio. This value correlates to the ratio of sensor rotations to wheel rotations which has a direct affect on the accuracy of the orientation value. Therefore a series of iterations were undertaken to decipher the most accurate value to be used. As the result of the tests show (Results C.3), this method of localising a robot was not as successful as the second method introduced into this project. This could have been down to several reasons, the inaccuracies of the rotation sensor which have been highlighted many times in many previous projects is presumably a major reason. Another key factor could have been the decision to go ahead with the direct drive rather than switching to the dual differential drive (section 5.3.2) that the RotationNavigator class is designed for. 44 Problem Solving with Lego® Mindstorms and Computer Vision Compass Senor Iteration One The compass sensor implementation, discussed in section 5.3.1, relied upon the robot rotating until the sensor gave the required value. The first implementation of this was designed as to only make the robot stop when the sensor value was exactly that of the required angle. This would generally work 1 in 5 times. On failures for the sensor to detect the single value the robot would continuously rotate. This was a limitation of the sensor; if the sensor worked perfectly the robot would stop every time. Possibly because of the speed the robot was rotating this was not the case. Iteration Two As the first iteration proved to be somewhat troublesome the redesign of this was to look for a set of values around the original value rather than just one value. This meant that the sensor would be more likely to detect a ‘stopping’ value, a value upon which would make the robot cease rotating. This value was set to 3 either side of the original value to give 7 stopping values, meaning the sensor would be 6 times more likely to detect the value than in the first iteration. As a result of this the robot would then stop 4 in 5 times, a significant improvement which was deemed acceptable with the error being put down to the limitations of the sensor. A further issue discovered with this implementation is that it would take the robot approximately 100ms to react to the fact that the sensor reading is equal to that of a stopping value. This meant that the robot was over rotating slightly every time. To limit this, before the set of stopping values was determined, 5 was subtracted from the original value as to allow for stopping time. This implementation of orientation localisation was far the more effective out of the two methods which ultimately led to the success of robot two over robot one. The reason for this is believed to have been the consistency of the compass sensor against the inaccuracies of the rotation sensor. Limitations of the Lego toolkit causing slippage of the rotation sensor plus the slight inaccuracies caused by the inability to drive in a straight line ultimately lead to the relative failure of the rotation sensor compared with the compass sensor. Whereas the compass sensor relied on none of these things in order to function. The compass sensor was completely separate from the wheels and once collaborated enabled the robot to accurately return to any angle. This meant any errors from the robot not being able to drive in a straight line were irrelevant as it could always be set back to its original orientation, 0. 7.1.5 Ball Finding Iteration One The success of the algorithm used for ball finding, as mentioned previously, heavily depended upon the accuracy of the localisation of the agents. Hence the algorithm appeared to work better on robot 45 Problem Solving with Lego® Mindstorms and Computer Vision two than robot one, as the results show (Results C.5). The algorithm was kept simple; a more complex algorithm could have resulted in further inaccuracies as the localisation was not 100% reliable. The agent would first align itself on the same region row as the ball and then move towards the ball, as described in section 5.3.4. This simple algorithm worked well for the purpose of this project however a more advanced algorithm could be introduced in future projects. For example, the algorithm could be extended as to be aware of the position of the second agent and make moves based on not only the location of the ball but also the second agent. Defensive tactics could then be implemented, for example if the ball is not in the agents half of the pitch and is close to the second agent, within one region in any direction, the robot should move back to defend the goal. Similarly advanced attacking algorithms could be implemented such as knowing if the second agent has turned away from the ball giving the agent the opportunity to steal the ball and potentially score a goal. A further iteration of the design of this algorithm were not undertaken due to time constraints, however if it was to be implemented some of the advanced tactics mentioned above would have been incorporated. 7.1.6 Goal Scoring Iteration One The goal scoring algorithm was limited due to the fact that the robot had been implemented without any means of direct ball control or ball kicking, therefore was only able to push the ball towards the goal. The robot would push the ball up the pitch towards the opposition goal. This had limited success within this project as seen in the result (Results C.6) which was drastically reduced when both robot were both attempting to score a goal (Results C.8). The problem with the algorithm implemented was that the robot would not take into account any obstacles in between itself and the goal, such as the second robot. Subsequently when the second robot was in the direct path to goal the ball would be pushed against the second robot and bounce off away from goal. As mentioned in section 7.1.5 the addition of advanced tactics would have aided the success of the algorithm. For example if the second robot was an obstacle on the path to goal the robot could flick the ball to the side of the obstacle, chase it and push it into the goal. The inability of either robot to be able to frequently score goals when pitted against each other was one of the most disappointing aspects of the final solution. 46 Problem Solving with Lego® Mindstorms and Computer Vision 7.1.7 Collision Detection Iteration One The collision detection implemented was like no other collision detection previously implemented as it relied solely upon the vision component. This worked relatively effectively, as shown by the results acquired (Results C.7) whereby 80% of all collisions, either into a wall or into the second agent, were dealt with by sending commands to the robots, see section 5.3.5 for details of this. The other 20% could have possibly been successfully handled if the touch sensors had been utilised as well as the vision system. The touch sensors could have been used on top of the design presented in this project so if a touch sensor is pressed x amount of times and the robot is not moving from the same region, cease any instructions presently trying to be carried out by the robot and make the necessary moves to free the robot from the collision. 7.2 Final System Overall the system worked well, the computer vision was able to detect the robots location and make a decision where to move based on this and the position of the ball. The project has also advanced on work done in the previous years projects reviewed through the inclusion of a second robot; hence the final system is seen as a success. The project could yet be improved by many of the factors discussed above on a component by component basis. As this method of computer vision to localise the robotic footballer has not been achieved before, this is clearly the component that could be improved the most. As mentioned in section 7.1.4, the original design (section 4.2) could be implemented which would have aided the accuracy of the final system. Simpler improvements to the vision component could have also been made such as evaluating the success of the system with a varying number of regions or pixel difference threshold, refer to section 5.1, if more time have been available. 7.3 Minimum Requirements Define a suitable objective or task for the robot to complete which incorporates basics of robotics and elements of computer vision. The task of a robotic footballer was decided early on after initial investigation and research into a variety of potential problems. This task allowed elements of robotics through the use of the Lego Mindstorms kit and computer vision to be implemented within the solution developed for the problem. Deciding the problem after initial investigation allowed a more educated choice on the task to be undertaken which assisted in the success of the project. 47 Problem Solving with Lego® Mindstorms and Computer Vision Construct a robot which is able to complete the defined task. The robot must also be able to overcome a computer vision problem utilising video input. Two robots were constructed from two Lego Mindstorms toolkits, one by the University and one provided by myself. Each robot was localised using part hardware, part computer vision solution. The system was able to locate the ball and move the robot towards the ball in the direction of the goal area thus achieving the aim of being able to play a version of robotic football. Create an algorithm which enables the robot to complete its task in an efficient and effective way overcoming any limitations of the robot design wherever possible. An algorithm was created which enabled the robot to move towards the ball as quickly and as efficiently as possible with a minimum amount of turns to reduce the number of inaccuracies that occurred. Limitations of the robots were attempted to be overcome by constantly re-evaluating the position of the robot and sending new instructions should the robot not have moved into the expected ‘region’. Furthermore the limitations of the communications protocol was attempted to be overcome by keeping local values rather than constant polling of orientation from the robot which would have clogged-up communication time resulting in more communication failures. Design and implement effective software enabling the robot to manipulate its environment in order to complete the defined task. The software was created as such so the robot could react to the ball or itself moving position from the original positions were the original route to ball was calculated. The implementation has been done as such so that it would be quite easy to implement tactics also based on the position of the opponent; time restrictions prevented this from being implemented within this project. Design a way to evaluate the success of the robot and also to include evaluation of the robot in different environments, such as differently lit environments as this can seriously affect many computer vision problems, in order to investigate the robustness of the robot and its algorithms. A comprehensive test plan was created whereby all major elements of each of the robots created were scrutinised and also pitted against each other. As the environment for this project was static the only variant possible would be the suggested one from the requirement therefore tests were carried out in different lighting conditions. 7.4 Advanced Requirements Build a second robot as to give the initial robot direct competition in solving the problem. A second robot was implemented with a different mechanism of acquiring the orientation localisation value of the robot’s current position which allowed the two to be compared through 48 Problem Solving with Lego® Mindstorms and Computer Vision various tests and also directly evaluated against each other by playing a game of robot football whereby the winner would be the first robot to successfully score a goal. Build a second robot to act as a “team mate” to the initial robot helping it complete the problem. This was not implemented; however the second robot could have been altered to perform another role rather than opponent such as goalkeeper, whereby the robot’s purpose would not be to score a goal but to defend the goal. Similarly the robot could have simply been program to pass the ball to the other robot rather than trying to score a goal. Research possible ways in which the robot can complete the task more efficiently or successfully. The initial design idea of using triangular shapes and computer vision to track all aspects of localisation, position and orientation, is thought to have been a solution that would have worked more efficiently reducing the number of errors occurring when the robots rotate. This is because the limitations of the sensors would have been completely irrelevant if the vision side of the system was able to track the robot and would have been far easier to correct the robot if it had veered off course. Furthermore it is believed that this approach could have been made more accurate if a larger number of ‘regions’ had been used within the computer vision component, however in this project hardware limitation limited this. 7.5 Project Schedule Evaluation The initial project schedule was unrealistic and was not aligned to the goals of the project. Consequently shortly after the completion of the comprehensive background research this was altered quite significantly. The second project schedule was far more successful and by following this it enabled the project to complete its main aims. This was aided by an unforeseen limitation placed upon the project whereby it could only be enhanced upon at weekends. At first this was seen as a drastic limitation which could have put the project in doubt. Somewhat contrary to this limitation actually aided the project as these days were dedicated to the project with little distractions. It kept the project on schedule as if a component solution had not been devised by Sunday afternoon a workable alternative was found. This is highlighted by the changes implemented to the original design of the vision system. Furthermore as mentioned in the planning chapter, altering the order in which the components were developed was believed to have improved the final solution. 49 Problem Solving with Lego® Mindstorms and Computer Vision Bibliography ________________________________________________________ Ashmore, D. (2006). Creating a Robotic Footballer. Leeds: School of Computing, Leeds University. Barrett, A. (2004). Lego Mindstorms Robotic Football. Leeds: School of Computing, University of Leeds. Baum, D., Gasperi, M., Hempel, R., & Villa, L. (2000). Extreme MINDSTORMS : an advanced guide to LEGO MINDSTORMS. Apress. Beattie, C. (2007). Mindstorms RoboCup Player. Leeds: School of Computing, Leeds University. cut-the-knot.org. (2007). Tower of Hanoi. Retrieved 12 7, 2007, from cut-the-knot: http://www.cutthe-knot.org/recurrence/hanoi.shtml Dodds, C. (2005). Sensory Aided Lego Mindstorms Robotics. Leeds: School of Computing, Leeds University. Ferrari, G., Gombos, A., Hilmer, S., Stuber, J., Porter, M., Waldinger, J., et al. (2002a). Programming Lego Mindstorms with Java. Syngress. Ferrari, G., Ferrari, M., & Hempel, R. (2002b). Building Robot with Lego Mindstorms. Syngress. Forsyth, D. a. (2002). Computer Vision: A Modern Approach. New Jersey: Prentice Hall. Green, R. (2007). Building static robots to solve manipulative puzzles. Leeds: School of Computing, University of Leeds. Griffiths, L. (2007). LeJos Vision System. Retrieved 12 7, 2007, from http://homepage.ntlworld.com/lawrie.griffiths/vision.html Intel. (2008). Open Source Computer Vision Library. Retrieved April 14, 2008, from intel: http://www.intel.com/technology/computing/opencv/index.htm Jacobsen, I., Booch, G., & Rumbaugh, J. (2000). The Unified Software Development Process. Addison Wesley. Jones, J., Seiger, B., & Flynn, A. (1998). Mobile Robots. A K peters. Kevan, P. (2003). A Lego Mindstorms Maze Solving Robot. Leeds: School of Computing, University of Leeds. Lego.com. (2007). Lego Timeline. Retrieved 12 03, 2007, from Lego Official Website: http://www.lego.com/eng/info/default.asp'page=timeline Lund, H., & Nielsen, J. (1999). Building Instructions for the LEGO® Soccer Player. Retrieved April 7, 2008, from http://www.mip.sdu.dk/~hhl/RoboCupJr/Build/ 50 Problem Solving with Lego® Mindstorms and Computer Vision Math.com. (2007). Tac Tix. Retrieved 12 7, 2007, from Math.com: http://www.math.com/students/puzzles/TacTix/TacTix.html mindsensors.com. (2006, 06 04). Compass Sensor for RCX. Retrieved 03 31, 2008, from mindsensors.com: http://mindsensors.com/index.php'module=pagemaster&PAGE_user_op=view_page&PAGE_id=51 rescuesystem.org. (2007). Retrieved 12 7, 2007, from RoboCup-Rescue: http://www.rescuesystem.org/robocuprescue/ RoboRealm.com. (2007). RoboRealm. Retrieved 12 7, 2007, from http://www.roborealm.com/ Russell, M. (2005). Soccer-Playing Robot. Make: Technology on your time , 06: Robots . Schreiner, A.-T. (2000). Infra red. Retrieved April 3, 2008, from http://www.vorlesungen.uniosnabrueck.de/informatik/robot00/doc/lego/infra red.pdf Solorzano, J., Bagnall, B., Stuber, J., & Andrews, P. (2006). LeJOS RCX. Retrieved April 2, 2008, from LeJOS: http://lejos.sourceforge.net/p_technologies/rcx/lejos.php Stapleton, J. (1997). DSDM: Dynamic Systems Development Method. Addison-Wesley. Technic, L. (2007). Lego Technic. Retrieved 12 03, 2007, from Lego Official Website: http://technic.lego.com/en-us/default.aspx Truffelli, G. (2006). Brick's Music Studio. Retrieved April 3, 2008, from Guy's LEGO® page: http://www.aga.it/~guy/lego/bms.html 51 Problem Solving with Lego® Mindstorms and Computer Vision Appendix A – Personal Reflections ________________________________________________________ A.1 Project Successes The project has a number of success of which I am particularly proud of. The use of LeJOS was critical in most of these successes as it allowed powerful control over the RCX with relatively simple implementation. Examples of this include the vision system, which was able to detect each element, the robots and the ball, successfully almost 90% of the time when the colours were correctly collaborated in a well lit environment. Further to this the communications between host and agents was impressive being virtually flawless as in tests and many test ‘matches’ the communication component did not let the system down. It would have been nice though to have been able to successfully implement two way communications. The part of the project that stands out as the main achievement was the use of two robots which has not been accomplished by any previous projects undertaken the problem of robotic footballers. As a result of this it meant for the first time in one project a game of robotic soccer could be played, having the two robots battle it out. It was most rewarding when a test game resulted in one robot actually scoring a goal. A.2 Project Failures The inability to implement the original vision system was a disappointment. This system could have drastically increased the successfulness of the project in terms of goal scoring. If this system could have been accomplished early enough more time may have been available to introduce the advanced tactics mentioned in the evaluation. Another aspect stemming from the previous point from which was disappointing was the unsuccessfulness of the rotation sensor and the direct drive solution that was used instead of the full vision localisation system. If this was to be done again it would have been implemented with a dual differential drive system in an attempt to improve inaccuracies. A.3 Lego Mindstorms Project Advice For students undertaking a project that uses the Lego Mindstorms toolkit the advice I would give would be to investigate the limitations of the kit before undertaking any problems. I attempted to overcome some of the limitations highlighted by projects done in this area previous to mine by introducing computer vision based localisation. Further limitations not yet discovered by any previous project may hamper a perfect design solution so be prepared to change design plans. I would also recommend not committing to one problem at an early stage in the project. It is best to 52 Problem Solving with Lego® Mindstorms and Computer Vision acquire the background knowledge first, such as; what is the kit capable of, what has been done previously (especially look at the book by Ferrari (2002b) who has innovative project ideas) and also consider original ways to take each project idea forward. Furthermore do not overlook the physical demands of a Lego Mindstorms project, as was found with this project whereby the environment could not be set up in my rented accommodation in Leeds due to the size. A.4 General Undergraduate Project Advice As a result of the project environment being too large for my house in Leeds I was forced to work on the project at weekends back at my parents’ home. This forced me to dedicate at least two days to the project each week which significantly helped in meeting deadlines and sticking to the project schedule. As generic advice I would recommend allocating a certain amount of time each week for purely project purposes and stick to this. Keeping the initial minimum requirements of the project realistic is also a huge aid as it enables these to be accomplished and advanced to be worked upon which are generally more interesting and see more rewarding results. Such as in this project the addition of a second robot was far more rewarding than tweaking the accuracy rate of the initial robot to meet bespoke minimum requirements. Finally, when coming to the end of the project and doing the arduous task of writing the report I strongly recommend complete isolation with no internet connection. 53 Problem Solving with Lego® Mindstorms and Computer Vision Appendix B – Project Schedule ________________________________________________________ B.1 Initial project schedule B.2 Reviewed project schedule 54 Problem Solving with Lego® Mindstorms and Computer Vision Appendix C – Results ________________________________________________________ Listed here are the results of the tests undertaken split up by component. Robot one relates to the robot with rotation sensors and robot two relates to the compass sensor implementation. C.1 Communication Can the host computer successfully communicate with each robot when each robot is in a variety of positions within the environment' Robot Robot One Robot Two Success Rate 5/5 5/5 C.2 Locomotion Can each robot run in a straight line' Robot Robot One Robot Two Inaccuracy () 4 5 C.3 Rotation Can each robot turn x accurately' Robot Angle () Inaccuracy () Angle () Inaccuracy () Angle () Inaccuracy () Angle () Inaccuracy () Robot One Robot Two 45 3 90 4 180 5 360 5 45 1 90 2 180 2 360 2 C.4 Vision Can the ball and robots be detected consistently at various points throughout the environment in different lighting conditions' Item Robot One Robot Two Ball Lighting Dark Dark Dark Success Rate 3/5 2/5 1/5 Lighting Dim Dim Dim Success Rate 4/5 3/5 2/5 Lighting Bright Bright Bright Success Rate 5/5 5/5 4/5 55 Problem Solving with Lego® Mindstorms and Computer Vision C.5 Ball Finding/Control Can each robot navigate to the ball when the ball is in a variety of positions' Robot Robot One Robot Two Success Rate 3/5 4/5 C.6 Goal Scoring Can each robot score a goal' Robot Robot One Robot Two Success Rate 2/5 3/5 C.7 Collision Detection Can each robot be freed should it become stuck against the walls' Robot Robot One Robot Two Success Rate 4/5 4/5 C.8 Final System Which robot is the first to find the ball when pitted against each other' Robot Robot One Robot Two Success Rate 1/5 4/5 Which robot is the first to score when pitted against each other' Robot Robot One Robot Two Success Rate 0/5 1/5 56 Problem Solving with Lego® Mindstorms and Computer Vision Appendix D - Figures ________________________________________________________ D.1 Standard Lego Brick (http://upload.wikimedia.org/wikipedia/en/4/44/LEGO_brick.png) D.2 Typical construction with standard Lego Bricks (http://www.teamgel.co.za/images/teamgel_images/half_day_workshops/house.jpg) D.3 Example of what can be built with Lego Technic Bricks (http://techdigest.tv/lego_technic_remote_control_motorised_bulldozer.jpg) D.4 RCX Brick (http://www.acm.org/crossroads/xrds10-4/gfx/toys1.jpg) D.5 Lego Infra Red Communication Tower (http://www.active-robots.com/products/lego/lego-spares/legotower-750.jpg) 57 Problem Solving with Lego® Mindstorms and Computer Vision D.6 Lego Mindstorms motor (http://www.active-robots.com/products/lego/lego-spares/legomotor-750.jpg) D.7 Lego Mindstorms light sensor (http://www.active-robots.com/products/lego/lego-spares/legosensor-750.jpg) D.8 Rotation Sensor (http://www.cma.science.uva.nl/english/Images/products/9891.jpg) D.9 Touch Sensor (http://discover.edventures.com/images/termlib/l/lego_touch_sensor/support.gif) D.10 Compass Sensor by mindsensors.com (http://mindsensors.com/images/pagemaster/legocompass2.jpg) 58 Problem Solving with Lego® Mindstorms and Computer Vision D.11 Layers of the RCX Architecture (Baum, et al., 2000) User Programs Firmware System ROM Hardware D.12 LeJOS Implementation of the RCX architecture (Baum, et al., 2000) LeJOS Program Host Computer RCX LeJOS Java Compiler User Programs LeJOS Firmware System ROM Hardware D.13 RCX LCD (Baum, et al., 2000) D.14 Example of how a track robot can adapt to a dense terrain environment (Jones, et al., 1998) 59 Problem Solving with Lego® Mindstorms and Computer Vision D.15 An example of a robot with legs (Jones, et al., 1998) D.16 Different methods of wheel alignment; ‘Car’(right) and ‘Wheelchair’ (left) (Ashmore, 2006) D.17 Design of the Robot entered into the RoboCup Jr. competition 1999 & 2000 by Lund & Nielsen (http://www.mip.sdu.dk/~hhl/RoboCupJr/Build/REV257.JPG) D.18 Dual Differential Drive System example (http://haciendarobotics.com/projects/dualdiffsmall/DualDiff-Small.jpg) 60 Problem Solving with Lego® Mindstorms and Computer Vision D.19 A Rubik's Cube (http://www.maniacworld.com/rubix-cube.jpg) D.20 Towers of Hanoi (http://www.cs.umbc.edu/courses/undergraduate/201/fall06/lectures/recursion/Hanoiklein.jp g) D.21 Example Tac Tix game board (http://www.gamesandpuzzles.co.uk/acatalog/tactix.JPG) 61 Problem Solving with Lego® Mindstorms and Computer Vision D.22 Activity diagram show the project methodology Start Initial problem decision Define system components Analysis of Component Design of Component Construction of Component True Testing of Component Failure Evaluation Success / Failure Success Another Component' False False Final Testing Extended Requirement Component' True Evaluation of testing Finish D.23 Russell’s method of localisation (Russell, 2005) 62 Problem Solving with Lego® Mindstorms and Computer Vision D.24 The regions the environment is split up into. D.25 Initial design to find orientation value where the red triangle is the agent and x is equal to the angle of the agent within the environment. D.26 An example of how the robot would score a goal D.27 A simple Lego Mindstorms modelling language (Barrett, 2004) 63 Problem Solving with Lego® Mindstorms and Computer Vision D.28 The environment that was used for this project. D.29 RoboCup Junior Pitch dimensions (http://rcj.open.ac.uk/html/Resources/soccer-1x1.jpg) D.30 How the compass sensor value map around the robot 64 Problem Solving with Lego® Mindstorms and Computer Vision D.31 Final design of the robots D.32 Legend for class diagram explaining communication implementation Legend Indicates message being passed Indicates communication link being established Class package Class Key elements within class 65 Problem Solving with Lego® Mindstorms and Computer Vision Appendix E – Final Solution Photographs ________________________________________________________ F.1 Robot One F.2 Robot Two 66