ResourceAllocatingVectorQuantizer

1. RAVQ

A RAVQ is an alternative to SOMs. A RAVQ can dynamically create new model vectors to describe novel stable input sequences.

Check the Pyro CVS Repository for the most recent version of ravq.py. http://compscitest.brynmawr.edu/cgi-bin/viewcvs.cgi/pyrobot/brain/ravq.py.

The RAVQ has three parameters. The first is a window size. This determines how many previous inputs will be used to generate the moving average. The second is an epsilon value. If the moving average is not within epsilon (by the metric found in references 1 and 2) of the set of inputs currently in the buffer that moving average is disqualified from being a model vector. The moving average does not reflect a 'typical' input given the window size. This indicates that the inputs are volatile. The third is a delta value. If the moving average is not at least delta from all existing model vectors, it is disqualified from being a model vector. The moving average in this case does not represent something 'new'. In an ARAVQ, there is an additional parameter, alpha, which specifies the learning rate. The ARAVQ algorithm updates existing winning model vectors to better match current inputs.

The ARAVQ and RAVQ algorithms don't specify a neighborhood that can be used for updating purposes as in Kohonen's SOM algorithm. Distance relationships among the model vectors can be calculated. This implementation currently supports a distance map showing the distance between any two model vectors. As with any set of highly dimensional data points, certain techniques can be used to capture the most important correlative features of the data. I am currently working on finding principle component analysis and other statistical tools available in Python to add to the functionality of the current RAVQ implementation.

Some thoughts: The delta and epsilon values depend on the scale and size of the vectors being quantized. Epsilon is also related to buffer size. Is there a way to make these relationships explicit? I've added a feature which fixes the number of model vectors. Would is be possible to train up a set of model vectors and then somehow initialize a SOM of the given size?

I've implemented an additional experimental version of the RAVQ that determines the winner based on the current input to the RAVQ. This differs from the previous approach in that the winner was previously determined using the moving average.

The most current RAVQ designs used in the Governor architecture:

http://www.cs.swarthmore.edu/~stober/ravq.jpg

Figure a shows the RAVQ with input histories associated with each model vector. Every time a model vector wins, the current input vector is stored in that model vector's history buffer. Figure b shows the ravq with a critical input history. The critical input history stores the inputs at the time of a change in the model vector winner. We consider these critical events in the input space, and would work well as training vectors for a network. Figure c shows the critical segment history, an adaptation of the critical input history to capture entire segments of the input sequence surrounding a change in the model vector.

A sample RAVQ brain is available in the Pyro CVS Repository. http://compscitest.brynmawr.edu/cgi-bin/viewcvs.cgi/pyrobot/plugins/brains/RAVQ.py.

Here is the most current version of the experiment I am running. I am attempting to duplicate Nolfi and Tani's results using the techniques of the RAVQ as described in Linaker and Niklasson within the pyro framework. The current implementation uses a ravq to classify both the scaled input vectors and the trained hidden layer activations of a prediction (motor values only) network. The robot is controlled by a prebuilt wall following algorithm. It is hoped that the trained network will be able to control the robot as well.

The current brain (be sure to change the paths!):


# imported modules 
from pyrobot.brain import Brain
from pyrobot.brain.conx import *
from pyrobot.gui.plot.scatter import *
from pyrobot.gui.plot.hinton import *
import pyrobot.brain.ravq
import os
import time
import sys

# log file directories 
rootDirectory = "/home/stober/ravq/experiments/"
currentExperiment = "Nolfi_RAVQ_Long/"
currentBrain = "/home/stober/ravq/Nolfi_Ravq.py"

