Grounded language in open systems

Many attempts were made in the past to describe natural language, boolean algebra and artificial intelligence but they didn't reflect about the symbol grounding problem. Stevan Harnad was the first researcher who introduced the subject in the year 1990. Grounded language works with a 2 box system, see the figure.

The box on the left is the human who describes the reality with natural language. The box on the right is the environment which can be perceived with sensors. Symbol grounding is the connection between both boxes.

From a system perspective the 2 box system is an open system because both boxes are connected to each other. Natural language from the left box is referencing to physical objects in the right box, while perceived reality in the right box gets described with English words in the left box.

The assumption is, that there are 2 different systems available which are working with different internal logic. The language layer consists of nouns, verbs, adjectives and grammars which is the symbolic layer. In contrast, the environment has no natural language but it consists of sensor perception, motor actions and 3d objects. The 2 box paradigm describes in a simplified format what natural language is about. Its an abstraction mechanism for the reality. Physical objects like a table or a banana are labeled with words. The ability to label objects is the key element in grounded language and allows to build intelligent robots.

Programming heuristic algorithms

 Around the year 1990 the understanding of heuristic algorithms was poor. The problems are visible even in the definition what a heuristic is about. Normal algorithms are step by step instructions formulated in source code, e.g. bubble sort or a path planning algorithms. In contrast, a heuristic algorithm is based on domain specific knowledge, but it remains unclear how this knowledge is encoded in software.

It makes sense to assume, that a heuristic algorithm isn't a technology but only a wish for such a technology. Its more a question for future mopre efficient algorithms not invented yet. Nevertheless there are some attempts available to describe the situation in detail. One famous example is a cost function. Cost functions are used to encode the knowledge of experts into a simple mathematical equation. For example the distance there is a distance in a maze to the goal, or there is a cost function available for colliding with an obstacle. The idea behind a cost function is to encode a high level descripotion "Move to the goal, avoid the obstacles" into a mathematical model which can be translated into actions.

If cost functions are an entry level heuristic algorithms, there is another more advanced strategy available which are text based robot control. The idea is, to provide domain knowledge on the fly, during the runtime of the program. The human operator speaks to the robot e.g. he gives the current subgoal, and this information is converted into a mathematical equation. In contrast to the previously mentioned static cost function, a text based teleoperation is harder to implement but provides higher flexibility.

Let us analyze the workflow in detail. The human operator provides the next subgoal in natural language, this information is translated into a cost function by a parser, and the cost function is used to plan the trajectory of the robot. Even if the pipeline sounds a bit complicated it can be realized in software. The bottleneck is how to translate natural language instructions into a mathematical equation.

The similarity between cost function and text based control is, that the domain specific knowledge isn't available in the robot itself, but its provided from the environment. This redfines the robot's role from a former autonomous robot into an interactive device. The principle is similar to bottom up robotics formulated by Rodney brooks in the late 1980s. In contrast to Brooks subsumption architecture, the robot is more dependent from the environment. Instead of using a frontsensor to avoid an obstacle, the robot gets textual input from a human operator, so its entirely remote controlled.

Why cognitive architectures can't solve real world problems

Under the term “good old fashion AI” many attempts were made in the past to develop a universal Artificial Intelligence. That's a computer program who mimicry the thought process and the behavior of a human. A well known example for a cognitive architecture is the BDI paradigm which is a framework to develop agent systems. On the first look, it's unclear why cognitive architecture are not able to solve real world problems. Because if a software like Agentspeak or SOAR consists of working memory, an inference engine and a sensory buffer it should be well prepared for all sorts of philosophical problems.

It has to do with a missing understanding of environments vs agents. The connection between both of them is explained in the literature as grounding, but the definition is not precise enough. The terms agent and cognitive simulation are often used with the same purpose. For solving practical problems from robotics only the simulation part is more important, and the AI can be ignored. If the domain was converted into a simulation the problem was solved. That means, a simulation doesn't need a sophisticated Artificial intelligence.

