Search This Blog

Saturday, December 18, 2010

More on the Maze

I redid the mouse/maze simulator.  It is much faster.  I also wrote it in a more procedural fashion.  I am getting a better idea of what the code will look like on the Pic this way.  I just swapped the files, so the old code is no longer available.  Instead, the new code is here:
maze and mouse simulator

This program parses a character based maze file.  Here is an example file:
Sample Maze File

It should be easy to create new mazes with this format.  Remember the IEEE rules.  The middle four tiles are the goal and must have at least one way to enter.  The start tile is in the lower left ( south west ) corner.  It must have only one open direction.  This simulator is only geared to the competition 16 x 16 mazes.

Screenshots:
The Maze in its Initial State

 The Maze After First "Flood" - no walls known

The Solved Maze - some unexplored cells

The next step for me is to figure out why gpsim isn't working with the I2C eeprom 256k bit module.  I can do everything but acknowledge polling.  It always times out.  This is odd since the code runs on a real Pic.

Thursday, December 16, 2010

Some Code - Bootloader, I2C, Maze Solving (virtual)

    Ok, time for some code updates.

    First up is the bootloader.  I rewrote my bootloader to accomodate my 16F877 and 16F876a chips.  Unfortunately, this meant the USART speed went down to 2400.  I didn't really notice much difference.  One thing I did put in my bootloader, a true erase sequence.  I made sure I wrote patch space ( 0x3FFF ) to every block from address 0x004 to the start of the bootloader code.  Yes, I know that the '877 and '876a do an erase before write, but what about old code that might sit in between your new code?  I opted for the safe route and made sure the space was clean.  It adds about 30 seconds to the '877's program time.  It adds about 10 seconds to the '876a.  I can live with it.  If you can't, just don't call the erase sequence.

You can download the assembly code for the 16F876a here. 
The adjusted Python code is here.

Note that the command line looks something like this now:
icsp.py /dev/ttyS0 16f876a 2400 /path/to/hex/file.hex -d
for program name, serial port, device type, baud rate, path to hex file, and -d debug switch.

    Next up is the test code I used to get the 32k eeprom working over I2C.  This is pretty much taken whole cloth from application note AN976 from Microchip.

Assembly code for I2C master mode with 32k eeprom.

    Last up is some test code I wrote.  It started as just a quick way to generate a graphical maze like those used for micromouse competitions.  I then patched in some maze-solving simulation.  It needs a total rewrite, but I still think it's cool and useful.

 Here is the maze code.

    And here is a screenshot of maze after solving:


    That's it for now.

I2C Working

    Here's what we have so far.  I got my bootloader working on the 16F876a chips on the first try.  I took the sample code from application note AN976 and got the uCU working with the 32k eeprom.  The next step is to start writing the maze solving code on the Pic.  I'll have plenty of room now that the eeprom chip is working.  I think the cell values want to live on the Pic's built in eeprom.  That way, when it is time to run the maze, I won't need to access the eeprom chip.  I'll store the wall values and a flags ( visited before, destination cell, start cell ) for each cell on the first 256 bytes of the eeprom.  The rest of it can be stack space.  I'll still need a counter word to guard against stack overflow.  Most operations other than init will be single byte reads/writes.
  
    I'll be able to compute "neighbors" by +1 for East, -1 for West, +16 for North, and -16 for South.  If the boundaries cross, it won't be a problem because the walls will let me know not to bother with them.  The initial load of the arrays will pre-fill the outer walls of the maze.

    I'll need to stay aware of what operation I'm doing.  If I try to read or write from the USART, I'll need to make sure and disable the I2C operation first.  Otherwise, I run the risk of errors.

    Order of operations:
    1. take bearings ( walls )
    2. partial flood fill ( update values )
    3. determine next move
    4. virtual move
    5. repeat until destination.

    This will be a fun first exercise!

Friday, December 10, 2010

