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.