Frühe ferngesteuerte Automaten

 Es gibt eine Reihe von Zaubertricks und technischen Vorführungen vor Beginn des Computerzeitalters die auf das damalige Publikum erstaunlich gewirkt haben. Streng genommen waren diese Maschinen keinen Roboter, weil sie keine Microcontroller enthielten, also eine CPU. Dennoch zeigten sie ein Verhalten was roboterähnlich aussah. Hier die Zeitleiste:

1770    Schachtürke von Wolfgang von Kempelen
1849    Antonio Diavolo von Robert-Houdin
1904  Telekino von Leonardo Torres Quevedo
1939    Elektro auf der New Yorker Weltausstellung

Die Funktionsweise dieser Darbietungen basierte auf mechanischer oder elektromechanischer Fernsteuerung. Vom Schachtürken ist bekannt dass ein erfahrener Menschlicher Schachspieler in der Kiste saß, von der Trapez-Marionette Antonio Diavolo ist bekannt dass sie über Baudenzüge gesteuert wurde, die in der Halterung versteckt waren, während das Telekino Boot von Quevedo mittels Funksignale aus der Distanz gesteuert wurde.

Die Erfinder hatten folglich die Aufgabe, diese Fernsteuerung zu realisieren. Entweder über mechanische angelsehnen wie es bei vielen Zaubertricks üblich ist, oder über das Übertragen von Funksignalen was seit 1895 möglich ist.

All die aufgeführten Automaten waren nicht autonom, sondern es gab einen menschlichen Bediener der heimlich Knöpfe gedrückt hat wodurch der Automat sich bewegt hat und das Publikum zum Staunen animiert hat.

Mit Aufkommen der ersten Computer ab den 1950er schien diese Technik des ferngesteuerten Automaten in Vergessenheit geraten zu sein. Stattdessen versuchten Robotik-Ingineure ein Programm zu schreiben was auf dem Computer ausgeführt wird, und darüber den Roboter zu steuern. Dies wurde speziell in der universitären Robotik als Goldstandard definiert. Gleichzeitig wurden ferngesteuerte Roboter oder mechanisch ferngesteuerte Automaten als unwissenschaftliche Zauberillusion belächelt.

Die Abkehr von ferngesteuerten Bühnentricks hinzu programmierten Robotern führte in eine Sackgasse welche zuerst nicht wahrgenommen wurde. Die Sackgassen entsteht dadurch dass ein computerprogram niemals so leistungsfähig sein kann wie ein menschlicher Bediener. Gleichzeitig sind ferngesteuerte Automaten einfacher zu konstruieren. Technisch gesehen sind es lediglich empfangseinrichtungen welche Befehle aus der Ferne in Bewegung umsetzen.

BNF Grammar for speaker to hearer interaction for a warehouse robot

A bnf grammar is a good starting point to specify a language game. The grammar provides possible action verbs, nouns and adjectives. Possible requests send to the robot are formulated in the syntax of the grammar.

For the example of a warehouse robot, possible utterances are:

Visual Question Answering (VQA)

Interaction 1: Count Query
    Speaker (Human): "How many boxs are on Conveyor 1?"
    Hearer (Robot): "Answer: 4."

Interaction 2: Attribute Query
    Speaker (Human): "What color is the parcel at Rack A Level 2?"
    Hearer (Robot): "Answer: blue."

Interaction 3: Location Query
    Speaker (Human): "Where is the container?"
    Hearer (Robot): "Answer: Pallet 3."

Interaction 4: Presence Query
    Speaker (Human): "Is there a item inside Bin 5?"
    Hearer (Robot): "Answer: Yes."

Instruction Following (IF)

Interaction 5: Pick & Place Action
    Speaker (Human): "Pick up the red parcel from Conveyor 2"
    Hearer (Robot): "Executing: Picked up red parcel."

Interaction 6: Movement Action
    Speaker (Human): "Move the damaged box to Bin 8"
    Hearer (Robot): "Task completed: Moved damaged box."

Interaction 7: Inspection Action
    Speaker (Human): "Inspect the barcode at Rack B Level 1"
    Hearer (Robot): "Task completed: Inspected barcode."

Interaction 8: Placement Action with Error
    Speaker (Human): "Place the blue container to Pallet 9"
    Hearer (Robot): "Error: Path obstructed."

