Autonomous Mobile Robot

Project Description

The advantage of the adaptation of the hardware structure of the EHW with changing environment is clearly demonstrated in the navigation task of a mobile robot which tracks a colored ball, while avoiding obstacles and which adapts its behavior when sensors break. While robotics, such as arm manipulators, are mostly programmed in a very explicit way to execute well defined tasks, mobile robots are forced to work in environments which are unknown and dynamic in nature. The robot has no a priori knowledge of the shapes and positions of obstacles, or of the position of the colored ball. The robot also has to acquire knowledge about the configuration of its sensors, which can be blinded or disabled from time to time. The robot's behavior is based on its current sensory input and its previous interactions with the environment. Its controller can be considered as a kind of adaptive reactive system which can be described by a dynamic Boolean function easily implemented in hardware using EHW. The robot learns how to navigate in the environment by on-line evolution and builds an explicit model of the environment as a collection of events. The simultaneous learning of both an implicit model of the environment within the genetic population and an explicit model can reduce the number of fitness evaluations required in the real physical environment, because the fitness evaluations can be carried out using the explicit model. The reduction in the number of required interactions together with the fact that the fitness evaluations are executed using the evolvable hardware has the advantage of speeding up the adaptive process.

People

• Yong Liu (Electrotechnical Laboratory)

• Masaya Iwata (Electrotechnical Laboratory)

• Didier Keymeulen (Electrotechnical Laboratory and Jet Propulsion Laboratory)

Project Details

• The robot and its environment: The robot shape is circular with a diameter of 25cm. It has 10 proximity infra-red sensors of 1 bit resolution equally distributed around its periphery. These sensors indicate the presence of objects at distances of less than 30cm, yielding 10 bits of sensory input to the reactive robot controller. Two cameras are mounted on the top of robot in order to locate the target within the four 90-degree sectors around the robot. The sector number locating the target is represented with 2 bits of sensory input. Thus, 12 bits of sensory input (proximity 10 bits, target direction 2 bits) is provided to the reactive robot controller which is implemented by one EHW. The output of the reactive controller is a 3-bits motor command to determine the motion of the robot. The robot is moved by two independent motor wheels, which are controlled in terms of speed.  This allows the robot to perform 8 pre-programmed motions; 2 translations, 2 rotations and 4 combinations of rotation and translation. The robot is controlled by a TMS 320 C44 board connected to one transputer for the infrared sensors, the vision sensor and the motor wheels, and two evolvable hardwares that execute robot controller and simulate the evolutionary processes respectively. The robot also has 4 bumping sensors to detect when the robot hits an obstacle at either the front or the back. The number of bumps during a navigation is counted and used in the fitness calculation to evolve the reactive robot controller, where a good navigation controller is one which yields the bumps.

• EHW implementation: The EHW on board the robot implements a dynamic reactive robot controller which accepts 12 bits sensory inputs and yields 3-bit wheel motor commands. When the robot does not detect obstacle in its neighboorhood (its 10 proximity sensors are all OFF), its beahavior is pre-progammed on the EHW to go toward the ball. When the robot detects obstacles (at least one of the proximity sensors is ON), the EHW implements a dynamic Boolean function with 3 FPGA Altera Flex 8000.  The Boolean function is implemented in terms of 50-term DNF (Disjunctive Normal Form) with an AND-array and an OR-array. In our experimental setup with 12 Boolean input sensors and 3 Boolean output, the AND-OR array has 27 columns and needs a maximum number of 4096 rows to represent any three-output Boolean functions of 12 Boolean variables. However to force the Boolean function to generalize, the number of rows can be reduced by merging rows with the same output. In our experiments, we were able to reduce the number of rows and thus the number of terms of the DNF to 50. The configuration bits of the 50-term DNF is 1350 bits long while 12144 bits are needed to represent any functions with 12 Boolean inputs and 3 outputs. The 1350 bits of the EHW are regarded as a chromosome for GA. To learn with fewer interactions with the physical environment and still maintain good online performance, the robot has to do some experimentations in an approximate explicit world model of the environment. Our approach consists of having the robot learn a model continually throughout its lifetime and, at each motion, the current model is used to compute an optimal controller which controls the robot until it hits an obstacle or became stuck. This first avoids an arbitrary division between learning phase and motion phase. Second, with this approach the robot is able to gather data about the environment progressively depending on the efficiency of the controller, and third, the robot is able to deal with changes in the environment or in its structure.

