UNIVERSITY OF
ILLINOIS LIBRARY
ftf URBANA-CHAMPAIGN
BOOKSTACKS
Digitized by the Internet Archive
in 2011 with funding from
University of Illinois Urbana-Champaign
http://www.archive.org/details/distributedknowl1159shaw
COPY 2
FACULTY WORKING PAPER NO. 1159
JUL 2 5 1985
A Distributed Knowledge-Based Approach To Flexible Automation
Michael J. Shaw Andrew B. Whinston
College of Commerce and Business Administration Bureau of Economic and Business Research University of Illinois, Urbana-Champaign
BEBR
FACULTY WORKING PAPER NO. 1159 College of Commerce and Business Administration University of Illinois at Urbana-Champaign
July, 1985
A Distributed Knowledge-Based Approach to Flexible Automation
Michael J. Shaw, Assistant Professor Department of Business Administration
Andrew B. Whins ton Purdue University
ABSTRACT
This paper applies automatic planning and distributed problem solving methods to the on-line planning and control of cellular flexible manufacturing systems, consisting of asynchronous manufac- turing cells. A knowledge-based approach is used to determine the course of action, resource sharing, and processor assignments. Within each cell there is an embedded nonlinear planning system that executes dynamic scheduling and supervises manufacturing operations. Because of the decentralized control, real-time task assignments are carried out by a negotiation process among cell hosts. The negotiation process is modeled by augmented Petri nets — the combination of production rules and Petri nets — and is executed by a distributed, rule-based algorithm.
1. Introduction
Flexible automation — automation that can handle a large and con- stantly changing variety of produced items — has played an increasingly important role in the efforts to improve the productivity of the manu- facturing industry [15] [23]. The recent progress in computer tech- nologies has accelerated the realization of flexible automation. The use of computers in manufacturing, such as the numerically controlled (NC) machines, adds programmability and thus versatility into manu- facturing systems. More important, computers also provide on-line exe- cution of manufacturing planning and decision making. These two capabilities, computerized control and on-line planning, are integrated into a well-orchestrated, automated manufacturing system — referred to as the Computer Integrated Manufacturing Systems (CIMS) — that can pro- duce wide-ranging items efficiently.
In implementing CIMS, the cellular architecture has emerged as the most effective and economical organization for the system [5] , [22] , [29] . Such a system, referred to as the cellular flexible manufac- turing system (CFMS), consists of a collection of "manufacturing cells." As shown in Figures 1 and 2, each cell is controlled by a host computer, which supervises the activities in the cell. Any cell can communicate with other cells through a communications network (e.g., a local area network). The computer architecture is highly distributed, e.g., the host computers used in the National Bureau of Standard facil- ity range from a VAX 11/780 to 8086- or 68000-based single board com- puters and multiple processor systems 122] .
Insert Figures 1 and 2 Here
-2-
Intelligent manufacturing planning and control in a CIMS requires knowledge bases that contain information about current tasks, manu- facturing procedures, and the production environment [22]. Furthermore, the evolution of the CIMS into distributed architectures has compli- cated the information processing requirements. Issues that must be considered include the effective planning and problem solving in the distributed environment; the structuring of knowledge bases to facili- tate knowledge sharing between system components; and the coordination and communication among manufacturing cells. To achieve these, this paper develops a distributed knowledge-based approach for manufac- turing planning and control. In it, an embedded nonlinear planning system in each cell generates production procedures, supervises resource sharing, and guides manufacturing executions. This planning system also keeps track of the manufacturing environment, directing adjustments on the production procedures when necessary.
Moreover, since a job may consist of a set of tasks to be assigned to several manufacturing cells, the system needs to supply a coor- dinating mechanism that, through the communications network, permits the matching of tasks to cells. To achieve such coordination by decentral- ized control, three issues need to be addressed:
(1) the design of an interface language that enables effective com- munication among cell hosts;
(2) the model of the problem-solving process which, through the com- munications network, dynamically distributes tasks among the cells; and
(3) the programming and execution of this problem-solving process at each cell in a decentralized manner.
-3-
Following the distributed problem solving framework [8], [31], this paper uses the "contract net" approach to meet these requirements. A negotiation protocol, a high-level protocol, is used to ensure orderly information transformation and events sequencing between asynchronous, cooperating cells. The underlying idea is to structure the interac- tions among cells by tasks negotiation.
In order to carry out the process systematically, it is important to have a good representation of the negotiation protocol and to capture the dynamic, concurrent nature of the protocol. Also, this represen- tation should be integrated into executable programs to coordinate task execution.
The augmented Petri net, an integration of production rules and Petri nets, is used to model the negotiation protocol. The automation of this augmented Petri nets leads to a distributed algorithm for task allocation. Since the procedure is designed to be implemented by a variant of a rule-based system — i.e., the control production system, the knowledge-based system in a sense contains two kinds of program knowledge: the knowledge for task planning and the knowledge for intercell cooperation.
The remainder of this paper is organized as follows. Section II characterizes the distributed problem-solving system in the CFMS envir- onment and discusses the planning approach for flexible automation. Section III shows the use of negotiation protocol for coordinating the tasks; this protocol is then represented by the augmented Petri net model. Section IV illustrates the implementation of the negotiation protocol. The final section summarizes the paper.
-4-
II. Knowledge-Based Planning
The planning system, when organized as a knowledge-based system, treats knowledge on three levels: data, knowledge base, and control. By contrast, conventional programs treat knowledge on only two levels: data and program. At the data level a knowledge-based system stores declarative knowledge about the goals, the current situation of the world, and the semifinished plan. At the knowledge-base level is stored the domain-specific, procedural knowledge. This knowledge models the actions of the world, and it is often represented by pro- duction rules or operators. Finally, at the control level the know- ledge about the strategy of plan construction is stored; this is the control knowledge indicating how to select operators, and when to apply them.
Because planning involves exploration of alternative sequences of actions, a symbolic model of the real world, the "world model," repre- sents the environment as the plans evolve. For any given planning problem, the initial condition and the stated goal condition are both treated as instances in the world model. The generation function of a planning system, then, is to construct a course of action that trans- forms one state of the world model, which contains an initial con- dition, to a state which satisfies the goal condition. Thus, as shown in Figure 3, a planning system for the CIMS has three basic com- ponents :
Insert Figure 3 Here
(1) the world model, which contains a symbolic description of the real world. This world model is represented by the collection of first-
-5-
order predicates in a database. Any instance of the database is called a state of the world model. Examples of such database elements in a world model are shown in Table 1.
Insert Table 1 Here
(2) The action model, which describes the transformational effects of actions that map states to other states. Such transformations are usually modeled by operators similar to the STRIPS operators defined in [10]. In such an action model, each operator can be specified
< list-of-arguments >
< list-of-precondition-literals >
< list-of-add-list-literals >
< list-of-delete-list-literals >
< resource-name >
< length-of-duration > In addition to the standard STRIPS formalism — which specifies an action by the add list, delete list, and preconditions — we have also included two more descriptions for each action — the "resource" used during the action, and the "duration" of the action. There are two advantages to this addition: the increased representational power of the action model and the resulting acceleration of conflict detection and conflict resolution. An example is shown in Figure 4.
< Action - name >
< Precondition >
< Add list >
< Delete list >
< Resource >
< Duration >
Insert Figure 4 Here
-6-
(3) The inference engine, which directs the plan generation process.
It selects a sequence of operators to achieve the goal state from
a given initial state.
The linear plans can be generated by any STRIPS-like plan genera- tion system [9], [10]. Such a planning system can use a backward- chaining method in searching for the best actions [26] — i.e., it works backward from the goal state and find a sequence of actions that could produce this goal state from the initial state. The process of plan generation, then, can be viewed as finding the solution path in a search tree. The root of the tree is the goal state, and instances of operators define the branches. The solution path starts with the root (the goal state) and leads to the leaves (the initial state), thereby defining the plan. An example of the search trees generated by the planning system are depicted in Figure 5.
Insert Figure 5 Here
Within this planning framework, the manufacturing process cor- responding to each task is modeled by state-changing transformations, represented by operators. If the manufacturing processes for different tasks are independent, then, in principle, they can be executed in parallel. In reality, however, different tasks usually are competing for machines, tools, and other resources; therefore, the planning system must take into account the interactions among the processes. In the planning literature, this interaction problem between tasks have been treated by imposing constraints between planning steps to avoid any potential conflicts [28], [34], [35]. Two kinds of schemes have
-7-
been used for this purpose: the "critic" mechanism [28] , and the "reasoning about resource" scheme [35] . Because the plans generated by these methods are partially ordered, these methods are called "nonlinear planning."
For the flexible manufacturing environment, Shaw [29] used a non- linear plan-generation scheme, implemented in Franz LISP, to derive the desired production plans within each cell. The scheme requires four steps:
Step 1. Generate a linearly-sequenced plan for each task.
Step 2. Identify problematic interactions between the planning steps.
Step 3. Use precedence constraints to avoid conflicts.
Step 4. Identify alternative planning steps to improve the performance. An example of the partially ordered plan resulting from the scheme is shown in Figure 6, where each of the nodes represents a planning operator.
Insert Figure 6 Here
This approach displays some desirable characteristics for real-time planning and control in the CIMS environment. First, it is goal- directed, i.e., users only need to specify the goals and the planning system would, accordingly, derive the necessary steps on-line. Second, it is dynamically adjustable. New goals can be accomodated while the current production plan is still being executed; also, plans can be modified when unexpected events occur (e.g., tool or machine breakdowns). A "plan revision scheme" is initiated when bottlenecks
-8-
are detected; the scheme, in turn, seeks to use alternative resources to improve the throughput [29]. In addition, travel paths taken by guided carts or the arm movements of neighboring robots should be analyzed so that any potential conflicts or interferences are avoided [2], [20J.
Formally, the problem to be solved in the planning system can be defined as a quadruple
PR = <S,0,IS,G>
where S is the set of states in the database, 0 is the set of opera- tors, defined as functions S -► S. Both IS and G belong to S ; IS denotes the initial state, and G denotes the goal state. The infer- ence engine selects the sequence of operators in the search space based on predefined control strategies.
To perform planning by a distributed system with a group of "agents," the problem PR is decomposed into subproblems. The final plan consists of a collection of plans for these subproblems, coor- dinated to be applicable to all initial states IS and to achieve the goal state G. The coordination between the planning agents may be accomplished through messages passed between agents. The key issue, then, is how to automate this coordination to result in orderly interactions. The strategy we shall use throughout this paper consists of four phases:
(1) Goal decomposition. A job is decomposed into tasks to be exe- cuted by different cells.
(2) Tasks distribution. Tasks are distributed among the cells so that each task is performed by the most appropriate cell available.
-9-
(3) Tasks execution. Cells perform the assigned tasks as required.
(4) Tasks synthesis. Finished tasks of the same job are assembled. This strategy is referred to as the task-sharing strategy. Another
widely used strategy is result-sharing — i.e., each agent will indepen- dently initiate its problem solving activities and subsequently aggre- gates its results [8], [19]. In the foregoing task-sharing scheme, the task distribution problem needs special attention because of the loosely coupled, decentralized control structure. The following sec- tions discuss the use of a negotiation process to achieve it.
III. The Contract Net Framework A. The Negotiation Procedure
In a CFMS, each manufacturing cell specializes in a predetermined part family so as to reduce the set-up cost. Several cells may be assigned to a single job if its components belong to different part families. To utilize the system resources efficiently, each task of a job must be assigned to the most appropriate cell — this process is referred to as task sharing. Task sharing also occurs when a cell is overloaded and needs to distribute some of its tasks.
A widely used metaphor for distributed problem solving is the "society of experts metaphor" — i.e., the system under study is viewed as a group of experts that solve problems cooperatively [4], [8], [17], [24], Applying this metaphor to the CFMS environment, we will treat each cell's host computer as an agent planning and managing its local tasks. The whole CFMS, then, is a group of such agents with different areas of specialties, and task sharing can be carried out by proper cooperation among the cells. A cell should "negotiate" with other
-10-
cells to determine how to share tasks. Specifically, announcement-bid- award cycles are used to distribute tasks to appropriate cells.
The anouncement-bid-award cycle is initiated when a manufacturing cell has a task it is not capable of handling. The cell announces the task to other cells to seek assistance. The announcement messages con- tain three types of task-dependent information:
a) The eligibility specification: listing the qualification for a cell to submit a bid.
b) The task abstraction: providing a brief description of the task
to allow interested cells to evaluate the task by comparing it with
other announced tasks. 3) The bid specification: specifying the expected format of the bid
to be submitted.
A cell in the network keeps an "active-task announcement list" for every machine in the cell and ranks each announced task in the list according to its type (Table A.l). When a machine becomes idle, the cell selects a task at the top of the list and submits a bid to the cell which announced the task (the manager cell). A manager cell may receive several such bids in response to a single task announcement. The award decision is made based on all the bids received, and the manager cell selects the most preferable cell based on a ranking func- tion, calculated by the distance between the two cells, the estimated processing time, and the loading factor of the bidder. The successful bidders are informed of the award through award messages from the manager cells and the task will be transferred accordingly.
-11-
B. The Negotiation Protocol
To execute the negotiation process by way of communications activ- ities, a set of communication rules must be established to regulate the interactions between the cells so that they proceed in an orderly fashion. Furthermore, the protocol also has to carry out the task sharing process — the process of distributing tasks among cells. A for- mal model for the CFMS protocol should contain three components:
1. A formalism for the message content. This task-dependent language describes the task information in messages.
2. A formalism for the message format. This formalism, independent of the task domain, is used to format all the messages, so that the message content can be properly interpreted. For instance, the formalism for a task announcement message is:
<task-announcement>: = TASK- ANNOUNCEMENT
{ name}
{ task-abstraction} {eligibility-specification} {bid-specification} An instance of such a message is shown in Figure 7.
Insert Figure 7 Here
3. A formalism for the negotiation process. This formalism is used to describe the proper sequencing of actions to carry out nego- tiation procedure among cells. Since there may be several manager cells at the same time, this formalism needs to describe asyn- chronous, parallel processes.
-12-
The first two formalisms can use the context free grammar with BNF expressions. This method is fairly standard in modeling protocols and will not be discussed here. Details of it can be found in [31], [33]. Subsequent discussions focus on the formalism for task nego- tiation.
The network, on which the negotiation protocol is implemented can be modelled as a three-layer structure. This structure is illustrated in Figure 8. The negotiation protocol is a high-level, problem- oriented protocol governing the coordination among cell hosts. The host-to-host protocol, or the transport protocol, is used to provide reliable communication between processes in different host computers; it is often implemented by programs called transport stations in the host's operating system. The lowest level of the protocol, the transmission protocol, is responsible for the correct transmission packeting and routing of data between cells; the transmission layer actually incorporates the functions of the physical layer, the data- link layer, and the network layer in the more common ISO multilayer protocol model defined in [32]. Based on this layered protocol struc- ture, task sharing among cells can be carried out by the negotiation protocol at the problem-solving layer, with proper communications sup- port from the transport and the transmission layers. Section IV will illustrate the utilization of a graph model, the augmented Petri net, to specify and, subsequently, to program the negotiation protocol.
Insert Figure 8 Here
-13-
IV. Modeling and Programming the Negotiation Protocol A. A Model for the Negotiation Process
A good model for the negotiation process must describe two aspects of task negotiation:
1. a procedural representation of the communication and coordination mechanisms between the cells; and
2. a declarative representation of the local problem solving process within a cell.
We use the augmented Petri net model [36] to achieve these require- ments. The augmented Petri net is an integration of two representation models: production rules are used to model the individual events (the declarative representation), and the Petri net is used to model the interactions and temporal relationships between these events (the pro- cedural representation). The augmented Petri net model has been proven effective in modeling asynchronous, concurrent processes where the com- bination of state variables grows exponentially. In it, each tran- sition corresponds to a production rule and the Petri net structure of the model can be viewed as the interactions between the productions. To understand the mechanism of an augmented Petri net, let us first review some features of the Petri net as a modeling tool.
Originally designed to model process concurrency and precedence relations, the Petri net model has been used to model, specify, and verify communication protocols [6], [27]. The definition of the Petri net follows:
-13-
protocol at the problem-solving layer, with proper communications sup- port from the transport and the transmission layers. Section IV will illustrate the utilization of a graph model, the augmented Petri net, specify and, subsequently, to program the negotiation protocol.
to
Insert Figure 8 Here
IV. Modeling and Programming the Negotiation Protocol A. A Model for the Negotiation Process
A good model for the negotiation process must describe two aspects of task negotiation:
1. a procedural representation of the communication and coordination mechanisms between the cells; and
2. a declarative representation of the local problem solving process within a cell.
We use the augmented Petri net model [35] to achieve these require- ments. The augmented Petri net is an integration of two representation models: production rules are used to model the individual events (the declarative representation), and the Petri net is used to model the interactions and temporal relationships between these events (the pro- cedural representation). The augmented Petri net model has been proven effective in modeling asynchronous, concurrent processes where the com- bination of state variables grows exponentially. In it, each tran- sition corresponds to a production rule and the Petri net structure of the model can be viewed as the interactions between the productions. To understand the mechanism of an augmented Petri net, let us first review some features of the Petri net as a modeling tool.
-14-
Definition 1 (Petri Net)
A Petri net, W, is a quadruple, W = <P,T,I,0>, where P is the set of places, T is the set of transitions; I:T -► P* defines the input function, and 0:T -► P* defines the output function.
A place is marked if it has one or more tokens; a transition is enabled if each of its input places are marked. The firing of an enabled transition removes one token from each of its input places and adds one token to each of its output places. A token distribution among the available places in a Petri net is called a marking of the net.
Corresponding to each Petri net and an initial marking, Petri net language is defined as follows:
Definition 2 (Petri Net Language)
If there exists a Petri net, W = <P,T,I,0>, a labelling function 1 for the transition 1:T + Z, and an initial marking X, then all the possible sequences of transition firings constitute the Petri net language:
L(l) » (1(3) E Z*|B e T* and 5(X,B)}
where 6 is the next-state function. For a sequence of transitions
t.., t.„, ..., t., , 6(X, t., t.„t,,.. .t., ) represents that the firing jl j2' jk' jl j2 j3 jk'
of the transition sequence, t.., t . „ , up to t., , is legal.
We now proceed to define formally an augmented Petri net:
Definition 3 (Augmented Petri Nets)
An augmented Petri net is composed of seven elements:
-15-
APN - <P,T,I,0,X ,AP,D>
where <P,T,I,0> is a Petri net as defined in Definition 1; X is the ini- tial marking of this net. The set of transitions, T, also defines the set of productions, with each transition corresponding to one produc- tion rule. D is the set of database elements in the production system and AP is the set of active productions whose conditions are satisfied by D.
A transition t in T is "firable" iff
(1) t e AP; and
(2) I(t) is marked; I(t) represents the set of input places of the transition t.
In the augmented Petri net model, since there is a production corresponding to every transition, we can label the transition and the associated production rule with the same labelling function. The Petri net language in the augmented Petri net can thus be seen as either the set of all possible sequences of transitions or, alter- natively, as the set of all allowable sequences of production rule invocations. If each transition corresponds to an activity, the Petri net language generates the correct sequence of activities.
Task negotiations for several tasks are usually executed con- currently. The manager cell may be ranking the incoming bids while the potential contractors at the same time are collecting task- announcements and deciding on whether to submit bids. Consequently, the transfer of messages (e.g., task-announcements, bids) from one cell to another requires synchronized activities among the cells
-16-
involved. Augmented Petri nets can help ensure the correct implemen- tation of these synchronized activities.
To use the augmented Petri net model, the negotiation process can be represented by two subsets: one (Figure 9) models the necessary actions of the manager cell who announces a task to other cells, pro- cessing the incoming bids and awards the task to the selected cell; the other sub-net (Figure 10) models the corresponding actions of the cells who receive the task-announcement (the contractor cells). This sub-net deals with the decision on submitting bids.
Insert Figures 9 and 10 Here
Each activity in the process is represented by a production rule, and the interactions among these activities are represented by the Petri net. Each transition in the Petri net (denoted by a bar in the figures) corresponds to one production rule. When a transition is enabled (i.e., all input places are marked), the corresponding rules will determine the firing condition.
Table 2 lists the set of production rules that correspond to the transitions in the two augmented Petri nets in Figure 9 and Figure 10. Rules Tl to T9 correspond to the task-announcement process of the manager cell; rules T10 to T16 correspond to the bid-submitting pro- cess of the contractor cell. At each step in the process, the aug- mented Petri nets guide the negotiation process of all cells so that the activities for task negotiation are correctly carried out.
Insert Table 2 Here
-17-
B. Implementing the Protocol
Consistent with the standard hierarchical structure for com- munications protocol [1], the negotiation protocol represented by the production system listed in Table 2 is specified at a higher level. Necessary support to carry out this high-level protocol is provided by protocol programs of lower layers, such as the transport and the transmission layers in Figure 6. Programming the production system in Table 2 requires three types of literals:
1. Simple predicates; these are state descriptions stored in the database (Table 3);
2. Functions; they return a binary value after their invocations. Functions are used mostly for conditions checking (Table 4);
3. Procedures; these are used to execute corresponding actions when rules are triggered. Some of these actions may include com- munication operations (Table 5);
Insert Tables 3, 4, 5 Here
Table 6 shows a language description, called PNL, for the Petri nets in Figures 7 and 8. The purpose of expressing Petri nets with a language like PNL is to have a machine-processable representation of the Petri net; the PNL is translated, in turn, into a procedure language recognizable to a host compiler [25]. To generate unambiguous Petri net language, the description and processing of PNL require that unique names be assigned to the places and transitions.
Insert Table 6 Here
-18-
C. Controlled Production Systems
The Petri net language discussed in Definition 2 can serve as the "control language" to regulate the invocation of production rules in the production system during its inference process. Such a production system whose control structure is represented explicitly is called a controlled production system.
Using control language in a rule-based production system gives two advantages: first, the execution becomes more efficient because the control language reduces the applicable set of production rules by eliminating irrelevant production rules from consideration; second, since the control structure is explicitly represented by this control language, it can be modified without having to change the contents of the production system. This separation between control and programs is an important feature of the knowlege-based programming [13], [18]. Now let us define a controlled production system and its relation with the augmented Petri net model.
Formally, a production system can be defined as follows:
Definition 4 (Production System)
A production system is a triple
PS = <R,D,h>
where R is the set of production names, D is the set of database ele- ments, and h is the interpretation of the production R, represented as:
h: R * (q,r)
-19-
q is the set of conditions and r the set of actions corresponding to R. The state of the production system is defined by the contents of the database elements. When the conditions of a production P , denoted q(P.), is satisfied by the current database, then P.. is said to be "invocable." If P. is invoked, then the database is transformed to a new state, denoted by r(P.).
Definition 5 (Controlled Production System)
A controlled production system is defined as a quadruple
M = <R,D,h,C>.
The subset <R,D,h> is a production system defined in Definition 4. A state in the CPS is defined by a pair S = <u,X.> with u e C and X, e D. A production rule p is said to be "applicable" if up e C. A state <up,X~> is said to be derivable from the state <u,X.>, denoted
<u,X1> -► <up,X2>
If p is applicable at <u,X.> (up e C) and the database elements in X. satisfy the preconditions of p (q(X. ) = TRUE), then the actions of p change X to X2 (r(X^ = X2).
The control language in effect guides the allowable sequences of production invocations, i.e., a production is applicable only if it is accepted by the control language. At each stage of the execution, the control language acts to "focus" the control on a subset of the pro- ductions, the applicable productions, and prohibits the other produc- tions from being invoked.
-20-
Based on Definitions 1 through 5, we can now propose a theorem which equates the augmented Petri net model to a production system controlled by the Petri net language.
Theorem 1 :
For any augmented Petri net
APN = <P,T,I,0,X»AP,D> there exists a controlled production system,
M = <R,D,h,C>
such that APN and M generate the same sequence of production rules.
Proof
For an augmented Petri net APN, the first five elements <P,T,I,0,X> can define a Petri net language L(l). (Definition 2)
Since the active set of productions, AP, in APN is generated by matching preconditions of the productions in T against the database elements in D, AP is derivable from the production system <R,D,h> in M. (Definition 4)
Now, if we let the Petri net language L(l) in APN be the control language C in M, then:
(1) (-►) If a transition t is firable in APN, t must satisfy (a) t e AP and (b) I(t) is marked. These are equivalent to the conditions (a) the production t is invocable in the production system <R,D,h> and (b) t is accepted by the language C. Therefore, t is applicable in M. (Definition 5)
-21-
(2) (+) If a production p is applicable in M, p must satisfy (a) p is invocable in <R,D,h> and (b) p is accepted by the control language C; these conditions are equivalent to the conditions (a) p e AP and (b) p z L(l); therefore the transition corresponding to p is firable in <P,T,I,0,X>. Thus, p is also firable in APN. (Definition 3)
Q.E.D.
This isomorphism between (1) the augmented Petri net model and (2) a production system model with a separate control language enables us to deal with the task-sharing problem by using the production system listed in Table 1, and the Petri nets (shown in Figure 9 and Figure 10) can serve as the control structure. Such an algorithm is similar to the inference procedure used in production systems, as the one used in 0PS5 [11]. The only difference is that in the beginning of each cycle the algorithm picks the "applicable" rules by the control language.
Procedure - Task-sharing {executed by a manager cell}
Input: a task T, consisting of a set of decomposable subtasks (t.)
Begin
Repeat {Based on Controlled Production System}
(Step 1) <Control> —
Determine the set of productions accepted by the control language
- p';
(Step 2) <Selection> —
Select the productions among p' which are invocable + CF {the conflict set} ;
-22-
(Step 3) <Conflict resolution> —
Select a production from the CF set according to the conflict resolution strategy;
(Step 4) <Execution> —
Activate the "then" part of the selected production; Until the goal condition appears in the database; end { task-sharing} .
The procedure uses the data-directed search scheme [3], [7]. In Step 1, p is the set of production rules whose corresponding transitions are firable by the current marking in the Petri net. Step 2 to Step 4 is the "recognition-action cycle:" a rule is invocable whenever there are database elements that satisfy the conditions of the rule. If more than one rule is invocable, then these rules are collected into the conflict set CF. A conflict resolution strategy is used in Step 3 to select one rule from the set CF. Although many conflict resolution strategies have been considered [3] [21] , Step 3 can be straightforward: select the first production rule that is applicable. Step 4, in turn, makes changes in the database according to the "then" component of the selected rule. The cycle continues until either of two conditions occurs:
(1) the goal state is derived and the inference procedure is success- ful; or
(2) the goal state has not been achieved, but the conflict set in Step 2 is empty.
In the second case, the inference procedure has failed; an exception handling routine will be called upon to take over.
-23-
D. Performance
The performance of the task-sharing algorithm is affected by two factors: the performance of (1) the inference procedure in the controlled production system and (2) the negotiation process among the cells. The former is determined by the organization and search strate- gies of the production system; the latter is determined by the param- eters of the negotiation protocol. This section will discuss both aspects.
For a conventional rule-based production executing data-directed inference procedure, the cycle time of the recognize-act cycle is [21]
T. cycle ■ T. condition-match + T. action
= (P x M x T. match) + ((A/P) x T.act),
where P = size of the production system;
M = size of the database (number of predicate literals);
T. match = Average time to find a match between preconditions
and the database elements; A = number of action elements of all rules; T.act = average time needed to execute the action parts of a
rule; and A/P = average number of actions of a rule.
Since the task-sharing algorithm utilizes a control language to screen the applicable production rules first, the cycle time of the production system is modified as
-24-
T. cycle' = T. control + (P* x M x T. match) + ((A/P) x T.act)
where T. control is the time needed to locate the applicable produc- tions by checking the control language. In our case, it is the time taken for the Petri net language to find the firable transitions based on the current markings.
P' is the size of the active production rules decided by the control language; in general, P' < P.
The response time of the negotiation process is the sum of four components :
T - T, + T2 + T3 + T4,
where T, is the time for making task announcements, T_ is the time for evaluating announced tasks by the bidders, T~ is the time for sub- mitting bids, and T, is the time for bid evaluation by the manager cell.
Among the four components, T. and T. are communications delays for transmitting messages, thus they are affected by the load of the com- munications network. T„ is the maximum time allowed for the bidder to evaluate tasks before submitting the bid. It should be adaptable to such factors as the deadline of tasks and frequency of job arrivals. If there is a deadline Tn for the job, then the manager cell should impose a time constraint on T„:
T2 < TD -Tx -T3 -T4 -T5,
where T, is the estimated travel time for the workpiece to get to the bidder cell from the manager cell.
-25-
E. Summary of the Approach
The production system, the inference engine, and the database for executing task-sharing are integrated into a knowledge-based system called the contract processor, to be implemented in every cell host. In terms of the distributed problem-solving strategy presented in Section II, the primary function of such a contract processor is to distribute tasks among the cells. According to this scheme, the complete distributed planning algorithm is shown in Figure 11.
The major thrust of using augmented Petri nets and the corresponding controlled production system is that it provides a suitably powerful modeling language for executing the task-sharing process. Because of the problem-solving ability of the negotiation protocol, the approach also has flexibility in achieving task sharing in different situations. More research needs to be done in exploring the optimization behavior of the negotiation process. Nevertheless, the knowledge-based approach has proved very effective in its performing the planning and control functions. In particular: (1) It enforces the separation of the knowledge description and the control structure. Knowledge is described by production rules and the control structure is represented by the augmented Petri nets. (2) It applies a uniform approach to both the multi-task planning within a cell and the task-sharing planning among the cells. As such, each cell's knowledge-based planning system con- tains two types of knowledge: first, knowledge for planning and sche- duling; and second, knowledge for task sharing and communication. (3) It uses a decentralized scheme to perform intelligent manufacturing planning and control. The approach, therefore, enjoys the benefits
-26-
associated with distributed processing systems such as: graceful degradation, modularity, extensibilty , improved performance, and reliability [12] .
Moreover, the utilization of the knowledge-based approach for handling information processing also permits future incorporation of expert rules and heuristics. In this context the generalized manufac- turing information system for a CIMS becomes a distributed expert system, at each node the knowledge base contains manufacturing opera- tors, task-sharing rules, and judgmental rules. This expert system's task is to utilize the system resources effectively in the dynamically changing environment.
V. Concluding Remarks
This paper has shown an approach for intelligent manufacturing information processing based on the distributed knowledge-based frame- work. The nonlinear planning system schedules tasks within each cell, and the negotiation protocol coordinates task sharing among cells. A model based on the augmented Petri nets has been developed to specify the negotiation protocol and to capture the dynamic and concurrent nature of the protocol.
The implementation of the protocol by a knowledge-based system enforces the separation of logic and control components in the computer program that executes the protocol; this gives flexibilities in the software design aspect of the implementation. The use of knowledge- based program also enables us to utilize unified representations for both the planning activities and the task negotiation process.
-27-
Ref erences
[1] G. Bochman and C. Sunshine, "Formal methods in communication protocol design," IEEE Transactions on Communications, pp. 624-631, 1980.
[2] D. Bourne and P. Fussell, "Designing programming languages for manufacturing cells," The Robotics Institute, CMU-Rl-Tr-82-5 , Carnegie-Mellon Universsity, 1982.
[3] B. Buchanan and R. Duda, "Principles of rule-based expert systems," Computer Science Department, HPP-82-14, Stanford University, 1982.
[4] B. Chandrasekaran, "Natural and social system metaphors for
distributed problem solving," IEEE Trans, on Systems, Man and Cybernetics, Vol. 11, No. 1, pp. 1-5, January 1981.
[5] Cutkosky, et. al. , "Precision machining cells within a manu- facturing system," The Robotics Institute, Carnegie-Mellon University, 1983.
[6] A. Danthine, "Protocol representation with finite state models," IEEE Transactions on Communications, pp. 632-642, 1980.
[7] R. Davis, et. al. , "Production rules as a representation for a knowledge-based consultation program," Artificial Intelligence, Vol. 8, pp. 15-45, 1977.
[8] R. Davis and R. Smith, "Negotiation as a metaphor for distributed problem solving," Artificial Intelligence, Vol. 20, pp. 63-109, 1983.
[9] R. E. Fikes, P. E. Hart and N. J. Nilson, "Learning and executing generalized robot plans," Artificial Intelligence, 3(4), pp. 251-288.
[10] R. E. Fikes and N. J. Nilson, "STRIPS: A new approach to the application of theorem proving to problem solving," Artificial Intelligence, 2(3/4), 1971, pp. 189-208.
[11] C. Forgy, 0PS5 User's Manual. Department of Computer Science, CMU-CS-81-135, Carnegie-Mellon University, 1981.
[12] P. H. EnsloWj "What is a Distributed Data Processing System," Computer, Jan. 1978, pp. 13-21.
[13] M. Georgeff, "Procedural control in production systems," Artificial Intelligence, Vol. 18, pp. 175-201, 1982.
-28-
[14] C. Hewitt, "Viewing control structures as patterns of passing messages," Artificial Intelligence, Vol. 8, pp. 323-364, 1977.
[15] G. K. Hutchingson, "Flexibility is key to economic feasibility
of automating small batch manufacturing," Industrial Engineering, pp. 77-86, June 1984.
[16] R. Kieburtz, "A hierarchical multicomputer for problem-solving
by decomposition," Proceedings of the IEEE Distributed Computing Systems, pp. 631-71, 1979.
[17] W. Kornfeld and C. Hewitt, "The scientific community metaphor," IEEE Systems, Man and Cybernetics, 1981.
[18] R. Kowalski, "Algorithm = logic + control," Communications of the ACM, Vol. 22, pp. 424-436, August 1979.
[19] V. Lesser and D. Corkill, "The distributed vehicle monitoring testbed: a tool for investigating distributed problem solving networks," The A.I. Magazine, Vol. 4, No. 3, pp. 15-33, 1983.
[20] T. Lozana-Perez , "Robot programming," Artificial Intelligence
Laboratory, Massachusetts Institute of Technology, A.I. Memo No. 698, 1982.
[21] D. McDermott and C. Forgy, "Production system conflict resolu- tion strategies," Pattern Directed Inference Systems, D. Waterman and F. Hayes-Roth, Eds., Academic Press, 1978.
[22] C. McLean, M. Mitchell and E. Barkmeyer, "A computer architecture for small-batch manufacturing," IEEE Spectrum, pp. 59-64, May 1983.
[23] M. E. Merchang, "Production: a dynamic challenge," IEEE Spectrum, pp. 36-39, May 1983.
[24] M. Minsky, The society theory of thinking," Artificial Intelli- gence - An MIT Perspective, P. Winton, Ed., MIT Press, 1979.
[25] R. Nelson, L. Haibt and P. Sheridan, "Casting Petri nets into programs," IEEE Trans, on Software Engineering, Vol. SE-9, No. 5, pp. 590-602, September 1983.
[26] R. Nelson, Principles of Artificial Intelligence. Palo Alto: Tioga, 1980.
[27] J. Peterson, Petri Net and the Modeling of Systems. Englewood Cliffs, NJ: Prentice-Hall, 1981.
[28] E. D. Sacerdoti, A Structure for Plans and Behavior. New York: North-Holland, 1977.
-29-
[29J M. J. Shaw, "The Design of a Distributed Knowledge-Based System for Intelligent Manufacturing Information Systems," Ph.D. Thesis, Purdue University, 1984.
[ 30 J M. J. Shaw and A. B. Whinston, "Automatic Planning and Flexible Scheduling: A Knowledge-Based Approach," Proceedings IEEE International Conference on Automation and Robotics, St. Louis, 1985.
[31] R. G. Smith, "The contract net protocol: high level communica- tion and control in a distributed problem solver," IEEE Transactions on Computer, Vol. 29, pp. 1104-1113, 1980.
[32J A. Tanenbaum, Computer Networks. New Jersey: Prentice-Hall, 1981.
(33 J A, Teng and M. Liu, "A formal approach to the design and imple- mentation of network communication protocol," Proceedings of COMPSAC, pp. 114-128, 1978.
[ 34 J S. Vere, "Planning in time: windows and duration for activities and goals," Pattern Analysis and Machine Intelligence, Vol. PAMI-5, No. 3, pp. 246-266, May 1983.
1 35 J D. E. Wilkins, "Domain independent planning: representation and plan generation," Artificial Intelligence, 22, pp. 269-301, 1984.
136] M. Zisman, "Use of production systems for modelling asynchronous concurrent processes," in Pattern Directed Inference Systems, D. Waterman and F. Hayes-Roth, Eds., Academic Press, 1978.
D/278
APPENDIX
Insert Table A.l Here
Figure 1. A Cellular Flexible Manufacturing System (CFMS)
2. The Organization of a Manufacturing Cell (Adapted from Cutkosky 1983)
3. Basic Structure of a Planning System
4 . Examples of Operators in the Action Model
5. The Search Tree Generated for the Planning of One Job
6. A Partially-ordered Network Generated by the Nonlinear Planning System
7. An Example of the Task-Announcement Message
8. The Protocol Hierarchy
9 . The Task-Announcement Process
10. The Bidding Process
11. The Flow Chart of the Task-Sharing Algorithm
CELL #2
CELL #3
CELL #i
CELL #1
CELL #N
Figure 1. A Network of Manufacturing Cells
loading robot
cnc
iatM
gffl
zs1
B 1 ~
13
I
o
linear tabla
Figure 2 The Organization of a Manufacturing Cell (Adapted from CutXosky 1983 )
->
CONTROL STRATEGY
<T
(Inference Engine)
±.
KNOWLEDGE BASE
- KNOWLEDGE RULES
> OPERATORS
• INFERENCE RULES
<r
>
±
DATA BASE
PLANS
PARTIAL PLANS CURRENT SITUATIONS GOALS
Figure 3. Basic Structure of a Planning System
TRANSFER(M, M\ PT, t) : Transfer p*rt PT from machine M to machine M'
at time t.
Precondition : FTNISH-OP(M, OP, PT, t)
DIFFERENT(M, M')
PT-NEXTO?(OP, OP, PT)
MACH-OP(M\ OP*)
IDLE(M\ t) Add-Iist : MACH-PT(M\ OP, PT, t)
IDLE(M, t) Dclete-list : FINISH-OP(M, OP, PT, t)
IDLE(M\ t) Resource : KT Duration : 2
NEXTOP(M, OP, OP, PT, t) : Perform operation OP on part PT following
operation OP on the same machine M.
Preconditon : FTNISH-OP(Ms OP, PT, t)
PT-NEXTOP(OP, OP, PT)
MACH-OP(M, OP) Add-Iist : MACH-PT(M, OP, PT, t) Dclete-list : FINISH-OP(M, OP, PT, t) Resource : M Duration : 0
Figure 4. Examples Of Operators In The Action Model
(m.iMd.t,.)
Figure 5. The Search Tree Generated for the Planning of One Job
figure 6. A Partially-ordered Network Generated by the Nonlinear Planning System
Eligibility Specification
MUST-HAVE: CONVEX -CUTTER
Task Abstraction
TASK-TYPE: Milling BATCH-SIZE: 45 CELL-CODE: 0015
Bid Specification COMPLETION TIME
Expiration Tim* 1200/3/10/1984
figure 7. An Example of the Task- Announcement Message
w
O
X
<3J
en O 93
c o
■u o
CO u
•-J o
4-1 4-1
o o
00 U
z
03
o
X
I
0
4->
I i-l
QO
o
o
CJ
o o
0-
I
u
(T3 S-i CD
O U O
4-1
o
a. a)
CO <D
3
En
30
c
i-l
o u
X >-,
C 03
C O •*-i w
03 1-
£ >.
x c
c _:
^3
00
^
o
ro
03 Cfl
a; u
o
-
C Q>
6 <u o
c
3
o
c c <
I
CD tS H
a> H
CTi 4)
3
c">
CO 0) 0)
o o
u
60
c
•H
CS
cu u
60
( st,rt )
Read Che Job Description
Partition the Job into Subtasks
Call
Taak-Sharing (Tj)
For Every Cell
Having Nev Assignments
in the Set
Update the Task Agenda
Inform the Monitor
of the New Assignment
The Cell Host
Initiates
Multitask Planning
( Stop J
<D
Fieure 11. The Flow Chart oi the Task-5'narir.? Algorich:
Table 1 Examples of Predicates Used in the World Model
IDLE(M,t): Machine M is idle at time t
MACH-PT(M,OP,PT,t): Machine M begins operation OP on part PT at time t
FINISH-OP(M,OP,PT,t): Machine M completes operation OP on part PT at
time t DIFFERENT(M,M'): Machine M is a machine different from machine Mf MACH-OP(M,OP): Machine M is capable of performing operation OP PT-FIRST-OP(OP,PT): Operation OP is the first operation on part PT PT-NEXTOP(OP,OP' ,PT): Operation OP' should be performed on part PT
immediately after operation OP DONE(PT.t): All operations on part PT are completed at time t TOOL(M,OP,t) : The tool for operation OP is available to the machine M at time t
Table 2 Specifying the Production System In Pros,ra» ?or»
Tt 11 (1TO-TASX cask)
Ch«n COSX-DTITTALIZATIOH task)
T If (TASE- EVALUATE Cask)
than (XRSK-AHMD KBSK cask)
T, If (BID-RETDRH bid)
AND (L2Q cljM-now deadline)
than (BID- PROCESSING bid)
T If (LBQ Clas-now deadline)
than
T If (CT clae-now deadline)
3 ARD (HE bid- Hat blank)
than (BID-ANARD bid- list)
T If (CT time- now deadline)
AND (EQ bld-ll.r blank)
than (REANNOUNCZ task)
T? If (REPLT-TO-AVARD accept)
than (LIST-ASS ICXMENT task)
Tg If (REPLY-TO-AWARD rejact)
Chan (BS-AUARD task)
T9 If (HOT(TASE-EVALnATZ task))
Chan (LIST-AGENDA cask)
t If (TASK-ANNOUNCED task)
AMD (BID-EVALOATE caak)
than (TASK-RANKINC tank)
T If (1Q (PROCESSOR- FOK- TASK task)busy)
Chan aiST-ACTTVE-TASR- ANNOUNCEMENT cask)
T , If (8Q (PROCESSOR- FOR- TASK cask) Id la)
Chan (BID- REPLY (BIS- SELECT a-C-a-D)
T.. If (LBQ claw-now dead Una)
Chan (BIDDING cask)
T If (BID- REPLY accapc)
AND (CELL- CONDITION normal)
Chan (LIST-ACENDA cask)
AND ( REPLY- TO-AWARD accapc)
I If (BID-REPLT accapc)
13 AND (CELL-CONDITION not-normal)
Chan (REPLY-TO-AWARD rejecc)
TJt If (BID- REPLY rajaec)
Chan («*- HDD INC (SID- SELECT a-t-a-D)
1. (NEW-TASK task)
2. (BID-RETURN bid)
3. (LEQ time-now dead-line) A. (REPLY-TO-AWARD accept)
5. (REPLY-TO-AWARD reject)
6. (NE bid-list blank)
7. (TASK-ANNOUNCED task)
8. (BID-REPLY accept)
9. (CELL-CONDITION normal)
Table 3. Predicate Literals Used in the Negotiation Protocol
1 . (TASK-EVALUATE task) :
To evaluate Che new task, the current loading condition of the cell, and the requirement of the task; the function returns binary values : TRUE: the host decides not to accept the task, will announce the
task. FALSE: the host will execute the task.
2. (Bid-EVALUATE task):
Similar to TASK-EVALUATE except now it is to decide whether to bid
or not. Also returns binary values:
TRUE: the cell decides to participate in the bidding.
FALSE: otherwise.
3. (PROCESSOR-FOR-TASK task) Returns two answers:
IDLE: a candidate processor within the cell can execute the task now, BUSY: all the candidate processors for the task are currently busy.
Table 4. Functions Used in the Negotiation Protocol
1 . TASK-INITIALIZATION
2 . TASK-ANNOUNCEMENT*
3. BID-PROCESSING
4. BID-AWARD*
5 . REANNOUNCE*
6 . REPLY-TO-AWARD*
7. REBIDDING*
8. LIST-ASSIGNMENT
9 . REAWARD*
10. LIST-AGENDA
1 1 . TASK-RANKING
1 2 . LIST-ACTIVE -TASK-ASSIGNMENT
13. BID-REPLY*
14. BIDDING*
* communication operations are involved
Table 5. Procedures Used in the Negotiation Protocol
00
CM
c
00
00
c
^ en
C H
O
i— i
c
en
»-h H
i— i >— i
H C
;owcocowcocow
ZtJZZUZZO
2S22Sa1c33 HCuHHOuHHO-i
CO
2
o
Oh
CO
z
CO
z
o
50
z
01
X
00
CO
o ••
CT\ «— t CO
H H C
<-l CM
1—1 1— I
en o •<
0> 1— < I— • I-
C H C H
CO
u
<u
z
<u
P.:
u o
i-l
o
00 V
a
►J z
Ou,
0)
0)
r-l
■9
ON
vO
00
|
I— 1 |
CM |
CM |
en |
en |
-tf |
en |
m |
un |
r» |
f^. |
w |
CM |
V |
|
H |
c |
H |
c |
H |
C |
c |
H |
c |
H |
c |
H |
H |
C |
|
W |
CO |
U |
CO |
Cd |
CO |
CO |
W |
CO |
u |
CO |
W |
U |
CO |
|
U |
z |
u |
z |
CJ |
z |
z |
U |
z |
u |
z |
U |
CJ |
z |
|
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
2 |
3 |
2 |
2 |
2 |
2 |
|
Oh |
H |
Oh |
H |
Oh |
H |
H |
Oh |
H |
Oh |
H |
Oh |
p |
H |
r-H CM
m
c
*©
1. Active-Task-Announcement-List (a-t-a-1) :
For each processor in the cell, this list keeps records on the tasks that have been announced but not expired, and within the capability of the processor. The cell-host will choose a task from this list once the corresponding processor gets idle.
2. Assignment List:
Each manager cell keeps an assignment-list on all the tasks awarded and the corresponding contractor cell.
3. Bid-List:
Each manager cell keeps a bid-list on all the bids received after a task is announced.
A. Task-Agenda:
Each cell has a task-agenda which contains all the tasks assigned to each processor.
Table A.l The Lists Used in the Negotiation Protocol
HECKMAN
BINDERY INC.
JUN95
» N MANCHESTER.! lBound-To-Pl«^ INpiANA 46962_