These speech acts were not created by a large language model, but are possible vectors from a BNF Grammar, given next. A bnf grammar is a vocabulary list plus grammar rule system and defines what each side can say.

BNF Grammar    

<interaction>         ::= <speaker_turn> " -> " <hearer_turn>

<speaker_turn>        ::= <command> | <query>
<hearer_turn>         ::= <acknowledgment> | <answer> | <error_response>

;; Command & Query Structure
<command>             ::= <action_verb> " " <target_object> <location_clause>
<query>               ::= <vqa_question>

<vqa_question>        ::= <count_query> | <attribute_query> | <location_query> | <presence_query>

<count_query>         ::= "How many " <object_type> "s are on " <surface> "?"
<attribute_query>     ::= "What color is the " <object_type> " at " <location_spec> "?"
<location_query>      ::= "Where is the " <object_type> "?"
<presence_query>      ::= "Is there a " <object_type> " inside " <container> "?"

<action_verb>         ::= "Pick up the" | "Move the" | "Inspect the" | "Place the" | "Scan the"
<target_object>       ::= <color> " " <object_type> | <object_type>
<location_clause>     ::= " from " <location_spec> | " to " <location_spec> | ""

<location_spec>       ::= <surface> | <container> | <shelf_location>
<surface>             ::= "Conveyor " <digit> | "Pallet " <digit>
<container>           ::= "Bin " <digit> | "Crate " <alpha_code>
<shelf_location>      ::= "Rack " <alpha_code> " Level " <digit>

;; Robot Responses
<acknowledgment>      ::= "Executing: " <action_description> "." | "Task completed: " <action_description> "."
<action_description>  ::= <action_verb_past> " " <target_object>
<action_verb_past>    ::= "Picked up" | "Moved" | "Inspected" | "Placed" | "Scanned"

<answer>              ::= "Answer: " <answer_content> "."
<answer_content>      ::= <digit_string> | <color> | <location_spec> | <boolean>

<error_response>      ::= "Error: Object not found." | "Error: Path obstructed."

;; Lexical Elements
<object_type>         ::= "box" | "parcel" | "barcode" | "container" | "item"
<color>               ::= "red" | "blue" | "green" | "yellow" | "damaged"
<boolean>             ::= "Yes" | "No"
<digit_string>        ::= <digit> | <digit> <digit_string>
<digit>               ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<alpha_code>          ::= "A" | "B" | "C" | "D"

Einführung in grounded language

 Das Ziel besteht darin natürliche Sprache also Englisch oder Deutsch zu verwenden um damit Robotikaufgaben zu lösen. Konkret sind damit Aufgaben wie motion planning, greifplanung und die navigation auf Straßen gemeint. Der Ansatz zur Lösung natürliche Sprache zu verwenden klingt zunächst ungewohnt weil üblicherweise Probleme der Informatik über das schreiben von Computer code sowie über mathematische Algorithmen gelöst werden. Natürliche Sprache ist demgegenüber schwer formalisierbar und für Computer gänzlich unverständlich da Computer nur Assembly befehle abarbeiten können.

Der Umweg über den grounded language machinenlesbar wird sind Computerspiele die etwas mit Vokabellernen zu tun haben. Der erste Schritt besteht darin einige solche Vokabelspiele als Programm zu realisieren:

- Bilder zu Worten zuordnen
- Deutsche Worte in Englische Worte übersetzen
- auf ein Objekt zeigen
- eine kurze Anweisung mit einem Roboter ausführen

All diese Spiele sind Wortspiele bzw. vokabelspiele. Es gibt diese Beispiele bereits als fertige Software man kann sie aber auch from scratch neu programmieren was empfohlen wird, weil sich dann leichter Erweiterungen hinzufügen lassen. Anders bei einem klassischen Vokabellernspiel geht es weniger darum, dass der menschliche Anwender die Vokabeln auswendig lernt sondern Ziel ist dass ein Computer sowohl die Fragen formuliert, als auch Antworten gibt. Die dabei verwendeten Algorithmen und Datenstrukturen sind im Bereich grounded language angesidelt. z.b. kann ein Bild zu Wort spiel mit Hilfe einer Lookup Tabelle durch einen Computer gelöst werden, während das pointing game über ein python dictionary lösbar ist.