Detour...Again... MicroMouse!

    Well, here I go again.  Hexapods are expensive!! I took a detour and looked into these things called MicroMice.  At first, it didn't seem all that great.  The robot runs around a maze and tries to find the center.  Wee!  Blindly follow a wall and always go right, right?  Wrong!  These suckers actually solve the maze using an heuristic algorithm.  The Bellman algorithm is apparently the standard.  Then, they improved on it with the modified "flood-fill" approach.  Then, they got even smarter.  The mice continue exploring after finding the center.  They calculate the best route over several options.  Then, they improved more.  The mice calculate diagonal as well as strictly vertical/horizontal attacks.  The Japanese competitions average around 15 seconds for a solve.  Wow.  This is way out of my league.  But I do like the idea of having a little uMcu solve a maze.  I whipped up a prototype in Python.
    What I came up with is a bit daunting.  I will need two arrays and a stack.  The arrays need to be 256 bytes long.  The stack needs to be at least 200 bytes.  The maze I test solved ( from 1993 ) needed a stack of 148.  It's pretty memory intensive stuff with a lot of recursion.  I think I'll need to back-solve the recursion to just do straight loops.  Ugh!  It makes my head hurt to do that.  I worked hard in college to get recursion.  I never did get the hang of implementing the same solution in straight loops.  Once I figured out how to do it with recursion, it always looked so neat and simple.
    The short term plan is just to get the chips to solve the maze.  Steps:  First, I need some new chips.  I'm sticking with the Ram deficient Pics.  I ordered some 16F876 chips and some 32K I2C Ram chips.  These will help alleviate the memory issues.  I will get I2C working between two Pics.  Then, I'll get it working with the Ram chip.  Then, I think I will simulate movement in the maze from a PC over USART.  I'll let the mouse solve the maze.  It will stream it's arrays back to the PC ( walls located and the value of each tile ).. I'll need to write a program to crunch this stream and generate the maze.  My simulator will help with that.
    The actual robot to solve a maze is pretty complex.  The motors/drivers must be able to know exactly how far they have traveled.  They must be able to turn on a pin head.  They can't be thrown off by rough terrain or miss-alignment.  The two choices here are stepper motors ( slow and new programming ) or DC motors with encoders.  I don't like the idea of encoders.  Too many interrupts that can mess with other time-sensitive operations.  Steppers, on the other hand are slow, expensive, and I can't seem to find good, cheap drivers.
    For sensors, most seem to use line following type IR sensors.  I'm thinking that three Sharp IR sensors might do the trick.  I'll mount them fixed front, left, and right.  That will only tie up three pins.
    It looks like the mouse wants either 2 or 3 controllers.  One will definitely be assigned to maze solving.  Another will handle motor control/movement.  The sensors could be handled by either of these chips or a third chip.  We'll see.
   I honestly don't know if I'll ever actually build this 'bot.  I'm sure whatever I could cobble together on limited funds wouldn't be much.  It'd be cool if it could just solve the maze, whatever the time.

Tuesday, November 30, 2010

Hexapod

I saw that Pololu offers a board to control 16 servos.  It's just a Pic16f87x.  I thought: wow! I could do that.  I wrote a proof of concept on the 16f88 at 8MHz that can do it without "jitter."  Of course, the 16f88 can't handle 16 servos.  It only has 15 pins output max.  My code looks solid, though.  I can move 2 servos on any two pins without "jitter."  I wonder if it is better to bundle the control with the gaits in one 16f87x chip, or should I invest in a Texas Instruments TLC to control the PWM...

Right now, as I contemplate a hexapod,  I think I will use a 16f87x to handle the gaits and PWM in one.  That's one less chip.  The main controller should talk to it via SSP or I2C.  SSP looks simpler, but everyone seems to use I2C.  I haven't played with either yet, so I don't have an opinion.  I don't want to use serial, for I want to preserve that for programming/debugging/talking to the PC.

The rough idea now is to make the lightest hexapod possible.  I would like to use the cheap, $8.00 servos from Sparkfun.  I'm thinking about 4 lipo batteries in series for power.  I'll need a recharge solution for sure.  I think a PCB for the base and paperclips for the legs.  I'll need to work out how to hold it all together and how to attach the paperclips to the servos....  I really have to take the time to do the math on the strength of the servos.  How much weight is involved, and can the servos support it?

In short, Yay!  New problems to figure out!

BootLoader Update

I found an edge case tonight.  My checksum value came up as zero.  Here is the rough update to the code to deal with it.  The whole program needs an overhaul for optimization, but here is the working version:


#!/usr/bin/python2.6

from time import *
from uspp import uspp
import sys

