UserPreferences

PyroModuleRAVQ


Pyro Module Resource Allocating Vector Quantizer

The Resource Allocating Vector Quantizer (RAVQ) was developed by Fredrik Linaker and Lars Niklasson. As indicated by its name, the RAVQ is a method of vector quantization. Given a data set of vectors, a vector quantizer generates a codebook of models that are meant to represent typical classes of vectors within the input set. Resource allocating in this case means that the size of the codebook is not fixed, but dynamically determined as vector quantization proceeds.

The RAVQ algorithm is unsupervised during vector quantization. The RAVQ consists of three main parts, an input buffer, a moving average, and a set of previously allocated model vector. When the RAVQ begins, the buffer must be initialized by filling the buffer with the first n inputs, where n is the buffer size. Then a moving average can be calculated. After the buffer is full, at each step the current input is added to the buffer and the oldest input in the buffer is deleted, maintaining the size of the buffer at n. A moving average vector is calculated by averaging all the inputs currently in the buffer. Then the RAVQ determines whether the new moving average qualifies as a new model vector. To do so the moving average must meet two criteria. It must be 'close' to the inputs and 'better' than any existing model vectors. If no model vectors exist, the moving average only has to meet the first criteria.

http://www.cs.swarthmore.edu/~stober/images/ravqExample.jpg

The determination of distance between the moving average and the input buffer and the model vectors are described in Fredrik Linaker and Lars Niklasson, "Sensory Flow Segmentation using a Resource Allocating Vector Quantizer, http://citeseer.nj.nec.com/285911.html and also contained in the source code.

The source code to the RAVQ implementation can be found at http://compscitest.brynmawr.edu/cgi-bin/viewcvs.cgi/pyrobot/brain/ravq.py, and click on the topmost (view).

RAVQ: Example 1

The following example will cover the basic functioning of the RAVQ and all the major method associated with the RAVQ class.

We'll begin by using an RAVQ to classify a data stream of binary vectors representing the numbers 0 to 255.

We'll using the following code from PyroModuleSelfOrganizingMap:

def makeBitList(maxbits = 8): 
    retval = [] 
    for i in range(2 ** maxbits): 
        retval.append( dec2bin(i, maxbits) ) 
    return retval 
 
def dec2bin(val, maxbits = 8): 
    """ 
    A decimal to binary converter. Returns bits in a list. 
    """ 
    retval = [] 
    for i in range(maxbits - 1, -1, -1): 
        bit, val = divmod(val, 2 ** i) 
        retval.append(bit) 
   return retval 

This code will generate a sequence of binary numbers (as python lists) which we will input into an RAVQ. Copy the proceeding and following code into a file and run that file as a python script.

from pyrobot.brain.ravq import *

bitlist = makeBitList()
#parameters are buffer size, epsilon, and delta
ravq = RAVQ(4, 2.1, 1.1)
for bits in bitlist:
    ravq.input(bits)
print ravq

The RAVQ parameters are buffer size, epsilon, and delta. While the buffer size is self evident, care must be taken with the epsilon and delta values. The epsilon value determines how close the moving average must be to the input buffer vectors to qualify as a new model vector. Make this value too small and no model vectors will be created; make this value too large the model vectors that are created won't well represent typical input sub sequences. The delta value determines how different a moving average vector must be from any existing model vectors to justify a new model vector. The delta parameter, in essence, partitions the input space.

There is a fourth, optional parameter call historySize, which is by default 0. Passing in a positive number N causes the RAVQ to keep a history associated with each model vector of the last N inputs that mapped to that model vector. (Passing in a -1 causes all vectors that map to that position to be saved and used. That option is only included for completeness, however.)

ravq.input(vec) drives the ravq. All the processing is done in this method automatically.

Now we'll need some more functions to demonstrate the effectiveness of the RAVQ.

