International Journal of Computer Applications in Technology
`
`225
`
`Manufacturing systems: parallel
`system models and some
`theoretical results
`
`Sanjay Parthasarathy and Steven H. Kim
`Laboratory for Manufacturing and Productivity, Massachusetts Institute of
`Technology, Cambridge, Massachusetts, USA
`
`Abstract: A suitable model of the manufacturing environment must incorporate constructs
`to represent and manipulate information about concurrency, physical change, and time. The
`actor' model of the manufacturing system is one such model, based on the actor model of
`computation and the transformation model of production processes. This paper formalises
`the basic elements of the actorC model, which is then used to study the behaviour and
`capabilities of autonomous productior, systems. The new approach also offers some
`interesting insights into the design of completely autonomous production environments.
`Theoretical results, such as the partial decidability of a general process planning problem, can
`be derived using the actor' model.
`
`Key words: actor-based manufacturing systems (ABMS), actor+ model, manufacturing
`systems, parallel system models.
`
`Reference to this article should be made as follows: Parthasarathy, S. and Kim, S.H. (1990)
`'Manufacturing systems: parallel system models and some theoretical results', International
`Journal of Computer Applications in Technology, Vol. 3, No. 4, pp. 225-238.
`
`1
`
`INTRODUCTION
`
`1.1 Background
`
`The manufacturing environment can be viewed as a heav-
`ily parallel processing system, consisting of numerous
`processors (machines, robots, etc.) that transform the raw
`materials flowing through the system. The manufacturing
`system can therefore be modelled as a concurrent system
`whose computations correspond to physical operations.
`An analogy can be drawn between the manufacturing
`system and the concurrent computer system. The signifi-
`cance of parallel systems lies in what they can accomplish
`in timely fashion. In scope, parallel computers can do no
`more than sequential machines or even Turing Machines;
`but they can dramatically reduce requirements on pro-
`gramming effort and task completion times. Advances in
`parallel computation and communication hold important
`lessons for the design of manufacturing systems, since the
`design considerations for parallel computing systems are
`analogous to those of the production environment.
`An important step in the formalisation of the concepts
`of manufacturing systems is a model of the system itself.
`Any model of the manufacturing system must represent its
`inherent parallelism in addition to its transformational
`nature. The model must also represent and manipulate
`
`temporal information about concurrency and parallelism.
`The ability to reason about time is key to the planning and
`scheduling functions of the manufacturing system. Thus,
`any suitable model of the manufacturing system must
`incorporate constructs to represent and manipulate
`information relating to:
`
`concurrency and parallelism,
`transformation or change,
`time
`
`Again, computer science offers interesting insights into
`formal models of parallel systems. The actor model, for
`example, is a model of concurrent communication in
`which several active and self-contained entities called
`actors process communications in parallel [I, 21. The
`acto; model together with the transformation model of
`production processes [3], a process-based perspective of
`the manufacturing system, can be used to develop an
`actorf model of the manufacturing system. The super-
`script plus (+) in actor+ refers to the model's ability to
`simulate physical flows and transformations in addition
`to information flows and computations. To incorporate
`the ability to reason about time in the actorC model, we
`will extend the work on point and interval representations
`of time [4, 5, 6, 81, temporal reasoning [5, 91 and
`collections of intervals [7].
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1025, IPR2022-00681, Pg. 1
`
`

