In recent years there has been an increasing interest in the application of robot teams to solve some kind of problems. Although there are several environments and tasks where a team of robots can deliver better results than a single robot, one of the most active attention focus is concerned with solving coverage problems, either static or dynamic, mainly in unknown environments. The authors propose a method in this work to solve these problems in simulation by means of grammatical evolution of high-level controllers. Evolutionary algorithms have been successfully applied in many applications, but better results can be achieved when evolution and learning are combined in some way. This work uses one of this hybrid algorithms called Grammatical Evolution guided by Reinforcement but the authors enhance it by adding semantic rules in the grammatical production rules. This way, they can build automatic high-level controllers in fewer generations and the solutions found are more readable as well. Additionally, a study about the influence of the number of members implied in the evolutionary process is addressed.
TopIntroduction
Robot teams are frequently being applied in order to solve certain tasks and we can find examples, mainly related to the behaviour-based robotic at the beginning of the nineties (Mataric, 1992; Parker, 1993; Balch, 1999). However, some studies in other areas were previous or parallel to this approach as (Reynolds, 1987) showed in the simulation with computer graphics of bird flocks or (Tu, 1994) detailed with the simulation of artificial fishes. These works share two distinguishing features:
- 1.
They are behaviour-based, both Arkin’s motor schema architecture (Arkin, 1989) or Brooks’ subsumption architecture (Brooks, 1986) and architectures that employ simple rules or algorithms based on equations.
- 2.
They try to solve mainly problems about formation of robot teams or simulated animals. Therefore, we can consider these approaches as a simulation of group behaviours in certain animal species like birds, fishes, cattle or insects.
There is another research line close to previous systems in using a robot team but this second approach is more interested in solving classic problems related with autonomous robots than simulating biological systems, even though both approaches take account of biological and natural principles. This alternative approach engages in studying some problems related to spread out, coverage and exploration with group of robots or agents situated in unknown or known environments. Spread, coverage and exploration are terms that Gage introduced with different names (Gage, 1992). Specifically, Gage named them as blanket, barrier and sweep coverage. To him, formation behaviours are an alternative to coverage behaviours with the aim to maintain a spatial relationship among members.
This work is concerned with problems of the second line and it tries to apply a hybrid system based on grammatical evolution and reinforcement learning in order to generate automatically high-level controllers. We hope these controllers will be able to solve static (spread out) and dynamic (exploration) problems in indoor and unknown environments. The system is completely reactive and it does consider neither communication among robots nor a map of the environment in this first stage.
A main aim in this work is to show a new case in that evolutionary methods provide a valuable alternative to manual design of controllers, an inherent problem in many architectures belonging to behaviour-based robotic. To solve this problem, evolutionary robotics (Nolfi, 2000) traditionally has evolved automatic controllers expressed as artificial neural networks although other structures such as programs are also used and we will mention some examples in the next section. Precisely, in this work we use programs to implement the robot controller. Each controller is generated by means of grammatical evolution but we combine this technique with a process that let each controller to learn new programs during its life time. Grammars are a valuable tool in order to create programs or controllers because they let us to specify a hierarchical structure for the behaviours instead of creating a monolithic whole system as artificial neural network evolution generally do. Using grammars we can develop solutions more readable and understandable than monolithic ones.
Besides solving static and dynamic coverage problems we are interested here in analyzing the influence of the number of members in the team during the automatic controller generation process. To check both issues we tested several cases in simulation with groups of 4, 8, 12 and 16 robots. We analyze different simulators but finally we chose the Simbad Robot Simulator (Hugues, 2006) because it offers a 3D environment and it is very simple of managing and integrating with the Java code of the algorithm which this work is based in. Although Simbad is not a very realistic simulator it allows implementing easily a lot of techniques based on artificial intelligence and we are more interested here in analyzing the design of high-level automatic controllers than in studying low level primitives for perception and action.
TopCovering an environment is an interesting task to be automated because it might help in cases as building surveillance, environmental monitoring or rescue missions.