CIM MPSG

Message Based Part State Graphs (MPSG)

Table of Contents

Introduction
Message-based Part State Graphs
MPSG - Definition
MPSG for Windows
The MPSG Builder
The MPSG Control Software
The TCP/IP Communications
Implementation Example

Introduction

A Message-based Part State Graph (MPSG) is a formal model of the execution component of shop floor controllers and serves as the input to an automatic code generation system. Within the target environment, the shop floor controllers are distributed according to a hierarchical architecture. Control is exercised through communication among the distributed controllers. The MPSG model represents the distributed shop floor controllers as communicating finite state machines. As such, an MPSG formally defines the protocol that the controller accepts. The MPSG model serves as an input to an automatic code generator for the execution portion of a controller. In order to have an operational controller, however, this execution module must be combined with a planner and scheduler which perform the decision making functions.

Top

Message-Based Part State Graph

In a distributed control system, control is exercised by passing messages between controllers and by performing controller tasks. The set of messages coming into and going out of a controller along with the set of controller tasks will be referred to collectively as a set of controller events. Furthermore, a processing protocol for a part is defined as a sequence of controller events required to process the part within the scope of a controller. For example, Table 1 shows the sequence of controller events required for a robot to load a part on a machine tool under the direction of a workstation controller.

In this situation, the workstation asks the machine tool where to place the part, and then synchronizes the actions of the machine tool and the robot during the transfer of the part. Although this structure imposes a hierarchical relationship between the controllers, the MPSG model itself is independent of the control architecture. It would be a simple modification to remove the workstation controller and have the robot and machine controller communicate directly. Similarly, the messages passed between controllers represent information flow which could also be achieved through queries to databases or through other forms of interaction. Moreover, these modifications would have no impact on the MPSG model for either device.

There are three distinct processing protocols associated with the dialogue in Table 1. The first is a workstation processing protocol, which includes all messages received by and sent from the workstation controller (events 1, 2, 3, 5, 6, 8, 9, 10 , 11, 12). The second is the machine tool processing protocol, which includes all messages received by and sent from the machine controller as well as all tasks issued to the machine by the equipment controller (events 1, 2, 6, 7, 8, 12). The last protocol is the robot processing protocol which includes all messages received by and sent from the robot controller and the tasks issued to the robot by the robot controller (events 3, 4, 5, 9, 10, 11). The individual controllers are each responsible for implementing their respective processing protocols. The interaction of these controllers during system operation creates the dialogue illustrated in Table 1. The objective of the MPSG-based shop-floor control generation is to provide formal definitions of the processing protocols and then to use these formal definitions to automatically generate a software implementation of the execution module for each controller.

Top

MPSG - Definition

A message-based part state graph (MPSG) provides a formal description of the processing protocol. As such, an MPSG describes the behavior of a controller from the parts' point of view, and each part within the domain of the controller is in a particular "state" as described by the MPSG for that controller. The MPSG model provides no information about the system state. The system state can only be determined as a function of all of the individual part states. So, given a part in a particular state, the MPSG determines which controller events are "legal" with respect to that part and how to transition when one of these legal events occurs.

An MPSG is a modified deterministic finite automaton (DFA), similar to a Mealy machine. The input to the MPSG is generated through messages from other controllers in the system and the output consists of messages sent to other controllers. The set of all MPSGs for a manufacturing system define a communication protocol for the system. The communications protocol can be extended to be a processing protocol by adding the controller tasks to the protocol. An important characteristic of DFA is that there are known methods for automatically constructing recognition programs, called lexical analyzers, based on the DFA. A lexical analyzer recognizes the same set of strings as the DFA and allows external software modules to be executed upon recognition of individual symbols in a string. Lexical analyzers are typically used in compilers to separate the input source code file into a stream of tokens which is fed to the parser. By modifying the structure of the DFA to accommodate a description of the processing protocol for a controller, these automatic generation techniques can be adapted for use in shop floor controller generation.

There are two primary modifications of the DFA structure required to model shop floor controllers. First, the input mechanism must be modified to accept input from multiple streams. This is accomplished by using the set of controller events as the input alphabet and by creating multiple input mechanisms for reading events. Second, the transition function must be modified so that controller tasks can be performed during state transitions. A Mealy machine is a DFA that defines symbols which are output during state transitions. For the current purpose, a similar mechanism is used to perform controller tasks such as moving a robot, opening a vise of fixture, or machining a part. This is accomplished by introducing a set of controller actions and a corresponding controller action transition function. Controller action is an executable function which performs some controller action.