def makeNoisyList(ls, percentNoise=0.1, minVal=0.0, maxVal=1.0):
    """
    Returns a noisy version of the given list, and assumes a range
    of values between 0.0 and 1.0.
    """
    retval = []
    for x in ls:
        if random.random() < 0.5:
            retval.append(max(x - (random.random() * percentNoise), minVal))
        else:
            retval.append(min(x + (random.random() * percentNoise), maxVal))
    return retval

def makeNoisySequence(sequence, repeat, percentNoise=0.1):
    """
    Returns a noisy version of the given sequence, with each item
    repeated the number of times designated by the repeat variable.
    """
    retval = []
    for x in sequence:
        for j in range(repeat):
            retval.append(makeNoisyList(x, percentNoise))
    return retval
from pyrobot.brain.ravq import *

seq = makeNoisySequence([[0.0, 0.5, 1.0],
                         [0.5, 0.5, 0.5],
                         [1.0, 0.1, 0.1],
                         [0.9, 0.9, 0.9],
                         [0.3, 0.3, 0.8]], 5, 0.05)
ravq = ARAVQ(4, 2.1, 0.5, 2, 0.03)
ravq.setVerbosity(2)
for x in seq:
   ravq.input(x)
   print ravq

The above example uses an adaptive RAVQ (ARAVQ). This version of the RAVQ algorithm has a learning rule which updates the winning model vector by the difference between the winning model vector and the moving average. The last parameter, alpha in the literature, is the learning rate -- it determines how much of difference is used in updating the model vector.

Exercise 1

Examine the previous example, being especially careful you understand how makeNoisySequence and makeNoisyList work. Now try using the ARAVQ and RAVQ to classify this sequence. How many model vectors do you expect? How does using the ARAVQ differ from the RAVQ? Try varying the parameters and seeing how each affects the operation of the RAVQ.

RAVQ: Example 2

Now it is time to see how the RAVQ might be used in a robot brain.

First we'll use the following brain to collect sensor data. The sensor data will be normalized and stored in the file sensor.dat.

# imported modules
from pyrobot.brain import Brain 
import os, time, sys

def saveListToFile(ls, file):  
    for x ls:  
        file.write(str(x) + " ")  
    file.write("\n")  

class SampleBrain(Brain):
    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.fp = open('sensors.dat','w')

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

    def kick(self):
        """
        How to get unstuck.
        """
        self.repositionLog.write("STALLED " + str(self.counter) + "\n")
        self.move(0.5 * random.random(), 0.0)
        time.sleep(1)
        self.robot.update()
        if self.robot.stall:
            self.move(-0.5 * random.random(), 0.0)
            time.sleep(1)
            self.robot.update()
            if self.robot.stall:
                self.move(0.0, 0.5 * random.random())
                time.sleep(1)
                self.robot.update()
                if self.robot.stall:
                    self.move(0.0, -0.5 * random.random())
                    time.sleep(1)
                    self.robot.update()
                    
    def controller(self):
        # tweakable parameters
        frontRange = 1.0
        minRange = 0.7
        maxRange = 1.0
        amount = 0.3
        # 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 < frontRange:
            if not self.blockedFront:
                self.direction = -1
            self.blockedFront = 1
            return [0, self.direction * amount]
        else:
            self.blockedFront = 0
        if minLeft < minRange:
            if self.blockedFront:
                return [0, self.direction * amount]
            else:
                return [amount/2.0, -amount]
        elif minLeft > maxRange:
            if self.blockedFront:
                return [0, self.direction * amount]
            else:
                return [amount/2.0, amount]
        elif minRight < minRange:
            if self.blockedFront:
                return [0, self.direction * amount]
            else:
                return [amount, amount]
        else:
            self.blockedFront = 0
            return [amount, 0.0]

    def step(self):
        # display count
        if self.verbosity > 0: print self.counter
        # switch between training network and training ravq
        if self.counter > 1000:
            self.pleaseStop()
        else:
            # train network or ravq
            motors = self.controller()
            sensors = [self.scaleSensors(s.value) for s in self.robot.range["all"]]
            # move robot
            self.move(motors[0], motors[1]) 
            saveListToFile(sensors, self.fp)
            # kick if things get bad
            if self.robot.stall:
                self.wasStalled += 1
            if self.wasStalled > 10:
                print 'Kicking!'
                self.kick()
                self.wasStalled = 0
            # sleep and increment counter
            time.sleep(0.1)
        self.counter += 1
        
