Pictures of the truck
RoboLogo is a system that enables children to program interactive robots. Children can program a robotic truck that interacts with the environment without having to deal with low-level implementation details.
Using iLogo, a high-level interactive language, the children can easily describe the robot's actions in the environment and just as easily program the robot's reactions to external events, such as encountering an obstacle. For example, to program a robot that bounces between two walls, the user need only write:
do.while [ do.unless [ forward ] (or readsensor fl readsensor fr) [ # do nothing ] do.unless [ backward ] (or readsensor bl readsensor br) [ # do nothing ] ] TRUE
This iLogo program is parsed and translated to assembly code. The resulting A51 file is linked with the low-level RoboLogo library routines and compiled into machine code. The Intel HEX file thus generated is downloaded onto the RoboLogo truck via the serial port. Unaware of the details, the child can now disconnect the programmed robot watch it run, and interact with it.
The goal of our 6.115 project was to enable this transition from the abstract description of the robot's behavior to an actual moving robot. This involved managing the mechanics and sensors of a robotic truck, laying out the electronics to control it, writing the assembly routines that coordinate its actions and sensors, developing the iLogo language, and implementing the compiler that translates iLogo to assembly code.
Like the name suggests, RoboLogo is based on the original LOGO language, developed in the 1960's at Bolt, Beranek and Newman, Inc. LOGO originally allowed children to program a small robot-called the ``turtle''-to move around on the floor in different patterns. Eventually the robot moved from the floor to the computer screen, and children could program the turtle to draw colorful, pretty pictures.
As an example, here is the LOGO code to draw a series of rotated squares:
REPEAT 36 GO SQUARE RIGHT 10 NEXT END # SQUARE REPEAT 4 DRAW 100 RIGHT 90 NEXT RETURN
LOGO is designed to be easy to learn, yet powerful enough to express complex ideas. It has a surprisingly rich set of features, including variables, procedures, and looping constructs. LOGO is an excellent tool for teaching children about analytic thinking and programming, yet it is enjoyable and rewarding.
The limitation of LOGO however is the lack of feedback from the environment. There is no way of expressing an event occuring in the outside world. If the robot bumps into a wall, it won't react. Even if someone gets on its way, a LOGO robot will keep going.
Setting out to overcome this limitation, we developed iLogo, an interactive version of LOGO. Simple constructs in iLogo extend the original LOGO language with interactivity capabilities of reading sensors and transfering control to different parts of the program.
We went back to the original mechanical idea of the LOGO turtle. However, our truck differs in one critical way; it has sensors that allow it to respond to its environment. Children may read and respond to sensory inputs without the complexity of interrupt vectors, AD converters, and register banks.
A child can thus program the truck to interract with the environment, bounce between two walls, follow a human, or even navigate a maze. The result should become an amusing but instructive toy.
Our report will present the RoboLogo architecture in a bottom up fashion. We will first talk about the low-level issues of making the robot work: basic hardware, sensors, controls. Then we will treat the language implementation: structuring the grammar, writing the compiler, translating iLogo.
In this section, we describe the mechanics of our truck, and the circuit and assembly primitives to control it. Because hardware and software are so closely linked, we will treat those two aspects jointly.
Our project started with the chassis of a toy remote-control truck. This truck has a driving motor which actuates all four wheels, a steering motor that changes the direction of the front wheels, and a simple feedback system with which one can determine the position of the front wheels. The motors are powered by a 9.6V nickel-cadmium rechargeable battery. On the four corners of the truck we mounted small switches extended with metal arms to act like bump sensors.
To control this truck we laid out a custom-made, two-layer printed circuit board. The schematic for this board is shown in Figure . The layout of the board is shown in Figure . This circuit board is basically the 6.115 microprocessor system. At its heart is an Intel 8051 microprocessor connected to a ROM, RAM, and serial port. An LM7805 step-down regulator converts the 9.6V power from the truck's battery to a 5V logic supply. An LM18293 push-pull motor driver connects the programmable counter array (PCA) of the 8051 to the truck's motors. In addition, the circuit board has space for an AD converter, a -5V switching power regulator, and an additional LS244. Unfortunately, we did not have time to use these parts.
Figure: RoboLogo Printed Circuit Board
Figure: RoboLogo Schematic
The external switches (the steering box and bump sensors) are connected with pullup resistors to the input of an LS244 tri-state driver. The output is connected to the processor's data bus. A PAL selectively enables the output of the LS244, as well as the RAM, ROM, unused AD converter, and second LS244. The resulting memory map is similar to that of the 6.115 circuit, except that low data memory is divided between the AD converter and the tristate drivers. The program for the PAL that controls the memory chips is shown in Figure .
device 22v10; positive PSEN@2, RD@3, WR@4, A12@5, A13@6, A14@7, A15@8; negative RomCS@23, RomOE@22, RamCS@21, RamOE@20, AdCS@19, Sensors1E@17, Sensors2E@16; RomCS = 1; RomOE = /A15*/PSEN; RamCS = 1; RamOE = A15*/RD + A15*/PSEN; AdCS = /RD*/A13*/A14*/A15; Sensors1E = /RD*A13*/A14*/A15; Sensors2E = /RD*/A13*A14*/A15;
As mentioned earlier, sensors are memory mapped. Reading from external memory locations 0x2000 through 0x2FFF causes a ``sensor word'' to be written to the bus. The truth table for the sensor word is shown in Figure . Note that bit 4 is unused. Also note that the logic for wheel positioning is somewhat complicated; this is a direct result of the implementation of the truck's steering box.
Figure: Truth table for sensor word
The procedure ReadSensor in sensors.a51 is a convenient way of reading the sensor values. This file is shown at the end of the report. Since none of the switches are hardware debounced, software must be careful when using ReadSensor frequently.
It is easy to drive the truck forward and backward; one simply sets the duty cycle of the pulse-width modulated waveform (PWM) from the 8051's PCA modules 0 and 1. Likewise, one can turn the steering wheels completely left or right by setting the duty cycle of PCA modules 2 and 3. Centering the wheels is trickier, as one must use the wheel position sensors. Unfortunately, our truck does not provide enough feedback to acurately turn the wheels partially, say to 30 degrees.
With the above primitives, it is fairly easy to construct higher level routines for driving the truck. The procedures ForwardStraight, ForwardLeft, ForwardRight, BackwardStraight, BackwardLeft, BackwardRight drive the truck in the specified direction forever, and do not return. Obviously these procedures are only useful in a context where they may be interrupted. The procedures ForwardStraightTG, ForwardLeftTG, ForwardRightTG, BackwardStraightTG, BackwardLeftTG, BackwardRightTG drive the truck in the specified direction for a given time and speed. A few implementation notes are in order:
When trying to develop the Interactive Logo language (iLogo), we wanted the language to posseses a few key features:
The result of our development was a subset of the Berkeley Logo language. We took the Berkeley Logo language design as our base and then added a primitive for reading sensor and an exception-based control structure. We also decided to take out a lot of unneeded structures and primitives to scale the down the implementation of the language. We decide to use Berkeley Logo because it is freely distributed on the web and comes with a user manual which was the closest free specification of the Logo language we could find. It also helped us accomplish key features 1 & 2, because this version of logo is already known for being easy to use and the code which came with the Berkeley Logo package already had a scanner for the language. Berkeley Logo can be found at:
Unfortunately, adding any new structures to the existing scanner proved very difficult, as the scanner was hand coded and contained little if any documentation. Fortunately, there are other free distributed tools on the web which helped us in the compiler generation. These tools will be discussed in the compiler implementation section.
After splicing out the unnecessary parts of Berkeley Logo and adding our two new features, we formalized the contex free grammar for the iLogo language, shown in Figure .
Program ::= Command* Command ::= MakeCommand | IfCommand | WaitCommand | ForCommand | DoWhileCommand | DoUnlessCommand | MoveCommand | PrintCommand MakeCommand ::= 'MAKE' Identifier Expression IfCommand ::= 'IF' BooleanExpression InstructionList [InstructionList]? WaitCommand ::= 'WAIT' NumericExpression ForCommand ::= 'FOR' List InstructionList DoWhileCommand ::= 'DO.WHILE' InstructionList BooleanExpression DoUnlessCommand ::= 'DO.UNLESS' InstructionList BooleanExpression InstructionList MoveCommand ::= MoveOp NumericExpression NumericExpression PrintCommand ::= 'PRINT' String InstructionList ::= '[' Command* ']' Expression ::= BooleanExpression | NumericExpression | List | Identifier BooleanExpression ::= '(' BooleanOp Expression Expression ')' | '(' LogicalOp BooleanExpression+ ')' | Boolean | 'READSENSOR' Sensors NumericExpression ::= '(' NumericOp Expression Expression* ')' | '(' NumericExpression ')' | Integer Sensors ::= 'FR' | 'FL' | 'BR' | 'BL' MoveOp ::= 'FORWARD' | 'FORWARDR' | 'FORWARDL' | 'BACKWARD' | 'BACKWARDR' | 'BACKWARDL' BooleanOp ::= '=' | '>' | '<' | '<=' | '>=' LogicalOp ::= 'AND' | 'OR' | 'NOT' NumericOp ::= '+' | '-' | '*' | '/' | '%' List ::= '[' Expression* ']' Boolean ::= 'TRUE' | 'FALSE' Integer ::= 0, 1, ..., 255 Identifier ::= [a-z|A-Z][a-z|A-Z|0-9|_]* String ::= '"' ~["]* '"'
This grammar describes an iLogo program as a list of commands. A command can be either a MakeCommand, IfCommand, WaitCommand, ForCommand, DoWhileCommand, DoUnlessCommand, MoveCommand, or PrintCommand. A MakeCommand is much like an equate statement in many language. It equates a value to some identifier. The wait command is a primitive which causes a delay based upon the result of the expression. A ForCommand is exaclt like a most 'for' loops. It takes an list which is an identifier, a lower bound, an upper bound, and an optional scale between iterations. The DoWhile Command is also much like a standard 'do-while' loop. It causes a loop until the a boolean condition is no longer true. The DoUnlessCommand was added as an exception-style control structure which executes a set of commands unless an exception condition is met. The subtleties of this new DoUnlessCommand are described in detail in section DoUnlessCommand. The MoveCommand is a primitive for moving the truck in a direction for a specified time and speed. Finally, the PrintCommand is a primitive for generating diagnostic messages from the truck over the serial port. We decided that these primitives were simple, but powerful enough to possibly create larger primitives written in iLogo (such as turning 90 degrees or turning in place).
Expressions in iLogo come in two varieties, numeric and boolean. This gives iLogo expressions only two types, integer and boolean. Expressions are created using Scheme-type parentheses. This approach was used in the earliest version of Logo, when Lisp and Scheme were the hot languages in the computer science field. Using this form of expressions make the parse trees for expressions explicit, and disallows operator precedence which complicates parsing and language usage.
Creating a grammar like the one described above was necessary for using freely distributed compiler tools. These grammars are used as input for tools like Lex and Yacc to create custom lexers and parsers for the languages described by the grammar written in C. Fortunately, we were aware of a nifty tool developed by Sun for the Java language. We decided to use the JavaCC/JJTree tools created by Sun for generating a custom parser for our iLogo language written in Java. Writing our compiler in Java was a big win for us because we could develop the compiler on multiple platforms (UNIX, Linux, Win32) and it would also link well with the visual layer we were hoping to develop for the language later in the project. It was also a big win to use JavaCC/JJTree because we had experience using it, and the turnover rate for creating a compiler using these tools was the smallest. JavaCC and JJTree are freely distributed Java programs, and can be found at:
The result of using JavaCC/JJTree with our grammar was about 4000 lines of Java code which would lex and parse any iLogo program specified by our grammar. All that we would need to add to this would be actions for converting a parse tree into translated a51 code.
Translation of iLogo into a51 assembly takes place in three separate stages:
After the parsing stage, the text version of the input program is changed into a parse tree, which is traversed once each by stages 2 and 3. (Of you are unfamiliar with parse trees, see Figure .)
MakeCommand | \ Identifier Expr | | "i" NumExpr / | \ NumOp Expr Expr | | \ "+" NumExpr NumExpr | | "1" "2"
We were lucky enough to know that every successfully checked program would be translated, so extra information is stored in the parse tree to speed up the translation (such as type information for identifers, max depth for expression, and a collection of string constants used).
The translation stage followed some very simple rules for performing a correct a51 translation, albeit not very efficient. We were not striving for efficiency, but could easily improve the run-time behavior of the output a51 program by adding other optimization phases to the compiler. The rules for the translator was as follows:
After the translation stage is completed, the output assembly file is assembled and linked with the library routines and a special startup file to create the output 8051-specific program. This hex version of this program is downloadable to the truck.
These above rules handle all of the commands and expressions of the iLogo language except for the DoUnlessCommand. This command will execute a list of commands unless a boolean condition is met. If so, control is switched to a new list of commands for handling the exception condition. Figure shows an example DoUnlessCommand which loops forever until the front right sensor is hit, and then prints a diagnostic message:
DO.UNLESS [ DO.WHILE  TRUE ] READSENSOR FR [ PRINT "Front Right Sensor Hit!" ]
startup.a51 starts a polling loop before it calls the compiled iLOGO program. At the start of a DO.UNLESS block, the compiled code enables interrupts and installs the address of the compiled UNLESS handler in _Handler. It also saves the stack pointer in _SpSave; we will see why shortly. When enabled, timer1 generates an interrupt every 255 cycles, which is handled by _PollHandler. After saving a few registers, _PollHandler unconditionally jumps to the address in _Handler.
The generated handler must first switch register banks before doing any work. Then it evaluates it the boolean expression specified in the UNLESS clause. If the condition is false, the handler restores registers and returns normally from the interrupt, allowing the DO block to continue executing. However, if the condition is true, the handler aborts the DO block and begins executing the UNLESS block. This requires a bit of trickery. First, the handler calls WheelOff and Stop to turn off the turning and driving motors. Secondly, the handler restores the stack to the position at the start of the DO block, thus terminating any procedures that might be executing at the time of the interrupt. Finally, it pushes the address of the UNLESS handler onto the stack and calls RETI, thus exiting from the interrupt and passing control to the UNLESS handler. The result of translating the code in Figure is shown in Figure , with comments.
;;;;;;;;;; DO block ;;;;;;;;;;;;;;;;;;;;;;; MOV _SpSave, SP ;save stack MOV _Handler, #HIGH(_H0) ;install handler MOV _Handler+1, #LOW(_H0) MOV TL0, #0 ;enable polling SETB ET0 SETB TR0 _L2: MOV A, #1 ;body of DO block JZ _L3 LJMP _L2 _L3: LJMP _L0 ;;;;;;;;;;;Handler for DO block;;;;;;;;;;;;;;;; USING 1 _H0: PUSH PSW ;save state (some saved by MOV PSW,#(1 SHL 3) ;by _PollHandler in startup.a51) PUSH B MOV R3, #FR ;test boolean condition CALL ReadSensor JZ _L1 CLR ET0 ;if true, 1. turn off timers CLR TR0 CALL Stop ; 2. stop wheels CALL WheelOff MOV SP, _SpSave ; 3. restores stack to MOV DPTR, #_L0 ; start of DO block PUSH DPL ; 4. pass control to PUSH DPH ; UNLESS block RETI _L1: POP B ;if ralse, restore state POP PSW ;(some saved by _PollHandler) POP ACC ;and return from interrupt POP DPH POP DPL RETI ;;;;;;;;;UNLESS block;;;;;;;;;;;;;;;;;;;;;;;;;; _L0: MOV DPTR, #_S0 CALL PutStr CALL Stop CALL WheelOff RET
Manolis was mainly responsible for the low-level routines, that controled moving back and forth, turning the wheels, reading individual sensors, waiting for a number of seconds. He was also responsible for the mechanical aspects of the truck, such as motor speeds and power, mounting switches and bump sensors and reverse engineering the turning control wires, that give feedback on wheel position. Having taken 6.270 and having had experience building robots before 6.115, we was best suited for this job.
Jeremy was in charge of the compiler. He wrote a parser, interpreter, compiler and translator. He found the Berkeley LOGO specification, the javacc tool for building parsers, and he wrote two thousand lines of Java code to make iLOGO a reality really early in the project. This is the fourth compiler Jeremy has written, and he was able to complete his part of the project in time, being already familiar with the development tools he had to use.
Chris was mainly in charge of the PCB. He spent long hours on Protel really early to get the board done, even when other teams had not even finished their schematic. The deadlines we had set for the PCB construction turned out unrealistic, but Chris worked to meet them very closely. When the board arrived, he worked full time once again to get it debugged and running.
However, those three parts are far from making the project complete, and all three of us spent a lot of time working together to integrate the parts. Manolis was doing a great deal of soldering, and debugging on the printed board. Jeremy became an expert of Protel very early and designed part of the PCB. Chris worked both in the low-level routines and the compiler itself, to get the parts integrated.
Looking back, each of us did much more than a third of the project.
Considering the RoboLogo project and team, we realize that we were very lucky. First of all, we were able to achieve our goals, in successfully creating an easy way of controlling interactive robots. Second, even though our separate parts were clearly enough defined to allow individual progress, we all had exposure to all layers of the project, and gained valuable experience.
We managed to finish the project on time, because we set early deadlines, dove right into work, and continued working steadily and effectively. This allowed us to continue making progress and be on schedule, despite drawbacks and unplanned delays. For example, we had not anticipated how long and laborious a process it is to get a PCB laid out, to select the right chip descriptions in our PCB and adapt them to our actual chips, to find the right power regulators, and to correct inaccuracies on the actual printed circuit board.
RoboLogo is a project with many parts that are closely interleaved. This allowed progress on different fronts, without direct dependencies of a part of the project on the completion of another. At all times, all three of us were busy. Manolis was able to write low-level routines and test them on the breadboarded kit, and Jeremy was working on the compiler long before the PCB had arrived. There was always something there to do, and the team was very strong in supporting each other's part, being able to step in and give a hand when help, or simply an opinion was needed. This allowed us each to gain experience about many different disciplines, and have a complete overview of the project.
The RoboLogo project itself exhibited this quality of joining many different disciplines, as a project where custom hardware is best fit in getting things done, low-level assembly routines are suited to the task, but that also integrates a strong software component.
All three of us agree, that this was probably the best team we've had so far. We got along really well, and worked very intensively together.
We are very happy with the development of the iLogo compiler. Although we did not have enough time to cover all the possible control structures and primitives, we did manage to get quite a few translated programs tested with our truck. After the initial setback of not being able to use the Berkeley Logo parser, we were pleased to find how easy and fast it was to develop our own robust parser using the JavaCC/JJTree tools. The object-oriented design of the compiler is also very pleasing to us. Each stage of the compiler is designed using the Visitor pattern described in the book Design Pattern by Eric Gamma, et al. This pattern allows tree traversers to be created as seperated objects, instead of doing all traversals as methods of the nodes of the tree. This keeps the nodes of the tree from gaining a lot of code and allows for state to be saved during the traversal without passing the information along to the separate nodes. It also keeps the parser fairly unblemished from the original and allows for easy extensions later.
The iLogo language itself seemed a great success. The DO.UNLESS construct seemed very well suited. On one side, it fits well with the rest of the Berkeley LOGO specification, and on the other side, it was expressive enough to be a sufficient extension in making a language interactive. This construct in conjuction with the DO.WHILE construct allow for a wide variety of situations to be handled, in fact seem to be universal in expressing interrupts and handling routines. We hope that either us or some other team will have some time in the future to put some more work into the project, for it to possibly have an educational use, and a reach outside the scope of this class. We are thinking of talking to the children's museum and the computer museum, to see if they would be interested in having a similar project to demo for children. If teachers spend a little time with the children, before taking them to the museum for an interactive demo, the tool can be of great help in teaching them both about robots and about programming.
The RoboLogo system is an easy and enjoyable way for children to learn about programming interactive robots. The iLOGO language is a simple but effective language for manipulating the programmable truck. The heart of the iLOGO language, the DO.UNLESS statement, is a new structure that doesn't have an concise equivalent in low-level languages such as C and assembly. Hence developping custom tools, our own language and our own compiler has been justified.
By abstracting away from the direct assembly control of interrupt handlers, RoboLogo makes programming interactive robots not only more accessible to children, but also allows experienced programmers to write more complicated behaviors, while keeping the code cleaner. We hope to see more languages exhibiting similar constructs for handling events and allowing interactivity.
This document was generated using the LaTeX2HTML translator Version 0.6.4 (Tues Aug 30 1994) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -t RoboLogo -dir /afs/athena.mit.edu/user/m/a/manoli/www/robologo/latex2html/robologo/ /afs/athena.mit.edu/user/m/a/manoli/www/robologo/latex2html/main.tex.