Adaptation technique for integrating genetic programming and reinforcement learning for real robots

We propose an integrated technique of genetic programming (GP) and reinforcement learning (RL) to enable a real robot to adapt its actions to a real environment. Our technique does not require a precise simulator because learning is achieved through the real robot. In addition, our technique makes it possible for real robots to learn effective actions. Based on this proposed technique, we acquire common programs, using GP, which are applicable to various types of robots. Through this acquired program, we execute RL in a real robot. With our method, the robot can adapt to its own operational characteristics and learn effective actions. In this paper, we show experimental results from two different robots: a four-legged robot "AIBO" and a humanoid robot "HOAP-1." We present results showing that both effectively solved the box-moving task; the end result demonstrates that our proposed technique performs better than the traditional Q-learning method.     

Evolving choice structures for genetic programming

It is quite difficult but essential for Genetic Programming (GP) to evolve the choice structures. Traditional approaches usually ignore this issue. They define some “if-structures” functions according to their problems by combining “if-else” statement, conditional criterions and elemental functions together. Obviously, these if-structure functions depend on the specific problems and thus have much low reusability. Based on this limitation of GP, in this paper we propose a kind of termination criterion in the GP process named “Combination Termination Criterion” (CTC). By testing CTC, the choice structures composed of some basic functions independent to the problems can be evolved successfully. Theoretical analysis and experiment results show that our method can evolve the programs with choice structures effectively within an acceptable additional time.     

Evolving gaits for hexapod robots using cyclic genetic algorithms

A major facet of multi-legged robot control is locomotion. Each leg must move in such a manner that it efficiently produces thrust and provides maximum support. The motion of all the legs must be coordinated so that they are working together to provide constant stability while propelling the robot forward. In this paper, we discuss the use of a cyclic genetic algorithm (CGA) to evolve control programs that produce gaits for actual hexapod robots. Tests done in simulation and verified on the actual robot show that the CGA successfully produces gaits for both fully capable and disabled robots.     

Design of robust model-based controllers via parametric programming

In this paper a method is presented for deriving the explicit robust model-based optimal control law for constrained linear dynamic systems. The controller is derived off-line via parametric programming before any actual process implementation takes place. The proposed control scheme guarantees feasible operation in the presence of bounded input uncertainties by (i) explicitly incorporating in the controller design stage a set of feasibility constraints and (ii) minimizing the nominal performance, or the expectation of the performance over the uncertainty space. An extension of the method to problems involving target point tracking in the presence of persistent disturbances is also discussed. The general concept is illustrated with two examples.     

Evolving evolutionary algorithms using linear genetic programming

A new model for evolving Evolutionary Algorithms is proposed in this paper. The model is based on the Linear Genetic Programming (LGP) technique. Every LGP chromosome encodes an EA which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization, the Traveling Salesman Problem and the Quadratic Assignment Problem are evolved by using the considered model. Numerical experiments show that the evolved Evolutionary Algorithms perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.     

鲁棒多目标线性规划模型及混合遗传算法

针对目标函数系数和约束条件系数均在椭球扰动集下的不确定多目标线性规划, 提出了椭球扰动集下的鲁棒多目标线性规划问题。基于每个目标均需获得鲁棒解的假设下给出了定理及证明, 以此把原问题转换为具有二阶锥约束的确定性多目标优化问题。设计了一种混合策略求解算法, 整体流程采用多目标遗传算法, 局部采用SOCP优化软件Sedumi进行计算, 从而获得不确定多目标线性规划的鲁棒解集, 并通过数值算例验证了该算法的有效性。     

Evolving recursive programs by using adaptive grammar based genetic programming

The publisher apologizes for an error that occurred in the above mentioned article. The error appears in the printed version, as well as in the html and pdf version online. Man Leung Wong is the sole author of this article. His affiliation is listed below. The online version of the original article can be found at     

Evolving priority scheduling heuristics with genetic programming