class Programmer:
    tty = None
    prog = None
    file = None
    filename = None
    portname = None
    debug = False
    ok = 'k'
    failed = 'n'
    dataStart = 9
    rewriteAddrH = '0F'         # each must be 2 characters
    rewriteAddrL = 'FC'
    startSignal = chr(0xc1)
  
    def __init__(self, args ):
        self.prog = args[0]
        if self.prog.rfind( '/' ) >= 0:
            self.prog = self.prog[self.prog.rfind('/')+1:]
        if len(args) < 3:
            print self.prog + ': usage:', self.prog, '/path/to/serial/port /path/to/myHex.hex [-d]'
            exit(1)
        if len( args ) >3 and args[3] == '-d':
            self.debug = True
        self.portname = args[1]
        self.filename = args[2]
      
    #    
    def writeProgram(self):
        if self.debug == True:
            print '\nProgrammer.writeProgram: PROGRAM: ' + self.prog + '   PORT: "' + self.portname + '"   FILENAME: ' + self.filename + '\n'
        self.openFile( self.filename )
        if self.debug == True:
            print 'Programmer.writeProgram: File open. Reading packets. . .\n'
        packets = self.makePackets( self.file )
        self.file.close()
        if self.debug == True:
            print '\nProgrammer.writeProgram: Packet dump:\n'
            for packet in packets:
                for c in packet:
                    val = hex(ord(c))[2:]
                    if len(val) < 2:
                        val = '0' + val
                    print val,
                print ''
        print '\nProgrammer.writeProgram: File read complete. Ready to reset pic . . .\n'
        self.openPort(self.portname)
        if self.debug == True:
            print 'Programmer.writeProgram: port open. Awaiting start sequence. . .\n'
        self.startSequence()
        for packet in packets:
            self.sendPacket(packet)

        # how to end? The chip will time out waiting and reset itself.
        print 'Programmer.writeProgram: Programming complete.'
  
    # attempt to send a packet to the pic up to three times. Die on no response.
    def sendPacket(self, packet ):
        retries = 3
        while retries >0:
            if self.debug == True:
                print 'Programmer.sendPacket: Sending packet...',
                for c in packet:
                    print hex(ord(c)),
                print ''
  
            self.tty.write( packet )

            while True:
                status = self.endlessWait()
                if 'k' == status:
                    print 'Programmer.sendPacket: Packet send successful.'
                    return
                elif 'n' == status:
                    if self.debug == True:
                        print 'Programmer.sendPacket: Packet send unsuccessful.  Retrying...'
                    retries = retries - 1
                    break
                else:
                    print 'Programmer.sendPacket: An unexpected response from the microchip.  Received: ', ord(status), 'Aborting. . .'
                exit(1)

        # if we get down here, we've failed
        print 'Programmer.sendPacket: Failed to get the packet to the microchip successfully. Aborting. . . '
        exit(1)
  
    # opens the serial port.  sets in in class variable and returns handle too
    def openPort(self, portname ):
        try:
            self.tty = uspp.SerialPort( portname, 0, 38400)
            self.tty.flush() # discard unread bytes
        except Exception:
            print 'Programmer.openPort: Could not open the serial port: ' + portname
            exit(1)
  
    # opens the hex file, stores file handle in class var and returns the file handle
    def openFile(self, filename ):
        try:
            self.file = open( filename, 'r' )
        except Exception:
            print 'Programmer.openFile: Could not open file: ' + filename
            exit(1)
        return self.file
  
  
    def makePackets(self, file ):
        lines = file.readlines()
        packets = []
        for line in lines:
            ind = line.find( '\n' )
            if ind > 0:
                line = line[:ind]
            ni = line[1:3]
          
            intNumInstr = int(ni,16)/2
            # Need to put high and low together
            # as a single hex value, divide by two, then split them.
            addrValue = int(line[3:7],16) / 2
          
            recordType = int(line[7:9],16)
            packet = ''
          
            # Record Type 0: data
            # Record Type 1: end of file
            # Record Type 2 & 3: Extended segment addressing.  throw warning for us...
            # Record Type 4: signals true 32 bit addressing.  throw warning for us...
            # Record Type 5: another extended address thingy.  throw warning for us...
            if recordType == 0: # This is a data line
                # compute address high and low
                addrH = ''
                addrL = ''
                if addrValue < 256:
                    addrH = '0'
                    addrL = hex( int( bin( addrValue ),2 ) )[2:] # take value as binary int & convert to hex string
                else:
                    b = bin(addrValue)[2:]                  # get as binary string but trim off the '0b'
                    addrH = hex( int( b[:len(b)-8], 2 ) )[2:]      # turn binary into --> int --> hex string and trim off '0x'
                    addrL = hex( int( b[len(b)-8:], 2 ) )[2:]
                intAddrH = int( addrH, 16 )
                intAddrL = int( addrL, 16 )
                addrH = chr( intAddrH )
                addrL = chr( intAddrL )
              
                # Now deal with the address given
                if intAddrH > 32:
                    print 'Programmer.makePackets: Not sure how to deal with data memory writes yet.  Skipping. . .'
                    continue
                # config bits will have address high of 32
                elif intAddrH == 32:
                    if self.debug == True:
                        print 'Programmer.makePackets: Config bit instruction. skipping this line'
                        print '\t\t\tConfig bits can\'t be programmed by this bootloader.\n'
                    continue
                # the bootloader will have an address space of 0xfff - 192 = 0xf1f
                # this translates to an address high of 15 and address low of 31
                elif intAddrH >= 15 and intAddrL >= 31:
                    print 'Programmer.makePackets: Your program is trying to overwrite the bootloader.  Aborting...'
                    print '\tThis program will not allow you to overwrite the bootloader program.  You will need to reprogram the chip if you wish to overwrite.'
                    exit(1)
                # need to deal with the first 4 instructions
                elif intAddrH == 0 and intAddrL == 0:
                    self.createFirstInstructionLines( packets, line, intNumInstr )
                else:
                    packet = self.createRegularPacket( line, intNumInstr, addrH, addrL )  
                    packets.append( packet )
              
            elif recordType == 1:  # end of file
                if self.debug == True:
                    print '\nProgrammer.makePackets: Hex file read complete.'
            elif recordType == 4:   # print inhx32 warning
                if self.debug == True:
                    print  'Programmer.makePackets: Found an indicator line to use 32 bit addressing.  Compile with inhx8s or inhx8m. Ignoring this line.\n'
            else:
                if self.debug == True:
                    print 'Programmer.makePackets: Found lines with extended segment addressing. Skipping this line. . .\n'  
        return packets
  
    def computeNumberOfInstructions(self, intNumInstr ):
        computedNumInstr = 8
        if intNumInstr <= 4:
            computedNumInstr = 4
        elif intNumInstr > 8:
            print 'Programmer.makePackets: Number of instructions was greater than 8.  Unexpected. Aborting. . .'
            exit(1)
        return computedNumInstr

    def createFirstInstructionLines(self, packets, line, intNumInstr ):
        """ This is an abysmal function and set of algorithms.  Need to refactor to make use of redundant operations.
Eventually, the redundant operations in this and the createRegularPacket should be combined.  For now, I just want it work."""

        computedNumInstr = self.computeNumberOfInstructions( intNumInstr )
        numInstr = chr( computedNumInstr  )
        # If less than 4 instructions, create special rewrite packet with what we have then pad instructions to 4.
        # The crc will need to be computed to account for the special address.
        # else if 4 or more, create rewrite packet for first 4
        # calculate crc
        if intNumInstr < 4:
            #get the data for all the instructions
            lineOne = line[self.dataStart:self.dataStart+4*intNumInstr]
            numToPad = (4 - intNumInstr) * 2
            for i in range(0,numToPad,1):
                lineOne = lineOne + '00'
        else:
            # create the lineOne data for the first 4 instructions
            lineOne = line[self.dataStart:self.dataStart+16]
        # expect doubleAddress to return 1e82
        crcOne = self.calculateChecksum( '04' + self.rewriteAddrH + self.rewriteAddrL + lineOne )
        packetOne = self.makeChar( self.rewriteAddrH ) + self.makeChar( self.rewriteAddrL ) + self.makeChar( '04' )
        for i in range( 0, len(lineOne), 4 ):
            packetOne = packetOne + self.makeChar( lineOne[i:i+2] ) + self.makeChar( lineOne[i+2:i+4] )
        packetOne = packetOne + self.makeChar( crcOne )
      
        packets.append( packetOne )
            # if more than 4 instructions and less than 9, create second packet with what's left
            # calculate new crc.  Address will be 0x04 for low
        if computedNumInstr == 8:
            start = self.dataStart + 16   #start at 5th instruction
            end = len(line) - 2           # knock off old crc
            lineTwo = line[start:end]
            if intNumInstr < 8:
                pad = computedNumInstr - intNumInstr
                if pad > 0:
                    for i in range(0,pad,1):
                        lineTwo = lineTwo + '0000'
            crcTwo = self.calculateChecksum( '04' + '0004' + lineTwo )
            packetTwo = self.makeChar( '00' ) + self.makeChar( '04' ) + self.makeChar( '04' )
            for i in range( 0, len(lineTwo), 4 ):
                packetTwo = packetTwo + self.makeChar( lineTwo[i:i+2] ) + self.makeChar( lineTwo[i+2:i+4] )
            packetTwo = packetTwo + self.makeChar( crcTwo )
            packets.append( packetTwo )
  
    def calculateChecksum(self, data ):
        tot=0
        for i in range( 2, len(data)+2, 2 ):
            tot = tot + int( data[i-2:i], 16 )
        s = bin( tot )
        if len(s) <10:
            s = s[2:]
        else:
            s = s[-8:]
        hx = 0x100 - int(s,2)
        crc = ''
        if hx < 0x100:
            crc = hex( hx )[2:]
        else:
            crc = hex( hx )[-2:]
        return  crc
  
    def createRegularPacket(self, line, intNumInstr, addrH, addrL ):
        # compute the number of instructions
        computedNumInstr = self.computeNumberOfInstructions( intNumInstr )
          
        numInstr = chr( computedNumInstr )
        packet = '' + addrH + addrL + numInstr
      
        # now add the data packets
        for i in range( self.dataStart, len(line) - 4, 4 ):
            packet = packet + self.makeChar( line[i:i+2] ) + self.makeChar( line[i+2:i+4] )
          
        # need to add padding for short lines
        pad = computedNumInstr - intNumInstr
        if pad > 0:
            for i in range(0,pad,1):
                packet = packet + self.makeChar( '00' ) + self.makeChar( '00' )
              
        # now add in the checksum
        data = hex( computedNumInstr )[2:].zfill(2) + hex( ord(addrH) )[2:].zfill(2) + hex( ord(addrL) )[2:].zfill(2) + line[7:len(line)-2]
        checksum = self.calculateChecksum( data )