`

`1.2 Outline
`
`This paper proposes a model of the manufacturing system
`called the actor' model. The new approach is based on
`the actor model of computation and the transformation
`model of production processes.
`The paper investigates the implications of the actor'
`model and the practical implications of parallelism and
`concurrency on the performance of production systems.
`In addition, the attachments review the foundations of the
`actor' model: parallel processing systems in Appendix A,
`the actor model of computation in Appendix B and the
`transformation model of production processes
`in
`Appendix C.
`Section 2.1 demonstrates the rationale behind our
`choice of the actor model as the basis for the model of the
`production environment. It illustrates the correspon-
`dence between a formal representation of the manufactur-
`ing system and that of the actor model of computation. To
`overcome the actor model's inability to represent physical
`flows and transformations, it is combined with the
`transformation model to obtain the actor' model.
`Section 2.3 formalises the concepts of the actor' model
`and demonstrates its expressive power.
`The actor+ model offers some interesting insights into
`the design of autonomous production systems: those in
`which each component (whether a machine, robot, stor-
`age element, transport network or other mechanism) can
`be considered as an individual agent, while planning,
`scheduling and other system functions are automated.
`The actor-based manufacturing system (ABMS), an archi-
`tecture for an autonomous production system, is dis-
`cussed in Section 2.2. The actor+ model is then used to
`obtain some interesting results about the capabilities of
`ABMS, such as batch (off-line) planning and real-time
`(on-line) scheduling.
`The autonomous decision-making capabilities of the
`ABMS depend on translator modules associated with
`each component of the system. A translator module
`consists of an interpretation function that translates
`communications received from other system components.
`Section 2.4 formalises the function of the translator
`module.
`Section 2.5 demonstrates the utility of the actor' model
`by proving the partial decidability of generalised process
`planning within ABMS's and notes the implications of the
`proof of partial decidability. Finally, the paper discusses
`future work in temporal reasoning.
`
`2 PARALLEL MODEL OF THE MANUFACTURING
`SYSTEM
`
`2.1 Actor' model of the manufacturing system
`
`The actor model of computation is one in which several
`independent agents called actors send, receive and process
`communications in parallel. Since this model does not
`
`S. PARTHASARATHY AND S.H. KIM
`
`impose any control on the flow of communications, each
`actor can communicate with any other.
`The actor model fulfils one of
`the requirements
`of a model of the manufacturing system. However, it
`models only information flows and computations on data
`streams, and as such is inadequate for modelling the
`transformational activities in the manufacturing systems.
`But this limitation can be addressed by combining the
`actor model and the transformation model of production
`processes. We call the result the actor' model of
`the manufacturing system. The general structure of the
`actor' model is similar to that of the actor model of
`computation (see Appendix B). But, communications in
`the actor' model are defined by the ordered pair (part,
`information).
`Some concepts of the actor model may introduce
`unnecessary complexity in modelling the behaviour of the
`manufacturing environment:
`The creation of actors, a concept crucial to the actor
`model, may seem irrelevant to manufacturing systems.
`Machines or robots within the system cannot create
`copies of themselves or of other machines. Moreover,
`actor creation implies a potentially infinite set of actors.
`These conceptual difficulties may be ovecome through the
`definition of an actor in the actor' model. Each machine,
`robot, etc. within the manufacturing system is assigned
`a unique 'address' or identifier. An actor is then defined as
`any distinct operation or transformation that can be
`performed at any of the addresses within the system. The
`concept of actor creation is retained and operations can
`now 'create' other operations.
`Coordination of information and physical flows in the
`actor' model can be achieved by synchronisation of
`events within the system or by providing each actor with
`a buffer in which to store information until the corres-
`ponding physical resources arrive. Furthermore, the
`assumption that an actor is an independent agent neces-
`sitates access to information concerning other actors as
`well as process plans and schedules.
`The mathematical structure of the actor' model is
`equivalent to that of the actor model of computation (see
`Appendix B) [lo] and is given by:
`(E, A, T, -act+, Arr)
`
`We propose that the actor+ model be used to model the
`behaviour of the manufacturing system.
`
`Proposition:
`A manufacturing system can be simulated by an actor'
`model.
`
`The rationale is as follows:
`The simulation will work if a formal structure of the
`manufacturing system can be represented using the
`actor' model.
`Let each component of the manufacturing system
`(machine, robot, store etc.) be assigned a unique address.
`Let each operation, performed at any of the addresses
`within the system, be represented by an actor. Then, the
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1025, IPR2022-00681, Pg. 2
`
`

`

`PARALLEL MODELS FOR MANUFACTURING SYSTEMS
`
`set of actors within the manufacturing system, represented
`by A = {a,, a,, a,, . . . ), is potentially infinite. This in-
`finitude is consistent with the actor model of computa-
`tion.
`Let the three basic transformations be represented
`respectively by g, i, and u. Then the set of all possible
`events within a manufacturing system is given by:
`
`Z* = {A, g, i, u, gg, gi, gu, ig, ii, iu, ug, ui, uu, giu, gui, ggi,
`99u, ggg, . . . )
`where A is the null transform and C = {g, i,u) is the
`alphabet. Each element of C* is called a word w. A
`word such as giu implies that g precedes i which in turn
`precedes u. A sentence s is then a collection of words, i.e.
`s = w 1 . w 2 . w 3 - ~ . . - w , wherew ,...w,~C*.Now,thesetof
`all operations that can be performed within a given
`manufacturing system is defined as
`
`Consider the schedule Y for a manufacturing system.
`In essence, the schedule Y is a function that maps a set of
`operations to a set of manufacturing system components.
`Therefore,
`Y : E + A
`where A is the set of manufacturing system components.
`Moreover, the schedule Y specifies the arrival times of
`parts at appropriate machines, the duration of operations,
`- etc., through a rigorous timetable of events.
`Consider the set of process plans 9 for a set ofparts that
`can be processed within the given system. The set of plans
`9 specifies operations pertaining to the parts and is
`a partial ordering of the operations required to manu-
`facture them.
`The manufacturing system can now be represented by
`the following Ctuple:
`
`The manufacturing system structure corresponds to the
`actor+ model structure. The schedule Y contains the
`information embodied in the target function (T) and the
`arrival ordering (Arr) of the actor model. The set of
`process plans contains the information embodied in the
`activation ordering (-act+) of the actor model. Thus, the
`manufacturing system has a structure similar to that of the
`actor+ model. Hence, the actor' model can simulate the
`manufacturing system.
`
`2.2 Actor-based manufacturing systems (ABMS)
`
`In this section, an autonomous manufacturing system
`called the actor-based manufacturing system (ABMS) is
`proposed. The actor-based manufacturing system is one
`in which each machine, robot, and other system com-
`ponent is a n independent agent that can communicate
`with other agents and make decisions concerning system
`operation and control.
`
`Esch such system component is assigned a unique
`mail address. To each address is assigned a translator
`module. The translator module consists of an interpreta-
`tion function. Each actor can behave as an independent
`agent since it can access the translator module. Com-
`munications are a (part, information) couple, and in-
`formation is represented using the notation of the trans-
`formation model.
`Consider the simple ABMS shown in Figure 1, consist-
`ing of three machines M I , M 2 and M3 and a store S. Let
`A and B be two products that can be produced within the
`system. Let the direction of the arrows connecting the
`system components indicate admissible information and
`material flow channels. Let the flow paths for A and B be:
`
`Path (A): S+M, - + M 2 + M 3 + S
`Path (B): S+M2 + M 3 +S
`
`Let the operations performed in the system for one unit
`of A and one unit of B be as shown in Figure 2. Figure
`2 shows operations at individual machines and two
`possible overall sequences of events. Sequence 1 makes
`better use of time and material resources than Sequence 2.
`In order that the ABMS, operating autonomously, selects
`Sequence 1 over Sequence 2, information concerning the
`simultaneous operation of machines M, and M, must be
`conveyed and processed. Such information is specified in
`the arrival ordering (Arr) or the schedule Y for the system.
`Moreover, information concerning the partial order of
`events is specified through the activation ordering (-act+)
`or through the process plans for A and B.
`
`indicates Translator module
`
`Figure 1 An actor-based manufacturing system (ABMS).
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1025, IPR2022-00681, Pg. 3
`
`

`

`228
`
`S. PARTHASARATHY AND S.H. KIM
`
`Receive unit B 1 Receive unit B
`I f from M2
`
`e 4
`
`from S
`
`10
`
`1
`Receive unit A
`from S
`
`e
`2
`
`Process unit A
`
`e
`3
`Send unit A to M3
`
`Process unit B A Process unit B
`
`Send unit B to M3 1 Send unit B to S
`
`from M I
`
`from M2
`
`Process unit A / 1 Process unit A
`
`9
`15
`Send unit A to M3 Send unit A to S
`
`I
`
`Arrival ordering = simultaneous ( el, e4 ); simultaneous ( e7, el 0)
`
`Figure 2 Events within ABMS.
`
`2.2.1 The translator module
`
`2.2.1 .I Purpose of the translator module
`Associated with each address within the ABMS is a trans-
`lator module. The function of the translator is two-fold:
`
`to determine whether an operation or a sequence of
`operations can be executed at that address (feasibility);
`to determine whether the operation or sequence of
`operations, given the initial raw material condition,
`achieves the specified final conditions (acceptability).
`
`The feasibility check refers to system capabilities. It
`involves checking that the dimensions, tolerance, surface
`finish, hardness and other gross specifications of the final
`product are achievable within the system. Such a check
`may be effected by matching the product specifications
`with the system capabilities. The acceptability test, on the
`other hand, involves a detailed analysis of the operation
`
`parameters (speed, feed, depth of cut, temperatures,
`pressures, etc.), fixturing, and precedence relationships
`among operations.
`The mechanism for testing, both for feasibility and for
`acceptability, depends on the representation of know-
`ledge. The rest of this section formalises the general
`principles of acceptability and feasibility testing.
`The translator module consists of an interpretation
`function 9,. This interpretation function translates com-
`munications received from the rest of the system. The
`domain of the function (D,), corresponds to the set of
`operations that can be performed at the address. Then, the
`translator associated with an address within the system
`consists of a function 9, that maps transformation words
`to the set of operations that can be performed at that
`address.
`The interpretation functions enable each address to
`interpret communications received from other addresses.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1025, IPR2022-00681, Pg. 4
`
`

`

`PARALLEL MODELS FOR MANUFACTURING SYSTEMS
`
`The function translates instructions that are represented
`using the notation of the transformation model (Appendix
`C). Moreover, the interpretation function also translates
`instructions that are well formed formulas defined over
`the standard logical operators such as 3, V, A , v , etc. The
`interpretation functions of addresses within the ABMS
`assist in online (real-time) scheduling within the system.
`
`Interpretation function: dejinition and illustration
`2.2.1.2
`Let 9, be a mapping of constants (denoted by w E C*) to
`D,, and 9, a valuation function which maps variables
`(denoted by x, y, z, etc.) to D,. Then the interpretation
`function can be defined as a pair consisting of a model
`M and the valuation function 9 , . The model M is a pair
`consisting of the domain of the mapping D, and the
`function 9 , . Thus, the interpretation function is defined
`as:
`
`here the following relationships hold:
`
`D,* =nj=OtonDja
`9, =(M,Yv>
`$a = ((Da,9c), 9 v )
`Consider the following example of an interpretation
`function for a lathe:
`.alathe = (({turning, drilling), { W+ turning, w+
`drilling) ), {x+ turning, x+drilling))
`
`This function specifies that the lathe can have two distinct
`behaviours, namely, that of a turning agent and a drilling
`agent. Now, 9,at,ewill map all geometric transformations
`into one of these two behaviours.
`Now, consider the interpretation of a logical formula
`which states that there exists a word w that is the
`combination of two other words x and y such that
`x precedes y. This formula can be satisfied by a material
`removal operation which is composed of two successive
`removal operations that achieve the same end result.
`
`Now, consider the possible interpretations of the above
`sentence by the function YIath,. Y,,,,, assigns all possible
`combinations of elements in its domain to w, x and y. The
`set of all possible assignments is:
`
`1 w+turning; x, y-tturning
`2 w+turning; x+turning, y +drilling
`3 w + turning; x +drilling, y + turning
`4 w-tturning; x, y+drilling
`5 w-tdrilling; x, y-turning
`6 w+drilling; x+ turning, y +drilling
`7 w+drilling; x-tdrilling, y + turning
`8 w +drilling; x, y +drilling.
`
`Since a turning operation can be composed of two
`separate turning operations or a drilling operation of two
`
`separate drilling operations, only assignments 1 and 8 are
`admissible.
`
`2.2.1.3 Group interpretation functions: definition and
`illustration
`Interpretation functions associated with groups of
`machines, robots, and others, may now be defined. For
`example:
`
`{w+ turning,
`drilling},
`Ylathe =(({turning,
`w+drilling}), {x + turning, x-tdrilling))
`.agrind = (({grinding}, {w +grinding)), {x +grinding})
`9 + lat.gri = (({turning, drilling, grinding), {w + turning,
`w +drilling, w +grinding)),
`{x + turning,
`x +drilling, x +grinding)).
`
`is the interpretation function correspond-
`where $+,a,,ri
`ing to the group comprised of the interpretation func-
`tions 9 1 a t h e and $grind.
`A group of addresses is associated with an intepreta-
`tion function 9 + , , where m specifies the addresses that
`define the function 9 + , . For example, the interpretation
`function associated with a cell consisting of machines
`MI, M2 and M3 can be defined as:
`
`where the following relationships hold:
`
`Here, Uia) is defined as the union over the set {MI, M2,
`M3).
`The interpretation function associated with an entire
`system (9,), can play the role of a knowledge-based
`advisory system since it contains the information re-
`quired for planning. A database containing interpreta-
`tion functions associated with the addresses can be used
`for batch (off-line) planning and as a knowledge based
`advisory system.
`
`Satisjiability
`2.2.1.4
`We can now define the concept of 'satisfiability'. A
`sentence s is satisfied ( I ) by a system (ABMS,) if and
`only if there exists, within the system, a set of addresses
`whose interpretation function can assign elements from
`its domain to the words w,, . . . ,w, in s such that the
`specified initial and final conditions are achieved. Let the
`set of addresses be denoted by A and let each individual
`address is denoted by a,, where i ranges from 1 to n and
`n is the total number of addresses. Then:
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1025, IPR2022-00681, Pg. 5
`
`

`

`3 THEORETICAL RESULTS
`
`3.1
`
`Implications of the actor+ model
`
`The actorf model of the manufacturing environment
`allows for the derivation of several results. One example
`is the theorem that demonstrates the expressive power of
`the actor+ model:
`
`3.1.1 Expressive power of the actor+ model
`
`Proposition:
`A Turing Machine is equivalent in expressive power
`to a manufacturing system model whose decision-
`making capabilities are entirely off-line.
`
`Here, expressiveness refers to the model's ability to
`describe computations. These computations may relate
`to decision-making, description of change, etc. An off-
`line manufacturing system model is one in which the
`computational entities representing individual machines
`cannot communicate with other elements of the sys-
`tem and hence cannot make decisions on-line.
`Consider a Turing Machine M over an alphabet C
`[ll]. It consists of a tape, tape head and a program that
`determines the behaviour of
`the machine. Let the
`alphabet be C= {g, i, u } . Assuming that any sequence of
`operations can be expressed as a sentence s = w, -.... w,
`where w,, . . . , w,EC* using the notation of the trans-
`formation model, a plan is defined as a string fi such
`is followed by the machine on
`that each word wi€s
`which the operation is performed. Let the set of
`machines be A = {M, M,, M,, . . . }. Then + is of the
`form:
`
`where '.' and '#' are from an auxiliary alphabet. The
`alphabet C, the set A , an auxiliary alphabet V and the
`blank symbol A constitute the set of tape symbols
`recognised by the Turing Machine. Let each square of
`the tape, beginning with the leftmost square, contain
`exactly one symbol of the plan fi.
`The program is a finite directed graph, whose vertices
`correspond to the states of the part undergoing trans-
`formation. There is a start state, denoted by INITIAL
`and corresponding to the initial state of
`the raw
`material, and a halt state, denoted by FINAL and
`corresponding to the state of the finished product.
`The program encodes several alternative sequences of
`operations leading from the INITIAL to FINAL state.
`Arrows leading from one state to another are of the form
`(a, 8, y) where a and ~ E C U A U V U { A } and y€{L, R).
`Then, given an input fi and the tape head initially
`positioned at the leftmost tape square, execution will
`proceed as instructed by the program. If, eventually, the
`FINAL state is reached then we say that the word fi has
`been accepted by M. If a state is reached such that there
`is n o way to proceed with execution then the word +i is
`rejected.
`
`S. PARTHASARATHY AND S.H. KIM
`
`For the reverse simulation, a word +L
`is translated into
`the corresponding sequence of physical transformations
`and the manufacturing system model halts if and only
`if the specifications of the final product are achieved.
`Theorem:
`The actor+ model has a greater expressive power than
`a Turing Machine.
`
`Proof sketch:
`The Turing Machine is equivalent in expressive power
`to a manufacturing system model whose decision-
`making capabilities are entirely off-line. Since the
`actor+ model is one in which actors are self-contained
`agents capable of on-line decision making, it has
`greater expressive power than a Turing Machine.
`
`3.1.2 Capabilities of ABMS
`The following definitions illustrate the use of the actor
`model to obtain results on the behaviour of an ABMS.
`These results concern the numerosity of actors and tasks
`within an ABMS.
`
`Definition 1: The set of all possible distinct actors
`equals the cartesian product of the set of all possible
`mail addresses and the set of all possible distinct
`behaviours.
`
`Definition 2: The set of all possible tasks within an
`actor system equals the product of the set of all
`possible tags, the set of all possible mail addresses and
`the set of all possible communications [2].
`
`Theorem (countability of actors):
`The set of all distinct actors in an ABMS is infinite
`but countable.
`
`Prooj
`The set of distinct actors is given by the product of the
`set of distinct behaviours and the set of addresses. The
`set of distinct behaviours of an address within the
`manufacturing system is finite and countable. The set
`of mail addresses is infinite because new machines and
`other components can be added to the system. T o
`each system component we can assign a unique
`address; for an infinite number of components we can
`still assign unique addresses. Hence, the set of addres-
`ses is countable. The product of the set of distinct
`behaviours and the set of mail addresses is therefore
`infinite but countable.
`
`Corollary:
`The set of all possible actors is infinite.
`The set of all possible actors is the set of all operations
`that can be performed within the system. Thus, two
`identical operations performed at different times on the
`same machine or at the same time at two similar
`machines will constitute two separate actors. Thus, the
`set of all possible actors is infinite.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1025, IPR2022-00681, Pg. 6
`
`

`

`PARALLEL MODELS FOR MANUFACTURING SYSTEMS
`
`Theorem (countability of tasks):
`The set of all possible tasks within an ABMS is
`infinite, but countable.
`
`Lemma 2:
`The set of all possible combinations of distinct addres-
`ses within an ABMS, is enumerable.
`
`Proof
`The set of all tasks within an ABMS is the product of
`the set of mail addresses, the set of tags and the set of
`communications. The set of all possible mail addresses
`within the ABMS is infinite, but countable. The set of
`all possible tags is finite (definition of actor systems)
`and each tag is unique. The set of all possible tags is
`countable since it can be mapped onto the set of
`natural numbers N [I]. Therefore, it is sufficient to
`prove that the set of communications is either counta-
`bly finite or countably infinite since the cartesian
`product of two countable sets, i.e. N x N, is countable.
`Communications within ABMS's are defined by a
`(part id#, w,) couple where w,EC*. Since C* is infi-
`nite, but countable, the set of communications is
`infinite, but countable.
`
`3.2 Partial decidability of process planning
`
`The partial decidability of a general process-planning
`problem is demonstrated by building a program that,
`given only the initial raw material state and the final
`product requirements, will determine an appropriate
`process plan. This program will ensure that possible
`plans are not ignored, and that the selected plan satisfies
`all requirements. Proof of
`the partial decidability
`involves the proof of the enumerability of the set of all
`plans (see Lemma 1 below). The transformation model
`of production processes is used to define the set of plans
`abstractly. The plans so generated are tested on combin-
`ations of ABMS components. Hence, the set of all
`possible combinations of ABMS components must be
`proved enumerable (see Lemma 2 below).
`
`Lemma 1:
`The set of all possible plans is enumerable.
`
`Proot
`Consider the set C* where C = {g, i, u}:
`
`C* = {A, g, i, u, gg, gi, gu, ig, ii, iu, ug, ui, uu, giu, gui,
`ggi, ggu, ggg, igu, iug, iig, iiu, iii, ugi, uig, uug,
`uui, UUU, giug, . . .}
`= {wI, w2, w3,. . .)
`We can write a program that systematically generates
`the successive elements of C*. Therefore, C* is
`enumerable. The set C* can be considered as the set
`of all abstract plans. The interpretation function
`translates the abstract plan representation to detailed
`specifications. An advantage of reasoning at the
`abstract level is that a plan can be determined quickly.
`Once the general plan has been obtained, the details
`of the plan can be worked out.
`
`Proot
`Let the set of all distinct addresses be A={@,, a,,
`a,, . . . a,). The set of all possible combinations is given
`by:
`
`We can write a program that systematically generates
`first the singleton sets, then the sets containing two
`elements, etc. Then for each element of d so gen-
`erated, the corresponding interpretation function Y+,
`can be computed. Therefore d is enumerable.
`
`Theorem (basic transformations):
`The sequence of basic transformations leading from a
`given initial state to a specified final state, is partially
`decidable.
`
`Proof
`Given the results of Lemmas 1 and 2 we can prove
`partial decidability of planning within the production
`environment. The proof involves building a program
`that systematically searches through the set of all
`possible plans and selects one that satisfies the initial
`and final requirements. We will prove that the test for
`satisfiability of a plan is partially decidable.
`Consider the following algorithm that checks whether
`an element of C* satisfies the initial and final specifi-
`cations:
`1 Generate the set d and the associated $+,
`2 Generate the first element, w,, of C*
`3 For each {ai) E d , check if any $+ ,lw,
`4 If 3,$+,lw1
`then halt and accept; print w, and {ai)
`5 Else generate w2 and test
`6 Repeat till a wi is satisfied.
`If there is a w i € C* that is feasible and acceptable,
`it will be found, since for every 9+, the domain
`D+, is finite and an exhaustive substitution will
`yield a solution. However, if there is no feasible and/or
`acceptable word in C* the program will loop forever.
`
`The planning problem, as defined above, is only
`partially decidable because the set of all possible plans is
`infinite. If the program does not find a word w that can
`satisfy the specified initial and final conditions then it
`will generate successive elements of C* and test for
`satisfiability. However, if the program is required to halt
`after a certain time or after a sufficiently large number of
`words has been found unsatisfiable, then the planning
`problem can be shown to be fully decidable. Another
`strategy involves setting upper and lower bounds on the
`number of initial raw material states, final product states
`and intermediate states. Olsen and DeVries [I23 use this
`strategy in their proof of process plan decidability.
`Suppose that the cardinality of the set of all distinct
`addresses within the ABMS is n, that is, I A I =n. Then
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1025, IPR2022-00681, Pg. 7
`
`

`

`the cardinality of the set of all possible combinations is
`16 (=2". For a reasonably sized system, n may be
`between 15 and 30. Thus, 2" is a very large number, and
`the time taken to generate the set d alone is enormous.
`The test for the satisfiability of a single word W,EC*, of
`length r, in the context of an interpretation function $'+,
`involves a total number of r k possible assignments. Here
`k is the cardinality of the domain of the interpretation
`function, i.e. I D f , I = k. Hence, for a system with I A I = n,
`the potential number of checks for an exhaustive search
`for a single word w is:
`number of checks = Cr(ki)
`
`for i = 1 to 2", where r is the length of the word and
`ki= ( D*, ( of the ith element of A.
`A number of consequences follow immediately from
`the Basic Transformations Theorem.
`Corollary:
`The word wi on which the program halts is the
`smallest feasible word in C*.
`
`In other words the program will halt on the plan with
`the fewest steps from the initial to the final states and
`will be one with the fewest distinct transformations. This
`is because the program systematically generates words
`of increasing length.
`
`Corollary:
`The set of manufacturing system components {a),
`which satisfies wi will be the smallest feasible set that
`can perform the specified operations.
`
`Corollary:
`Given only the final requirements of a product, the
`question whether the product can be made within the
`given system, is partially decidable.
`
`For all practical purposes the set of initial raw material
`states for a particular product is finite and enumerable.
`Then, an exhaustive, check to determine an initial state
`and a plan that satisfies the final specifications can be
`encoded in a program.
`Corollary: It is impossible to determine the set of all
`products that can be made within a given system.
`
`Since C* is infinite, the set of final conditions achiev-
`able from a given initial state is infinite. Since each final
`state achievable can be a product, the set of all products
`that can be produced within a system is infinite.
`
`4 CONCLUSION
`
`The actorf model can be u