But let us take a deeper look into the BDI framework. The Belief desire intention concept is often described as a software for creating AI-agents. But in reality, a BDI agent has at foremost the obligation to represent the problem. If the agent was designed for a robocup like game, the agent will contains of procedures and variables from the soccer domain. That means, it provides a variable ball, a function “moveto” and an event like “lost the ball”. According to strict border between agents and simulations these terms are not located in the agent but they are part of the environment. That means, the variable ball doesn't belong to a certain agent who likes to play the game, but it is provided by the game engine of the domain.

The question is not how to play a given game, but how to create a formalized game for a domain. Before a software program can be implemented which kicks the ball in Robocup, there is a need to write a simulator which allows agents to play the game. If the simulator has more features and was programmed well, it will become much easier to write an AI for it.

A typical mistakes of robotics engineers is, to leave out the step of programming a simulator. They are using a robot in hardware, for example an Arduino board and the idea is, that after pressing the on button the robot is able to play the robocup game. The beginner assumes, that the robot itself needs a certain amount of intelligence and knowledge to understand the game and determine the next action. This assumption leaves out the importance of a simulator:

Robocup domain -> agent plays the game

The robot who plays the game was programmed with an agent architecture. Such project will fail. The agent aka the AI is not able to interact with the domain in a meaningful way. The more elaborated workflow is:

Robocup domain -> simulator -> agent

To understand why the second pipleline is more efficient we assume that the agent is equal to a random generator. He can't inference anything, but the robot is producing random numbers all the time. On the first look this strategy will fail to solve the robocup game. Surprisingly it is working great if the underlying simulator was programmed already. The simulator provides meaningful motion primitives like “take ball”, “kick ball”. If the agent sends random numbers to the simulators, it's possible that the agent plays the game reasonable well.

The intelligence is not located within the robot but in the simulator. The domain simulator converts a domain into machine readable API. It's called grounding and is the most important part of an Artificial Intelligence system.

Creating complex simulations

There are some techniques available for creating complex realistic simulations for a domain. In traditional software engineering there are object oriented programming languages invented. They can be utilized for creating hierarchical object oriented models. That's an UML chart which contains lots of classes distributed in hierarchical layers. Sometimes the protege tool is recommended to design such object oriented model The idea behind Protege is, that the user can creates classes which are describing a domain.

Object oriented programming and the Protege tool is used for creating simulations. A given domain, for example a soccer game, is mapped into objects. All the allowed sensor rules, actions, and events are formalized in an object hierarchy. This is called by game programmers a game engine, or rule engine because it holds the game itself.

In a short but readable tutorial it was explained how to use object oriented programming for create videogames, https://gamedevelopment.tutsplus.com/tutorials/quick-tip-intro-to-object-oriented-programming-for-game-development--gamedev-1805 Three different domains were given: Asteroids, Tetris and Pacman. All the games can be realized by creating objects which have attributes and methods. This is equal to create a game simulator, it's a computer program which executes a certain game. After the game objects are created, it's possible to interact with the game engine. For example, in the Asteroids game it's possible to send a “turning” command to the spaceship which will modify the trust variable.

It's interesting to know, that without a simulation written in a object oriented language it's not possible to play a game. Also it doesn't make sense to discuss a possible AI which can play the game autonomously.

A convenient way for accessing lots of UML models for games is the “site:genmymodel.com pacman” website. It's possible to ask the site for a certain game, and it will result a list of UML diagrams which are used as a game engine. Easy games are containing not more than 10 classes, which are connected on the same hierarchical level. More complex games are realized by a hierarchical object model which allows to store 50 and more classes. It's interesting to know, that no object model is available for the problem of simulating an AI or a robot. Because this kind of game is to general. Instead, only concrete domains like pong, pacman, soccer and RPG games are available.

From a simulation to an AI

On the first look an existing UML Diagram for a video game or the written sourcecode for the game engine doesn't answer the question how to play this game autonomously by an AI. Because the question is not how to program a game, but how to realize the Artificial Intelligence ... It's interesting to know, that both is connected together. A well written game engine can be easily scripted. A script is short computer program which sends commands to the game API. If the Game API has more features it's much easier to write a script and vice versa.

Apart from scripts there are other options for utilizing an existing game engine API, for example neural networks, a random generator, reinforcement learning and so on. All these AI techniques become more powerful if they are not used from scratch but are producing commands for a given game API. That means, the intelligence of the resulting non player character isn't located in the neural network but in the game engine which provides the allowed actions for the neural network.

