So what do you do there at the university? Chapter 7: Training Pacman to score goals - about evolutionary robotics

I met with Shlomi Israel to ask him what is being done there at the university

Shlomi is nearing the completion of his master's degree in electrical engineering at Tel Aviv University. He carried out his research under the guidance of Dr. Amiram Moshiev from the School of Mechanical Engineering, and our focus is on evolutionary robotics. He earned his first degree at the Technion in electrical engineering and physics. Shlomi, until recently a permanent resident, is married and lives with his wife and daughter in Haifa. In his spare time He likes to listen to podcasts, and recently started playing Ultimate Frisbee, which is a hybrid Between Frisbee and American football.

Hello, so what are you doing there?

We deal with the combination of two fields: evolutionary robotics and multi-objective optimization. I know the concepts are daunting but don't worry, we'll break them down slowly and carefully.

Image 1: A robot with differential drive developed at the Georgia Institute of Technology. Image source: Wikipedia.
Image 1: A robot with differential drive developed at the Georgia Institute of Technology. Image source: Wikipedia.

So let's start with the question of what are robots?

The robots we deal with are entities that have the ability to sense input about the world around them and react according to certain legalities. The inputs can be, for example, sensors that measure the distance from a wall or a ball and the output can be movement. The movement in our robots is carried out by differential drive with the help of two wheels. Between the input and the output there is a controller that determines how to behave for different inputs. The controller has external parameters that can be changed and affect the behavior of the robot.

Although these are robots that move in space, both the robots and the space are usually in a computer simulation. However, the sensors, propulsion and controllers of the robots are based on the real hardware and it is relatively easy to transfer the system to the real world. If we take the Roomba device for example, it is likely that before it was first created it was tested as a computer program that cleans a completely virtual room, and was only built after it showed good performance there.

Photo 2: Roomba at the docking point. Image source: Wikipedia.
Photo 2: Roomba at the docking point. Image source: Wikipedia.

Okay, so what is evolutionary robotics?

The human operator defines a super-goal for the robots that is not pre-programmed into them. The experiment is carried out in an arena where a random population of robots competes to achieve the goal, and after several competitions the performance of the robots is checked. If, for example, the ultimate goal is to get from point A to B, then we check which of the robots came closest. From the most successful robots, they create the next generation of robots, when they duplicate their controllers with random changes, and even combine different controllers in a kind of pairing. The chance of mutations is usually determined in advance from previously studied models. The experiment ends after several generations but then it is re-run several more times because the starting data is random and the results of a single experiment vary from run to run.

Evolutionary robotics makes it possible to develop very complex controllers efficiently. But the general goal of the research is engineering - to develop methods with which we can more easily design robots that will deal with a variety of environmental conditions that were not determined in advance. That is, not to develop the perfect robot, but to develop the optimal process to train robots for required tasks.

And what is multi-objective optimization?

When performing optimization, an objective function must be defined that will tell us how successful the robot is. For example, if the goal is to get from point A to B, then the closer the robot is to B, the higher the score will be. In multi-objective optimization, several objective functions are defined. If we think of Pacman for example, then one of his goals is to eat as many points and fruits as possible, and a second goal is to keep as many Pacmen alive as possible.

Usually the different goals come at the expense of the other because otherwise we could be satisfied with only one of them. For example, if Pacman takes too many risks in order to eat many fruits, it is likely that he will end the game quickly due to frequent encounters with demons. But if he doesn't take risks at all, he won't eat fruit. The problem has a set of optimal solutions, different in composition but equally good. Our goal is to bring the system to one of those solutions. As long as one objective can be improved without harming another objective, we know that we have not yet found one of the optimal solutions (in parlance: searching the Pareto front).

Image 3: Screenshot of a Pacman game from this site.
Image 3: Screenshot of a Pacman game from this site.

And how do you connect the multiplicity of goals to evolution?

In the case of multi-objective optimization, the robots that will make up the next generation will choose according to several super-objectives, using the analysis I described earlier. For example, we can define two super goals: get from point A to B and collect as many objects as possible on the way. Since these are two opposing goals, it is likely that at the end of the process the robots will not excel in any of the individual goals but will demonstrate some kind of optimal compromise.