Der Fokus auf Sprachspiele ist deshalb erforderlich weil sich in einem Spiel ein Thema maschinell formalisieren lässt. Es geht darum in einem regelsystem eine Entscheidung zu treffen, also z.B. für das Wort "Apfel" das objekt in einem Bild zu finden was wie ein Apfel aussieht.

Aus Sicht der Informatik sind Vokabellernspiele die Antwort auf die Zustandsraumexplosion. Speziell Robotikaufgaben besitzen einen sehr großen Zustandsraum der von gängigen Suchalgorithmen nicht in Echtzeit untersucht werden kann. Indem eine Aufgabe wie greifpalnung als Sprachspiel gedeutet wird, verkleinert sich der zustandsraum. Sprache ist demzufolge eine Universalheuristik mit der frühere unlösbare KI Probleme plötzlich lösbar werden.

Interactive turing machines

Classical turing machines are based on algorithms. The algorithm is stored in program and gets executed by the CPU. This model is powerful because it describes all sort of software from games to databases and word processing software.

There were many attempts available mostly driven by theoretical curiosity to extend classical Turing paradigm into Super turing machines (by HT Siegelmann), oracle turing machines and interactive turing machines [1]. Each author defines the principle a bit different so here is an introduction into the subject.

Instead of running an algorithm, there is a speaker to hearer language game. That means, a robot communicates with the outside world. The robot is the hearer and the outside world is the speaker. The robot behaviors doesn't depends on its internal algorithm but the robot gets teleoperated. The importance of the robot's internal software is reduced to a minimum, technically spoken the robot is only the receiver in a remote control setup and the decision are made by the speaker.

Such sort of interactive Turing machine is more powerful than a normal turing machine because it allows to solve tasks from artificial intelligence like navigating in a room, grasping objects and so on. Instead of designing better algorithms, e.g. for motion planning, the focus in on the communication interface between the speaker and the hearer. This interface is described by a dialogue grammar, similar to a protocol grammar. The grammar defines which sentences are valid.

[1] Wegner, Peter. "Why interaction is more powerful than algorithms." Communications of the ACM 40.5 (1997): 80-91.

Event recogntion grammar for maze robot

 _

BNF grammars are known for programming language specification but are also useful for language games between speaker and hearer. A pointing game or an instruction following game can be realized with such a grammar. Reversing a pointing game results into an action recognition game in which a human controls a robot with arrow keys, and the grammar recognizes the demonstrated actions. Such an action recognition game was implemented in python as a simple maze game. The robot can move around and pick&place objects. 

The game doesn't need a large language model and not a vision language action model realized as a neural network, but its a symbolic approach based on a grammar.[1][2]

[1] Dantam, Neil, Irfan Essa, and Mike Stilman. "Linguistic transfer of human assembly tasks to robots." 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2012.
[2] Wegner, Peter, and Dina Goldin. "Computation beyond Turing machines." Communications of the ACM 46.4 (2003): 100-102.
 

import re
import pygame


# -------------------- Configuration --------------------

COLS, ROWS = 20, 14
CELL = 36
GRID_W, GRID_H = COLS * CELL, ROWS * CELL
LOG_H = 180
WIDTH, HEIGHT = GRID_W, GRID_H + LOG_H

# '#' is a wall; '.' is a walkable cell.
MAZE = [
    "####################",
    "#....#.............#",
    "#....#..####..###..#",
    "#.......#.....#....#",
    "###.##..#..##.#.##..#",
    "#...##.....##......#",
    "#.######.####.###..#",
    "#........#.........#",
    "#.###.####.###.##..#",
    "#.....#......#.....#",
    "###.#.#.####.#.###..#",
    "#...#..........#...#",
    "#........#.........#",
    "####################",
]

# Named locations are recognized in the event log.
LOCATIONS = {
    "start": (1, 1),
    "junction": (7, 3),
    "workshop": (15, 5),
    "storage": (4, 9),
    "exit": (18, 12),
}

# Objects can be picked up and placed with G.
OBJECTS = {
    "red_key": (3, 3),
    "blue_box": (16, 9),
    "coin": (9, 11),
}