#        checksum = line[len(line)-2:]
        packet = packet + self.makeChar( checksum )
        return packet
  
    def makeChar( self, str ):
        return chr(int( '0x' + str, 16) )


    def startSequence(self):
        """Go into endless wait, listening on port for the startSignal.  When it receives the start signal, it
echoes it back to the pic.  It then waits endlessly for the pic to send ok ('k').  It then returns."""
#        self.waitForResponse( self.startSignal )
#        self.endlessWait()
        self.waitForStartDiscardJunk()
        sleep(.002)
        self.tty.write( self.startSignal )
        print 'Programmer.startSequence: Sent the start signal to the pic.'
        # for echo only, write ok back
#        self.tty.write( self.ok )
        self.waitForResponse( self.ok )

    def waitForStartDiscardJunk(self):
        c = ''
        while True:
            c = self.tty.read()
            if self.startSignal == c:
                return
            elif '' != c:
                print 'junk char received: ', c, 'ord:', ord(c)

    def waitForResponse( self, charWeExpect ):
        c = self.endlessWait()
        if charWeExpect != c:
            print 'Programmer.waitForResponse: We did not receive the character we were expecting.  Looking for:', hex(ord(charWeExpect)), '.  We received:', hex(ord(c)), '. Aborting.'
            exit(0)
        else:
            ch = ''
            try:
                ch = c.decode('ascii')
            except:
                ch = hex( ord(c) )
            print 'Programmer.waitForResponse: Got expected response:', ch
    def endlessWait( self ):
        c = ''
        while True:
            c = self.tty.read()
            if '' != c:
                return c
  
