Improved Heatmap in Python

In addition to a previous posting an improved version of the heatmap sourcecode is given. The sourcecode was formatted in the HTML mode with the "pre" tag.

import pygame

class Game:
  def __init__(self):
    self.pygamewindow = pygame.display.set_mode((700, 350), pygame.HWSURFACE | pygame.DOUBLEBUF)    
    self.fps=5 # 20 
    for i in range(1000000):
      self.pygamewindow.fill(pygame.Color(255,255,255))   
      self.paintmap()
      pygame.display.update()
      pygame.time.wait(int(1000/self.fps))
  def heatmapcolor(self,value):
    # value 0..1, returns colorcode (r,g,b) 
    # init gradient
    gradient=[]  # (value,r,g,b)
    gradient.append((0.0,  0,0,1)) # blue
    gradient.append((0.25, 0,1,1)) # cyan
    gradient.append((0.5,  0,1,0)) # green
    gradient.append((0.75, 1,1,0)) # yellow
    gradient.append((1.0,  1,0,0)) # red
    gradient.append((1.0,  1,0,0)) # red extra
    # search base color
    for baseid in range(len(gradient)):
      diff=value-gradient[baseid][0]
      if diff>=0 and diff<0.25: 
        break
    # relative color
    relvalue=(value-gradient[baseid][0])*1/0.25
    color=[] # (r,g,b)
    for i in range(1,4):
      temp=(gradient[baseid+1][i]-gradient[baseid][i])*relvalue # get difference
      temp=(temp+gradient[baseid][i])*255 # convert to 255 scale
      temp=int(round(temp)) # round
      color.append(temp)
    return color  
  def paintmap(self):
    width=pygame.display.get_surface().get_width()
    grid_width,grid_height=20,300
    maxstep=int(round(width/grid_width))
    for i in range(maxstep):
      value=i/maxstep # 0..1
      temp=self.heatmapcolor(value)
      col=pygame.Color(temp[0],temp[1],temp[2])
      x=0+i*grid_width
      pygame.draw.rect(self.pygamewindow, col, (x,0,grid_width,grid_height))

mygame=Game()

The advantage is, that the resolution can be adjusted easily to reduce the gridwidth.

The symbol grounding problem is overestimated

A normal expert system works great if the facts are defined precisely. An example for a fact is, that the robot is near to the box, another fact is, that the box has an angle of 0 degree. The expert system takes these facts as input and executes operators on the facts. Not all rules can be applied but only a subset. The concept is known in game AI as a GOAP planner, because the solver is able to bring the system into a goal state.

According to some computer scientists, something is missing in that loop. They ask who the expert system gets all his facts. In the literature this question is called the symbol grounding problem because it's about a connection between the environment and the facts in the expert system. But is this problem really so important? In most cases the transition from perception to the fact database is not very complicated. The sensor is able to measure an information and the data is converted into a fact. If the robot is near to the box or not can be determined by a single line of code. Calling this transition a bottleneck which prevents expert systems from become a useful tool is an exaggeration. The real problem is not to convert a variable back and forth the difficulty is, to inference from the given facts. Instead of focus on the environment-to-sensor workflow the more important part of the overall architecture is the expert system itself.

Are all employees internal customers?

Quote: “It is recognized in the marketing literature that all employees of an organisation are internal customers. [...] Internal customers generate goods and services for the end customer” [1] page 2

This description is remarkable advanced, because in the common understanding of leadership the employees tries to satisfy his boss. The customer sees his boss as a customer who gives him an order. But it seems, that the marketing literature and especially the newer one has a different understanding of how management is working. The idea is to flip the social roles. That means, the boss is trying to help the employees and the employees are helping the external customers.

This is called total customer orientation and it seems, that at least in the management literature it's the quasi standard of how to organize a modern business.

[1] Conduit, Jodie, and Felix T. Mavondo. "How critical is internal customer orientation to market orientation?." Journal of business research 51.1 (2001): 11-24.

Heatmap in Python

According to the website http://www.andrewnoske.com/wiki/Code_-_heatmaps_and_color_gradients a heatmap is created by a color gradient which goes from blue to cyan then to green, over yellow to red. For realizing a function which takes as input a value between 0 .. 1 and returns as output the colorcode the inbetween values of two categories needs to be calculated. The Python function for doing so is a bit longer and takes 25 lines of code. In the referenced URL only the C++ version was given, I have reprogrammed the code.

During the creation of the sourcecode, a slider widget from TKinter was a great help. This allows the user to set a value between 0 and 1 interactively and observe what the return value of the function is.

Update: Sometthing is wrong with the embedded sourcecode. It seems, that the if statement (font) was formatted by the Blog engine a bit randomly.

import pygame

class Game:
  def __init__(self):
    self.pygamewindow = pygame.display.set_mode((500, 350), pygame.HWSURFACE | pygame.DOUBLEBUF)    
    self.fps=20 # 20 
    for i in range(1000000):
      self.pygamewindow.fill(pygame.Color(255,255,255))   
      self.paintheatmap()
      pygame.display.update()
      pygame.time.wait(int(1000/self.fps))
  def heatmapcolor(self,value):
    # # value 0..1, returns colorcode (r,g,b) 
    # init gradient
    gradient=[]  # (value,r,g,b)
    gradient.append((0.0,  0,0,1)) # blue
    gradient.append((0.25, 0,1,1)) # cyan
    gradient.append((0.5,  0,1,0)) # green
    gradient.append((0.75, 1,1,0)) # yellow
    gradient.append((1.0,  1,0,0)) # red
    gradient.append((1.0,  1,0,0)) # red extra
    # search base color
    for i in range(len(gradient)):
      diff=value-gradient[i][0]
      if diff>=0 and diff<0 .25:="" font="" nbsp="">
        break
    # relative color
    relvalue=(value-gradient[i][0])*1/0.25
    red=(gradient[i+1][1]-gradient[i][1])*relvalue
    red=(red+gradient[i][1])*255
    green=(gradient[i+1][2]-gradient[i][2])*relvalue
    green=(green+gradient[i][2])*255
    blue=(gradient[i+1][3]-gradient[i][3])*relvalue
    blue=(blue+gradient[i][3])*255
    # result
    result=(int(round(red)),int(round(green)),int(round(blue)))
    return result      
  def paintheatmap(self):
    grid_width,grid_height=12,50
    maxstep=40
    for i in range(maxstep):
      value=i/maxstep # 0..1
      temp=self.heatmapcolor(value)
      col=pygame.Color(temp[0],temp[1],temp[2])
      x=0+i*grid_width
      pygame.draw.rect(self.pygamewindow, col, (x,3,grid_width,grid_height))

mygame=Game()

Creating a Task and motion planner

A so called Task and motion planner is very complicated to realize. From the description itself, it's a mixture of a high level text adventure plus an underlying physics engine. The idea is, that a solver determines in the text adventure what the actions are to fulfill a goal, and then the motion planner converts the high level tasks into concrete motions which are executed by the robot. The problem is to implement such an architecture in sourcecode.

My project so far relies on the programming language python. The easier part was to create the simulation itself. Thanks to the libraries pygame, tkinter and box2d it was easy in doing so. The resulting robot can be controlled with the keyboard by a human operator. The more compliated parts are the text adventure and the motion planner. The first idea was, to utilize the STRIPS or the Prolog syntax which is equal to store facts and rules. In the literature the concept is explained in detail but in reality, the resulting text adventure was hard to maintain. The problem was, that the rules have access to all the facts and no modules are available.

The better idea is to realize the text adventure with object oriented programming techniques. Which means, that every item in the game like the robot, the box and the map get a separate class, and the methods in the class can only operate on the internal datastructures. This time, the sourcecode was easier to read, because it's compatible to normal programming paradigm. That means, if somebody creates a standalone text adventure he will use for sure an object oriented language, but not the STRIPS notation.

What is open right now, is to combine all the modules into a runable application. This makes it hard to predict if the idea make sense or not. Even the example problem was a minimal example, the amount of needed sourcecode is higher than usual. Especially the concept of running two simulations in parallel makes the code complicated. The problem is, that the normal physics engine represents the game but in the text adventure the same game is calculated but in a different way.

Is there a need to create the text adventure at all? The answer is yes, because without a text adventure the solver can't determine the next step. The precondition to search in a tree for a node is, that a forward model is available which can produce the game tree. Let us go a step back and describe what a GOAP solver is doing. The idea is to test out randomly some actions in the model. A random generator executes an action and then the result is stored in a graph. And exact here is the problem. The action can only be executed inside a text adventure.

What will happen, if no text adventure is available? Then the solver has to send random actions to the normal physics engine. The problem with Box2d, ODE and Bullet is, that there performance is low. They are providing the future state of a system but for doing so lots of cpu ressources are needed. It is not possible to plan longer sequences of around 1 minute with these engines. 1 minute is equal to 60 seconds = 1200 frames. If 100 actions are calculated, the amount of cpu compuation is enormous.

Perhaps the term “task and motion planning” provides the description itself. A task is a high level action for example “bring the box to the goal”, while a motion is a low level action e.g. “move 20 pixels forward”. The normal physics engine works on a motion level, it has to do with a near time horizon of 1-2 seconds and detail movements. In contrast, a task planner has to provide the long term strategy which includes the selection of waypoints and define subgoals. On a task level a pick&place operation can be described with natural language:

1. moveto object

2. grasp object

3. moveto goal

4. ungrasp object

This short plan isn't providing any details. It's not possible to execute the plan directly on a physics engine. A physics engine needs a concrete command for example “left(-20)”. And that is the reason why task and motion planning are handled as different layers. There is a need to plan the actions with different hierarchies.

Practical example

For controlling a puck collecting robot the first thing to do is to create the motion planner. It is working on a low level and affects the underlying physics engine. The motion planner contains of two subfunctions which are “reach angle” and “forward”. The first one controls the direction of the robot, while the second one effects the forward motion. The details of implementing the motion primitives is up to the programmer, in most cases a simple difference calculation is sufficient. After the sourcecode is written it's possible to send to the motion planner the following plan:

1. reachangle(45)

2. forward((100,200))

The interaction with the robot works with these motion primitives. They are providing an interface to control the robot movements. It's not possible to control complicated tasks with these primitives, but only short horizons issues. For longer plans a task planner is required. The task planner is equal to a text adventure and provides also some primitives. The task primitives are:

1. moveto(goal)

2. graspbox

3. ungraspbox

The task planner is not allowed to send commands directly to the robot but the taskplanner sends commands to the motion planner. That means a high level task like moveto() is decomposed into motion primitives like reachangle and forward.

Avoiding the task planner?

If motion primitives are able to control the robot and it's possible to write a longer program which contains a sequence of motion primitives, why is there a need for a high level task planner? Suppose the plan for the robot is to drive to the box, grasp the object, move to the goal and place the object at the position. All the motion primitives are executed in a linear fashion and now an interruption takes place. The robot looses the box during the transit. The motion planner itself doesn't recognize the problem, only the higher instance will detect the issue.

A motion sequence should be tolerate against interruption. And the task planner has to figure out the new motion sequence.

Semi autonomous control

Unfortunately, the amount of frameworks and algorithm to implement a task and motion planner is low. Creating such a software is mostly an art but not an engineering discipline. A good starting point is to set a focus on manual control. If the robot is controlled manual, it's for 100% sure that a task is fulfilled. A planner should be understand as optional. The idea is to start with a teleoperated robot and improve the system slowly into an autonomous system. From the programmer perspective the question is how to improve the control of the robot in a way, that the workload for the human gets lower.

A typical example for this transition is to replace a keyboard control with a mouse control. A normal robot arm for example in an excavator is controlled by different sliders. With slider1 the operator controls motor1, with slider2 motor2 and so on. The first step is to write a software which takes a mouse as input and calculates the servo signal as the result. In the literature the concept is colloquial described as inverse kinematics and it helps a lot to reduce the workload. An inverse kinematics doesn'T mean that the robot works autonomously, it means, that the human operator points with the mouse to a target and the robot arm reaches the point.

What is the technology behind expert systems?

The literature about expert systems and general problem solving is large and many ideas are mentioned, for example the Lisp programming language, cognitive architectures and rule based systems. The problem is to identify subjects which are important to realize Artificial Intelligence and some which are not but can be described as a fashion of the 1980s and subjective preferences of researchers.

The main problem with the early AI research in the 1960s was, that no modern desktop computers were available. If the in 1960 and early 1970s somebody was interested to run a software he wasn't able to do so. Operating systems like Windows 95 were not invented, and interpreted languages like Python wasn't there. Most of the early AI literature is a mixture of AI principle and computer science in general. A typical example is the LISP language which was used for anything and nothing. Lisp was an operating system, self-modifying code, a programming language and an interactive environment. The first thing to do is to sort the own tools. So we should ask direct: what is the basic principle of an expert system?

