Wednesday, January 28, 2009
Turing Machine Demonstration Video
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 :)
Monday, January 26, 2009
Conclusion
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:
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.
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
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.
Tuesday, January 20, 2009
Optimization
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
- Read request
- 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
Compensating for excessive movement
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,- Starts the motor
- Checks the light sensor for colour change
- Counts down the number of transitions remaining by one if a change has occurred
- Stops the engine once the count reaches 0
- 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?
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.
Friday, January 9, 2009
Building the GUI
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:
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.
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.
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.
Wednesday, January 7, 2009
Initialization & testing of the Input tape
Date: December 5
Duration of activity: 3 hours
Group members participating: Anders, Mikkel, Martin, Sean
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.
Sunday, January 4, 2009
Bluetooth communication
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:
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.
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
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.
Friday, January 2, 2009
Internal operations on the robot
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.
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.
Monday, December 22, 2008
Calibration of the Read/Write motors
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 b y 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" unread able.
Furthermore, in using the bluetooth con nection 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.
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.
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.
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
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" unread
Furthermore, in using the bluetooth con
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 designResult
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.
Sunday, December 21, 2008
Software Architecture of the Turing Machine
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.
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.
Sunday, December 14, 2008
Tape conventions
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).
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).
Sunday, December 7, 2008
Constructing the Turing Machine
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
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:
For use in LEGO Designer
Monday, December 1, 2008
Turing Machine Architecture
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:
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.
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
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.
Thursday, November 27, 2008
Week 12 - End course projects
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:
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.
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.
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.
Subscribe to:
Posts (Atom)