if __name__ == '__main__':
    programmer = Programmer( sys.argv )
    programmer.writeProgram()

Saturday, November 27, 2010

Lots of Minor Work

I completed a lot of minor work today.  I adjusted my bootloader.  For the initial load of the bootloader, I found it was necessary to add a dummy program to the upper region to stop the code from flowing back to the start of the bootloader.  If I didn't, the icsp program on the PC might get noise and fail to receive the start signal.  I also added a new start method on the PC end.  It waits for the start signal from the Pic, and it ignores anything else ( like bogus 0x00 from an open output on the TX line.

I cut some scrap wood for a base and taped on a ball caster in place of the electrical taped LED I was using for the back balance.  I got the ball caster in the mail today along with a few other goodies from Sparkfun.  One of the other goodies was an RS232 shifter kit.  I soldered that together.  It not only freed up a load of space on my breadboard, it also allowed me to reprogram my 'bot in circuit.  Happiness!  It is much faster than I'd ever hoped.  It has been remarkably error free, too.

I've started playing around with the Sharp IR sensor and some basic IR transmitter/receiver stuff.  I want to rewrite CDR to use the Sharp instead of the Ping ultrasound sensor.  I also want to add line following capability.

I got a pair of really small ( and probably fragile ) servos, too.  They are just fodder for some routines I want to try.  I want to write a routine that will do interrupt driven servo control.  I'll start with two or three servos.  I want to see how many servos I can control with a single Pic 16f88 at 8MHz, using a single timer1 at 1 or .5 mSec interrupts without "jitter".

I see the button to add a video here, I'll try to link in a vid I did of CDR: