Lego of Doom

Turing Machine Demonstration Video

2009-01-28T15:36:00.003+01:00

We have made a short TV Shop themed demonstration of the Turing Machine.

The demonstration is intended to be fun and entertaining while providing idea and intuition of our project and what the Turing Machine can do. It does, as such, not give detailed information on the techniques and theories behind the project. For this, we refer to this blog :)

Pictures of the Turing Machine

2009-01-28T12:18:00.009+01:00

Conclusion

2009-01-26T13:43:00.004+01:00

In the blog about the end course project, we decided that our project would be to construct and program a Turing Machine, a theoretical model of computation described by Alan Mathison Turing in 1936.
The Turing Machine we had planned would consist of three main parts, or functions, to mirror the theoretical design:

A tape of input symbols which also functions as the working tape
A mechanism to read values from said tape at the Machine's current position
A mechanism to alter the content of the tape at the current position

The machine would also have to be able to move back and forth across the tape.

In the weeks following the formulation of our statement of intent, we constructed the Lego Turing Machine Robot to be capable of all these things.
The tape was made physical using Lego train tracks, the input symbols represented by Lego bricks encoding binary values.
Reading from the tape would be possible by the use of movable pressure sensors, which would descend onto the tape to detect the position of each "bit block" in turn.
Writing was accomplished by the movement of a sliding "arm" or "claw" which could move the "bit blocks" from one binary position to the other.

Moving back and forth across the tape was trivial; doing so precisely was another matter. The solution we ended up with uses reactive control to accurately navigate the track. The Turing Machine Robot moves along a strip of alternating black/white squares at the side of the tape by taking readings of it with a light sensor. Two black/white transitions correspond to one shift of binary cell.

Our success in implementing the Turing Machine as a physical device is exciting because the Turing Machine theoretical construct is such an iconic part of computer science. The Robotic Turing Machine is not in itself a practical machine, but it does illustrate the theoretical points made by Turing, and so could easily find application in the field of teaching. Illustrating the theory of a Turing Machine might be made easier with a physical machine at hand to aid in comprehension. Seeing a physical machine performing TM operations can be easier to follow than the typical java applet example and might give a better intuitive understanding of the TM theory.

At the moment, however, the Turing Machine does not completely emulate all facets of the theoretical model. For one thing, we don't have access to an infinite tape. As we do have access to quite a lot of tape, this "problem" is pretty academic.
To fully conform to the theoretical model, we want to be able to position the Turing Machine in one spot and performing calculations from that spot, instead of automatically positioning it at the left-hand side of the tape.
A few further expansions could be made on the robot, given another month or so. The fact that the write and read arms are not positioned over the same cell is impractical and could be rectified by combining the two into one mechanism.
In fact, given enough time, a complete overhaul of the Turing Machine to run on more standard-sized Lego tracks would be useful.
Enhancing the user interface might also be a good idea, since at the moment, running a program on the TM Robot requires some degree of insight into its inner workings.

However, all these modifications are strictly unnecessary as the Turing Machine Robot already runs successfully on many different inputs (including palindrome) and lives up to every expectation we have had.

Optimization

2009-01-20T17:36:00.000+01:00

Date: January 22
Duration of activity: 1 hour
Group members participating: Anders, Mikkel, Martin, Sean
Ignoring redundant write operations

Goal: To make optimizations to the robot in order to make it more efficient during its computations. Our first goal, was to make the robot ignore a write request if it knows that the current cell has the same value as it is going to write.
Experiment - optimizing read/write mechanism
Since the sequence of bluetooth commands is fixed, we know that a write request follows after a read request.
A standard sequence of commands send by bluetooth looks like the following:
- Read request
- Write request
- Move request
We maintain the last value read doing the read requests and checks at the write request if the value is the same, if it is, we ignore the write request internally on the robot. We still send the OK signal back via bluetooth.
Result:
This simple optimization is seen to maximize the efficiency of the robot by a large degree. Before, the robot could try to write the value already present in the cell, but now, it checks whether it should write the new value. Besides being faster, it is also easier to see what is happening since the naive write commands are gone.

Group members participating: Anders, Mikkel, Martin, Sean
Improving the move function

Goal: To move the Turing Machine across the tape, a move function is called repeatedly. This function starts the engine, then waits until the light sensor detects a transition in colour and stops the engine. Calling this function repeatedly means starting and stopping the engine for each transition to be moved, which causes slow and choppy motion in the TM. The goal of this experiment is to improve this code to enhance performance.
Experiment
Since the point is to let the TM move across several transitions without stopping at each, a new move function is implemented. The function, which takes as parameter a count of the number of transitions we wish the TM to move,
With this new move function implemented, it should be obvious whether it has had a positive or detrimental influence on runtime and efficiency. Due to the architecture of the Turing Machine, no further changes should be made to compensate for the new function.

Result:
The effect of the alteration is immediately noticeable. The motion of the Turing Machine is much smoother and quicker, as expected. However, a new concern arises from the faster motion across the track: Will the engine be able to stop "in time" when it crosses a transition?

Group members participating: Anders, Mikkel, Martin, Sean
Compensating for excessive movement

Goal:
In testing the new move function it would appear that the machine is prone to stopping "too late" and ending up displaced by one transition. The error seems to depend at least partially on light conditions, as the light sensor might pick up on transitions too late to allow the Machine enough time to come to a complete rest.
The goal of this experiment is to improve the movement code to compensate for this error.
Experiment:
The experimental improvement works as follows:
If the robot ever slides too far along the track after a move, the light sensor ends up over a square of the opposite colour to what it is supposed to. If this happens, the robot is instructed to move backwards a single transitions. However, "backwards" is not trivially decidable currently, as the error can occur in both directions of motion.
Therefore, we make the following alterations:
The robot always keeps track of the direction given to the last call to the move function.
Before moving, the move method takes a light reading at the current position. After moving, another reading is taken and compared to the first. If the number of transitions to move was an even number, the light readings should match. On uneven numbers they should be different.
If a discrepancy is found, the machine is told to move backwards by one transition. This move too, is subject to correction, so theoretically the machine might never STOP correcting its move, if each move goes too far. We do not expect this to occur, however. The error is very infrequent, especially in small moves.
Result:
Running the Turing Machine robot with the new modification clearly allows it to compensate correctly for faulty moves. Replicating the error is simple, as one can simply force the robot an extra transition forwards by hand, but the correction is also noticeable in standard executions.
With the addition of the compensation modification, the issue of excessive movement has been effectively nullified.

Building the GUI

2009-01-09T17:05:00.002+01:00

Settling on the need for a computer-based GUI
We have discussed at length how big a part of the Turing machine should be handled by the robot and a computer.
Duration of activity: approx 10hrs spread across several days
Group members participating: Mikkel, Martin, Anders, Sean

In the one extreme, the only thing handled by the computer is sending the transition function and input tape to the robot who then carry out all other operations, and finally either writes the output on the tape or sends it back to the computer.

In the other extreme, the computer handles most of the operations and the robot has a more mechanical purpose. In that case, the robot only needs the input tape, and in each step of the operation the robot will read the current cell value and ask the computer what to do next.
The transition function will then reside on the computer, and given the input from the robot, the computer will determine the next action and send the corresponding command to the robot.

We decided to choose the latter, at least to begin with. This decision is based largely on the desire to avoid the added overhead of having to implement a way of serializing, sending and deserialize the transition function to be able to use it on the robot.
Furthermore, this approach will make it much easier to test during development, as we get feedback after each step in the computation, and thus we can easily debug every action the robot carries out. We have planned on implementing the Turing machine as abstractly as possible to allow for various degrees of computer/robot relationships without too much trouble or repeated code.

In either case, we will need some kind of graphical user interface to be able to input data for the Turing machine, and to be able to transfer the data to the robot. To this end, we decided to build a simple Java GUI application using Swing.

The requirements of the graphical user interface
The GUI should allow for various settings and configurations of the Turing machine in addition to specifying the input tape and output values.
Examining the parameters that are required by the Turing machine and the functionality that we would like to have, we arrive at a preliminary number of options that should be available through the GUI.

The basic options required in the GUI are the following:

Number of bits per cell
This option is for specifying the number of bits that each cell contains, and thus the range of values that the cell can contain. For instance, specifying 1 bit per cell thus allows for {0,1} in the cell and specifying 3 allows for {0,1,2,3,4,5,7} in the cell.
Input tape
The data to be written on the tape before execution begins. This data must conform to the cell size, so that no cell has an input value less than zero or greater than 2^i-1, where i is the specified number of bits per cell.
Working tape/output tape
In addition to the input tape, it would be nice to have a continuous display of the working tape during execution, and finally of the output tape when execution has ended.
Transition function and functionality to load from file
Naturally, we also need a way of specifying the transition function that will form the foundation that the execution will depend upon. This transition function is based on a format detailed elsewhere. Furthermore, we will like to be able to load the transition function from file in addition to inputting it manually.
Button for running
We need a button for activating the execution of the Turing machine.
Option for selection which device to run on; the computer or the robot
This functionality should be for selecting whether the Turing machine should be executed on the computer or the robot. The primary reason to allow execution on the computer, is to test and debug transition systems before having the robot carry operations out on them.
Speed of execution
We would like to be able to control the speed of execution, both on the computer and the robot. On the computer, this will be important to be able to continuously monitor the execution on the tape, instead of just executing so fast that the output is available instantaneously (in case it doesn't loop). On the robot, it will be nice to be able to set and run at different speeds, slower to allow close observation of its operations, and faster to speed up execution.

Below is a screenshot of a preliminary layout of all the above mentioned controls and options required.

It is however, still lacking most of the functionality, so this is still to be implemented. We will strive to have the GUI be a thin a layer as possible as it should only invoke the other modules responsible.

Initialization & testing of the Input tape

2009-01-07T12:30:00.001+01:00

Date: December 5
Duration of activity: 3 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To implement a functional Initialization method on the robot that knows how to find the leftmost cell and how to setup the inputtape. It should be possible to send an "INITIALIZE" signal via bluetooth, to make the robot run the method.
Experiments: Before the Turing machine can start on the computation, we need to setup the input tape. We had a little brainstorm on the topic, and we discussed whether to setup the inputtape manualy or letting the robot handle it. We found that the robot should be responsible, since we could use the move/write methods to implement the behavior.
As the first part, the robot should be able to figure out if it is positioned in the middle of the tape or to the side of it. Before we read the bit at the initial position, we have to look if we are positioned on a black or white surface. If we are positioned on a black area, we move on position the left, then read the bit value. If there is a bit at the location, we move left until we spot a cell with no bit in it, then move (cellSize-1)*2 intensitychanges to the right. (The robot's read head is position over the least significant bit in the first cell). If the robot is located to the left of the cells that contain bits, we move right until we spot a bit, then (cellSize-1)*2-2 intensity changes to the right. At present, we do not handle that the robot is positioned to the right of the cells.

When the robot is located at the leftmost cell, we send write and move signals to the robot via bluetooth. In a iterated process, we write the i'th value to the current cell, then move to the right cell. We continue until we have written the last entry in the input tape.
When done, we send an "OK" signals to the computer.
Results: At first, we ran into some trouble since we did not handle the two starting positions of the Turing Machine, as described above. It meant that the robot did not position itselft correctly on the tape and was off by either a half step or a whole step, based on the starting position of the TuringMachine.

At the present state, the initialization method has been implemented and should be called from the computer that is responsible for handling the abstract turing machine. At the moment, the computer is responsible for setting up the input on the robot by sending the move and write signals via bluetooth.
In the future, we would like the robot to have a method that sets up the input tape. Then, the computer only need to send setup signal and the array of tape entries to the robot via bluetooth.

Bluetooth communication

2009-01-04T14:01:00.001+01:00

Duration of activity: approx 8hrs spread across several days
Group members participating: Mikkel, Martin, Anders, Sean

Goal:
We needed some underlaying structure to handle our communication between the NXT Turing Machine and the PC controlling it. This structure should support handling the communication between the robot and computer. For instance, we need instructions like:

Read cell
Write cell
Move left/right
Initialize the input tape values
Setup parameters for tape size, motor speed etc..
(Transition function)
Commands for testing individual parts of the robot

Experiment:
To ease the development we used the Composite pattern and made it event based. When it received an event, it should send that event to the listeners function for handling that specific event. This makes it easy for us to add new event types later, if we need more, and we can also implement the functionality part by part.
The listener implements an Interface that specifies which functions that handle the events we have implemented. To implement a new type, we add it as an enumeration value, and tell what function in the Listener interface it should call when it should notify the listener. The event is always built up by a Short containing the event type, and a Integer with the value. If we have a function that doesn't take a value (like read), the value is just set to 1, and ignored by the implementing function.

When starting the Turing machine program on the NXT, it enables the Bluetooth and waits for a connection with a PC. On connection, it creates two streams, a DataInputStream and a DataOutputStream. Now it starts a thread that listens to the input stream, and when it recieves data, it creates events for them, and sends them to the listener.

We have chosen the PC program, to be the one searching for the robot, and setting the connection up, as this requires a lot of different objects to be set up and activated, and we would like the robot to do as little unnecessary work as possible. Then it has private send and receive methods, to send events to the robot.
We have implemented simple methods to send read and write events, as these are often sent, and therefore should be easy to come by.

Results:
The first events we implemented were debug methods to check how many tachos the motors should rotate for the reader and writer. Also speed of these debug methods were implemented. When we had these functions going, a big error showed up. If the next event was sent before it was ready to receive it, it would be ignored. Not the behavior we wanted. This meant we have to make sure it was ready to get another event before the PC sent one. This was done by making a new event, called OK, that should be sent back when it was ready to get a new event. The only event now sending back an OK is READ, this sends back an READ_ANSWER instead.

Internal operations on the robot

2009-01-02T17:03:00.004+01:00

General observations:
The class which resides on the NXT is responsible for the methods that interact directly with the motors and sensors. That is; reading, writing and moving. These methods have been implemented in the class Robot.java.

Basically, since the light sensor is positioned above the black track markers on the left side of the track, we use it to detect changes in light intensity, which tells us that it has moved from one black square to a space between squares. The move method turns on the motor and drives forwards as long as no change in intensity is detected.

The reader arm is five intensity changes away from the writer claw, so some maneuvering is required between reading and writing.

When the read method is called, the robot swings the read arm down to read the first bit, then moves two intensity-changes (one bit) forwards and reads the next. When it is done, it resets its position over the bit.

The writer operates in similar fashion, save that it swings back and forth across the track depending on the type of bit that needs to be set.

Since the move method keeps the motor on until there is a intensity change in the light sensors reading, it is built upon reactive control. We have not used an approach where we observe several readings before judging whether or not an intensity change has occurred. The observations of this straight forward implementation gives a solid picture that the robots behavior is indeed correct.

The model of movement is quite solid, even though that we are not positioned directly above the bit when we have to make a reading. When the read head is extended, it only touches the LEGO bits by half of its surface, as can be seen in the videos posted.

The amount of movement required to read/write was experimentally established previously.

Test process
The read/write mechanism, has been tested locally on the NXT by making a simple test method in the robot class that is called on execution. Here, we hardcode the transition function by simple calls to read, write, and move.

Duration of activity: 2hrs
Group members participating: Mikkel, Martin, Anders, Sean

First experiment:
Goal:
Testing the read mechanism.

Experiment:
We started testing the read method, by doing iterated tests on the cellSize. At each iteration, we gathered information on the correctness on the value read, the movement between individual bits and the movement back to the least significant bit (the start position of a given cell). We also tested that the conversion from bits to integers was indeed correct.

Results:
During the testing of the read mechanism, the touch sensors gave us a bit of a problem. How long do we have to rotate the motor, and what cell position equals one and vice versa. Earlier we tested the rotation of the motor with a Bluetooth connection. When the touch sensors extend, they have to be able to read the correct position of the bit. The problem was, that we had not come up with a convention that says which positions equals what. This is discussed in a previous blog entry.

To avoid the same mistake again, we chose to use sounds and the LCD display to play/display output during a test run.

Second experiment:
Goal:
The write method was tested in the same way. The primary differences are, that we need to convert from integers to bits, which is a little bit different than making the conversion the other way around, and that the rotation of the motor has to be more precise.

Experiment:
We have made the write method be responsible for checking that we do not write the same value as the last read value, and that we do not try to move a bit to the same position as it is in. At present, to test the first functionality, we manually have to set the input tape to a given value and then try to write the same integer.

The second case also requires that the tape has been set manually. It is a success if the robot "skips" the bits that do not have to be moved.

Results:
The write arm functions as expected, no further observations made.

Conclusion of the tests:
In testing the above we have found that it is sometimes difficult to determine when the Turing Machine fails and why.
We have been thinking about making the Turing Machine a little bit more responsive the value it reads and writes to the tape. To achieve that, we have had a look at the Sound.java class which have the functionality we are looking for. At the moment, if the robot reads a bit with value 1, it plays a positive beep sequence. On the other hand, if it reads a zero, it plays a sad sound. This information is also a good supplement in debugging, since we know what the robot reads and writes.

Calibration of the Read/Write motors

2008-12-22T12:51:00.002+01:00

Experiment: Moving the write claw by tacho.
Duration of activity: 4hrs
Group members participating: Mikkel, Martin, Anders, Sean
Goal
Calibrating the claw to move exactly enough to shift a Lego bit block from one side of a cell to the other.

Plan
Using the tacho counter we plan to move the engine controlling the write claw by different amounts, to simply establish how many tics on the tacho counter it takes to move the claw from one side of the track to the other, without "grinding" the engine or knocking over the lego block and without leaving the lego block halfway across the track.

Results
To adjust the motion of the arm, we contructed an experimental test program which allowed us to set the movement amount by bluetooth connection.
We tried a number of different values and, using a basic binary search approach, eventually homed in on a set amount by which to rotate the engine controlling the arm.
Mechanically, the write arm is heavily geared down, which means that it moves quite slowly in relation to the engine and offers greater accuracy. It is therefore quite feasible to control it by engine tacho count. Due to the low gearing, the arm does not move significantly out of alignment during program execution, and inital tacho values can be relied on throughout.

However, once we had found a suitable tacho offset, we found that even though the arm moved exactly the width of the track, it would occasionally knock over the bit blocks, rendering the "tape" unreadable.

Furthermore, in using the bluetooth connection to transfer orders to the experimental program, we found that the way the robot received orders from the PC was prone to "dropping" messages if it was already working on a previous order at the time of transmission.
This basic problem of distributed systems we had simply had not anticipated initially.
We are planning to handle it by letting the NXT send a "ready" signal to the PC when it is done executing an order. This way, the PC won't send messages to the NXT when it is not ready to receive them.

Experiment: Improving the claw mechanically
Duration of activity: 2-3hrs
Group members participating: Mikkel, Martin, Anders, Sean
Goal
The mechanical implementation of the claw causes faults when writing; bits fall over and become unreadable when switching the claw from one side of the track to the other. The goal of this excersize is to modify the design of the write claw to avoid this.

Plan
Examining the claw, it appears that one cause of the problem is that the horisontal alignment of the claw is somewhat unstable. It is clear that the instability is caused by the way the claw rests on the rotating worm gear. Since they are connected by a single, small gear, and stabilized by no other factor, the claw has a tendency to wobble, which causes the fault. The plan is, then, to redesign the claw with this in mind, giving it a wider area of contact with the worm gear. The diagram below illustrates the basic idea.
Additionally, the original claw is built of slightly rounded parts, which means that the area which presses against the side of the bit blocks is smaller. This in turn means that the force applied to the bits is applied further up. Since the bottom of the brick scrapes against the surface below, the bricks are more prone to "trip" the further up the force is applied. The claw must therefore also be modified to have a larger area of contact with the bits, as shown in the diagrams below.

Previous claw design

New design

Result
Modifying the claw in this fashion proved quite difficult, from a mechanical point of view. Since the claw needs its full range of motion across the track, there is little room to add stabilizing structure around it.
In the end, we settled on a design which places a gear rack (as pictured above to the right) against the front of the worm gear, where it wouldn't interfere with the motion of the claw.
Also, the contact area was increased by replacing the rounded lego parts with standard flat blocks.

With these improvements, the machine no longer tips over bits as it did before. If stopped in an improper configuration and then moved across the tape, it is still possible for the TM to knock over bits. In a standard execution, though, it is no longer an issue.
The instabilities are now no longer noticeable, and the increased bit contact area has had an obvious effect on the stability of the bit blocks.

Software Architecture of the Turing Machine

2008-12-21T15:10:00.002+01:00

Duration of activity: discussion across several days
Group members participating: Mikkel, Martin, Anders, Sean
Goal: Achieving a flexible and modular software architecture for the Turing Machine system.

Plan: We are planning on utilizing acknowledged techniques from the area of object oriented software architecture to make the system modular and extensible. Specifically we'll use design patterns to make an abstraction of the Turing Machine and having the implementations hereof deal with the details.

Results: Our initial idea was to make a completely abstract Turing Machine that only had functionality for the primitive operations such as reading and writing cells and moving the head. Other concrete implementations would then have the responsibility of implementing the corresponding functionality for the primitive operations (ie. the Template Method pattern). Thus it would be easy to make different implementations, eg. one running on computer and one running on the NXT robot. This allows for easy debugging and less error prone code for the concrete implementations.

The object structure and relationships that we decided to use is illustrated in the UML diagram below:

TuringMachine is the abstract class defining the interface and structures that is required for the Turing Machine to have sufficient functionality. In our project, we have made two implementing classes; TuringMachinePC and TuringMachineRobot which are the versions operating on computer and NXT, respectively.

TuringMachinePC handle the operations internally as the data is represented on the computer, and TuringMachineRobot consists primarily of invoking the primitive methods on the robot via Bluetooth messages.

A central part of the design of the Turing Machine is the transition function that specifies the actual operations performed by the machine given a state and a cell value. This we have represented in the class TransitionFunction. This class has a number of State objects, each symbolizing a state in the automaton that make up the transition function. Additionally, the State object has a number of Action objects that maps a value to an operation, thus enabling the Turing Machine to query the next operation given a state and a read value.

In order to get a continuous feedback on the execution of any Turing Machine, we created a listener interface based on the Strategy pattern. Hooking this listener to a Turing Machine will cause the listener to be invoked after each step in the computation, and provided with data regarding the current configuration. This means that we can setup the listener to update the graphical user interface whenever the Turing Machine operates, no matter whether the implementation runs on the computer or the NXT or elsewhere. We use this information eg. to update the "working tape" of the GUI to reflect the actual working tape of the configuration.

Conclusion
The architecture proposed has several advantages. First, it allows us to have a very abstract representation of the Turing Machine that only has the bare-bones functionality such as reading, writing and moving the head. Furthermore the chosen architecture allows us to make new concrete implementations of the Turing Machine with minimal effort. Thus this approach satisfies our initial needs for what problems the architecture should help to solve.

Tape conventions

2008-12-14T11:09:00.001+01:00

Duration of activity: 1.5hrs
Group members participating: Mikkel, Martin, Anders, Sean
Goal: Establishing general conventions about the tape

Problem: How are bit-patterns represented on the tape?

In our first test implementations, we experienced a lot of confusion with the order of bits. Early on, we agreed that "right" and "left" on the tape are determined from the point of view of a person reading the display on the NXT, i.e. from the side of the track that does not have the black cell markers which are used for navigation.
In our early tests, we had the least significant bit to the left, in defiance of convention.
We soon found this to be both problematic and confusing, and opted to follow convention instead. This meant rethinking some of the calculations we make to move the robot around the track. See the below for particulars.

Finally, the following diagram illustrates the conventions that we have (somewhat arbitrarily) chosen for the TM and its tape.

Problem: The robot's read arm and write claw are not centered over the same cell. Which sensor rests over the active cell at what times and how do we maneuver back and forth to read/write the correct bit?

The calculations used to solve this problem arose from a thorough study and contemplation of the track layout. In other words, we simply counted cells.
Recall that the track is divided into cells, and that each cell is identified by the light sensor by the presence of a black marker on the marker track at the side of the tape. Moving away from one cell to one side or the other is therefore a transition in light value from black to white. Moving from one cell to the next is therefore two transitions, one from black to white and one from white to black.

The first observation (or design decision, if you will) that we made was that the write claw is five transitions away from the read arm.
The second was that for a cell size n, that is, when the number of bits that comprise a symbol on the tape is n, the robot has to move (n - 1) * 2 transitions on the guide markers to move the reader or the writer from the least significant bit to the most (and vice versa).

Constructing the Turing Machine

2008-12-07T16:40:00.007+01:00

The design of the robot is the product of several iterations. At first we wrote down what requirements we had for the robot. We needed a tape with an available alphabet. We also needed that the robot could move on the tape, read from it and manipulate it.

To make a rigid tape we used the old LEGO train tracks for the tape. This meant that the robot was able to move forward and backwards without us worrying about the robot moving out of alignment and reading the bits wrong. Our first idea was to build the robot from a LEGO train and then have the bits positioned next to the train. We would have like to have tape underneath the reading head, however that was not possible in this approach. So here our problem was that we had no idea how to read and manipulate the tape.
The next idea was to use a mechanism that used bits in the form of bricks and placing these in a booth or removing them. The idea looked like a too big project and instead we considered making a tape with statically placed bits on the track where each bit would represent 0 in one "left-most" position, and 1 in the "right-most". Thus all the available bricks are on the track initially and we only need to move between the 0 and 1 position. This way we couldn't make the tape longer over time, but in the old model there was still a maximum amount of bricks to move. Now we had a much simpler mechanism to build that should only move a brick from one position to another. This approach also meant that we had to have '0' represent the empty cell, and this therefore decreasing the data the bits in the cell could represent by one value.
Next problem was the reader. We decided to use s stack of 2x2 bricks to represent bits, and move them to each side of the train tracks. We tried to use light sensors to read the position of the bit, but tests showed that this approach was highly unreliable and dependent of lighting conditions. Instead we used 2 touch sensors that we would move down on the bits and register which sensor the bit was underneath. This setup required that the tracks was 1 LEGO unit wider to get the sensors to fit by each other. As our train tracks are the 80's 12V tracks, this was an easy adjustment because they consist of single track pieces.

Now we had simple reading and writing mechanisms and a representation of the tape. These now had to be connected into one robot. As we now had to drive over the bits on the tracks, and it was wider than the original tracks, we couldn't use the original train motors. The first iteration of the robot as shown, is elevated over the bits and is wide enough for the reader but not long enough for both the reader and writer.

The biggest problem was the writer. It has to be controlled with a 1 width brick, span over 5 and be able to move 3. The first working writer made us rebuilt the base of the robot, but now we could built a whole robot that could do what we needed.

We now had to place the mechanisms on the base and also have room for motors them and one for moving. None of these motors should block for the bits while moving, so we had to elevate them and use gears to move. The first motor was the one for moving, simply placed in the one of the ends and going upwards to use as little space as possible. Now the writer was added in the other side, and the motor placed close by also in a standing position. The third motor placed just beside to make it symmetric. Then we made room on the other side of the motors to the reader, and connected it to the other motor. To stabilize the motors we connected them using the NXT and fastened it. Now we had a working Turing Machine, just without code.

Optimizations to the robot
The robot was built up by modules which made it easy for us to remove a single module, rebuilt it and place it again without disassembling any other part of the robot.

The first optimization made was to the wheels, they sometimes jumped over ticks on the cogs. We tried a lot of different cog sizes, and tried many methods for keeping them together. We ended up using gear chains, as these made it more stable.
The reader also had problems with gears jumping, mostly due to the fact that there didn't exist gears that fit with the distance we needed. Even gear chains didn't fit here. This was fixed later by using more cogs, and fastening them on both sides. It changed the direction the motor had to move, but fortunately this could be fixed by negating a constant in our program.

The writer was our biggest problem. It used to tip over bits when moving them and didn't always move back to the start position, making it move in to the other bits while moving, causing it to stop or pushing bits in to some of the other bits' room.
The optimized writer used a gear rack to stabilize it and used old "LEGO Technic" parts to make it longer, thus pushing with a larger area. It was also constructed using bars, so we could adjust the distance between the arms more precisely.

References:
Turing Machine on Wikipedia

Build Guide:

Newest design

For use in LEGO Designer

Turing Machine Architecture

2008-12-01T13:31:00.020+01:00

This post describes the general discussions we have regarding the architecture of the Turing Machine robot.
Participants: Anders, Martin, Mikkel and Sean

Topics of discussion regarding the architecture of the Turing Machine.
In this log entry four central problems are presented along with the gist of our discussions on the topics and, in some cases, suggestions for solutions or concrete implementations.

Blank input symbols.
Problem: A Turing machine has an input alphabet and a blank symbol in its tape alphabet. Our Lego tape can only hold two different symbols (represented by shifting a Lego block to the right and left sides of the containing bit field). We cannot currently represent a blank symbol with a Lego brick.

One solution would be letting more than one Lego bit blocks represent a single character in the input alphabet. With two bits we have four possible symbols, or three input alphabet symbols and a blank symbol. We plan to use a binary input alphabet, which leaves us with an "extra" bit configuration if we use the idea of two bits per symbol. Using more bits would enable us to represent decimal numbers or even alphabetical A-Z symbols.
We will need a couple of methods to handle bits. When reading an input character that stretches across several bits, we will be reading the bits one at a time, and we will need a method that takes this stream of bits and converts it to a symbol in the input alphabet.
When writing, we will need to reverse the process, converting a symbol in the input alphabet to a stream of bits.

Reading, sending.
Problem: We plan to distribute the complete functionality of the Turing Machine across a PC and the NXT via Bluetooth connection. At which end does computation take place, who waits for signals and when?

The initial idea for control-flow went as follows:

Write initial tape configuration to the tape
Read the initial state
Send value to PC
React to answer (from PC)
Repeat steps 3-4 until a halting (accept or reject) state is entered

The NXT idles while waiting for a movement signal from the PC. When this is received, the PC waits for a confirmation signal from the NXT while it maneuvers the robot into position over a cell/bit, reads it and sends its contents.
In this model, the PC performs the Turing Machine computations and simply sends movement, read and write calls to the robot.

The PC could also take a hands-off approach, and simply starts the Machine by sending the transition function to the robot which performs all calculations and movements independently on the NXT.

Due to the limitations that the NXT imposes on java code, we have found that keeping a lot of the calculations on the PC might be easier to implement.
More specifically, it appears that maps aren't supported. Our implementation of the transition function uses two maps, one for states and one for input symbols. We find this to be the most intuitive and natural way of representing the transition table.

Converting bits to integers is simply a case of adding 2^i to the result for the i'th bit if it is 1.
Converting integers to bits is a question of taking the remainder of a division by 2 and the dividing the input by 2, rounding down, until the input is 0.

How are states represented?
Convention: What Turing called m-configurations, that is, the part of the Turing Machine that tells it what to do depending on the current input symbol, we have decided to call states, to avoid confusion.
Turing's original state concept has not been renamed, to increase confusion.
Concrete implementation: States are currently represented in the code as a map from input symbol to Action tuples, an Action tuple being a three-tuple of actions to perform on the given input: what to write, which way to shift and which state to enter next.

Initial state in input file?
Problem: We want to be able to give the transition function of the Turing Machine as input, but how do we know which state is the initial state and which states are final?

One solution to the first problem is simply to demand that the first state in the input always be the initial state.
The final, or halting state doesn't need a separate state in the input. Rather, we allow states to point to a next-state "HALT" which doesn't exists in the input. This we are able to do since we know that no actions can be taken once a halt state has been entered, and so we do not need to keep track of the information pertaining to the actions in the halt state.

Week 12 - End course projects

2008-11-27T14:21:00.011+01:00

The purpose of this lab session is to discuss various candidates for our final End Course Project. For each suggestion we will discuss what sort of architecture would be used and what problems might be involved.
Here is a list of brief idea descriptions:

Synthetic creatures. Robot or robots trying to mimick simple insect-like behavoir.
Balancing "butler" robot. A robot which is able to drive across rough terrain while keeping a part of itself perfectly level. The purpose would be to carry a drink without spilling.
Room Mapper. A robot that maps the boundaries of a room by way of (for instance) the ultrasonic range sensor and a steady form of motion.
Turing Machine. A lego robot which emulates the action of a Turing Machine on a finite tape made up of Lego train tracks.

The "Synthetic creatures" robots would be an exercise in trying to build robots that act like primitive insects-like creatures. This project would include modelling simple behavior for searching for food, avoiding obsticles and dangers, sleeping etc.. It would be based largely on the ideas for insect-like robots presented in the lectures and articles on behavior by Thiemo Krink.
Further development could include adding more robots and creating a reasonable interaction between them. They could, for instance, inform others of found food, dangers etc. and have boids-like behaviors that makes them flock and move together.

The "Butler" robot would be largely an excercise in balancing, much like the balancing robot discussed in the course. The main problem is that it is no longer possible to gauge balance by looking at the distance to the ground, since the robot will be traveling over rough ground. Thus a new sensor type would most likely need to be incorporated (acceleration, gyroscopic).
Lots of parameter-tweaking is probably to be expected.
Presentation of this robot would obviously be to have it drive up with an open Coca Cola and present it to, for instance, the lecturer of the course.

The "Room Mapper" would use the distance sensor to gauge distances to its surroundings. It would drive around a room, hopefully completing a closed circuit while measuring distances at each point. Finally, the data it captures could be used to reconstruct the room for whatever purpose. One example might be allowing a lego robot to traverse the room more efficiently, for instance, as discussed in the example project page. Active elements might be added to make waypoints for this bot.
Problems involved include keeping accurate track of the robot's position in the room. To mitigate this, a more precise control method would have to be implemented. The robot might only be able to make turns "on the spot", for instanced, using other methods than the wheels, to avoid changing position and direction at the same time.
Inaccuracies on the distance sensor would also have to be taken into account.
Finally, the algorithm that compiles the data to a model of the room could prove tricky to implement.
Demonstration of the Room Mapper might be accomplished by constructing a small "room", using cardboard obstacles and simple NXTs as active elements or similar. The room mapper would map the room and would then either display the computed map somehow (by bluetooth transmission to a PC) or it would demonstrate that a traversal of the room could be computed from the data it had gathered.

The "Turing Machine" will need to traverse a track of some kind, reading marks on the track and altering them.
Reading and altering bits on a track entails three things: Detecting that the machine is over a cell, detecting the state of the cell and altering the state of the cell. These three problems will each be solved by careful application of various sensors. Many solutions exist for each problem and much experimentation will be needed to find out which yields the most stable results.
Architecturally speaking, the Turing Machine robot could be in contact with a PC via bluetooth connection. Via this connection, the robot could leave some calculations to the PC which would send back instructions. One example of this could be that the PC handles all the "boring" Turing Machine calculations while the robot itself could be in charge only of cell and bit state detection as well as motor control.
The main part of this project would be getting the robot to accurately read and set the bits on the track. The implementation of the turing machine itself is trivially accomplished. The "meat" of the project is embedding the program in a machine that actually performs computations in a physical environment.

Having discussed the above options for end course project, we have decided to build the Turing Machine as our end course project. This project seems both feasible and interesting: Feasible, since it requires no "exotic" sensors, all detection can be accomplished by either light or touch sensor, and interesting, because the Turing Machine is such an iconic part of Computer Science. Building a Turing Machine in Lego would make Lego Turing Complete, which is an interesting consequence in itself.
Furthermore we anticipate that working with the robot and making it precisely manipulate the "tape" will prove challenging enough to give us a lot of material for discussion in project logs.
Depending on how we implement the tape (and thus, the length of the tape available) we will be able to have our robot perform all sorts of simple calculations, from palindrome to "busy beavers".

The other projects we have discussed each had shortcomings in relation to the Turing Machine project.
The "Synthetic Creatures" is an interesting idea and would be fun to implement, but the most interesting aspect - the group interaction - seems very troublesome to implement so that it works in pratice, especially the boids behavior. Besides which, we feel that this idea has already been covered in previous years, and we'd like to make a more "unusual" project.
The "Butler" hinges too much on the availability of special sensors to measure balance.
The "Room mapper" presents too many technical difficulties in precisely tracking robot position, we might end up with hitting a limit on precision due to either robot motion or sensor accuracy.

Week 11 - Behavior

2008-11-20T15:43:00.016+01:00

Date: November 21
Duration of activity: 2 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To examine, analyze and discuss the details of the example "BumperCar" project that utilize the leJOS subsumption API to implement a behavior-based control architecture.
Results: We will now answer the questions that relates to the inner workings of the example project.
- Press the touch sensor and keep it pressed. What happends ? Explain.
  Most likely the car will never try to drive forwards, but will continue to back up, since HitWall will always return true on TakeControl() and has the highest priority besides.
- Both DriveForward and HitWall have a method takeControl that are called in the Arbitrator. Investigate the source code for the Arbitrator and figure out if takeControl of DriveForward is called when HitWall is active.
  Yes, takeControl() is called from Monitor. However, even though DriveForward is the only behavior requesting control it isn't granted control because HitWall is still active and has higher priority. As soon as HitWall is finished, DriveForward will be granted control.
- Implement a third behavior, Exit. This behavior should react to the ESCAPE button and call System.Exit(0) if ESCAPE is pressed. Exit should be the highest priority behavior. Try to press ESCAPE when HitWall is active (hint: set the back up time to 10 sec to be sure HitWall is active when ESCAPE is pressed). The Exit behavior is not activated immediately. Why (hint: look in the Arbitrator) ? Can it happend that HitWall continues controlling the motors even after the suppress method has been called from the Arbitrator (hint: the answer is yes, explain) ?
  The while-loop in the start() method waits for the last call to action() to complete before calling the next action() method, regardless of whether the last behavior was suppressed or not. The action call of HitWall contains a call that sleeps the thread for one second, so before HitWall is done executing chances are that the Exit bottom is unpressed and thus Exit does now not request control.
- Implement a fourth behavior PlaySound that react to the ENTER button and play a sound when the ENTER button is pressed. Insert an instance of this behavior in the Behavior array between the instances of Drive Forward and HitWall. Now Drive Forward has the lowest priority, PlaySound is next, then comes HitWall and Exit has the highest priority. Activate HitWall by a touch sensor press. While HitWall is active press ENTER and then ESCAPE. What happens ? Explain.
  PlaySound is given high priority by the Monitor when Enter is pressed. It does not, however, interrupt HitWall, since it has lower pirority. If Escape is pressed before the Monitor has a chance to reassign priority (giving it to DriveForward if both keys and the sensors are unpressed) and while HitWall is still running its action() it will interrupt PlaySound but not HitWall.

Week 10 - Navigator

2008-11-17T11:12:00.012+01:00

Date: November 15
Duration of activity: 2 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To create a Lego car from the instructions in Brian Bagnalls Maximum Lego NXTBuilding Robots with Java Brains, Chapter 12, and to implement a navigator/"BlightBot" who can find its way around.
Plan: We plan to start out by building the LEGO car from the exercise. When this is done, we'll implement the Navigator program and test it according to the test on the lab assignment. Furthermore, we plan to make additional tests to get a feeling on the error in the navigator.

Problems encountered: We had some minor problems with regard to the construction of the robot. The sketch was quite poor, which meant that we had to guess a couple of times which ended up with parts that could not be assembled

Experiments & results: The implementation of the program went quite smoothly. Since we build the robot from the article, we decided to use the parameters mentioned. We revised the "goTo" test by dividing every number by a factor of two, so we could test the robot in our office where the floor space is a bit cramped. The goal of the program was to have the robot return to its initial position after completing the assigned route. Results of the test showed that the robot returned to the start position, and was only off by approximately 1 cm. We did the test multiple times, and the result was the same.

To test if the parameters was set at correct value, we toyed around with the arguments. Trying to tweak the parameters only resolved in a larger error between its starting and ending position.

As a last test we decided to test how the robot would manage a longer route that also involved more turns. The route that we devised for the robot to travel was arranged in 10 rows, 10 cm apart. The BlightBot thus had to go 10 cm forward, then right for 1 m., then left for 10 cm., left for 1 m. and so on.
When the robot reach the end of the last row, it goes back to the starting position. The error is the difference between the start and endpoint. Unfortunately the error was about 20 cm. We tried tweaking the parameters, but to no avail; it only increased the error.

In conclusion it's pretty clear to see that the TachoNavigator class and the technique of using the tacho counters has its merits, but it also has some disadvantages. On the plus side, it can be used to quite accurately find its way back on simple routes. On the other side, once the route gets a bit complicated or involves too many turns, the acuracy quickly drops. This corresponds quite well with Brian Bagnall experiences with this technique as he noted that "(...) his [the BlighBot's] weekness arises when he rotates".

Further improvements could involve more tweaking with parameters, or perhaps continously calculating an estimated probability of the robot to arrive within a certain distance from the starting position. Another possibility could involve other auxiliary sensors, for instance in the form of fixed stations where the robot can synchronize its position. This could perhaps even generate some statistics on how the synchronized position corresponds to its believed position and be used to "train" the robot to learn to calibrate for its error.

Week 8.b - Driving towards light

2008-11-07T11:57:00.006+01:00

Date: November 7

Duration of activity: 3 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To implement the SoundCar from Lesson 8 and to add extra behaviors the the model.
http://www.legolab.daimi.au.dk/DigitalControl.dir/NXT/Lesson8.dir/Lesson.html
Plan: We plan to fetch the available source code, and add extra functionality, "Drive towards light".
Experiments & problems encountered: In order to implement the extra behavior, we had to spent some time looking at the code. One thing becomes clear. It does not look like a subsumption architecture but rather an inhibit mechanism controlled by a boolean, "Suppressed".

Another thing is, that for every behavior, the constructor takes n arguments, the behaviors to suppress. This could be done more elegantly, ie. a list of behaviors. Since the program is structured this way, it is necessary to modify a lot of existing code, which should be avoided.
Results: We had to decide where to put the "Drive towards light" behavior in the model. We chose to make it the highest priority and make it suppress the other behaviors.

On the matter of understanding the LCD output, The LCD write a "1" to the right of the behavior if it is being suppressed and a "0" if not. When the "drives towards light" behavior is running, the display reads 1 on all other behaviors, since the drive behavior has the highest priority.

Week 8.a - Breitenberg robots

2008-11-07T10:43:00.003+01:00

Date: October 31

Duration of activity: 3 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To implement and test the three types of Braitenberg robots and observe how they react to light sources.
Plan: We plan to implement the Breitenberg robots as explained and detailed at the lectures and in Introduction to Machina Speculatrix and Braitenberg Vehicles.
We will use the Datalogger class from the Lejos framework to get the light and power settings plotted to a graph. The assignment is located here: legolab.daimi.au.dk/DigitalControl.dir/NXT/Lesson7.dir/Lesson.html
Experiments & problems encountered: The implementation and testing phase went quite smoothly.
At first, we used both a NXT light sensor and a RCX light sensor (as the other NXT light sensor was used in another robot). This proved a bit troublesome however, as the different readings were hard to compare. To be sure that the readings of the two sensors were matching we ended up prying out the other NXT light sensor and using that as well.

To test the different programs, we decided to use two light sources displaced on the floor. Then, for each of the three programs, we started the car from the same starting location. The results can be seen in the results section.

Results: We have used a direct linear mapping between the light reading and the power setting of the motors. We have implemented two applications, one which uses a direct mapping between the sensors and actuators, and one that has a cross mapping, meaining that the left sensors input is sent to the right motor and the right sensors input is sent to the left motor.

The first car drives forward as long as there is sufficient light. The second car tries to get near the light source, and the third, wants to get away from the light. This makes sense in regard to the mapping between light input and motor control.

Week 7 - Robot race

2008-10-09T12:00:00.008+02:00

Lesson 6 - The Robot Race

Goal
Our goal this week was to build and program a robot which would "win the race", ie a robot that follows a line as fast as possible. We took this challenge to mean that the robot should be able to follow any given line (black on white background) from one end to the other as closely as possible and in as little time as possible.

Plan
Our hypothesis was that we could accomplish this with a robot design based on a modified version of the standard robot as described in the NXT set manual. That is, a robot with two powered front wheels controlled by independent motors which manoeuvres the track by applying varied torque to each of the powered wheels. We would add a set of front-mounted light sensors to sense the lay of the track.

Experiments, results, revision
In early experiments with the standard robot chassis, we felt that for a cheap increase in speed we might simply exchange the standard wheels with much larger ones. Results of this modification were largely as expected, save that the reconstruction forced us to lower the unpowered rear wheel to match the height of the new wheels. Speed increase was not overwhelming, but we decided to stick with the larger wheels in future experiments.

The standard line following car as described in the NXT manual has only one light sensor, which meant that a "bang-bang" mode of control had to be employed. We hoped that adding a second light sensor would enable us to control the car in smoother movements.
Results of the modification were positive: The car now had two light sensors, mounted to take readings on either side of the track. The idea was that the car would be able to detect when it was directly over the track (both sensors reading white) and thereby gain a speed increase on long straight segments.
Further testing, however, showed that this speed increase would send it too far out in relation to the track. The car would end up oscillating back and forth across the track, increasing angle of entry each time, leading to more oscillation. Much like the original bang-bang controller.
In essence, we had simply added a third "bang" for straight segments, still a quite unsophisticated method of control.

Experiment: Adding a third sensor
To approach a more analogue steering method we had the idea of introducing a third light sensor, set some distance forward of the first two. This light sensor would detect the lay of track ahead of the robot. Through this additional knowledge of upcoming curves and straight segments we would be able to construct a control program that would be more sensitive to changes in the track, the idea being that we would thereby avoid sending the robot careening out across the edges.
In addition to this change, we would attempt a more state-based control program. We would "remember" the last state and act according to this. With the 3 sensors we now knew on which side of the line we were, even when they all read white. This was accomplished by saving which of the left and right sensor last saw black.

Final program

In our final code we had made a class "ColorSensors" which had 3 booleans, each one saying if a colorsensor was black. It also had a boolean for checking if all sensors saw blue. These were updated in every with a call to update(). It also came with its own calibration program, so we could store what was black, white and blue in the light we were in at the moment.

Now, the only thing the main program had to handle was to call update, and else act acording the the following cases:

Middle sensor black and the two other white
This means we are on track, and give it full speed

Two sensors black
We are on a slight curve, and choose to speed down left motor, to turn left. As we only turn slightly means our car doesn't go too far off the line on the other side

One side sensor black
The curve is shaper thus we have to turn even more

All sensors white
Here we act acording to the last sensor which was black.
If the left one was black, we make a sharp turn to the left. Opposite for right.
If the last reading wasn't one of these 2, we slow down. The option could happen at a sharp curve, as our front sensor was further ahead than the two others. In this case we slowed down, as we soon had to do a turn, and thus would be faster reacting when we knew what to do.

While not entirely analogue, this method has enough different cases that we feel that the robots motions will be adequately smooth, avoiding unnecessary oscillation.

Results
Results of this final modification were very positive. When properly calibrated the robot would adjust its speed in accordance with the cases above to take turns with great precision and speed. The calibration was a sticking point, however, as the performance hinged greatly on the threshold values for black and white that had been set for each light sensor. Taking readings, altering code and recompiling soon proved tedious, and we implemented a simple function that would allow us to take readings of black and white values before each execution of the race program.

public void calibrateBlue() {

NXTBlueThreshold = (int)((left.readValue() + right.readValue()) / 2);

RCXBlueThreshold = middle.readValue();

Sound.playTone(500, 20);

}

With this system in place we were able to shave out time to about 20 seconds for the entire track.

As far as our original goal was concerned, we had two practical measures of success: The time the robot took to complete the track and the degree to which the robot followed the line. It is difficult to set a hard target for both of these measures, especially since one is usually inversely proportionate to the other. In both aspects, we found our robot adequate to our original goal.

Conclusion
The results of our robot were satisfactory only in the sense that they met our expectations to the original design strategy. Shaving further seconds off our final time, we feel, can at this point only be accomplished be changing the fundamental workings of our design.
Having observed the results of the other groups participating in the course, such changes might be a speed increase through gearing or the inclusion of differential steering, which would allow for much smoother turns.
Given more time, our immediate strategy would be to redesign the robot to use improved gearing and differential steering, and we did in fact make such an attempt at the eleventh hour of the race. Unexpectedly, we failed to make the deadline and abandoned the project before the robot became fit for competition.

Week 3.b - Balancing robot

2008-09-24T14:09:00.001+02:00

Date: September 24

Duration of activity: 3 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To construct and code a LEGO robot that is capable of balancing upright on two wheels.
Plan: At first we'll try finding out how to construct the robot so that it is possible of balancing at some later point.
When the model is completed, we will implement code that will actually allow the robot to balance by reading from a light sensor and utilizing the motor controlled wheels to counter any diversion from the balancing.
We suspect that the primary challenge will consist of tweaking the parameters that control the balancing behavior.
Results: At first, we needed to find out how the robot model was to be constructed. In that respect there are several issues that needs to be considered. The robot should have wheels mounted so that it can be balanced, and it needs to have a light sensor mounted so that it can measure the light reflection from the surface. Furthermore, it needs to have a low center of gravity to be easier to balance.
In the end, we chose to follow the construction guide from http://www.philohome.com/nxtway/nxtway.htm, so our robot looks exactly like it. Unfortunately, constructing this robot meant tearing apart our old beloved robot.

Experiments & problems encountered: After we had implemented the code, inspired by "SeyWay.java", we ran into a lot of problems with the tuning parameters related to the PID controls. We tried tweaking the different parameters, but we did not end up with a robot that could keep its balance appropriately. The best result achieved is when the robot managed to balance for 5 seconds.
We've tried several tweaks to the parameters and in the end simply ran out of time to tweak them further. Our plan, however, was to tweak the value of p until we had a smoothly oscillating motion and then adjust the scale value to make the oscillations as small and slow as possible. Watching the videos on the site linked from the course homepage it seemed that a good strategy would be to have the wheels turn as slowly as possible rather than oscillate wildly across an upright position (which also makes sense given previous discussion in the course).

Week 3.a - Sound controlled robots

2008-09-17T14:59:00.001+02:00

Date: September 17
Duration of activity: 3 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To build various different types of sound controlled robots.
Plan: Add a sound sensor, test it and code two different types of robots responding to sound.
Results: We've gotten a good understanding of the sound sensor and managed to implement the two programs.

Experiments & problems encountered: This time we did not have that many problems compared to the wall follower.
We started with a simple test program to find out how the sensor reacted to different sounds. We tried to make noises at different volume levels and also to knock on the sensor itself. The result was that the sensor was quite effective a registering the sounds in the surroundings.
The second assignment was to download the program "SoundCtrCar" and test how the robot would react to sounds. When a sound with a high enough volume has been registered, the car goes forward, waits for another sound, then turns, waits, turns, waits, and stops.

Other experiments
- Low Rider: We have tried getting the NXT to play "Low Rider" by War. We have converted an midi with Bricl's Music Studio. The NXT plays sounds, but we can't get it to sound right. We have tried tweeking the wait-time and tone by multiplying them with different values in the funcion call, but haven't found a way where we can recognize the song. We will try harder next week
- NXT Train: This week we have also createt a new connector to another actuator, namely the lego 12V train from the 80's. Now we can control the train with power from the NXT, meaning we can control the train forward and backwards in different speeds. This we can maybe use for our project, we just havent testet how much weight the train can handle with sensors and more lego added.
- Improvements on the line follower: Unfinished.

Week 2.b - Wall following robot

2008-09-12T10:57:00.002+02:00

Date: September 12
Duration of activity: 3 hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: To build and implement a functional wall following robot.
Plan: Add a ultrasonic sensor the the side of the robot, and program it to detect nearby walls and follow them at a certain distance.
Results: We have a functional wall follower, but it still needs some tweaking.

Experiments & problems encountered: At first, we tested how the sonic sensor measured distances on different update intervals. It turned out that on close distances sleep intervals of 100ms worked fine with respect to the update speed of the sensor. However, when measuring on longer distances then update speed of the sensor slowed to a point where it were causing problems.

At first, we tried mounting the sonic sensor on the side of the robot so that it was orthogonal to the forward direction of the robot. The hope was then to also keep the sensor orthogonal to the wall, and thus allowing the robot to follow along the wall. However, we quickly discovered that when the error (that is; the difference between the measured distance and the desired distance) grew, the turning of the robot would cause further increase of the error, and thus an even steeper turning. In the end the robot could have to misfortune to either crash into the wall or just circling around itself.
Investigating the cause of this behavior we could observe that the distance to the wall obviously increased when we turned either way because of the increased angle with respect to the wall. In order to avoid these unfortunate readings, we tried mounting the sonic sensor at a 45 degree angle from the forward direction of the robot.
Experiments proved that this position eliminated the misleading readings we had before; when the robot turned toward the wall, the distance decreased and when turning away the distance increased. So now, we had a much more stable set of readings to base our (re)actions on.
Now we could tweak the desired distance to wall, the amount the error influences the turning speed, and the amount of error required before we start trying to correct it.

Another difficulty we encountered, was that we had a hard time computing the correct error value to be applied to the power of the motors. We tried solving this by simply tweaking the numbers.
Measurements:

Graph 1: Distance measurements over time.

Graph 2: Same as Graph 1, but cropped.

Graph 3: Distance, left power and right power over time.

Graph 4: Same as Graph 3, but cropped.

Week 2.a - Improving the line following robot

2008-09-11T15:24:00.001+02:00

Date: September 11
Duration of activity: ? hours
Group members participating: Anders, Mikkel, Martin, Sean

Goal: Getting input from a third light sensor, positioned between the two other light sensors. Then we'll use that input to improve the speed of which the car can correctly finish tracks.
Plan: At first we'll refer to the lejos API for documentation on how to use the light sensor (we are using the older version of the light sensor). Once we are able to get sensible input from the sensor, we'll move on to using it for improving the track results. We'll do that by designing an algorithm that takes advantage of the additional knowledge gained from having a light sensor positioned in the middle. We are then going to try out the different approaches
Results

Experiments: After attaching the middle light sensor, we tried an aproach where we move forward if the middle sensor senses black, and if both left & right sensors spots white, we move forward at an increased speed. If the middle sensor senses white, we look at what sensor spots black and what sensor spots white.
Problems encountered: We had a concern about the placement of the middle sensor. We thought it probably was placed to close to the ground in order to pick up the correct raw values. Aside from problems with detection, The sensors proximity to the ground ment it would get stuck on cracks and bumps in the ground. At the end, we got a Linefollower that is better at following lines, that with only two sensors.

Week 1.b - Improving the line following robot

2008-09-05T10:49:00.001+02:00

In an effort to reduce oscilation we have added a second light sensor to the standard car model. The idea is that with one sensor on each side of the black track, the car will know to go forwards when both sensors are over the white background. At first we had the sensors mounted quite close together, meaning that the car would move forward when both sensors were above the track. This proved problematic, however, as the narrowness of the track meant that there was little room for error: The car had to adjust its direction quite often, and the oscillation persisted.

Mounting the sensors to the sides of the track meant that we had a few more centimeters of "give".

We still need to make some adjustments to the program. The turn speed in particular needs fine-tuning: we want the car to make small adjustments when turning so we don't tend to oscillate across long straight sections of the track, but it also needs to turn enough that the car doesn't run off the track on sharp corners.

Finally, we have added a larger wheel type to the car which gives it a significant speed increase, but also a tendency to fall over on sharp corners. Additionally, we need to tweak the parameters for turning around cornes because of the added speed and as the increased wheel-size causes the turning radius to be larger compared to the previous wheels. We still need to adjust the program with these new factors taken into consideration.

We tried turning off the floodlight function of the light sensor. By measurements, it turned out that it decreased the light sensitivity and made the boundary threshold between black and white smaller, thus not providing an attractive solution when we are trying to stick to the black road. However, if we were trying to use the sensor to detect colors, it might be better to deactivate the floodlight to avoid measuring the reflection of red.

We modified our code to use Runtime.getRuntime().freeMemory(), and to print out the result to the LCD screen. When the text strings are stored as strings, the memory usage was constant when the program was executing. When using strings directly in method calls, however, the free heap memory quickly shrunk in size. This is apparently caused by the program allocating space for the string at each iteration of the loop. When the heap was quite low in size, the garbage collector kicked in and started freeing some of the memory.

Next week onward we will try to stick more to the "recipe" of the lab logs in order to get a more structured reports from each lab session.

Week 1.a - Setting up and testing the NXT

2008-09-02T15:09:00.002+02:00

We've been playing around with our Mindstorms set a lot this week, trying to get the hang of both the building and coding aspects of the set.

First order of business was, of course, to flash the NXT unit's firmware. This proved more difficult than anticipated as the USB connection drivers proved incompatible with the Windows Vista machine we were attempting connection with. Disastrously so, in fact, as the incompatible drivers rendered the computer unable to even connect to its own usb-based devices.
Specifically the "libusb" file in the 3rd party folder ws incompatible with Vista's usb handling. We found no other compatibility problems with Vista.

When we tried connecting through an XP machine, the process went a lot smoother and we were able to install the new software without further disaster.

Meanwhile, construction on the sample car/robot (as described in the manual accompanying the Mindstroms set) was going smoothly, and we were able to construct the fully enhanced robot and to test its capabilities using the sample programs already present on the unflashed NXT unit.

With the robot constructed and the firmware installed we were able to install the "Line follow program" which worked fully as expected. We added support for the ultrasonic sensor in order to avoid obstacles on a course.

Inspired by the standard claw parts present in the Mindstorms box, we have started construction on a claw-like appendage for the robot. At the time of writing it is fully capable of opening and closing by power supplied by a standard motor and has a touch-sensor embedded in between its claws.
The dimensions were chosen to match the size of the red and blue balls in the standard Mindstorms set, so that it might eventually be programmed to pick up these balls, as they appear to be designed to be distinguishable by the light-sensor attachment.

Hello World

2008-09-02T15:06:00.000+02:00

In following the course "Embedded Systems - Embodied Agents" at the Computer Science dept. of Århus University, this blog will serve both as a repository of knowledge for our group, "Lego of Doom", and as a source of information for other interested groups.