3d2 Grounding with a cost function

 < 3d1 Pipeline for robot programming

 

In the AI domain there is a single problem available which is less frequently discussed. It is the symbol grounding problem. Solving this problem has practical relevance because it allows to program robots. To understand why grounding is important we have to describe first why robots in the past have failed.

Suppose someone has built a robot in hardware which contains of servo motors, sensors, and electric battery pack. On the other hand the user has access to an advanced supercomputer which can process millions of operations per second. The supercomputer is equipped with the latest Unix operating system which includes all sort of programming tools and databases.

But, the robot won't move a single step. Something is missing to connect the robot with the computer. And it is not a wire or a wifi connection. What is missing is transformation from the robot problem into a computional problem. Computers are great in solving something, but before they can apply algorithms to a problem, somebody has to define what the problem is.

It is difficult to circumcise the grounding problem in technical terms. It is part of the problem that grounding remains something not available for modern robotics. But there are some hints available how grounding works in theory. A robot domain consists of features. For example the current position. These features have to be converted into a cost function. And a cost function can be solved by a computer with algorithms.

So it seems that grounding has to do with converting features into a cost function. The problem is the terms features and cost function are very general term which can mean anything and nothing. Perhaps it makes sense to give an example. Suppose the robot is 50 cm away from the goal. Then the feature is “distance_to_goal” and the value is 50. A possible cost function would be: cost=distancetogoal/100.

In the concrete example, it is possible to determine the score for the robot. The cost would be: cost=50/100=0.5 And the goal is to bring this value downto zero. Then the robot has won the game.

 

see also 3a1e Improved production line robot

3d1 Pipeline for robot programming

< 3d The bottleneck in robot programming

The following simple pipeline allows to create fully autonomous robots for all domains:

1. Create a simulation with object oriented programming

2. control the robot in the simulation with teleoperation

3. Extract features like distance to goal and angle of the robot

4. convert the features into a cost function

A cost function in a simulation allows to solve the concrete domain. If such a cost function is available the domain was grounded.

 

see also: 3a1 Reward function

3e Cognitive simulation with text adventures

< 3d The bottleneck in robot programming

Most existing robotics was realized in a spatial environment. That means, the robot has a position in the 2d space and can move forward and backward. The interaction with the robot works providing numerical action signals for example the human operator press the forward key which moves the robot 1 cm ahead. Even if the robot can do useful thinks the man machine interface is working only on a low level without using natural language.

Cognitive architectures are trying to introducing a more human like interaction. The assumption is that human thinking and human decision making is working with natural language as a descriptive layer. From a technical perspective such an interface can be programmed as a point&click interface similar what was introduced in the game Maniac Mansion a long time ago.

Point&click graphical adventures are working by selecting action verbs and mention the objects by name. The robot isn't simple moving 1cm forward, but the robot executes a skill which has a name and it can reach a waypoint which has also a name formulated in English.

 

Understanding cognitive models and cognitive architectures 

What is symbolic AI? 

3a1g Playing Tetris with a cost function

 < 3a1f Reward maximization in a production line

Similar to most AI domains, the game of tetris is an np hard optimization problem, which means, that a desktop PC will need to process the information for over 1 million years, until the next action can be determined ... To overcome the bottleneck a heuristic is needed. To be more precisely, it is about a heuristic cost function or short “a cost function” which is used to play Tetris by an AI.

Such an attempt to solve the game might sound a bit surprising, because most programmers assume that the game of Tetris provides a cost function as default and there is no need to define the rewards. The problem with the built in default cost function is, that it works with a delay. The player will recognize that he has lost if it is too late. So what is needed is a modified cost function which provides a continuous very precise feedback signal if a certain action makes sense or not.

In the game of Tetris, the human player can take two decision: at which position the next block is placed and at which rotation. The interesting situation is, that it is possible to judge about the decision even before the block has fallen downwards. This allows to determine a score before the official score was determined.