In a standard DFA implementation the input symbols are read from a single stream (e.g. a compiler reads a source code file). In an MPSG implementation, however, the input symbols are read from two different streams: the controller communications module, and the task list. The communications module receives incoming messages from the supervisory and subordinate controllers and the task list is the communications medium between the execution module and the scheduling module or decision-maker within the controller. The input alphabet is, therefore partitioned into three sets of controller events based on the event type : (1) a set of valid input messages which are received from other controllers. These events are read from the communications module, (2) a set of valid output messages which are sent to other controllers in the shop, and (3) a set of controller tasks which identify controller actions to be executed. (2) and (3) are specified by the scheduler by placing them on the task list and these must be scheduled events because they can initiate physical action in the manufacturing system. For example, moving a robot into a machine tool is a task from the robot's point of view. From the machine tool's point of view, granting permission to enter the machine's work volume is an output message. Both of these can initiate the physical action of moving the robot. By contrast, incoming messages can only change the state of the part. As such, an output message is essentially a special case of a task, where the task is to send a message to an external system. The distinction is made because output messages from one controller become input messages to another controller whereas tasks are specific to a single controller. Consequently output messages for a controller must also appear in another controller's protocol and tasks are specific to the local protocol.

The set of controller actions is a set of executable functions which perform the controller tasks (sets (2) and (3) mentioned above). For example, the task function grasp_part is an executable function which closes the machine tool's part fixture. The implementation of these functions is device specific (e.g., the action for a solenoid-activated pneumatic vise would be different from the action for a vise activated by a G-code). Upon successful completion of the task, the MPSG undergoes a corresponding state transition.

The feasibility of many controller tasks depends on the current system state rather than the part state. For example, putting a part on a fixture is only feasible if there is no other part currently on the fixture. In general, these conditions are verified by the scheduling module (using the system state, which is external to the MPSG model). However, since the execution module causes physical action, there must be a mechanism for physically verifying certain preconditions. The physical preconditions are used to verify the system state prior to executing controller tasks. Many of these conditions involve other parts within the system. Since the MPSG models part states rather than system states, a mechanism for identifying external constraints is required. Associated with each controller action task there is a physical precondition, which must evaluate to true in order for the corresponding controller action to be called. If this condition does not evaluate to true the specified task is not consumed by the MPSG, and no state change occurs. The physical preconditions are used to prevent catastrophic errors in the system. A catastrophic error involves a collision between machines or parts within the system. For example, if a robot is holding a part and is instructed to pick up another part, a collision will occur between the part in the gripper and the part to be picked up unless the robot knows to queue the pickup task until the gripper is unoccupied. The physical precondition for the robot pick task provides this information and will prevent this collision from happening.

The logical preconditions mentioned earlier in the description of the physical models are determined by the process plan for the part and are not considered by the execution module. As such, these preconditions are dependent on the specific parts being processed. The execution module is independent of the specific parts and must, therefore implement tasks based only on the physical preconditions. So the execution module verifies and performs "possible" tasks, not necessarily "smart" tasks. Furthermore, the controller action must also successfully execute in order for the task to be removed and a state change to occur. This will prevent the state change from occurring in situations where the controller action fails due to an equipment problem. Therefore, given an MPSG in a particular state, scanning task or output message , the following pseudocode represents the controller operation.

determine the controller action

if <<physical preconditions evaluate to true>>
if the action executes change states remove task from the task list
else notify error recovery
endif
endif

Verifying the successful execution of the controller task facilitates error recovery when an unexpected event occurs. For example, if a robot drops a part during a move task, the task will not successfully complete. The last valid state will correspond to the most recently completed action or message. In this case, error recovery might remove the task from the task list. Optionally, M could transition to an explicitly defined error state based on the message received from the robot.

Top

MPSG for Windows

The MPSG for Windows software is used to automatically generate the control software for an equipment from the MPSG for the equipment. The software is written in Visual C++ (ver 4.0) and runs on 32-bit Windows Operating Systems. The software comes in two parts - (1) the MPSG builder, and (2) the MPSG control software. The MPSG builder automatically generates some files using the MPSG of the equipment for which control software is required. These files are then introduced in the control sofware project and compiled to generate the executable control software for the equipment. The state change transitions as specified by the MPSG and the TCP/IP-based communications necessary to communicate with other controllers is incorporated into the control software. The subsequent sections describe the entire process of control software generation using the MPSG for Windows software.

Top

The MPSG Builder

The MPSG builder is used to generate the files for the control software that are specific to the MPSG of the equipment. Thereby, the MPSG of the equipment is the necessary input for the builder. The MPSG is provided as an ASCII text file with *.m extension. An example MPSG is shown in Figure 1.

The *.m files is made up of four sections. The first section is the definitions section contain information about the name of the controller class, object and output files. The 'states' field specifies the number of states in the MPSG. The 'in', 'out', and 'tasks' fields specify the number of input messages, output messages, and task functions in the MPSG respectively. The 'final' field specifies the final state of the MPSG while the 'assign' field specifies the possible initial input messages of the MPSG. The second, third and fourth sections specify the state transitions on input messages, output messages and task functions respectively.

