Faculty:

Embedded systems are specialized computer systems that are part of a larger system or machine. Typically, an embedded system is housed on a single microprocessor board with the programs stored in ROM. These systems consume most of the microprocessors in the market and constitute a significant portion of the computer industry [1]. Virtually all appliances that have a digital interface utilize embedded systems. They can be found in consumer electronics (VCRs, cable boxes, microwave ovens, and video games), automobiles (cruise control, engine control, and anti-lock brake systems), medical appliances (life monitoring systems and rehabilitation exercise equipment), electronic commerce (automated teller machines and modern vending machines), and communication devices (cellular phones and satellite receivers).

The embedded system software can generally be modeled as one of two classes of problem solving methods: a) mathematical or data processing methods and b) decision making methods.

Mathematical methods are used in embedded systems with small number of complex inputs. The problems solved by these methods have mathematical solutions, such that the output response is calculated as a func tion of the inputs. The problem solving software is made up of a few modules that use numeric equations to produce the results. Robots, laser printers, scanners, pagers, personal communication systems, ATM machines, credit card readers, and digital cameras are examples of the applications that use mathematical methods.

Decision making methods are usually employed in embedded systems with large number of simple (binary) inputs. In contrast to the previous type, the problems solved by these methods usually have no mathematical solutions and use monotonic logic and heuristics to achieve reasonable results. The decision-making module consists of numerous conditional statements, referred to as rules. It selects the appropriate output by making a series of binary decisions based on the inputs. Examples of these systems are distributed sensor-based control, security and monitoring systems, navigation systems, and large building temperature control.

While there has been extensive research in providing efficient component-based software architecture for applications using mathematical problem solving algorithms [2] , little progress has been made in develop ing time-bounded deterministic decision-making solutions for embedded systems. The key contribution of this research is a component-based software infrastructure that facilitates the development of decision-making modules in real-time embedded systems. The objective of this research is to provide a component-based methodology to support decision-making in real-time embedded systems. Specific goals include:

Component-Based Design: Provide a software framework to facilitate the development of real-time decision-making modules. Today, the software development for embedded system resembles more an art form rather than a branch of engineering. Our intent is to simplify this procedure such that programmers with limited software engineering knowledge will be able to carry out the implementation and maintenance of these systems. Similar to the concept of port-based objects in the Chimera Methodology [2] , the proposed framework will ease the burden of programming by supplying major portion of the code. The developer is only required to provide several methods in accordance with the detailed specifications given by the framework. The reduction of the amount of user code and ease of programming will significantly lower the effort and cost of the design, implementation, and maintenance of the real-time decision making modules.

Time-Bounded Decision Making: Introduce a deterministic and time-bounded decision making mechanism. In real-time applications, the time of generation of the result becomes as important as its correctness. A late result, whether correct or not, is a failure and can be detrimental. For example, a life support system should respond quickly to the changing conditions of the patient. Any delay may have fatal consequences, and the manufacturer of the machine will face serious legal actions. Or, if a moving robot fails to detect and react to the surrounding obstacles in time, it may collide to other objects and cause damage. Hence, it is imperative that every task has a predictable time-bounded execution time. If the worst-case execution time of every decision-making component in the module is known, the response time (time lag from input to output) is bounded.

Cooperation: Develop an efficient dispatching mechanism to resolve conflicts among problem solvers and to activate them in a timely fashion. Cooperative problem solving is a group of problem solvers working together to solve problems that are beyond their individual capabilities. Cooperation is necessary because no single problem solver has sufficient expertise, resources, or information to solve the problem. Three types of problem solvers can be distinguished in cooperative systems: collaborative, competitive, and conflicting problem solvers.

Implementation: Use a low-cost and safe testbed to implement and validate the concept of real-time decision making in embedded systems. Two embedded systems, that require real-time decision-making abilities, have already been developed in SERTS (Software Engineering for Real-Time Systems) lab. The first system is an electric train set with large number of binary sensors mounted on the tracks. The software that controls the train will show how decision-making can be used for error detection and handling. The second application is a pinball machine. The current decision making module is implemented using the sequential organization of rules. This module, that consists of approximately 5000 lines of code, will be redone to demonstrate the validity of the concepts of this research, including ease of programming, embeddability of the application, and time-bounded execution.

Some of the problems with the existing approaches include difficulty of programming, absence of hard real-time guarantee, lack of support for embedded processors, and huge memory requirements. First, due to dependencies among rules, it is difficult to implement decision-making structures, as experienced in the pinball project. Organizing the rules is a very complicated task, because the order of the rules affects their outcomes. Second, most of the current applications are at best 'soft' real-time systems, in that they claim to be fast [3]. A 'hard' real-time system would have features that guarantee a response within a fixed amount of real-time. As a result, these systems are unable to guarantee that all the hard deadlines will be met and at best can be used for soft real-time processing. Third, rule-based systems are intended for powerful 32-bit CPUs that can be found in personal computers and require special development tools such as real-time expert shells. However, embedded system usually use low-end microprocessors (8- and 16-bit CPUs), microcontrollers, or DSP processors, and the only available development tools for embedded processors are C compilers, assemblers, linkers, and debuggers. Finally, to speed up the decision-making process, the inference engine of a rule-base system records the information about the previous decisions, that requires large amount of memory, while the available storage in embedded systems is generally in kilo byte range.

This research is not limited to systems with binary inputs. Even systems that use mathematical methods can benefit from it. For example, error detection and handling is a form of decision making. Error conditions can be represented by a binary array such that each bit is associated with an error. When an error occurs, the corresponding bit is set. The decision-making module will then activates the error handlers in a timely fashion with respect to the level of urgency of the error. One of the benefits of this approach is that error handling is not scattered throughout the application. The decision maker is the only module that have the access to the exception handlers. Reconfigurable software can also take advantage of decision-making in reconfiguration on the fly. The status of the system can be represented by a set of flags. The decision making mechanism monitors those flags and changes the configuration of the modules accordingly. Other applications include advisory, monitoring, and diagnostic systems. This concept can also be applied to more complex and multi-valued inputs through replacing monotonic logic by fuzzy logic. The proposed research combines the advantages of the current approaches, e.g., separation of knowledge from its control, modularity, and offers an agent-based paradigm to resolve the above problems.