On base of this cost score, a receding horizon planner can determine the optimal action. What the planner is doing is to maximize the reward. The open question is, what costs exactly should be calculated for a certain game situation? This depends from the heuristics. It is possible to invent a simplified cost model or a more advanced scoring system. A slightly accurate cost function allows a desktop PC to play the game of tetris with super human level performance without occupying too much CPU ressources.

3a1f Reward maximization in a production line

 < 3a1e Improved production line robot

The example with the production line game was introduced in a previous post. Even if a human operator can interact with the game, the more exciting task is to program a robot which can solve the game. Because the game is already grounded with an elaborated reward function such a robot solver is pretty easy to realize. For the concrete game, only 30 lines of code in the python language were enough to create such a robot.

What the machine is doing after it gets started is simple. It will maximize the reward. That means, the solver has a clear understanding about the goal of the game, and it can plan the optimal action sequence. The resulting performance is much higher than what a human operator has to offer. Not a single mistake was made and the amount of picks per seconds is high.

The reward is growing constantly over the time, also the robot is visiting regularly the charging station. This sense making behavior is not the result of the onboard AI itself, but it has to do with the reward function. The reward function defines which actions are good and and which not and this guides the search in the state space.

The perhaps most surprising insight was that not the robot is intelligent, but the game has this built in feature. The opposite is a game which has no reward function. Without a reward it is not possible to play this game automatically.

 

3a1e Improved production line robot

 < 3a1d Programming an assembly line robot

In addition to the previous simulation game, the GUI was improved a lot. The robot has to sort the tokens but this time the task is more complicated. Also the performance evaluation was improved, so the robot needs to adjust it's movements.

One thing remains the same. The robot isn't controlled by an AI, but the game is played by human intervention. That means the operator has to press the arrow keys and this will trigger the actions of the robot. The AI is located in the referee, that means, the box with the performance information on the left lower side is generated by software on the fly.

For example, if the robot worker has placed the token into the wrong bin, his reward is reduced by -4. Also if the robot keeps on walking even the energy level is low, a negative reward is the result. Why this performance evaluation is needed is because of grounding reasons. The task of navigating a robot in a factory is translated into a score. That means it is not important what exactly the robot is doing but the only thing who cares is the measured reward.

At the end of the game it is pretty easy to judge what the robot has done. For example he has executed 16 picks, has reached an overall score of 11 and it took a time of 92 seconds. All the quality criteria are available as numerical integer values, that means, they can be stored in a computer program very well. In contrast, the original domain which has to do with sorting tokens by color and place them to the correct position are hard or even not possible to understand by a computer. So we can say, that the shown game is an example for a grounded Artificial Intelligence.

 

Let us take a look into the game itself. The incoming line on the left side delivers new tokens in random order. The task for the robot work is to sort them by putting them on the outgoing lines on the right side. So it is some sort of pick&place task.

The interesting situation is, that the robot worker isn't controlled by a sophisticated Artificial Intelligence but it is working in the teloperated mode. That means, the shown simulation is a normal computer game. After pressing the keys the robot is doing something. The new and advanced element is, that the virtual referee determines very precisely if the action is making sense or not. That means, every action of the robot is tracked, monitored and translated into a reward score. The robot worker is under total surveillance and has to explain itself for everything. So it is a highly accurate scoring system to determine the performance of the robot.

On the first look such a game doesn't look very pleasant, because human workers doesn't like the idea to be monitored. But from the perspective of Artificial Intelligence it makes a lot of sense. Because such a domain is a great testbed for an optimal control algorithm. The domain has possible actions (up,down, left, right), and the domain provides a feedback stored in the total reward. The feedback is a numerical value and the task for the model predictive control algorithm is pretty easy. The goal is to maximize the reward. This is equal to win the game.

Here the pipeline in short:

Teleoperation -> simulation -> features -> cost function

 

Playing the game with an algorithm

How humans are playing such games is easy. They are looking at the monitor and decide which actions should be done next. With a bit of training a human operator will reach a better performance and for sure he will make some minor mistakes after repeating the actions over and over again.