Let me explain this strange situation on a concrete example. Suppose a real time strategy game was programmed already. The game engine supports the creation of new buildings and it's possible to move units on the screen. The only missing part is the AI. Instead of programming a dedicated AI, the user writes a 10 line python scripts which is using a random generator for generating a number between 0 and 100, and then a random action from the game API is executed.

The resulting AI will produce only sense making actions. He will build first some buildings, move the units and builds more buildings, very similar to what a human user would do. The reason is, that the game API transforms the random generated numbers into semantic correct behaviors. If the strength of the AI is too low, not the AI has to be improved but the game engine.

Symbolic AI explained

The amount of literature about classical AI is large. It's important to extract the dominant ideas. Symbolic AI is often mentioned together with cognitive architectures. This is equal to a cognitive simulation. It means, to mimicry the behaviors of a human in a computer program. Realizing a cognitive simulation in computer code can be done with an agent-based simulation.

Agent-based programming languages like Agentspeak are working with the belief-desire-intention model. This is an abbreviation for 1. recognize the current state, 2. define the future state, 3 create a plan. It's interesting to know, that this kind of workflow can be implemented with a STRIPS like planner. The STRIPS Solver needs as input the current world, it needs also the goal state, and then strips is able to plan the actions in between.

STRIPS and the more recent declarative AI language PDDL are examples for a cognitive architecture. They are used to simulate the behavior of a human. Unfortunately, it's not answered yet how to convert a certain domain into a STRIPS notation or into a agent-simulation language like golog. Most practical projects from within the robotics domain are not focused on simulation of human thinking but they are domain oriented. That means, converting the Mario AI game into the strips notation is done with actions and goals from within the Mario game, while converting a snake game into a agent-simulation has to be done with the typical motion primitives from snake.

So in reality, the term cognitive architecture is a bit misleading. In reality, it's a more a domain-specific simulation in which not the human is simulated but the task he is trying to solve.

Agentspeak = qualitative simulation

Agentspeak defines itself as a cognitive architecture written in Java. The idea is, that the programmer gets a tool for creating a multi agent system. It's interesting to know, that the programmer doesn't define the agent itself, but he writes down the domain in a machine readable form. Converting a domain into the agentspeak syntax is equal to program a qualitative simulation.

Let me give an example. Suppose the domain has to do with a robot in a maze. For simulating the robot a symbolic game has to be written. The game consists of a game state, and possible actions. In the game programming literature this is described as a game engine or rule engine. The robot has a position (variable pos), he can move in 4 directions (action move), and he can collide with an obstacle (event collision).

Where exactly is the difference between a cognitive architecture written in Agentspeak and a game engine? Right, there is no difference, it's the same. Agentspeak can't be utilized for creating agents, but it's a game construction kit. From an abstract point of view, an agent simulation is utilized for simulating a system. The term system isn't referencing to an Artificial Intelligence, nor a cognitive agent, but to a domain. A possible domain is the “Super Mario game”, the Snake game, or a robot in a maze. The question is how to convert these domains into a computer simulation. This process is called agent programming, or game engine programming. From an engineering perspective the correct term is forward modelling or system identification. It means to convert a given domain into a computer simulation.

The most interesting aspect is, that system identification doesn't need an intelligent agent in the loop. If a the movement of a rigid body are formalized by ordinary differential equations, it's for sure, that the rigid body isn't able to think. Instead he is following physical laws. The same is true for implementing a racing car. The game engine which calculates the current position of the car in response to the speed value isn't an agent, nor an Artificial Intelligence, but it's the normal game engine. The result of the game engine is visualized by the graphics engine of the program.

That means, in practical projects, an agent can't be identified in a given domain. If the domain was transfered into a simulation, all the work was done.

What is symbolic AI?

In the history of AI the well known General problem solver was the first example for an abstract planning system. Later examples were STRIPS and a modern version is called GOAP (goal oriented action planning). What these systems have in common is that they are using rules to solve a problem. A rule is part of a simulation, very similar to what a player activates in a textadventure to reach a goal.