This paper investigates the use of genetic programming in automated synthesis of scheduling heuristics for an arbitrary performance measure. Genetic programming is used to evolve the priority function, which determines the priority values of certain system elements (jobs, machines). The priority function is used within an appropriate meta-algorithm for a given environment, which forms the priority scheduling heuristic. The evolved solutions are compared with existing scheduling heuristics and found to perform similarly to or better than existing algorithms. We intend to show that this approach is particularly useful for combinations of scheduling environments and performance measures for which no adequate scheduling algorithms exist.     

Evolving non-trivial behaviors on real robots: A garbage collecting robot

Recently, a new approach involving a form of simulated evolution has been proposed to build autonomous robots. However, it is still not clear if this approach is adequate for real life problems. In this paper we show how control systems that perform a non-trivial sequence of behaviors can be obtained with this methodology by “canalizing” the evolutionary process in the right direction. In the experiment described in the paper, a mobile robot was successfully trained to keep clear an arena surrounded by walls by locating, recognizing, and grasping “garbage” objects and by taking collected objects outside the arena. The controller of the robot was evolved in simulation and then downloaded and tested on the real robot. We also show that while a given amount of supervision may canalize the evolutionary process in the right direction the addition of unnecessary constraints can delay the evolution of the desired behavior.     

Representations of controllers that achieve robust performance for systems with real parameter uncertainty

Consider a family of single input single output plants described by transfer functions that involve real parameter uncertainty. Parameter values are known to lie in a hypercube. Assume that a class of available controllers has been prescribed, along with a bound for the sensitivity transfer function to ensure tracking. It is of interest to determine whether a controller from the given class exists that guarantees robust stability and robust asymptotic tracking. In this paper we present a problem formulation and then provide a solution based on it. Not only do we address the existence question but also give representation of controllers from the class that meet the robustness requirements.     

Automatic generation of biped locomotion controllers using genetic programming

Generating biped locomotion in robotic platforms is hard. It has to deal with the complexity of the tasks which requires the synchronization of several joints, while monitoring stability. Further, it is also expected to deal with the great heterogeneity of existing platforms. The generation of adaptable locomotion further increases the complexity of the task.In this paper, Genetic Programming (GP) is used as an automatic search method for motion primitives of a biped robot, that optimizes a given criterion. It does so by exploring and exploiting the capabilities and particularities of the platform.In order to increase the adaptability of the achieved solutions, feedback pathways were directly included into the evolutionary process through sensory inputs.Simulations on a physic-based Darwin OP have shown that the system is able to generate a faster gait with a given stride time with improved gait temporal characteristics. Further, the system was able to cope with tilted ground within a specific range of slope angles. The system feasibility to generate locomotion more entrained with the environment was shown.     

Evolving rule induction algorithms with multi-objective grammar-based genetic programming

Multi-objective optimization has played a major role in solving problems where two or more conflicting objectives need to be simultaneously optimized. This paper presents a Multi-Objective grammar-based genetic programming (MOGGP) system that automatically evolves complete rule induction algorithms, which in turn produce both accurate and compact rule models. The system was compared with a single objective GGP and three other rule induction algorithms. In total, 20 UCI data sets were used to generate and test generic rule induction algorithms, which can be now applied to any classification data set. Experiments showed that, in general, the proposed MOGGP finds rule induction algorithms with competitive predictive accuracies and more compact models than the algorithms it was compared with.

Development of membrane controllers for mobile robots

The main contribution of this paper is the introduction of the new concept of membrane controller based on the structure and functioning of a deterministic numerical P system. The procedure for developing a membrane controller and for using it to control a mobile robot is explained and several test cases are given in which membrane controllers are used to control both simulated and real mobile robots and to generate various desired behaviours (obstacle avoidance, wall following, and follow the leader). The experiments reported in this paper validate the concept and prove that the performance of a membrane controller is comparable to or better than that of other controllers (such as fuzzy logic controllers).     

Evolving controllers for autonomous robot search teams