So what can be explored with all these robots?

I will give you an example. A few years ago a study was published in which robots ran in an arena where two elements are important: food points and poison points. The overarching goal of the planner, unknown to the robots, is for them to stay as long as possible at the food points and avoid the poison points. The robots can signal to each other with light, without the meaning of the action being defined for them.

The selection of the robots to assemble the next generation was done in the study in one of two ways: either according to the success of individual robots or according to group success. The results of the study indicated that in cases where success was judged by a group, the robots developed the ability to signal "Guys, come here, there's food here!". The robots that developed a connection between a signal and the location of food are the ones that passed on to the next generations. On the other hand, in cases where success was judged by individual robots, either the signaling did not develop into something meaningful or it developed into a signal whose purpose is misleading, for example signaling near the poison, and this is because there is competition for resources.

That is, in a fairly simple experiment, the researchers were able to make the robots develop quite complex behavior, one that matches what we see in nature.

Tell me briefly about what you do in your research.

with fun We train two robot teams to play a simple version of soccer, meaning the goal is to score goals. As I already mentioned, the experiment is started with a random population. But what is the chance that such a population will manage to score even one goal? And if they all fail, then how do we choose the successful robots for the next generation? It is possible, of course, to define more focused goals, but then we are actually already engineering the solution and this is a bit sinful for the purpose of the experiment. We have a bootstrapping problem here - initializing the experiment. Our approach to the solution is to separate the general problem from the initialization problem. For the initialization problem we set intermediate goals, and attack it using multi-objective optimization.

Using statistical methods, we were able to show that the method we developed achieves better results (for example, more expatriates) than other accepted methods under identical running conditions.

————————————————————

I would be happy to meet and talk with any research student (maybe you?) who is willing to participate and tell me a little about what he is doing (and all for the price of a not too long conversation). You can contact me through the contact form.

It's time to tell everyone what you're doing, maybe this time they'll understand too 🙂

7 תגובות

  1. hi ram,
    Your question is interesting and has engaged many researchers.
    The best answer I came across is that of a researcher named Thomas Miconi who devoted a chapter to this in his doctoral thesis. What I like about him is the ability to balance between rigorous scientific writing and keeping the text readable and fluid, so if you are really interested in the subject you will enjoy reading (see chapter 8):
    http://etheses.bham.ac.uk/148/

    In size, the common mistake is to perceive the increase in complexity as a driven (directed) advance, whereas it can be seen as a passive advance that happens simultaneously with retreats in complexity (see diagram 8.1).

  2. The phenomenon you describe - of a decrease in complexity happens all the time, we don't feel it, because it's hard for us to know which creature was once more complex. Even then it is the survival of the fittest, take for example creatures that fall into a cave and lose their eyes, they adapt themselves to their environment.

  3. Well, questions that are not directly related to the topic, but I'm trying to understand evolution. And please no accusations about intelligent design, I'm really just trying to understand how complexity is created.

    The blind mechanism of evolution created humans in the last billions of years (the pinnacle of creation according to God, the peak of complexity so far according to evolution. Or am I wrong?) but theoretically it is possible to imagine, or describe a situation where the *conditions* will dictate a decrease in complexity, loss of consciousness, disintegration of many cells to single cells or even atomic particles. Will the theory still call it survival of the fittest?

    And more on the topic of complexity: suppose there is an organism that depends on sugar, and the sugar level drops. Evolution claims that someday, under certain conditions (which we have no ability to predict) the organism will develop the ability to exist with less sugar or without it. In the same way, because the mechanism is blind, in other samples the organism will become extinct, or its quantity will decrease, or it will develop the ability to exist on something completely different. That is, statistically, the level of complexity - as opposed to variance - will not change. So where, conceptually, do you fit into the story of the movement we see on Earth towards complexity?

    what am I missing? Maybe all I need is a recommendation for a good book...

Leave a Reply

Email will not be published. Required fields are marked *

This site uses Akismet to filter spam comments. More details about how the information from your response will be processed.