The difference between rules and normal functions in a c program is, that the order of rules isn't fixed. It's the task of the solver to determine the sequence by it's own. This provides a higher flexibility. The simulation can start at a initstate and can be transfered into a goal state. Very similar to what a classcal pathplanner is doing, except that the world isn't a 100x100 pixel map but the state space contains of abstract actions like “take key”, “walkto location” and “open door”.

To get an idea how to use symbolic AI in the reality, a new environment was published in the year 2018 by Microsoft Research called Textworld. https://www.microsoft.com/en-us/research/project/textworld/ It is a textadventure and a solver in the same program. The textadventure simulates a world in which the player can do tasks which have to be entered on the command line. The solver is able to determine the actions autonomously to reach any state in the simulation.

The reason why robotics can profit from this idea is because the state space of a textadventure is much smaller than the geometrical statespace. The amount of possible goals and actions in a symbolic simulation is not very great. A graph search solver will find the actions very fast. The interesting aspect is, that GOAP like solvers doesn't need a certain framework, nor a dedicated STRIPS like programming language. The more important aspect is, to convert a domain into a textadventure. This is the most harder part.

In the famous monkey banana problem the domain contains of only 3 actions and 2 objects. In a robotics domain, the amount of actions is higher. The AI engine for a computergame will need hundred of rules and a dozens of subgoals. This programming task can be handled with the normal software engineering paradigm. That means with the help of UML diagrams, git version control and bugtesting. Or let me explain it from the other perspective. The question is how does a textadventure look like which is about a self-driving car, a biped robot, a Lemmings playing AI or a Mario AI bot? If somebody has answered these question he gets a fully working AI which is planning very fast. Sometimes the concept is called “Task and motion planning”. Task planning is referencing to symbolic AI planning which is equal to GOAP, STRIPS and GPS. Motion planning is the lowlevel side which includes inverse kinematics and pathplanning in a map. The more important part is the task planner, or to be more specific, the textadventure in which possible tasks are formalized.

Text adventure solver

The fascinating information about text adventures is, that they can be solved relative easily automatically. In contrast to a normal computer the amount of possible actions is not billions but only a few thousands. The famous blocksworld example in which a robot arm has to pick and place boxes can be interpreted as a textadventure as well. The robot has certain commands like grasp, ungrasp, moveto and the goal is to find the correct action sequence. It's some kind of puzzle game which can be solved with a graph search algorithm in under a minute.

Unfortunately, most games are not available as a textadventure. For example, Mario AI, Lemmings, or Starcraft are working with graphics but not with text and the available actions are unknown. To overcome the bottleneck one idea is to monitor an existing textadventure if it's fit to a game. That means, the Mario AI original game plus the Mario AI textadventure are started at the same time and the question is, if both instances are in the same state. If not, the textadventure version has to be modified.

Simulation

The Situation calculus is the theoretical background behind the STRIPS planning language. It describes a world which contains of a world state which has actions to change the state. Running such simulation is called a qualitative simulation because it's not based on numerical values but on natural language. For example, if the player types in “open door”, the string of the door variable gets changed into “door is open”. It's important to understand, that a qualitative model isn't an algorithm but it's a text adventure. It forms an environment in which a human player can execute actions and observe the resulting game state. An algorithm is needed only on top of the simulation to bring the system into a goal state.

In the history of AI many techniques were developed to realize a qualitive simulation. One example are the planning languages which are ADL, STRIPS, Golog or PDDL. Another attempt are XML based models and the latest innovation are RDF-triple storage and General description languages. All of these techniques are trying to build a textadventure as easy as possible.

Production systems are language based game engines

The history of AI knows production systems, General problem solvers and STRIPS like solvers. What they have in common is, that they are using language based transformation of a system which results into high speed problem solving. To explain the idea in detail i give an example.

A robot is located within the center of a map. He can move in 4 directions (up, down, left, right). The numerical way of problem solving is working with a gametree. All possible sequences of the robot, e.g. “up, up, left, up, left” is stored in a graph and a solver can search in the graph for a goal node. Dedicated path planning algorithm like A* or RRT modify this approach a bit and search the graph faster.

A production system is working different from graph search. The basic idea is, to describe the problem on a semantic level with the help of a robot language. This is equal to introduce macroactions. The robot language contains of the following words:

- lowlevelactions: up, down, left, right

- midlevelactions: 5up, 5down, 5left, 5right