Basically spoken it's not an algorithm but a text adventure which is simulating something. The programmer has to construct a game engine, which is equal to a rule engine, and then he can send commands to the text adventure. Either manual or with an automatic solver. This brings the game into a goal state. The understanding of an expert system as a textadventure is the core idea of symbolic AI. It helps to simplify a problem into smaller tasks. The advantage is, that any textadventure can be solved by a solver.

The next question is how to convert a given domain (for example a robot arm) into a text adventure. The answer has to do with human machine interaction. A human operator is able to control the robot and while he is doing so, it is possible to observe his actions in a psychological experiment. These studies are going beyond computer science, because a psychological experiment has a lot to do with humans but only little with turing-machines. From a computer science perspective, such experiments are equal to generate a dataset. That is a database with the recorded game log of the experiment. And it's up to the AI engineer to convert the game log into an expert system which is equal to a text adventure.

Unfortunately, the rules of a human machine interaction task are hidden in the dataset. They are not available as machine readable instructions but are based on experience, natural language instructions and general problem solving capabilities. Creating an expert system doesn't mean to invent an AI algorithm, but the algorithm is available as default. The more important goal is to invent a space in which actions can be executed. From a technical point of view, the attempt in doing so is called “model induction”, sometimes it is called a forward model because it describes how the system is working. Using a solver to bring an existing forward model into a goal state is not very hard. The algorithm are known, and in most cases a simple graph search technique is fast enough. The more demanding task is, that for most problems the forward model is not known.

The process of converting a human demonstration into a text adventure is called grounding. It's the core problem in AI because it allows an improved human machine communication. A grounded problem can be understood by both sides: for the computer the text adventure contains of symbols which can be stored and manipulated in the memory and for the human the game represents the reality.

On the first look, the most important question for expert systems programmer is how the expert system is working internally. This question has a surprisingly simple answer. The internal working is not important. It is working with a graph search algorithm or a similar algorithm which brings the current state into the goal state. In a primitive expert system the search algorithm contains of only 20 lines of code, who is testing out the entire state space and programming such an algorithm is not very complicated. The more demanding task is the question how an expert system perceives the environment. That means, the human operator is doing with the robot a task and the expert system monitors the actions. How exactly identifies the expert system a subaction, and what is shown on the screen as the detected event? A well programmed expert system is at foremost an activity recognition engine. It translates human activities into machine readable description.

Frameworks are not available

Even if some techniques are known to construct expert systems for example the CLIPS shell, the LISP programming language, the PDDL domain definition standard and the means-end analysis for searching in the state space none of these techniques are needed in a robotics project. They can be called less important details but are not are here to stay. If Lisp, PDDL and all the other techniques are useless which kind of framework, programming language or algorithm can be utilized for developing an expert system? Unfortunately, there is no such think like a framework, but a software engineering workflow which consists of three simple steps:

1. create a simulation which is controlled by a human operator

2. create a plan recognition system

3. create a fully autonomous solver

The first step is easy to solve because it's equal to normal game programming. The idea is use an existing programming language like C#, and use an existing game engine like Unity3d to create a standard game which takes the input of a human operator. The steps 2 and 3. are more complicated to realize. In most cases they have to do with observing humans who are doing a task and try to formlize the steps in a text adventure. This text adventure is used to parse a demonstration but is the baseline for the automatic solver as well. Instead of recommending a concrete programming language or an algorithm the better idea is to understand the steps 2 and 3 as part of a software engineering process. They are handled with version control systems like git and get visualized with the UML notation.

Pros and cons of the Shakey the robot project

A while ago a paper was published, which introduces the Shakey the robot project again and explains the advantage and disadvantages of the STRIPS planning system. On page 1 it was also explained, that Rodney Brooks wrote an anti-Shakey paper in which he explains that formalized planning is a dead end. It's important to focus first on the idea of a logical model of the environment. The Shakey robot has a preprogrammed environment model in which his own position, the allowed actions and other objects are foramlized in the situation calculus. This model allows Shakey to plan from the current situation into any future goal state.

