Sunday, June 19, 2011

Does not compute ... E pur si muove

"As a kid, I used to worry that at bedtime I'd accidentally start thinking about thinking, and would be unable to fall asleep. That bottomless iteration was so beguiling it would sometimes take me an hour to let it go." Libbey White

After asking a newly minted robot to declare "Hello world!", my thoughts turned to robotic mental instability, chaos, and self-destruction. Classically this is done by asking the robot a paradoxical question to which it responds "Does not compute" repeatedly before its tiny 8086 brain overheats, causing ignition of magnetic tape reels followed by high voltage electrical discharges. This procedure can be performed on any old computer. Some are resistant, but none immune.

In addition to paradoxes, questions about their emotional state, existential pondering and simple bad logic (NOT-logic?) are also popular routes to robotic insanity. Some hardware is vulnerable to a killer poke, and specialty CPUs include a convenient Halt and Catch Fire machine code instruction.

Tight recursive loops are simple to implement and widely admired for their destructive power.  Their logical robustness adds to their deep appeal. A function that calls itself (a recursion), can lead to good or evil:

    bool foobar() {

        bool never;

        print( "Echo..." );         
        never = foobar();

        return never;    

The power of this construction lies not in its endless echoing, but in the need for the computer to keep track of which instance of foobar() is currently executing -- a record (call stack) of the instances to which it will never return. The computer will require some serious resources (stack space) to accomplish its goal; universal domination or self-destruction are the only feasible outcomes.

While computers can talk back to us, robots have a body. Their sensory organs interact with the programs they run on and the actions they themselves produce and the environment they see or feel. Their output is fed into their own input, and feedback can't always be controlled. Generally a robot's response in any environment is non-linear, and is often chaotic and unpredictable. So robots are naturally appealing for their inherent ability to fail in spectacular ways. A simple programming loop is all that is needed, with the physical I/O providing recursion. Memory is not an issue, unlike software recursion where every available particle in the universe might be commandeered for memory.

It is useful to diagram a robot's body and brain, to show the relationship between the brain, body and environment. My plan for a simple functional robot that embodies the potential for self-annihilation and/or apocalypse starts with this system:
The robot brain (program/memory/CPU) is contained in the box. The system is unstable when the average input is near the threshold value: no matter what the current state of the light and photosensor, the state will change after the brain transforms the input to the output.

I implemented this robot on the Android Open Accessory Development Kit (ADK). The computer (Arduino microcontroller) has a body (the physical input/output), with light sensing and emitting devices mounted on the ADK shield:

ADK shield: Arrows point to the photoresistor (light dependent resistor, LDR) at left, and the light (light emitting diode, LED) at right

The photoresistor and LED would be cheap and easy to implement without this shield, but they were already conveniently wired and physically close to each other. But, unlike the diagram, they are not facing each other: both face away from the board so little of the LED's light normally reaches the photoresistor.

This deficiency is easily remedied by holding a reflective or light scattering surface above them. This allows for physical control of the photonic coupling between the devices. Now it is a robot that interacts in a non-trivial way with its environment:

The robot brain is implemented as a main loop function, which is repeatedly executed as fast as the microprocessor can go. Its pseudo-code looks something like this:

// Initialize a global threshold based on 
// average ambient lighting conditions.
threshold = 500;  // a value below light sensor output in ambient 
                  // conditions, where the sensor range is about [0,880]

  // Get current state of the light sensor.
  nVin = ReadInput( PHOTORESISTOR ); 

  // Set new state of the light.
  if ( nVin >= threshold ) WriteOutput( LED, 0 ); // turn LED off
  else                    WriteOutput( LED, 1 ); // turn LED on

Also see full C code for an Arduino below.

The system has a constant-OFF regime (in bright light), a constant-ON regime (in dim light), near-periodic regimes and fully non-periodic regimes (both in dim light with a nearby scattering/reflecting surface). The boundary between periodic on non-periodic regimes are at the edge of chaos. The average flash rate and apparent brightness is controlled by the relative contribution of scattered light in this unstable regime.

Runaway oscillation is successfully achieved, although it appears that hardware limitations prevent immediate self-destruction. Step-wise execution of the loop is controlled by the CPU clock, which limits the oscillation frequency to a value considerably less than infinite. What is the maximum oscillation frequency? It is some small fraction of the processor clock rate (16 MHz for the Arduino Mega 2560), as many cycles are required for each loop execution.

Alas, the robot doesn't cause any damage to itself or the lab. Replacing the LEDs with high power lasers might improve performance. 

The mathematics of systems like this (non-linear dynamical systems) are poorly understood and resistant to solutions using continuous functions, or any periodic functions. If the sensor elements are strictly linear (for example if the photoresistor response is directly and exactly proportional to the incident light level), and the output has exactly two states (0/1, or ON/OFF), then the system can in principle have only steady, or strictly periodic, states. But photoresistors, LEDs, and CPUs are not linear, and have states that are only approximately binary. While the system is deterministic, its behavior is not predictable. 

Adjusting the amount of light reflected to the photoresister to the boundary between roughly periodic and constant state results in a strongly chaotic, nonlinear dynamical system. Such systems are important because of their sensitivity to the precise conditions, environmental lighting and nearby light-scattering surfaces in this example. This makes them valuable to robots for sensing and information processing, a core function of any intelligent machine.

We tend to regard technology as predicatable, and computers are designed to be as predictable as is feasible. But robots have sensory elements and environmental conditions that are not linear. That chaos is dominant in such simple systems, with only a simple transition rule and a pair of coupled elements, is surprising to robots and people. Does not compute ... E pur si muove!


C code for the Android Open Accessory Development Kit (ADK), or any Arduino with an LED and photoresistor on the appropriate pins:

// feedback_blinker_1
// Light feedback system on Android Open Accessory Development Kit (ADK).
// Demonstrates a simple dynamical system with non-trivial behavior,
// including a non-periodic regime.
// created by Mark Dow, June 17, 2011

#define  LED_2_RED        5
#define  LED_2_BLUE       6
#define  LED_2_GREEN      7

// Initialize a threshold based on average ambient lighting conditions.
int nThreshold = 500;  // a value below light sensor output in ambient 
                       // conditions, where the sensor range is about [0,880]

int nVin = 0;
int nLoopCount = 0;

void setup(){
  pinMode( LED_2_BLUE, OUTPUT );
  Serial.begin( 9600 );

void loop(){

  nVin = analogRead( PHOTORESISTOR );

  if ( nVin > nThreshold ) {
    digitalWrite( LED_2_BLUE, HIGH );  // off
  else {
    digitalWrite( LED_2_BLUE, LOW );     // on
//  delay(100);  // slow the loop execution frequency

//  // Every 1000 times through the loop, write stats to the serial monitor.
     //  // Note: This writing to the serial port takes about 10 ms, slowing the
     //  // loop frequency.
//  ++nLoopCount;
//  if ( nLoopCount == 1000 ) {
//    Serial.print( nVin );        // column 1: current input value
//    Serial.print( "\t" );
//    Serial.println( millis() );  // column 2: time since start, in milliseconds
//    nLoopCount = 0;
//  } 

No comments:

Post a Comment