• EHW performance: Because this approach is extremely demanding computationally and to accelerate the entire evolutionary process, the evolutionary process was implemented with evolvable hardware situated next to the evolvable hardware controlling the robot. The evolvable hardware evaluated a population of controllers by computing their Boolean functions. Each controller was evaluated in the explicit world model using an experience replay strategy. The fitness function is a combination of three factors; (1) the number of times the robot hits an obstacle, (2) the number of times the robot became stuck near an obstacle, and (3) the distance covered by the robot in a fixed period of time. In our approach, evolution is used as an adaptive strategy searching continuously for controllers to avoid bumping into the obstacles and becoming stuck near obstacle, and for covering the greatest distance for an explicit world model that is gradually changing. The population size of the genetic algorithm was 500 individuals. For the selection algorithm, we used a tournament selection with tournament size 20 and an elitist algorithm. Using these three factors and the pre-programmed behavior, the real robot was able to reach the target by searching and switching controllers in the population every time the world model changed. The performance of this robot navigation system is remarkable, in comparison with other autonomous robots, both in terms of its adaptation speed and the degree of self-adaptation. On average, within 10 minutes on average, the robot Is able to find a set of suitable hardware configurations for the reactive robot controller and is able to switch dynamically, and in real-time between these hardware configurations to track the ball while avoiding obstacles. This is two orders of magnitude faster than previous works. When some of the proximity sensors are intentionally blinded, the robot will autonomously start to search for another set of hardware configurations for the reactive robot controller, and within a few minutes of navigation can succeed in finding a new set of reactive controllers which allow the robot to continue tracking the ball with the remaining functioning sensors. The EHW implementation is almost 6 times faster than a DSP simulation with a TI C44 processor, but the speed can be improved further by employing the EHW chip described in the next section.

• EHW Evolver Chip: We are currently working on the LSI design of the integration of the genetic algorithm, a specialized memory system and   the dynamic Boolean function on a single chip. It will allow to increase the speed of the adaptation and also to apply the apporach for extremelly small robots. 

Demonstration

Publications

Interesting Past Events

• International Real World Adaptive Robot Worshop, AIST Hall, Tsukuba, Japan. March 1998.

• Co-Habitation with the Evolving Robots Exhibition, NTT InterCommunication Center, Tokyo, Japan. January 29 - March 22, 1999.

• Artificial Life Journal, Special Issue on Evolutionary Robotics. Vol.4, Issue 4, Fall 1998. Cambridge, MA, MIT Press.

Other Groups

• Inman Harvey (Evolutionary and Adaptive Group, School of Cognitive and Computing Sciences, University of Sussex, UK)
• John Hallam (Mobile Robots Group, Department of Artificial Intelligence, Edinburgh Univerity, UK)
• Mark W. Tilden (Beam Robotics, Los Alamos National Laboratory, NM, USA)
• Alan Schultz (Machine Learning Section, Navy Research Laboratory, Washington, USA)
• Jordan Pollack (Center for Complex Systems, Brandeis University, USA)
• Henrik Hautop Lund (The LEGO Lab, Department of Computer Science, University of Aarhus)
• Dario Floreano (Laboratoire de Micro Informatique, EPFL, Switzerland)
• Jonathan W. Mills (Adaptive Systems Laboratory, Indiana University, USA)
• Maja Mataric (Robotics Research Lab, University of Suthern California, USA)
• Barbara Hayes-Roth (Adaptive Intelligent Systems, Stanford University, USA)
• Thomas Christaller (Autonomou s Systems, National Center for Information Technology, Germany)
• Minoru Asada (Department of Adaptive Machine Systems, Osaka University, Osaka, Japan)
• Daniela Rus (Sudikoff Laboratory, Dartmouth University, NH, USA)
• Wolfgang Banzhaf (Computer Science Depat., Dortmund University, Germany)
• Craig Reynolds (Sony computer Entertainment America, USA)

For further Information Contact Didier Keymeulen

Last modified, Thursday, June 10, 1999 01:06:26 AM