The disadvantage of the concept and the reason why Brooks wrote a STRIPS critique is, that such a logical model is hard to program and it doesn't fit to the environment. In reality, it's not possible to reuse an existing STRIPS model. The Shakey description can't be utilized in a different robot for example a modern Lego Mindstorms system. Instead the STRIPS model has to be programmed again, which takes a large amount of time.

To understand the problem we have to go a step backward. The normal interaction between a robot and a human operator is done via teleoperation. That human can move the robot by using a joystick. If the robot should drive autonomously, he needs a logical model. The basic question is how to come from a teleoperated robot into an autonomous robot system. The answer is called plan recognition and learning from demonstration. This is the step inbetween and means, that the human interaction with the robot is tracked and converted into a model.

Plan recognition is equal to model tracking. The idea is not that Shakey should plan the next actions, but the idea is analyze if the logical model of the environment is right. The idea of STRIPS and Shakey goes into the right direction, what is missing is the ability to analyze human interaction with a teleoperated robot.

In the literature the idea of plan recognition is a new development because it's hard to explain why this technique is needed. From a practical standpoint it's equal to control a robot with a joystick and the software is able to recognize the actions. That means, the human operator let Shakey collide with an obstacle, and on the screen it is shown “collision detected”. Because the human operators knows the information in advance it seems that for such a message there is no need. Without a working plan recognition it's not possible to verify or build a logical representation of the environment. That's the reason why most STRIPS based projects have failed.´

Shakey the robot and STRIPS is working great, if the logical representation is there. The planner can take the model and plan the next steps to reach a goal. It's not very complicated to write such a planner and he will run with maximum performance. The bottleneck is there if the logical model isn't correct or no such model is available. In such a case, the robot won't make any action.

Plan recognition is equal to human-machine communication.[2] The robot and the human operator are speaking the same language. The problem is not how the Shakey software works internally, the question is, if Shakey is able to understand the teleoperator.

The plan recognition problem is a relative new develoopment which was analyzed after Shakey was built:

quote ”Schmidt, Sridharan and Goodson [1978, 1976] are the first to identify plan recognition as a problem in its own right” [3]

In contrast to robot control, plan recognition doesn't result into a working system. Instead the idea is to annotate the movements of a teleoperated robot. Somebody may argue, that it has nothing to do with Artificial Intelligence because the robot is controlled by a human operator. Additionally, the detected events and activities are grounded in natural language and psychology which is outside of computer science.

Debugging

Plan recognition can be seen as a model debugger. It is only successful, if the plan library contains of predefined actions which are able to detect events in the environment.[4] This allows for the programmer to implement and test new plan libraries, similar to writing computer code. He types in an action and used the plan recognizer to verify if the action makes sense.

Plan corpus

To simplify the process of plan recognition it's useful to build a plan corpus. That is a large plan library which contains action primitives and events for detecting and annotating raw data. It's not possible to generate a plan corpus automatically, but it's a manual task similar to create an English dictionary. A plan library is usually created by asking human participant to do a task, for example to walk on a line. Then the motion capture suite is recording all the information and they are annotated manual. On top of the recorded trajectory a parser is programmed. The overall plan library project has to provided as Open Science project in the internet which allows other researchers to participate.

Examples for corpus from the past are: HASC corpus, USC-HAD, Hugadb[5], PRAXICON and other datasets for activity recognition. Most of these projects were realized in the last 10 years.

[1] Shanahan, Murray. "Reinventing shakey." Logic-based artificial intelligence. Springer, Boston, MA, 2000. 233-253.

[2] Pollack, Martha E. "The uses of plans." Artificial Intelligence 57.1 (1992): 43-68.

[3] Mao, Wenji, and Jonathan Gratch. Decision-theoretic approach to plan recognition. ICT Technical Report ICT-TR-01-2004, 2004.

[4] Goultiaeva, Alexandra, and Yves Lespérance. "Incremental plan recognition in an agent programming framework." Working Notes of the AAAI Workshop on Plan, Activity, and Intention Recognition (PAIR). 2007.

[5] Chereshnev, Roman, and Attila Kertész-Farkas. "Hugadb: Human gait database for activity recognition from wearable inertial sensor networks." International Conference on Analysis of Images, Social Networks and Texts. Springer, Cham, 2017.

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.