The more interesting question is how will an optimal control algorithm play the game. The algorithm doesn't have any sort of human intelligence so he has to focus on the information box on the left lower side. The box contains the variables: elapsed time, energy, picks, totalward reward.

From a computer perspective these variables are stored in an integer array which contains of 4 elements. In addition the computer will need another variable to store possible actions for the robot (0=left, 1=up, and so on). The interesting thing is, that with this minimalist information a computer is able to play the game. There are many existing algorithm available to determine the optimal action sequence. Most of them are working with graph search which is improved by the reward information.

 

The inner working of the AI

In the concrete example it is possible to explain who the AI is working. The normal conception is that the robot is doing something and the robot should be determine by it's own intelligence which action is the best one. So the question is how exactly does the AI know, that the the robot has to go the charging station or place the token to the correct place?

The surprising answer is, that the robot doesn't know the answer. What is available instead is a virtual referee. The referee determines the score during the game. He determines if the action was good or not. Such a referee is used in most video games to determine the collision of a player with walls. Here in the production line simulation the referee is more advanced and determines many other details. The interesting situation is that the referee can judge about human players and AI Controlled robots itself. So the new understanding is, that the robot doesn't need an onboard AI, but the game needs a virtual referee.

This referee allows to ground a game. Grounding means to convert the pixel map which is 320x200 into a small list of variables shown on the lower left. These small amount of variables are used by a solver to play this game automatically.

3d The bottleneck in robot programming

 < 3c The misconception about bottom up robotics

In contrast to a famous myth, the bottleneck is not to program the robot itself. But it has to do with defining the cost function. The initial situation is, that a teleoperated robot is available. For example a robot arm or a remote controlled car. What is missing is a numerical judgement if the actions of the robot are pleasant or not.

In most cases this decision is made by humans but not by algorithm. And this missing scoring system prevents that the task can be automated. So the challenge is to create a software which is judging about a teleoperated robot. For example if the car collides with an obstacle the costs are high and if the car stays on the lane the costs are low.

Such an algorithm or software is mostly a mathematical equation. It takes features as input and determines the cost value as output. This processing step is the core element of a virtual referee and the bottleneck in today's robotics. There is a large difference is such a scoring system is available or if it is missing.

3a1d Programming an assembly line robot

< 3a1c Game design with petri nets

The picture shows an assembly line simulation game. The user can control a robot in the middle and the task is to sort incoming tokens. The robot has a battery level and all the actions are scored. If the robot puts the wrong token on the outgoing conveyor a certain amount of error costs are created. So the overall objective of the game is to reduce the costs.

Sounds not very complicated, right? The AI is located in the game engine. The game engine determines the score, and simulates pick&place actions in the game. The shown game can be played by a human player very well.

The interesting situation is that such a grounded domain can be automated easily. All what is needed is to solve the given optimization problem. The goal is, to minimize the costs for the robot and the costs are calculated by the game.

3a1 Reward function 

 

Let us try to elaborate the situation a bit. In bottom up robotics the idea is to program the robot in a certain way, that he is solving a task. Such a program is not needed here and it wasn't implemented. The idea of top down robotics is, that the AI is equal to the virtual referee. The virtual referee monitors a game and determines the score for a player.

The example simulation allows the robot to do certain actions. It can pick a token, it can place a token, it can walk around and it can charge the battery at the lower position. All these actions have consequences. For example if the battery level is below a certain threshold, the costs for the robot are growing fast. So it is a classical video game, except a strong emphasizes was put on the scoring function.

The interesting situation is that after starting the game in the command line the robot won't do anything. the reason is, that it wasn't the objective to program the robot. Instead the idea is that core element is the scoring function which is located inside the physics engine. What this scoring function is able to do is to judge about the actions. It converts possible behaviors in the game into a score. This score is shown on top left of the screen. It is a numerical feedback about the meaning of actions. Only actions which are generating low costs are sense making.

The principle has to do with social roles. There is an actor which is the robot. In theory, the robot can do anything which includes to put the token on the wrong conveyor. In the game, such actions are producing a higher costs. This virtual referee is sometimes called a critic because he judges about the robot.