class RAVQBrain(Brain):
    """A brain that uses a RAVQ to classify hidden layer activations in a prediction network."""
    def setup(self):
        # robot parameters 
        self.robot.range.units = 'ROBOTS'
        self.maxvalue = self.robot.range.getMaxvalue()

        # status variables 
        self.verbosity = 1
        self.direction    = 1
        self.blockedFront = 0
        self.wasStalled   = 0
        self.counter = 0
        self.previous = [0.0, 0.0]

        # tweakable params 
        self.timer = 50000 # turns on hiddenRavq 
        self.stop = 100000
        self.sleepTime = 0.1
        self.backupTimer = 10000

        # create network 
        self.net = SRN()
        self.net.setSequenceType("ordered-continuous")

        self.inSize = self.robot.range.count + 2
        self.net.addLayers(self.inSize, self.inSize/2, 2)

        # defaults - but here explicit 
        self.net.setBatch(0)
        self.net.setInteractive(0)
        self.net.setVerbosity(0)
        self.net.setInitContext(0)

        # initialize network 
        self.net.initialize()

        # learning parameters 
        self.net.setEpsilon(0.2)
        self.net.setMomentum(0.1)
        self.net.setTolerance(0.05)

        # set learning 
        self.net.setLearning(1)

        # hidden ravq (tweakable parameters) 
        self.hiddenRavq = pyro.brain.ravq.ARAVQ(10, .2, .5, .03)
        self.hiddenRavq.setHistory(0)
        self.hiddenRavq.setAddModels(0)
        self.hiddenRavq.setLearning(0)

        # input ravq (tweakable parameters) 
        self.inputRavq = pyro.brain.ravq.ARAVQ(10, .2, .6, .03)
        self.inputRavq.setHistory(0)
        self.inputRavq.setAddModels(1)
        self.inputRavq.setLearning(1)

        # file IO 
        self.path = rootDirectory + currentExperiment
        if(os.path.isfile(self.path + "exp.lock")):
            raise "Lock error!"
        else:
            try:
                os.mkdir(self.path)
            except:
                pass
            lock = open(self.path + "exp.lock", "w")
            lock.write("This file locks the experiment directory to prevent overwriting experimental data.")
            lock.close()
        # archive brain 
        os.system("cp " + currentBrain + " " + self.path + "archive.py")
        self.netInfo = open(self.path + 'nn.dat', 'w')
        self.hiddenRavq.openLog(self.path + 'hidden_history.log')
        self.hiddenRavqInfo = open(self.path + 'hidden_ravq.dat', 'w')
        self.inputRavq.openLog(self.path + 'input_history.log')
        self.inputRavqInfo = open(self.path + 'input_ravq.dat', 'w')
        self.repositionLog = open(self.path + 'reposition.dat', 'w')

        # gui displays 
        self.plot1 = Scatter()
        self.plot1.setTitle('Target: Translate x Rotate')
        self.plot2 = Scatter()
        self.plot2.setTitle('Activation: Translate x Rotate')
        self.hidd = Hinton(self.inSize/2, title = 'Hidden Layer')
        self.inputs = Hinton(self.inSize, title = 'Input Layer')

    def destroy(self):
        self.plot1.destroy()
        self.plot2.destroy()
        self.hidd.destroy()
        self.inputs.destroy()
        self.netInfo.close()
        self.hiddenRavq.closeLog()
        self.hiddenRavqInfo.close()
        self.inputRavq.closeLog()
        self.inputRavqInfo.close()
        self.repositionLog.close()
        del self.net
        del self.hiddenRavq
        del self.inputRavq

    def scaleSensors(self, val):
        """From Robots (or anything) to [0, 1]"""
        return (val / self.maxvalue)

    def scaleMotors(self, val):
        """[-1, 1] to [0, 1]"""
        return (val + 1) / 2.0

    def kick(self):
        """How to get unstuck."""
        self.wasStalled += 1
        self.repositionLog.write("STALLED " + str(self.counter) + "\n")
        self.move(0.1, 0.0)
        time.sleep(.2)
        if self.robot.stall:
            self.move(-0.1, 0.0)
            time.sleep(.2)
            if self.robot.stall and self.wasStalled > 10:
                self.repositionLog.write("Cannot fix stall at " + str(self.counter) + " " +  \
                                         str(self.robot.simulation[0].getPose("Pioneer")')) +
                                         " so repositioning to (796, 2211, 92).\n")
                # we'll call this the hand of god  
                self.set('robot/truth/pose', (796, 2211, 92))
        else:
            self.wasStalled = 0

    def controller(self):
        # tweakable parameters 
        minRange = 0.85
        maxRange = 1.25
        #rand = random.random() * 0.5 
        rand = 0.25

        # important sensors 
        minFront = min([s.value for s in self.robot.range["front"]])
        minLeft  = min([s.value for s in self.robot.range["front-left"]])
        minRight = min([s.value for s in self.robot.range["front-right"]])
        left =  min([s.value for s in self.robot.range["left"]])
        right = min([s.value for s in self.robot.range["right"]])

        # the decision algorithm 
        if minFront < minRange:
            if not self.blockedFront:
                if right < left:
                    self.direction = 1
                else:
                    self.direction = -1
            self.blockedFront = 1
            return [0, self.direction * rand]
        elif minLeft < minRange:
            if self.blockedFront:
                return [0, self.direction * rand]
            else:
                return [rand, -rand]
        elif minLeft > maxRange:
            if self.blockedFront:
                return [0, self.direction * rand]
            else:
                return [rand, rand]
        elif minRight < minRange:
            if self.blockedFront:
                return [0, self.direction * rand]
            else:
                return [rand, rand]
        else:
            self.blockedFront = 0
            return [0.5, 0.0]

    def backup(self, tag):
        self.net.saveWeightsToFile(self.path + "predict" + str(tag) + ".wts")
        self.inputRavq.saveRAVQToFile(self.path + "input_ravq" + str(tag) + ".pck")
        self.hiddenRavq.saveRAVQToFile(self.path + "hidden_ravq" + str(tag) + ".pck")

    def step(self):
        """ 
        1. Determine new motor values. 
        2. Determine inputs (old sensors + old motors). 
        3. Step through with new motor values as targets. 
        4. Move robot. 
        5. New motor values become old motor values. 
        """
        # display count 
        if self.verbosity > 0: print self.counter

        # switch between training network and training ravq 
        if self.counter == self.timer:
            self.net.setLearning(0)
            self.hiddenRavq.setAddModels(1)
            self.hiddenRavq.setLearning(1)
            self.net.saveNetworkToFile(self.path + "predict")
            self.net.saveWeightsToFile(self.path + "predict.wts")
        elif self.counter == self.stop:
            self.hiddenRavq.logHistory(0, str(self.robot.simulation[0],getPose('Pioneer')))
            self.hiddenRavqInfo.write(str(self.hiddenRavq))
            self.hiddenRavq.saveRAVQToFile(self.path + "hidden_ravq.pck")
            self.inputRavq.logHistory(0, str(self.robot.simulation[0].getPose('Pioneer')))
            self.inputRavqInfo.write(str(self.inputRavq))
            self.inputRavq.saveRAVQToFile(self.path + "input_ravq.pck")
            self.pleaseStop()
            self.destroy()
        else:
            # train network or ravq 
            motors = self.controller()
            inputs = [self.scaleSensors(s.value) for s in self.robot.range["all"] +  map(self.scaleMotors, self.previous)
            (error, correct, total) = self.net.step( input = inputs, \
                                                     output = map(self.scaleMotors, motors))
            self.inputRavq.input(inputs)

            # hidden ravq 
            if self.counter > self.timer:
                self.hiddenRavq.input(self.net['hidden'].activation)
                self.hiddenRavq.logHistory(0, \
                                           str(self.robot.simulation[0].getPose('Pioneer')))

            # backup sometimes 
            if self.counter % self.backupTimer == 0:
                self.backup(self.counter)

            # other IO 
            self.inputRavq.logHistory(0, \
                                      str(self.robot.simulation[0].getPose('Pioneer')))
            self.netInfo.write(str(self.counter) + " " + str(error) + "\n")
            self.plot1.addPoint(self.scaleMotors(motors[0]), self.scaleMotors(motors[1]))
            self.plot2.addPoint(self.net['output'].activation[0], \
                                self.net['output'].activation[1])
            self.hidd.update(self.net['hidden'].activation)
            self.inputs.update(self.net['input'].activation)
            if self.verbosity > 0: print (error, correct, total)

            # move robot 
            self.move(motors[0], motors[1])
            self.previous = motors

            # kick if things get bad 
            if self.robot.stall:
                self.kick()

            # sleep and increment counter 
            time.sleep(self.sleepTime)
        self.counter += 1


def INIT(engine):
    return RAVQBrain('RAVQBrain', engine)

[RAVQLevelOne.py]

The current world file:

# Desc: 1 robot with player, laser, sonar and gps
# CVS: $Id: nolfi2.world,v 1.1 2003/05/15 21:45:55 yeelin Exp $

# the resolution of Stage's raytrace model in meters
#

resolution 0.02

# GUI settings
#

gui
(
  size [ 502.000 506.000 ]
  origin [5.018 4.950 0]
  scale 0.021 # the size of each bitmap pixel in meters
)

# load a bitmapped environment from a file
#

bitmap
(
  file "nolfi2.pnm"
  #resolution 0.1
  #resolution .044
  resolution 0.07
)

include "/usr/local/stage/worlds/usc_pioneer.inc"

# create a robot, setting its start position and Player port,
# and equipping it with a laser range scanner
#
#position
#(
# port 6665
# pose [1.0 1.0 20]
#laser()
#)

usc_pioneer
(
  color "green"
  name "robot"
  port 6665
  pose [.796 2.211 92]
  #(1101, 1113, 48)
  truth()
)

# coordinates are defined from the center of the box
#box ( size [0.75 0.75] color "blue" pose [2.5 3.5 0.000] sonar_return "visible" )
#box ( size [0.75 0.75] color "red" pose [2.5 1.5 0.000] sonar_return "visible" )

The nolfi2.pnm file can be found here: http://www.cs.swarthmore.edu/~stober/nolfi2.pnm

I ran a long experiment and the results are in. The first level is certainly a success in this limited context. The network learned the primitive behavior, and the hidden ravq classified the hidden layer activations into roughly three categories, corner, wall, and corridor. I'll continue tweaking the parameters to find out what other features can be abstracted from the hidden layer. I also need to figure out how to get level two to work. I'm thinking of labeling all model vectors from the ravq after training, so as to further compress the data.

Update: I ran an experiment to see how well the model vectors captured the basic behavior of the robot. The setup was as follows:

1. Propagate level one network using sensors + previous motors. 2. Classify hidden layer using RAVQ. 3. Copy RAVQ winner into hidden layer. 4. Propagate from the hidden layer. 5. Use the outputs of this second propagation as motor values.

I am also training an L2 network that would predict the sequence of RAVQ winners. Then the level 2 predictions can determine what model vectors are copied into the hidden layer.

L2 prediction for anything other than the asynchronous case has proven to be too difficult without some adjustments. Matt and I are currently working on the governer idea to try to make predicition of rare events possible.