def INIT(engine):
    return SampleBrain('SampleBrain', engine)

if __name__ == '__main__':
    os.system('pyro -s Stage -w tworoom.world -r Player1')

Now we need to train a RAVQ using the sensor data that we've gathered from the robot. The following simple code should be all we need.

from pyrobot.brain.ravq import *

fp = open('sensors.dat')
ravq = ARAVQ(10, .2, .6, 5, .02)

for line in fp:
    # input the data into the ravq
    ravq.input(map(float, line.split()))
print ravq

Exercise 2

Try adjusting the parameters to the ARAVQ. What results do you get with different parameters? Can you apply labels to the model vectors produced? Make sure you understand the layout of the sensors on the simulated pioneer robot. Are there model vectors for such concepts as 'wall on left' and 'wall on right'? RAVQs can classify other types of inputs as well. Try using the RAVQ to classify a sequence of visual information. You'll need the information from PyroModuleVision.

Example 3

To demonstrate the usability of the RAVQ consider the following example.

from pyrobot.brain.conx import *
from pyrobot.brain.ravq import *
import Numeric

def normalize(vector):
    """
    Take any vector and normalize all components to [0,1].
    """
    arr = Numeric.array(vector)
    largest = Numeric.fabs(arr[Numeric.argmax(arr)])
    smallest = Numeric.fabs(arr[Numeric.argmin(arr)])
    if largest > smallest:
        return ((arr / largest) + 1.0) / 2.0
    else:
        return ((arr / smallest) + 1.0) / 2.0

ravq = ARAVQ(5, .2, .4, 5, 0.03)
n = Network()
n.addLayers(2, 2, 1)
n.setInputs([[0.0, 0.0],
             [0.0, 1.0],
             [1.0, 0.0],
             [1.0, 1.0]])
n.setTargets([[0.0],
              [1.0],
              [1.0],
              [0.0]])
n.setEpsilon(0.9)
n.setMomentum(0.9)
n.setTolerance(0.1)
error, correct, total = 0.0 , 0.0, 0.0
tssError = 1.0
while tssError > n.tolerance:
    n.randomizeOrder()
    tssError = 0.0
    for i in n.loadOrder:
        error, correct, total, totalPCorrect = n.step(input = n.inputs[i], output = n.targets[i])
        tssError += error
        ravq.input(normalize(n.arrayify()))
print ravq

This RAVQ is classifing the network weights during this network's training process.

Exercise 3

Run the script. What can you say about the classifications that resulted from inputing network weights into the RAVQ?

Further Reading

  1. Fredrik Linåker and Lars Niklasson. Sensory Flow Segmentation using a Resource Allocating Vector Quantizer. [WWW]http://citeseer.nj.nec.com/285911.html.

Pyro Modules Table of Contents

Modules

  1. PyroModuleIntroduction

  2. PyroModuleObjectOverview

  3. PyroModulePythonIntro

  4. PyroModuleDirectControl

  5. PyroModuleSequencingControl

  6. PyroModuleBehaviorBasedControl

  7. PyroModuleReinforcementLearning

  8. PyroModuleNeuralNetworks

  9. PyroModuleEvolutionaryAlgorithms

  10. PyroModuleComputerVision

  11. PyroModuleMapping

  12. PyroModuleMultirobot

  13. FurtherReading

Additional Resources

  1. PyroIndex

  2. PyroAdvancedTopics

  3. PyroUserManual

  4. [WWW]Pyro Tutorial Movies

Reference: PyroSiteNotes