Design Methodology
for
State based Embedded Systems
Case Study: Robot Controller
by
PHANEENDRA VANKA
B.E., Nagarjuna University, India, 2001
submitted in partial fulfillment of the
requirements for the degree
MASTER OF SCIENCE
Department of Computing and Information Sciences
College of Engineering
KANSASSTATEUNIVERSITY
Manhattan, Kansas
2004
Approved by:
Major Professor
Dr. Masaaki Mizuno.
- 1 -
ABSTRACT
Time triggered systems are the best matched models forthe real world embedded system applications. In thisproject we derived time triggered system based onrational unified process by taking the behavior inputs, definingentity classes and associated boundary classes. Thishelped us to categorize and understand thecomplexities of time triggered systems. Use caserealization suggested us that the system can be described using finite state machine method, whichjust needs mutual exclusion of variables assynchronization. In this method the inputs to thesystem change the state in the finite state machine.As a case study we implemented RobotController, a modeldesigned using Lego Mindstorm computer brick calledRCX (Robotic Command eXplorer) using leJOS (version2.1.0) programming language. The leJOS API is apruned version of the Java API along with classes tocontrol motors, sensors and other components of theRCX brick.
TABLE OF CONTENTS
LIST OF FIGURES
ACKNOWLEDGEMENT
1. Introduction
1.1 The Robotics Invention System
1.1.1 RCX Brick
1.2 leJOS
1.3 Behavior Control
1.3.1 leJOS Behavior API
1.4 Robot Controller
1.4.1 Specification of the Robot Controller
2. DESIGN METHODOLOGY FOR TIME-TRIGGERED STATE MACHINE BASED SYSTEM.
2.1 Rational Unified Process
2.2 Time-Triggered and Event-Triggered Systems
2.3 Allocating a thread for each scenario
2.4 Finite State Machine based implementation
3. CASE STUDY: ROBOT CONTROLLER.
3.1 Use-Cases:
3.2 Use-Case realizations
3.3 Time Triggered-Finite State Machine based implementation
4. Conclusion
5. References
1
LIST OF FIGURES
Figure 1 :The leJOS memory map [1]
Figure 2 : Fire-Fighting Behavior Control
Figure 3: Hierarchy of Behavior [1]
Figure 4: Rational Unified Process
Figure 5: Class Diagram for Time-Triggered Systems
Figure 6: Class Diagram for Event-Triggered Systems
Figure 7: Allocating a thread for each scenario
Figure 8: Finite State Machine based implementation
Figure 9: Time Triggered model for Finite State Machine
Figure 10: Use Case Model for Robot Controller
Figure 11: Initial Class Diagram for Robot Controller
Figure 12: Finite State Machine for Robot Controller
Figure 13: Finite State Machine Model– Action call
Figure 14: Finite State Machine Model– Suppress call
Figure 15: Revised Class diagram for Robot Controller
ACKNOWLEDGEMENT
I am thankful to my advisor Dr. Masaaki Mizuno for his guidance and vision without which I probably would have not accomplished this project. His advice and guidance has helped me understand and evaluate my work.
I would like to thank Dr. Mitchell Nielsen and Dr. Gurdip Singh for serving in my committee. I am grateful to my colleagues in the Computer Science Department, Vivek Subramaniam, Raghavendra Mamamdgi and Priya Padmanaban for helping me out in some of the problems I have faced during the course of this project work.
I would also like to extend my gratitude to Ms. Delores Winfough and other staff members of the Department of Computing and Information Sciences for guiding me through the academic and graduation procedures.
Also, I thank my parents, for always believing in me and for allowing me to take chances, and my friends for their invaluable support and for their warm wishes.
1
1. Introduction
1.1 The Robotics Invention System
The MINDSTORMS is a product of LEGO that allows one to build robots. At the core of this product range is the Robotics Invention System (RIS). The RIS (as of version 2.0) kit consists of 718 individual parts -of which 129 are unique LEGO parts. It includes motors, touch sensors, light sensors, infrared transmitter, bricks, pulleys and gears.
1.1.1 RCX Brick
At the heart of the MINDSTORMS is the Robotic Command eXplorer (RCX) brick, which acts as the brain for the RIS kit. The unit is only about 6cm x 10 cm x 4cm and weighs 280 grams with 6AA batteries. It has a Hitachi H8/3292 series micro- controller, which has a 16Kb ROM, 512 Kb RAM (on board) and a clock speed of 16MHz. The ROM contains algorithms for communication between motors and sensors, displaying data on the LCD and downloading programs from the computer. The RCX also contains 32Kb external RAM where the user programs will be stored. This memory is ample for most of the robotics programs.
There are 3 input ports numbered 1, 2 and 3 to whom sensors like touch sensors, light sensors, temperature sensors, and rotation sensors can be connected. There are also 3 output ports named A, B and C to whom the actuators can be connected. These ports are used for motors and lights.
The RCX also has 4 buttons, On-Off, Run, View and Prgm. These provide user interaction for controlling program execution. The On-Off button turns the power on and off for the RCX. This does not delete the program on the RCX. The RCX can hold a maximum of 5 programs at any time and the Run button starts executing the program, selected using the Prgm button. The View button alternates between the following views: current time, input sensors and output ports. In the case of sensors, based on how they have been programmed, a Boolean value (0 or 1) or Percentage (0-100) or a raw value is displayed.
The RCX has an infrared transceiver, which is used for downloading programs from the computer and for communicating between RCX and host computer or two RCX’s. There is an IR tower to download programs from the PC into the RCX. The IR tower can even send commands to the RCX brick, allowing the PC to act as pseudo-remote [1]. There is a battery compartment on the underside that holds the 6 AA batteries that power the RCX.
RCX also has a LCD panel which displays up to 5 characters and there are other segments which display the status of sensors and the program. It also has a speaker which can produce variety of simple sounds.
1.2 leJOS
leJOS is a replacement firmware for the Lego Mindstorms RCX brick - a JVM that fits within the 32kb on the RCX [3]. It grew out of the TinyVM. leJOS is a Windows version, which doesn't require CygWin, where as TinyVM does. The leJOS API is a smaller version of the Java API. It has classes to control the motors, sensors and other components of the RCX brick apart from the basic features of java. The packages that are included in leJOS contain reduced number of interfaces, classes and exceptions than their counterparts in the Java API. In most cases identical method names and return types are used to maintain consistency between the java and the leJOS. leJOS supports threads, arrays, Java event model, exception handling and recursion. Automatic garbage collection, switch statements, arithmetic expressions on long variables is not included in leJOS VM. The RCX specific classes control the motors, sensors, buttons, LCD, battery power, speaker, IR communications, timers and system time. Because the RCX is most often used for robotics programming, leJOS includes josx.robotics package which has several classes and interfaces for behavior control and navigation.
When the compiled files are downloaded in to the RCX, they will be interpreted by the Java Virtual Machine (JVM) that resides in the RAM of the RCX. The RCX has a 32Kb external RAM, of which JVM uses up 16 Kb, the ROM routines reserve for a space of 4 Kb. The remaining 12 Kb of memory is for the user programs. This number is normally more than enough for most robotics programs.Figure 1 gives graphical version of the memory map.
Figure 1 :The leJOS memory map [1]
1.3 Behavior Control
The most popular cliché in small robotics programming is behavior control programming [1]. Behavior Control is pioneered by Rodney Brooks at the MIT Artificial Intelligence Laboratory. Brooks adapted the insect’s complex behavior, which is a series of alternations of simple behaviors, to robot control architecture to come up with what was originally known as subsumption architecture. Later the subsumption architecture is renamed to behavior control. A behavior is a set of conditions and the action to be done on satisfaction of those conditions. The condition could be some sensory information, either external or internal, on which it issues an action. To coordinate the action, each behavior can disable some of the other behaviors, which conflict with its own action. This is based on the priority assigned to the behaviors and this capability to override other commands is called subsumption. If we were designing the Fire-Fighting Behavior control, it could be represented as in Figure 3 according to the behavior descriptions given in Figure 2. This is the standard diagram for representing the hierarchies of behavior priorities given by Brooks [8]
Behavior / Condition / Action / PrioritySeek heat / Temperature hotter in another area / Move toward heat / Low
Extinguish flames / Ultraviolet light sensor detects flame / Spray CO2 / Medium
Avoid flames / Temperature > 160o / Move away from heat / Highest
Figure 2 : Fire-Fighting Behavior Control
Figure 3: Hierarchy of Behavior [1]
1.3.1 leJOS Behavior API
Behavior API is very simple and has a single interface, josx.robotics.Behavior to define behaviors. Any behavior can be defined using this API.
The API of the Behavior interface has the following method declarations
- boolean takeControl()
It returns a Boolean value indicating whether this particular behavior should become active or not. A Boolean value of true means this behavior needs to be active and vice versa.
- void action()
The action() method contains the code corresponding to the action that has to be executed when the behavior is active. This is executed when the takeControl() returns true.
- void suppress()
The suppress() method contains code that is used to stop the action of current behavior and it is generally used to update the necessary data.
Once the required set of behaviors for the robot has been designed, it is given to an arbitrator, defined by the class josx.robotics.Arbitrator. The arbitrator then decides which behavior should be activated.
The API for the Arbitrator has the following method declarations
- public Arbitrator(Behavior[] behaviors)
- public void start()
The Arbitrator object is instantiated by providing it with an array of Behaviors. Once it has these the start method is called. The Arbitrator then keeps going through the Behaviors array checking if any of them want to take control. It always chooses the higher index behavior as the behaviors are filled in the order of priority. Once a ready Behavior is found, arbitrator executes the action method of that behavior. Action method is kept small so that the arbitrator executes it in short time and goes back to loop through the array. Whenever a higher priority Behavior is ready to take control, the suppress method of the currently executing Behavior is called to stop it and then the actionmethod of the new Behavior is executed.
1.4 Robot Controller
To test our design methodology we chose a modified version of “Tippy Senior”, a simple and easy to build navigator robot given in [1]. The RCX brick was mounted on top of a chassis, built with LEGO plates and beams. Two motors and two rotation sensors, one for each wheel, were attached at the bottom. The gear train from the wheel axle to rotation sensors axle was such that the rotation sensor axle rotated three times for every one rotation of the wheel. A touch sensor was placed at the front and a bumper was also added. Whenever the robot hits an obstacle the bumper would be forced inwards making contact with the touch sensor. Another motor was attached to an arm on the left side of the robot.
1.4.1 Specification of the Robot Controller
1) Behavior Move: - In this behavior it always calculates a random point to reach. Once robot picks the random point, it calculates the angle and the distance which will lead it to that point. Then it turns that angle, and makes a straight line motion to that point.
2) Behavior Command: - In this behavior robot travels to a predefined point. While traveling to that point if bump occurs robot will remember that point, track back 20 units and takes an alternative path bypassing the point where bump has occurred to travel to the predefined point.
3) Behavior Bump: - When a bump occurs, robot travels a distance of 20 cm in backward direction.
4) Behavior Go Home: - When the timer reaches 30 seconds, the Go Home Behavior is set. In this behavior robot always travel to the initial point. It calculates distance and angle to initial point and then it rotates and moves to that point.
5) Behavior Rotate Arm: - Once in every 8 seconds robot rotates its arm. For 2 seconds it will rotate its arm in forward direction and then for another 2 seconds it will rotate its arm in backward direction.
6) Travel in Straight line: - Using the rotation sensorsrobot travels in a straight line. Rotation sensors are also used to measure the angle rotated and the distance traveled.
2. DESIGN METHODOLOGY FOR TIME-TRIGGERED STATE MACHINE BASED SYSTEM.
2.1 Rational Unified Process
Rational Unified Process is a general framework that can be used to describe specific development process. The steps in RUP are as shown in Figure 4. In the first step we identify the different actors and the use-cases that those actors take part in. Next we draw the use-case realizations and class diagrams for the previously identified use-cases. From the class diagrams and use-case realizations we can easily implement the system.
Figure 4: Rational Unified Process
2.2 Time-Triggered and Event-Triggered Systems
The inputs to the system can be gathered in two ways. In event-triggered systems the control starts at the origin of input and passes on to other objects in the system. In time-triggered systems the active object pools the inputs from time to time and when there is an input it transfers the control to the appropriate object. The difference between these two systems can be clearly seen in their class diagrams as shown in Figure 5 and 6.
Figure 5: Class Diagram for Time-Triggered Systems
Figure 6: Class Diagram for Event-Triggered Systems
For concurrent systems there are two methods of implementation.
1)Allocating a thread for each scenario.
2)FiniteState Machine based implementation.
2.3 Allocating a thread for each scenario
In this method we identify the regions which require synchronization in each scenario. For each such region we specify a global invariant and develop a coarse-grained solution from which we derive a fine grained solution [11]. This along with the component code derived from the class diagram will give the complete solution for the desired system. These steps are summarized in Figure7.
Figure 7: Allocating a thread for each scenario
2.4 FiniteState Machine based implementation
Figure 8: FiniteState Machine based implementation
The steps in this method are as shown in Figure 8. From the use-case realizations if we observe that there are asynchronous waits in the system the actions between the waits can be grouped as small chunks of synchronization regions. These divisions act as states and the entire system can be described using a finite state machine. In the next step we revise the class diagram to include this state information. In time triggered systems we create two active threads where one thread will be pooling the inputs and another thread will traverse the state table. Once we have the class diagram, active threads and the scenario for each thread we can easily implement the system.
Figure 9: Time Triggered model for FiniteState Machine
3. CASE STUDY: ROBOT CONTROLLER.
3.1 Use-Cases:
The first step in design is to identify the actors and use-cases in the system. In a behavior model some the inputs are the actors to the system. The behavior which needs to be executed for an input is the use-case in which that particular actor participates. These inputs may be external real time inputs or internal inputs like timers. These inputs may require the current behavior to yield to the new behavior. There might be some other inputs which do not cause a change in behavior but provide supporting role to the behaviors of the system. The use-cases of all these inputs represent the functional requirements of the system.
Given here are the use cases for Robot Controller.
Default input (MOVE behavior): If no other behavior is ready to take control, we start the move behavior. Once MOVE is completed, we call it again. This behavior takes control whenever no other higher priority behavior is ready to take control. This is the default behavior of the system, and it runs at the lowest priority level.
1) Pick up a random point(x, y) and calculate angle and distance
2) Rotate for the calculated angle
3) Travel the calculated distance in a straight line
Command input (COMMAND behavior): Whenever robot receives a COMMAND signal from a computer, this behavior is executed. Robot will go to a predefined point in this behavior.
1)Calculate the angle and distance to travel to (MAXX,MAXY)
2)Rotate for the calculated angle