Changes between Version 1 and Version 2 of WikiStart

01/04/16 00:36:48 (4 years ago)

Initial README


  • WikiStart

    v1 v2  
    1 = Welcome to Trac 0.12.3 = 
     1= Hanoi Towers (played by robot) 
    3 Trac is a '''minimalistic''' approach to '''web-based''' management of 
    4 '''software projects'''. Its goal is to simplify effective tracking and handling of software issues, enhancements and overall progress. 
    6 All aspects of Trac have been designed with the single goal to  
    7 '''help developers write great software''' while '''staying out of the way''' 
    8 and imposing as little as possible on a team's established process and 
    9 culture. 
     5== Project goal 
    11 As all Wiki pages, this page is editable, this means that you can 
    12 modify the contents of this page simply by using your 
    13 web-browser. Simply click on the "Edit this page" link at the bottom 
    14 of the page. WikiFormatting will give you a detailed description of 
    15 available Wiki formatting commands. 
     7The goal of the project is to learn robot to solve Hanoi tower problem. We have to develop a program that works with robot. Then we have to the program compile and run in real-time environment. Finally we must test the behavior and reactions of the robot. 
    17 "[wiki:TracAdmin trac-admin] ''yourenvdir'' initenv" created 
    18 a new Trac environment, containing a default set of wiki pages and some sample 
    19 data. This newly created environment also contains  
    20 [wiki:TracGuide documentation] to help you get started with your project. 
     9== Hanoi towers problem 
    22 You can use [wiki:TracAdmin trac-admin] to configure 
    23 [ Trac] to better fit your project, especially in 
    24 regard to ''components'', ''versions'' and ''milestones''.  
     11Tower of Hanoi is a mathematical puzzle. It consists of three rods (or towers). At the beginning, some discs of different diameter (different width) are placed to one of them (we will call it rod A), ordered from largest (bottom) to smallest (top). The task of solver is to move all discs to the other rod, called C. The third rod, called B, will serve as auxiliary for a temporary storing. During the movement, each disc must observe the following rules: 
     13 * In one move, just one disc can be replaced. 
     14 * One move consists of taking the upper disc of one tower and putting it on top of another tower. 
     15 * It is forbidden to put greater disc on a smaller disc. 
    27 TracGuide is a good place to start. 
     17In our case we will not work with rods and discs with different diameters, but with equally big cylinder which we will stack up in columns. This has the advantage that a column of cylinders is not fixed, so if robot hand accidentally bumps into a tower of cylinders, it will knock it down instead of halting. So the robot engine is not blocked. It also helps with testing of the robot, when moves do not need to be as accurate as when rods are used. 
    29 Enjoy! [[BR]] 
    30 ''The Trac Team'' 
     19The problem can be solved in several different ways, we choose a recursive algorithm that solves the problem simply and straightforwardly. It is sufficient to realize that we need to move all discs on another rod to achieve the largest disc. It is first necessary to solve the problem for N - 1 discs. More precisely, for N discs: 
    32 == Starting Points == 
     21 * Move N - 1 discs from A to B 
     22 * Move the lowest disc from A to C 
     23 * Move N - 1 discs from B to C 
    34  * TracGuide --  Built-in Documentation 
    35  * [ The Trac project] -- Trac Open Source Project 
    36  * [ Trac FAQ] -- Frequently Asked Questions 
    37  * TracSupport --  Trac Support 
     25In the case of N = 1, the solution is trivial. It can be shown by mathematical induction that 2N - 1 moves are needed for replacing of discs from A to C. This is also the optimal solution of the problem, it needs the least turns to solve it. The implemented algorithm works for general N, but for technical reasons, we will work with only three cylinders, so the number of necessary movements is 7. 
    39 For a complete list of local wiki pages, see TitleIndex. 
     27== Robot 
     29To solve the Hanoi towers problem, we will write a program that will control a robot that will move individual cylinders from one column to another. Here we use 3D Fischertechnik Robot. This robot can move in three directions (it has three axes) and it can use grabber claw (clamp), which can grasp a cylinder of specified size. The robot has four independent DC motors, three of them move the clamp in all directions and the last one allows to grasp objects. 
     31For detection of robot position, 8 switches are present, two for each motor. First one is pressed by part of robot construction when the robot is in the initial position in certain direction. The initial position is always one of borders of certain direction. Before beginning of using the robot, it must move to its initial position in all four directions, since program has not any other chance to find out the real position of it. 
     33The second switch indicates the movement of the robot, it is pulse counter for travel measurement. Gearwheel, which moves along the axis, is in close contact with the switch. As the robot moves, wheel teeth alternately press and release switch and thus it creates periodical pulse signal. Since the wheel has four teeth, the signal changes 8 times during one wheel round. It is necessary to realize that the actual value of the switch is not important, important is its change. 
     35We know one border in every direction, but the other borders are unknown and we have to guess the first border for the first time from specification of the robot and then set it by a measurements. Speed of the robot can change (and it is a problem during the sampling), but the number of pulses from initial to end position will always be the same for each engine of each robot. It is sufficient to measure the value only once. We will try to set the other limit as far as possible, but it is not necessary for solutions of Hanoi towers. 
     37The robot itself is quite imprecise in some aspects. The speed of individual motors may vary with every robot, the limits of movement can be a bit different. Moreover, the robot is a mechanical device, its precision depends on physical condition of components. For instance, the clamp can be very imprecisely grasp each cylinder. We will describe four options, how the robot can move and what are measured values: 
     39 * Axis x (Rotation) - The robot can rotate around its vertical axis to both sides. The direction from the initial position is clockwise. Range of motion is a bit more than 180°. During the movement between the limits, the signal will change 242 times. The measured time required for pass the entire range is 6.5 seconds. Speed of this engine may vary a lot, so we will assume a much higher value. The motor speed according to the values 279.23 TPM (Turns Per Minute). This is the fastest engine, so we will determine the sampling rate according to it. 
     40 * Axis y (Forward/backward) - The robot can move forward and backward. The robot can move up from the initial position about 100mm forward, this is 157 signal changes. Movement lasts 11 seconds, so the speed is 107.06 TPM. This engine is very slow, so it should be used as little as possible. 
     41 * Axis z (Height) - The robot can move up and down. The initial position is up and the way down is 160 mm, lasts 6.7 seconds and 246 signal changes. The speed of motor is 275.37 TPM. 
     42 * Clamp - Robot has a clamp that can grasp objects. The initial state is fully opened. The hand closes during the 38 signal changes, but this limit can vary quite for each clamp. The value for the correct grip may not be entirely accurate, because the range when clamp holds the cylinder tightly enough and it still moves at the same time is sufficiently large. The movement takes approximately 2.5 seconds and speed is 114 TPM. 
     44== Hardware and OS 
     46The robot itself has no control unit or memory for user programs. It can be controlled via the input / output card MPC-7632 connected through connector SCSI-2 with 50 pins. It transforms the signal such that the robot can be accessed through a simple program interface. We can get one byte (with eight bits) from the input, where each one bit represent each robot switch. When a switch is pressed, binary value 1 is set in appropriate bit of the byte. There can be written also one byte on the output where each bit determines the direction of robot elementary motion. 
     48The card is built in a single-board computer (SBC) GEME-3000 with its own power supply in one "box". This is a much more comfortable and more robust solution than using a PC, because this computer is configured exactly as we need. It can be connected to computer thought SSH (instead of a keyboard) and every user has automatically root privileges. 
     50The robot is piece of hardware that works in "real time" and every change in the input signal has to be caught. Reactions of operating system to it must be prioritized, so we need a real-time operating system (RTOS). There are installed two important types of software on device GEME-3000, XtratuM and PaRTiKle. XtratuM is a open source hypervisor specially designed for embedded real-time systems. Hypervisor is a hardware virtualization techniques which allows to run more operating systems on one host computer concurrently, every OS executes in its own space, called domain. It should be noted that this is not a full operating system. Over this layer can run non-real-time OS as well, but capabilities of this OS are insufficient and deadlines not need to be met. 
     52We use PaRTiKle as our regular RTOS. Its advantage is that it can run on some different execution environments. We can run as a stand-alone system on a bare machine, but it is too complicated for our needs. We can also compile and run it like regular Linux application. Although we can use APIs and libraries of Linux in our programs, Linux does not respect the properties of RTOS. 
     54We prefer the option when we can load our program as a module to XtratuM domain. In this case, we run a program (such as a small OS with support of PaRTiKle libraries) concurrently with Linux. Linux runs in the domain with the lowest priority, our application runs with higher priority. Thus our program is able to observe properties of RTOS. However, we must be careful, because in this case, the program will have priority control over the computer. The module can be unloaded from Linux but it may happen that Linux never gets control over computer again. Just one infinite cycle with active waiting (without using the command delay) and we lose control over the computer. At first, we need to configure and compile the compiler PaRTiKle, pgnatmake, properly by using the following sequence of commands: 
     57cd /usr/src/partikle 
     58sudo make distclean    # It resets current setting. 
     59sudo make menuconfig    # Here we need to set the Ada language and XtratuM platform. 
     60sudo make    # It compiles PaRTiKle compiler 
     63When we have a compiler we can create a module for XtratuM. At the beginning of work with XtratuM, we need to execute command `xmctl start`, which will allow Linux to work with domains. Then each module can be loaded and unloaded due to commands `xmctl load program.prtk` and `xmctl unload program.prtk`. Once loaded, our program starts immediately. Because the program can not use the library of Linux, the output can only write to the message buffer of the kernel. That may be printed by dmesg command on the command line. 
     65== Timing management 
     67The source code of the program that controls the robot is written in Ada. Ada is a language used to write programs for RTOS. Its advantage lies in the fact that it has strong build-in support of concurrency programming. Our program uses several tasks which are essential units in Ada that are obeyed concurrently with other parts of the program. 
     69The first task, Sampler, periodically checks the state of the signal pulse. If the signal changes, the sampler changes the current position. It is necessary to capture every change of pulse signal by Sampler, otherwise it will not represent the correct position. Sampling frequency is determined by the engine that changes the pulse signal the fastest. That is the motor of axis x. The measured speed of rotation is 279.23 TPM. However, according to the experience, the speed of other robots may be much higher, almost twice. Furthermore, it happens often that when the robots stops, it "jerks" a bit and changes signal quickly. So let the robot speed to 500 TPM and for sure we choose sampling rate 10 times higher. If we suppose that the speed of the robot is 500 TPM, then the sampling period is 1 / (((500 * 8) / 60) * 10) = 0.0015 seconds. Sampler should not be affected by electrical noises with such period. 
     71The second task, Positioner, moves the robot from current position to the destination. At first, it lets the robot to move in the right direction and then determines for each direction separately whether it is the target position. It is obvious that Positioner depends on Sampler. Positioner may not be as fast as a Sampler, because if it does not detect any change of position, it can return. However, the period should not be twice the period of Sampler, otherwise it could still miss some positions. We set the period 6 times shorter than signal pulse to 1 / (((500 * 8) / 60) * 6) = 0.0025 seconds. 
     73The third task is Main. This task solves the problem Hanoi towers problem. It use the other tasks to move with robot. 
     75As we work with a real device on RTOS, it is necessary task not to cross the deadline given by their period. It is the best to assign a priority to each task. The robot has the highest priority. Since the Sampler has higher sampling frequency, Sampler has the second and Positioner the third highest priority. Since the Main task is not periodic, it can be set to any lower priority. 
     77Suitable dispatching policy to this problem is FIFO_Within_Priorities. This is the fixed-priority based task dispatching policy where we maintain a queue of waiting processes. All processes wait for running process. When the process is blocked (for instance, by using the command delay), It is selected from all waiting processes the first one which has the highest priority. FIFO_Within_Priorities is also the only guaranteed to be supported by all implementations. 
     79All of these tasks access to a protected type Monitor. This is the kind of wrapper that works with the robot interface. It only one can directly write one byte on the output and read one byte from input. It also maintains the current direction of robot movement and the current position which Sampler must update. Since we want to run methods of protected type with the same priority like the task with the highest priority, we set that the same priority like Sampler. Moreover we must set locking policy to ceiling locking protocol. 
     81== Source Code 
     83First we say some tips where to beware when writing the code. Program on XtratuM platform debugs poorly. It is not very wise to use types Natural and Positive instead of Integer, because to get into minus values is fairly simple, and then the program behaves quite unpredictably. We also need to be careful when dividing integers, then it is needed to explicitly cast to float. 
     85It is not very suitable to use protected types if it is not absolutely necessary. To observe mutual exclusion principle is unnecessarily time-consuming. In each cycle, where we expect a active waiting, it is necessary to give the delay command! Otherwise, RTOS can not switch content and the program blocks entire RTOS. Then, there is often no other option but to reset the computer. It is also clearer to use the delay until command instead of delay to observe period exactly. 
     87The program is divided into 4 packages: HanoiTowers, DiscsMover, ColumnContainer and RobotMonitor. They each represent a different level of abstraction, in this order from the highest to the lowest one. 
     89The RobotMonitor package contains the code of Sampler, Positioner and protected type Monitor. It also defines bit masks that can be used when working with low-level functions. The Main task uses MoveToPosition function to be able to access to Positioner. When Main task calls this function, then it waits until Positioner moves the robot to given position. MoveToInitialPosition function moves the robot to initial position. There is also a function MeasurePulses, which measures the number of pulses of specified switch. It is not part of the program. 
     91The ColumnContainer package takes care of correct picking and dropping of the cylinder on the column. Function PickDisc takes the topmost cylinder from given column and function DropDisc drops the disc to the column. These functions do the following sequence of movements: robot moves forward, pulls itself down to the right height according to the number of cylinders in the column, picks/drops the cylinder and returns to the original position. The height of a cylinder has to be precisely measured (78 pulses in this case) to assure that cylinders get dropped exactly on each other.  
     93The DiscsMover package has function MoveToColumn that rotates the robot from originating column to the target one. The MoveDisc function uses the MoveToColumn function and moves a cylinder from originating column to the target column. It also keeps track of how much cylinders has each column. The HanoiTower package contains functions that solve the Hanoi tower problem recursively. 
     95The Main procedure moves the robot to the initial position, solves the Hanoi Tower problem by moving all discs from the column A to the column C and then the other way around and finally terminates tasks Positioner and Sampler which allows the Main task to terminate. 
     97== Conclusions 
     99To write a working application for the robot is much harder than for the simulator. A working program on simulator has a lot of changes to do to work with robot. The program compiled for the XtratuM is much more prone to errors, but it is also harder to debug. Anyway, thanks to the robot is much easier to see what is really happening. 
     101== Licensing 
     103See LICENSE file.