The MPSG builder MPSG.exe is run from command line with *.m file name as argument (without the .m extension). The MPSG builder generates the *.sch, *.h, and *.cpp files, the names of the files being as specified in the 'output' field of the *.m file ('example' in this case). These files are to be added to the project of the MPSG control software and compiled to obtain the control software for the equipment.

Top

The MPSG Control Software

As specified earlier the *.cpp file generated by the builder is added to the project file control.mak and compiled in order to obtain the MPSG control software control.exe for the equipment. This executable is a generic control software that just has the MPSG state-transitions and the communications embedded in it. Running the executable at this stage would just take one through the state transitions without any real task function executed. This initial run would enable in verifying the correctness of the transitions as desired. (It is necessary to have a default.map file in the same directory as the control.exe, the details of this file are subsequently)

The automatically generated *.cpp file provides functions for each task function with its corresponding pre-condition function. The user-defined code has to be included in these functions to perform the desired task action functions. (Each task function has a commented line indicating the place where the user-defined code is to be included). Once the user-defined code corresponding to the task functions is added, the project is compiled again to generate the final operational control software. This software can be run in real/simulated execution and communication mode. In simulated communication mode, the output messages are not really sent, but just simulated. Similarly, in the simulated execution mode, the task functions are not actually executed. This mode is thus used for dry-runs when testing.

The controller has a GUI with windows for entering console messages, for displaying output, for displaying part information and for displaying controller events history. The console messages can be entered from the keyboard and are typically used to enter controller in-coming messages. The part information window provides information such as part number, current state of part and the location of each part in the vision of the controller. A part can be entered into the vision of the controller by double-clicking on 'New Part'. A dialog-box with the list of assign messages for the controller opens up. The user has to select the approproate assign message and enter the part number of this new part. The user can also enter blackboard (described below) entries for that part. The new part now appears on the part information window and double-clicking on its entry opens up a dialog-box with the possible state transitions from its current state, its blackboard entries etc. A desired state transition can be selected by double-clicking on the appropriate transition entry in the list. The event history window maitains a chronological history of all the controller events. The output window is used to display general information. Additional help is available by typing the 'help' in the console input window.

The options menu in the mainframe menu provides the option to turn the scheduler 'on' and 'off' (default in 'on'). When the scheduler is 'on', the out-going messages and the task action functions are scheduled in the task list automatically and are executed. Turning the scheduler 'off' enables the user to schedule the tasks manually. The views menu has options to clear the output, the part information and the event history windows.

The blackboard is used to maintain all data in the controllers. It is a data list that is used by the controller to maintain part information, node number information (for TCP/IP communication) etc. The blackboard consists of three tuples - (1) the element id, (2) the key id, and (3) the key value. This data list can be updated from entries from the default.map file, addends to in-coming messages, or by using blackboard administrative commands from the console input window. The controller obtains necessary information by appropriately querying the blackboard.

Top

The TCP/IP Communications

The controllers communicate by passing messages consisting of strings between controllers. The basic string format is the following: SOURCE:DESTINATION:MESSAGE where SOURCE and DESTINATION are the source node number and destination node numbers, respectively, as set in the DEFAULT.MAP file and MESSAGE is the message to be transmitted. The strings are transmitted using TCP/IP stream sockets.

The controllers use the MFC 4.0 class CSocket to implement TCP/IP stream communications. For an application to communicate with the MPSG controllers it must implement stream TCP/IP communications and use the message format described above.

Having done that, the application, as all controllers, will connect to the Router application which handles communications among controllers. The Router parses the message, checks if the destination controller is available, and sends the message to the appropriate controller if it is available.

The last thing needed to communicate using the scheme described above is a way of tracking the node numbers associated with the nodes in the simulation. For the MPSG controllers this was done using the DEFAULT.MAP files. There are two types of DEFAULT.MAP files, one type for controllers and one type for the Router.

%my_node_number
%superior_node_number
%router_node_number
%router_ip_addr
%routing_port
list* of all nodes in simulation
....
non-negative number
non-negative number
non-negative number
valid Internet IP address
valid TCP/IP port number

Description of DEFAULT.MAP file for a controller.

*The last element in the DEFAULT.MAP file description is a list, each element of which is a 3-tuple containing the nodename, the descritptor word node, and the node number associated with the node name.

%my_node_number
%routing_port
list of all controllers
...
non-negative number
valid TCP/IP port number

Description of DEFAULT.MAP for the Router application.

For Arena/SIMAN to communicate with the MPSG controllers the following

1.. Place a copy of the RTDLL.DLL that has been modified to communicate with the MPSG controllers in the Arena directory or inidicate its location under the Setup selection of the Run menu item.
2.. Set the environment variables (listed below) appropriately.
3.. Start Arena (by typing start arena) from the same command line from which the environment variables listed above were set.

The following environment variables are needed by the RTDLL.DLL to initialize its communications components.