# Robot begins at the named "start" location.
robot = list(LOCATIONS["start"])
carried_object = None
event_log = ["Arrow keys: move    G: pick up / place"]

# Draw colors
WHITE = (255, 255, 255)
BLACK = (25, 25, 25)
WALL_COLOR = (70, 75, 85)
GRID_COLOR = (205, 205, 205)
ROBOT_COLOR = (30, 105, 220)
LOCATION_COLOR = (30, 135, 65)
OBJECT_COLORS = {
    "red_key": (205, 45, 45),
    "blue_box": (45, 80, 205),
    "coin": (190, 145, 0),
}


# -------------------- Event grammar --------------------

# Events emitted by the controls:
#
# <event>       ::= <move-event> | <grasp-event> | <ungrasp-event>
# <move-event>  ::= "movto" <location>
# <grasp-event> ::= "grasp" <object>
# <ungrasp-event> ::= "ungrasp" <object>
#
# <location> includes the named locations above and all walkable maze cells,
# represented as cell_X_Y. <object> includes the names in OBJECTS.
#
# The parser below checks both the event's form and its vocabulary.

def location_names():
    names = set(LOCATIONS)
    for y in range(ROWS):
        for x in range(COLS):
            if MAZE[y][x] != "#":
                names.add(f"cell_{x}_{y}")
    return names


LOCATION_NAMES = location_names()
OBJECT_NAMES = set(OBJECTS)

EVENT_PATTERNS = [
    ("movto", re.compile(r"^movto\s+([a-z][a-z0-9_]*)$")),
    ("grasp", re.compile(r"^grasp\s+([a-z][a-z0-9_]*)$")),
    ("ungrasp", re.compile(r"^ungrasp\s+([a-z][a-z0-9_]*)$")),
]


def parse_event(text):
    """Return (verb, argument) if a generated event matches the grammar."""
    for verb, pattern in EVENT_PATTERNS:
        match = pattern.fullmatch(text)
        if not match:
            continue

        argument = match.group(1)
        valid_names = LOCATION_NAMES if verb == "movto" else OBJECT_NAMES
        if argument in valid_names:
            return verb, argument

    return None


def log_recognized_event(text):
    """Only add events that are accepted by the grammar."""
    if parse_event(text) is not None:
        event_log.append(f"Recognized: {text}")
        del event_log[:-7]


def location_at(x, y):
    """Prefer a named location; otherwise use the cell's generated name."""
    for name, position in LOCATIONS.items():
        if position == (x, y):
            return name
    return f"cell_{x}_{y}"


# -------------------- Robot actions --------------------

def is_walkable(x, y):
    return (
        0 <= x < COLS
        and 0 <= y < ROWS
        and MAZE[y][x] != "#"
    )


def move_robot(dx, dy):
    x, y = robot
    nx, ny = x + dx, y + dy

    if not is_walkable(nx, ny):
        return

    robot[:] = [nx, ny]
    log_recognized_event(f"movto {location_at(nx, ny)}")


def toggle_grasp():
    global carried_object

    current_cell = tuple(robot)

    if carried_object is not None:
        # Place the held object on the robot's current cell.
        if current_cell in OBJECTS.values():
            event_log.append("Cannot place: this cell already has an object.")
            del event_log[:-7]
            return

        object_name = carried_object
        OBJECTS[object_name] = current_cell
        carried_object = None
        log_recognized_event(f"ungrasp {object_name}")
        return

    # Pick up an object on the robot's current cell.
    for object_name, position in OBJECTS.items():
        if position == current_cell:
            carried_object = object_name
            del OBJECTS[object_name]
            log_recognized_event(f"grasp {object_name}")
            return

    event_log.append("No object here to pick up.")
    del event_log[:-7]


# -------------------- Pygame setup and drawing --------------------

pygame.init()
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption("Robot Maze — BNF Event Log")
clock = pygame.time.Clock()

font = pygame.font.Font(None, 24)
small_font = pygame.font.Font(None, 19)
robot_font = pygame.font.Font(None, 28)


