One of the main concerns in robotics is to plan a path for a robot system moving purposely and safely in an environment filled with known or unknown obstacles. Using the sensor motion planning approach, information about obstacles is assumed to be unknown or only partially known and local on-line information is assumed to come from sensory feedback. Since no detailed model of the environment is assumed, planning is performed continuously based on whatever partial information is available at the moment. The advantages of sensor motion planning are twofold: (1) it can deal with unstructured environments and the uncertainty typical of such environments, and (2) it requires much less memory or computation because relatively little information has to be processed during each step. On the negative side, generality is an elusive goal and optimality is usually ruled out.
A control strategy, mapping sensory feedback into a robot's actuators, is an essential component for a mobile robot under the sensor motion planning model. It can be designed by a human according to both the physical structure and the behavior requirements of the robot. However, human design of control strategies doesn't always work well because sometimes desired behaviors are fuzzy and difficult to explicitly define and not all useful behaviors of an autonomous robot can be determined a-priori, or recognized by humans.
During the last decade, much work has been done to explore the evolution of robot control strategies. A series of technical reports has been published by Cliff, Husbands, and Harvey on using genetic algorithms (GAs) to design neural-network control architectures for a simulated visually guided robot [1]. Koza has used genetic programming to evolve LISP programs that control and guide a variety of simulated robots performing navigation and other tasks [5]. Murray and Louis used genetic algorithms to first design combinational circuits for basic (low-level) behaviors, then used the genetic algorithm to design a switch to choose between these low-level behaviors for performing more complex tasks [10].
We cast low-level robot control strategy design as a search problem in a search space of possible strategies and use a non-traditional genetic algorithm to computationally design control strategies, in the form of a combinational circuit connecting sensor inputs to actuators, for a simulated robot (simbot) which can navigate and eat food in a two-dimensional environment with rectangular obstacles. At first, the simbot learns (and memorizes) basic behaviors such as food approach, obstacle avoidance, and wall following in specially-designed separate simulation environments. The best performing simbot from each environment can be considered an expert at one specific behavior and its control strategies must have some useful building blocks corresponding to this behavior. Next, seed solutions (cases) are selected from these experts by calculating and ranking their performance in a new and more complex target environment. Finally, we inject these cases as seeds into the initial population of another GA running in the more complex target environment. Selecting the ``right'' number of ``appropriate'' cases results in speedy design of promising control strategies for the simbot. Our strategy therefore seeks to provide a genetic algorithm with a long term memory in the form of a case-base, borrowing ideas from the field of case-based reasoning [12].
In the next section, we introduce the traditional genetic algorithm and describe our modifications. In addition we provide a brief description of case-based reasoning and the combined system. Section 4 describes the simulated robot and its environment. We present the experimental parameters used by our system in section 5. Experimental results are displayed and analyzed in section 6, followed by conclusions and future work.