Deploying autonomous robot teams instead of humans in hazardous search and rescue missions could provide immeasurable benefits. In such operations, rescue workers often face environments where information about the physical conditions is impossible to obtain, which not only hampers the efficiency and effectiveness of the effort, but also places the rescuers in life-threatening situations. These types of risk promote the potential for using robot search teams in place of humans. This article presents the design and implementation of controllers to provide robots with appropriate behavior. The effective utilization of genetic algorithms to evolve controllers for teams of homogeneous autonomous robots for area coverage in search and rescue missions is described, along with a presentation of a robotic simulation program which was designed and developed. The main objective of this study was to contribute to efforts which attempt to implement real-world robotic solutions for search and rescue missions.     

Evolving an emotion recognition module for an intelligent agent using genetic programming and a genetic algorithm

Most studies use the facial expression to recognize a user’s emotion; however, gestures, such as nodding, shaking the head, or stillness can also be indicators of the user’s emotion. In our research, we use the facial expression and gestures to detect and recognize a user’s emotion. The pervasive Microsoft Kinect sensor captures video data, from which several features representing facial expressions and gestures are extracted. An in-house extensible markup language-based genetic programming engine (XGP) evolves the emotion recognition module of our system. To improve the computational performance of the recognition module, we implemented and compared several approaches, including directed evolution, collaborative filtering via canonical voting, and a genetic algorithm, for an automated voting system. The experimental results indicate that XGP is feasible for evolving emotion classifiers. In addition, the obtained results verify that collaborative filtering improves the generality of recognition. From a psychological viewpoint, the results prove that different people might express their emotions differently, as the emotion classifiers that are evolved for particular users might not be applied successfully to other user(s).     

Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems

We solve the multi-objective flexible job-shop problems by using dispatching rules discovered through genetic programming. While Simple Priority Rules have been widely applied in practice, their efficacy remains poor due to lack of a global view. Composite dispatching rules have been shown to be more effective as they are constructed through human experience. In this paper, we evaluate and employ suitable parameter and operator spaces for evolving composite dispatching rules using genetic programming, with an aim towards greater scalability and flexibility. Experimental results show that composite dispatching rules generated by our genetic programming framework outperforms the single dispatching rules and composite dispatching rules selected from literature over five large validation sets with respect to minimum makespan, mean tardiness, and mean flow time objectives. Further results on sensitivity to changes (in coefficient values and terminals among the evolved rules) indicate that their designs are robust.     

Evolving strategy for a probabilistic game of imperfect information using genetic programming

We provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. Ant Wars contestants are virtual ants collecting food on a grid board in the presence of a competing ant. BrilliAnt has been evolved through a competitive one-population coevolution using genetic programming and fitnessless selection. In this paper, we detail the evolutionary setup that lead to BrilliAnt’s emergence, assess its direct and indirect human-competitiveness, and describe the behavioral patterns observed in its strategy.

---

Nonlinear time-varying controllers for robust stabilization

In this paper we consider the problem of robust stabilizallon for a certain class of plants with unstructured, infinite-dimensional uncertainty. We demonstrate that for the problem of robustly stabilizing this class of plants, linear time-invariant controllers perform as well as nonlinear time-varying (NLTV) ones. Ihis, in particular, implies that adaptive control laws offer no advantage as far as the problem of robust stabilization of this class of plants is concerned. As a corollary we demonstrate that the small-gain theorem is both necessary and sufficient for a certain class of NLTV operators.     

Universal controllers for robust control problems

In this paper we discuss the construction of “universal” controllers for a class of robust stabilization problems. We give a general theorem on the construction of these controllers, which requires that a certain nonlinear inequality is solvablepointwisely or, equivalently, that arobust control Lyapunov function does exist. The constructive procedure producesalmost smooth controllers. The robust control Lyapunov functions extend to uncertain systems the concept of control Lyapunov functions. If such a robust control Lyapunov function also satisfies a small control property, the resulting stabilizing controller is also continuous in the origin of the state space. Applications of our results range from optimal to robust control.