def draw():
    screen.fill(WHITE)

    # Maze
    for y in range(ROWS):
        for x in range(COLS):
            rect = pygame.Rect(x * CELL, y * CELL, CELL, CELL)
            if MAZE[y][x] == "#":
                pygame.draw.rect(screen, WALL_COLOR, rect)
            pygame.draw.rect(screen, GRID_COLOR, rect, 1)

    # Named locations
    for name, (x, y) in LOCATIONS.items():
        label = small_font.render(name, True, LOCATION_COLOR)
        screen.blit(label, (x * CELL + 3, y * CELL + 2))

    # Objects
    for name, (x, y) in OBJECTS.items():
        cx = x * CELL + CELL // 2
        cy = y * CELL + CELL // 2 + 4
        pygame.draw.circle(screen, OBJECT_COLORS[name], (cx, cy), 10)
        label = small_font.render(name, True, BLACK)
        screen.blit(label, (x * CELL + 2, y * CELL + CELL - 17))

    # Robot, displayed as R
    rx, ry = robot
    robot_label = robot_font.render("R", True, ROBOT_COLOR)
    robot_rect = robot_label.get_rect(
        center=(rx * CELL + CELL // 2, ry * CELL + CELL // 2)
    )
    screen.blit(robot_label, robot_rect)

    # White event log panel
    log_top = GRID_H
    pygame.draw.rect(screen, WHITE, (0, log_top, WIDTH, LOG_H))
    pygame.draw.line(screen, BLACK, (0, log_top), (WIDTH, log_top), 2)

    title = font.render("Recognized events", True, BLACK)
    screen.blit(title, (10, log_top + 8))

    if carried_object:
        held_text = small_font.render(f"Holding: {carried_object}", True, BLACK)
        screen.blit(held_text, (WIDTH - 150, log_top + 11))

    visible_events = event_log[-6:]
    for i, message in enumerate(visible_events):
        text = small_font.render(message, True, BLACK)
        screen.blit(text, (10, log_top + 38 + i * 21))

    pygame.display.flip()


# -------------------- Main loop --------------------

running = True

while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

        elif event.type == pygame.KEYDOWN:
            if event.key == pygame.K_ESCAPE:
                running = False
            elif event.key == pygame.K_UP:
                move_robot(0, -1)
            elif event.key == pygame.K_DOWN:
                move_robot(0, 1)
            elif event.key == pygame.K_LEFT:
                move_robot(-1, 0)
            elif event.key == pygame.K_RIGHT:
                move_robot(1, 0)
            elif event.key == pygame.K_g:
                toggle_grasp()

    draw()
    clock.tick(30)

pygame.quit()
 

BNF grammar for instruction following of a kitchen robot

The communication between speaker and hearer can be formalized with a dialogue grammar which contains of objects and actions. The grammar stores a language in a compact format. Possible sentences are:

1. Put the clean plate on the table.
2. Place the large bowl beside the sink.
3. Move the blue cup to the counter.
4. Cut the small red tomato.
5. Wash the dirty pan.
6. Open the cabinet.
7. Take the bottle from the refrigerator.
8. Put the whole apple into the bowl.
9. Clean the empty sink.
10. Please place the warm bread on the table.
11. ----
12. Peel the small yellow potato.
13. Place the clean glass on the counter.
14. Move the large pan to the stove.
15. Put the red pepper into the bowl.
16. Wash the dirty spoon in the sink.
17. Take the cold bottle from the refrigerator.
18. Chop the whole onion on the worktop.
19. Open the white cabinet.
20. Fill the empty cup with water.
21. Please serve the warm bread on the table.
22. ----
23. Slice the green tomato.
24. Put the round plate onto the table.
25. Clean the large sink.
26. Bring the blue cup to the counter.
27. Place the sharp knife beside the cutting board.
28. Mix the ingredients in the bowl.
29. Close the open cabinet.
30. Empty the full container into the pan.
31. Dry the clean glass near the sink.
32. Heat the cold soup on the stove.

All these sentences doesn't require the full English vocabulary and the standard grammar for English but the sentences are formulated as a mini language specified in the BNF grammar. Such a mini language can be implemented easier as a parser for robot.

<instruction> ::= <command>
                 | <sequence>
                 | <conditional-command>

<command> ::= <imperative>
            | <polite-imperative>

<polite-imperative> ::= "please" <imperative>

<imperative> ::= <transitive-command>
                | <intransitive-command>
                | <movement-command>
                | <placement-command>
                | <cleaning-command>

<transitive-command> ::= <transitive-verb> <object-phrase>

<intransitive-command> ::= <intransitive-verb>
                          | <intransitive-verb> <location-phrase>

<movement-command> ::= <movement-verb> <location-phrase>
                     | <movement-verb> <object-phrase> <location-phrase>

<placement-command> ::= <placement-verb> <object-phrase>
                      | <placement-verb> <object-phrase> <location-phrase>

<cleaning-command> ::= <cleaning-verb> <object-phrase>
                     | <cleaning-verb> <location-phrase>

<sequence> ::= <command> "and then" <command>
             | <command> "," <command>
             | <command> "then" <command>

<conditional-command> ::= "if" <condition> "then" <command>

<condition> ::= <object-existence>
              | <state-condition>

<object-existence> ::= "there is" <object-phrase>
                      | "there are" <object-phrase>

<state-condition> ::= <object-phrase> <state-adjective>
                    | <location-phrase> <state-adjective>


<object-phrase> ::= <determiner> <adjective-sequence> <object-noun>
                   | <determiner> <object-noun>
                   | <possessive> <adjective-sequence> <object-noun>
                   | <possessive> <object-noun>

<location-phrase> ::= <preposition> <determiner> <adjective-sequence> <location-noun>
                    | <preposition> <determiner> <location-noun>
                    | <preposition> <location-noun>

<adjective-sequence> ::= <adjective>
                       | <adjective> <adjective-sequence>


<transitive-verb> ::= "wash"
                    | "cut"
                    | "chop"
                    | "slice"
                    | "peel"
                    | "mix"
                    | "stir"
                    | "pour"
                    | "fill"
                    | "empty"
                    | "open"
                    | "close"
                    | "pick up"
                    | "put down"
                    | "take"
                    | "bring"
                    | "place"
                    | "move"
                    | "put"
                    | "heat"
                    | "cool"
                    | "serve"

<intransitive-verb> ::= "wait"
                      | "stop"
                      | "start"
                      | "continue"
                      | "turn"
                      | "pause"

<movement-verb> ::= "go to"
                  | "move to"
                  | "take"
                  | "bring"
                  | "carry"

<placement-verb> ::= "place"
                   | "put"
                   | "set"
                   | "leave"

<cleaning-verb> ::= "clean"
                   | "wash"
                   | "dry"
                   | "wipe"


<object-noun> ::= "apple"
                 | "banana"
                 | "tomato"
                 | "potato"
                 | "onion"
                 | "carrot"
                 | "pepper"
                 | "bread"
                 | "cheese"
                 | "egg"
                 | "plate"
                 | "bowl"
                 | "cup"
                 | "glass"
                 | "pan"
                 | "pot"
                 | "knife"
                 | "spoon"
                 | "fork"
                 | "bottle"
                 | "container"
                 | "ingredient"
                 | "food"

<location-noun> ::= "kitchen"
                  | "counter"
                  | "table"
                  | "sink"
                  | "stove"
                  | "oven"
                  | "refrigerator"
                  | "drawer"
                  | "cabinet"
                  | "shelf"
                  | "dishwasher"
                  | "cupboard"
                  | "floor"
                  | "worktop"

<adjective> ::= <color-adjective>
              | <size-adjective>
              | <state-adjective>
              | <shape-adjective>
              | <temperature-adjective>
              | <quantity-adjective>

<color-adjective> ::= "red"
                    | "green"
                    | "yellow"
                    | "blue"
                    | "white"
                    | "black"

<size-adjective> ::= "small"
                    | "large"
                    | "big"
                    | "tiny"
                    | "deep"
                    | "shallow"

<state-adjective> ::= "clean"
                    | "dirty"
                    | "empty"
                    | "full"
                    | "open"
                    | "closed"
                    | "hot"
                    | "cold"
                    | "ready"
                    | "broken"

<shape-adjective> ::= "round"
                    | "square"
                    | "flat"
                    | "sharp"

<temperature-adjective> ::= "warm"
                          | "cool"
                          | "hot"
                          | "cold"

<quantity-adjective> ::= "single"
                       | "extra"
                       | "remaining"
                       | "whole"
                       | "half"

<determiner> ::= "the"
               | "a"
               | "an"
               | "this"
               | "that"
               | "these"
               | "those"

<possessive> ::= "my"
               | "your"
               | "the robot's"

<preposition> ::= "to"
                | "from"
                | "on"
                | "in"
                | "into"
                | "onto"
                | "under"
                | "beside"
                | "near"
                | "behind"
                | "inside"
                | "out of" 

NPC Quest generator

 Grounded language can be demonstrated with a speaker to hearer interaction. Such a language game seperates knowledge from each other, that means, the speaker has a different knowledge than the hearer and during the game the mismatch or match gets visible.

The verbal utterances of a speaker can be implemented as NPC Quest generator. This is a random generator who produces quests which have to be fulfilled by the hearer. A possible grammar for a warehouse robot would be:
- action: lookat, moveto, grasp
- noun: greenbox, redbox, roomA, roomB

The NPC quest generator takes this grammar as input and generates possible questions like:
1. lookat greenbox
2. moveto roomA
3. moveto redbox
4. grasp redbox

If the hearer wasn't implemented the robot won't fulfill the quests. The game generates only endless amount of tasks but the robot won't do something.

A NPC quest generator produces high level goals based on a vocabulary. These gals can be used to play a language game which can be "pointing game" or "instruction following". After implementing the hearer in software too, the lahguage game is working autonoamously, that means one side generates the tasks while the other fulfills them.

Creating chatty robots

 

The Micromouse challenge is a well known robot competition which is mostly a hardware building plus programming challenge. The rules of the challenge can be modified so that the ability of a robot is determined to generate grounded language. In the screenshot, the robot has a text widget at the bottom for showing the text.

The human user controls the robot and at the same time the textual output of the robot gets updated. This textual output allows a rule based AI to control the robot automatically which wasn't implemented yet. The only difference to the normal micromouse challenge is, that in the example the mentioned text widget is visible.

The text gets produced with a dictionary of words. Possible words like [move, goal, blocked] are describing objects and events of the game. The program detects situations and uses the words to generate the output. Because there is a mapping between the game state and the textual output its called grounded language.

import math, sys, pygame

# 1. SETUP & CONFIGURATION
WIN_W, WIN_H, MAZE_H = 800, 700, 580
WHITE, BLACK, GREEN, BLUE, GRAY = (255, 255, 255), (0, 0, 0), (40, 180, 40), (40, 100, 220), (200, 200, 200)

# Grounded language vocabulary for rule-based AI parsing
DICT = {
    "verbs": ["detected", "reached", "turn", "move"],
    "nouns": ["wall", "path", "goal", "junction", "distance"],
    "adj": ["ahead", "left", "right", "clear", "blocked", "near"]
}

# Solvable Maze Walls [x, y, w, h] & Goal
WALLS = [
    pygame.Rect(0, 0, 800, 10), pygame.Rect(0, 0, 10, 580),
    pygame.Rect(790, 0, 10, 580), pygame.Rect(0, 570, 800, 10),
    pygame.Rect(150, 0, 10, 420), pygame.Rect(300, 160, 10, 420),
    pygame.Rect(450, 0, 10, 420), pygame.Rect(600, 160, 10, 420),
    pygame.Rect(150, 250, 80, 10), pygame.Rect(450, 350, 80, 10)
]
GOAL = pygame.Rect(680, 480, 80, 80)

# 2. ROBOT CLASS
class Micromouse:
    def __init__(self, x, y):
        self.x, self.y, self.angle, self.radius, self.sensor_len = x, y, 0, 14, 55

    def update(self, keys):
        speed = (2.5 if keys[pygame.K_UP] else 0) - (1.5 if keys[pygame.K_DOWN] else 0)
        self.angle = (self.angle + (3.5 if keys[pygame.K_RIGHT] else 0) - (3.5 if keys[pygame.K_LEFT] else 0)) % 360
        rad = math.radians(self.angle)
        nx, ny = self.x + math.cos(rad) * speed, self.y + math.sin(rad) * speed
        
        # Collision detection with walls
        nrect = pygame.Rect(nx - self.radius, ny - self.radius, self.radius * 2, self.radius * 2)
        collided = any(nrect.colliderect(w) for w in WALLS)
        if not collided:
            self.x, self.y = nx, ny
        return collided

    def sense(self):
        """Scans left (-45 deg), ahead (0 deg), right (+45 deg) for obstacles."""
        dirs, res = {"left": -45, "ahead": 0, "right": 45}, {}
        for d, off in dirs.items():
            rad = math.radians(self.angle + off)
            ex, ey = self.x + math.cos(rad) * self.sensor_len, self.y + math.sin(rad) * self.sensor_len
            res[d] = any(w.clipline((self.x, self.y), (ex, ey)) for w in WALLS)
        return res

    def draw(self, surface):
        pygame.draw.circle(surface, BLUE, (int(self.x), int(self.y)), self.radius)
        rad = math.radians(self.angle)
        pygame.draw.line(surface, WHITE, (self.x, self.y), (self.x + math.cos(rad)*self.radius, self.y + math.sin(rad)*self.radius), 3)

# 3. HELPER FOR WORD WRAPPING TEXT
def render_wrapped_text(surface, text, font, rect, color=BLACK):
    words = text.split(" ")
    lines, current_line = [], ""
    for word in words:
        test_line = f"{current_line} {word}".strip()
        if font.size(test_line)[0] <= rect.width:
            current_line = test_line
        else:
            lines.append(current_line)
            current_line = word
    lines.append(current_line)
    
    y = rect.y
    for line in lines:
        if y + font.get_height() <= rect.bottom:
            surface.blit(font.render(line, True, color), (rect.x, y))
            y += font.get_height() + 2

# 4. MAIN LOOP
def main():
    pygame.init()
    screen = pygame.display.set_mode((WIN_W, WIN_H))
    pygame.display.set_caption("Grounded Language Micromouse")
    clock, font = pygame.time.Clock(), pygame.font.SysFont("Arial", 30, bold=False)
    mouse = Micromouse(50, 50)

    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit(); sys.exit()

        collided = mouse.update(pygame.key.get_pressed())
        sensors = mouse.sense()
        dist = int(math.hypot(mouse.x - GOAL.centerx, mouse.y - GOAL.centery))

        # Build rule-oriented grounded language output
        tokens = []
        if GOAL.collidepoint(mouse.x, mouse.y):
            tokens.append(f"{DICT['nouns'][2]} {DICT['verbs'][1]}")  # "goal reached"
        else:
            tokens.append(f"{DICT['nouns'][4]} to {DICT['nouns'][2]}: {dist}px")  # "distance to goal: Xpx"

        if collided:
            tokens.append(f"{DICT['nouns'][0]} collision {DICT['adj'][4]}")  # "wall collision blocked"
        
        # Tactical language for rule-based navigation AI
        blocked_dirs = [d for d, is_blocked in sensors.items() if is_blocked]
        if not blocked_dirs:
            tokens.append(f"{DICT['nouns'][1]} {DICT['adj'][3]}: {DICT['verbs'][3]} {DICT['adj'][0]}") # "path clear: move ahead"
        else:
            tokens.append(f"{DICT['nouns'][0]} {DICT['verbs'][0]} on " + " ".join(blocked_dirs))
            if sensors["ahead"]:
                suggested_turn = "right" if not sensors["right"] else ("left" if not sensors["left"] else "back")
                tokens.append(f"recommendation: {DICT['verbs'][2]} {suggested_turn}")

        # Render Scene
        screen.fill(WHITE)
        pygame.draw.rect(screen, GREEN, GOAL)
        screen.blit(font.render("GOAL", True, WHITE), (GOAL.x + 18, GOAL.y + 30))
        for w in WALLS: pygame.draw.rect(screen, BLACK, w)
        mouse.draw(screen)

        # Bottom Text Panel (White Background, Black Text, Word Wrapped)
        panel = pygame.Rect(0, MAZE_H, WIN_W, WIN_H - MAZE_H)
        pygame.draw.rect(screen, WHITE, panel)
        pygame.draw.line(screen, BLACK, (0, MAZE_H), (WIN_W, MAZE_H), 2)

        output_str = f"STATUS: [ {' | '.join(tokens)} ] | CONTROLS: Arrow Keys"
        render_wrapped_text(screen, output_str, font, pygame.Rect(10, MAZE_H + 8, WIN_W - 20, WIN_H - MAZE_H - 12))

        pygame.display.flip()
        clock.tick(60)

if __name__ == "__main__":
    main()