- highlevelaction: movetolocation, moveincircle, resetgame

The words of the robot language can be combined to larger programs, very similar to a behavior tree. A production system is using the grammar for reaching a goal. The advantage over a graph search algorithm is, that the computational effort is much lower. The reason, why STRIPS like solvers are not very common in robotics is because it's hard to invent the robot language from scratch. In most problems only the low level commands (up,down, left, right) are known, but not macro-actions.

In the STRIPS notation, the domain grammar is stored in the STRIPS syntax, while in the SOAR production system the syntax is based on SOAR production rules. In both cases, the domain file is equal to a grammar which describes a problem on a higher level. The grammar allows to search in the action space of the robot more efficient than testing out only lowlevel sequences of actions.

Symbolic AI

Symbolic AI is equal to create a higher abstraction layer on top of movement primitives. On the lower side, the robot can only move in four directions with one step each. He is not able to reach with one command a position far away. This kind of super-actions has to be invented by the programmer. It's possible to transform a super action like “moveto(10,20)” into a sequence of lowlevel actions. In the literature the concept is described as hierarchical planning and it's improves the efficiency in problem solving.

The major question is not how STRIPS or SOAR works internally, which is equal to plan in a hierarchical fashion, the bottleneck is the grammar which describes the macro-actions. Using an existing STRIPS domain description for determine the lowlevel actions of the robot is an easy to solve problem. Because the solver will search in the domain file, test out some alternatives and then he will have found the correct action sequence. The more demanding challenge is to convert a game into the STRIPS domain file.

A language grammar allows to execute high level actions in a game. After running a macro-action the game will be in a new state. The transition is formalized in a symbolic game engine. Let me give an example. According to the grammar, the macro-action “5up” is available. The meaning of the command has to be formalized in sourcecode:

newposition = oldpos + (0,-5)

defines the action precisely. The action modifies the underlying game. It changes the position of the robot. Now we can ask which lowlevel actions are needed to become the same result. The transformation from high level actions into lowlevel actions can be realized with a solver.

Language understanding machines

A software which accepts natural language commands is easier to realize then it might look at the first side. All what is needed is an if-then-statement:

if input==”5up” then ...

if input==”5down” then ...

We can feed the program with a string for example “5up” and the program is doing something. From a perspective of a game programmer, such a software module is called a game engine. It specifies which actions can be send to the game. The statement after the “then” section are grounding the input word. They are formulating precisely, how the game state get changed. After a game engine was programmed it's possible to formulate a high level program written in the domain specific language:

5up

5up

5down

... is an example program. Each command is send to the game engine and is executed in a virtual machine.

A simple grammar for solving Sokoban like puzzles

In he example picture the well known game of sokoban is shown. To make things easier no obstacles are there but the robot has to push the boxes to the goal position at the lower right of the map. The lowlevel actions available for the robot are: left, right, up, down.

The first idea to solve the problem with a RRT graph failed. It's not possible to generate the entire action sequence, because the number of required actions are to high. The robot has to reach first box0, then he has to push the box to the goal, then he has to go to the next box and so on.

The next better approach after using RRT graph search is implementing a robot control language and use a symbolic solver for figuring out the low level actions. This approach works much better. The implemented grammar has the following elements:

"reset","movetobox","pushboxtowaypoint","movesmall", "pushsmall"

All these words are equal to powerful macroactions. It modifies the position of the player in absolute values. For example the action “movesmall” is able to teleport the robot 2 fields with a single command. Let us observe how a potential high level plan will look like:

1. movetobox 0 # a parameter is given to the command to specifiy the box0

2. pushboxtowaypoint 0

3. movetobox 1

4. pushboxtowaypoint 1

If the high level planner is made more detailed the improved plan will look the following:

1. movetobox 0

1a movesmall

1b movesmall

2. pushboxtowaypoint 0

2a pushsmall

2b pushsmall

2c pushsmall

3. movetobox 1

3a movesmall

3b movesmall

4. pushboxtowaypoint 1

4a pushsmall

4b pushsmall

Even this detailed plan is not expanded fully. A low level planner has to convert all the movesmall and pushsmall actions into lowlevel primitives. The resulting plan will contains only “left,right,up,down” actions. That's the basic idea of a hierarchical planner and the idea is powerful enough to determine the actions of the robot. The proposed system contains of three elements:

1. the Sokoban game itself

2. the grammar which includes lowlevel and highlevel actions

3. the planner which generates the plan and converts it into lowlevel action sequence

Let us dive into potential pitfalls. There are two possible pathways in generating the macro actions. I have choosen the manual way. That means, in the program there is a subroutine for “movesmall” and for “pushsmall”. In the subroutine the angle to the goal and the new position is determined with normal computer code. I'm unsure if it's possible to generate the macro actions without human intervention. In the literature the concept is called “Rule learning”, but I'm in doubt if this works for Sokoban. That means, my program doesn't have learning capabilities but it's static. All the macro actions are defined before the runtime.

Solving a symbolic problem

Let us go a step backward and describe what the planner has to do. Instead of trying out a sequence of lowlevel actions, the newly established environment contains of macro actions:

"reset","movetobox","pushboxtowaypoint","movesmall", "pushsmall"

The goal state has to reached with using a sequence of these actions. Because the macro actions are more powerful than the regular actions the sequence will become much shorter. The proposed plan can be described with a few commands. Before the planner can generate the actions autonomously it's important to ground the macro actions. Grounding means, that the actions are not only given in a Python list, but that the game engine accepts the command as a valid command and so something in return. That means, if the command movetobox is send to the game engine, the game engine will modify the robot's position and the result is displayed on the screen. This is called grounded actions, because the resulting game engine state can be measured by the planner.

Let me give an example. We are using a simple randomized planner which is sending randomly macro-actions to the game engine. After each trial we are testing what the position of the robot and the boxes is. If the boxes are at the goal position the plan has been found. Before we can measure the robot's position the action need to have an influence on the game engine. The counter example would be, that we are sending the high level action “movesmall” to he game engine but nothing happens. Then the action is not grounded and it's only a word in the program without having a meaning.

Short description of symbolic AI in the 1960s

The General Problem solver and the Logic Theorist program was both realized in the late 1950s on mainframe computers. It was an early attempt in realizing a production systems. Later examples from the same subject were OPS5 (late 1970s) and SOAR (early 1980). A production system has much in common with STRIPS and PDDL planning tools. The idea is to formalize a problem into abstract actions which are planned by a solver. Sometimes, the planning process is supported by a goal stack and (Strips) and a working memory which is common for cognitive architectures for agent simulation.

The reason why the General Problem Solver and modern PDDL planners doesn't match the requirements into Artificial Intelligence is, because the planner/solver itself is useless, if the domain model is not available. All the capabilities which are provided by the STRIPS planner which includes the recursive goal stack will not solve a problem, if the strips input file is missing.

A production system is similar to an expert shell only the environment which is able to find the actions for a given STRIPS file, but it can't answer the question how to transform a domain into the strips file. Before it's possible to start the SOAR program, execute the PDDL solver or taking advantage of the OPS5 system an input file has to provided which contains of the action names, the variable names and the effects written down in a programming language. Even a modern cognitive architecture has the ability to learn, it's not so powerful that it can learn the domain description itself.

Let us analyze the simplest possible cognitive architecture which is a strips planner. Strips takes a domain description as input, creates a graph, and then it will search for a path through the symbolic graph. Programming a strips solver from scratch isn't very hard, because the algorithm for backtracking a graph is well known and the sourcecode is available at Rosettacode. The more demanding problem is how to convert a problem for example a game of Lemmings into a STRIPS domain description. This transformation is called grounding and STRIPS nor General Problem solver has the answer to the problem.

STRIPS domain file

Every STRIPS like planner needs as input file a domain description. This is equal to a domain specific language (Formalized as a grammar) plus some routines written in that language. In the well known robot gripper domain (blocksworld) the grammar is equal to a robot programming language. It contains of commands like opengripper, closegripper and movedown. The STRIPS planner is able to transform the language specification into a program. It's some kind of automatic programming aka genetic programming. The program can be executed on the robot which brings the system into a goal state.

“Learning from demonstration” allows acquire a robot language from human interaction.[1]

[1] Mohan, Shiwali, et al. "Learning grounded language through situated interactive instruction." 2012 AAAI Fall Symposium Series. 2012.