The development of theoretical-based methods for the assessment of multi-agent systems properties is of critical importance. This work is a preliminary investigation on methodologies for modeling, analysis and design of multi-agent systems. Multi-agent systems are regarded as discrete-event dynamic systems and Petri nets are used as a modeling tool to assess the structural properties of the multi-agent system. Our methodology consists of defining a simple multi-agent system based on the abstract architecture for intelligent agents. The abstract architecture is modeled as a discrete-event system using Petri nets and structural analysis of the net provides an assessment of the communication and coordination properties of the multi-agent system. Deadlock avoidance in the multi-agent system is considered as an initial key property, and it is evaluated using liveness and boundedness properties of the Petri net model.

This paper presents a modeling technique for analyzing supply chains that represent a process oriented approach to producing and delivering products. The system is modeled by using a new extension to ordinary Petri nets (PNs) named complex-valued token Petri nets. Such a high-level of Petri nets employs complex-valued tokens to increase their descriptive abilities. A two stage supply chain is analyzed and a pull JIT/Kanban methodology is used to synchronize the successive completion of the products. The simulation of the stochastic complex token PN modeling the supply chain evaluates the system performance under different values of Kanbans and transporters.

This paper presents a new extension to ordinary Petri nets (PNs) that uses complex-valued tokens. By allowing two kinds of tokens, "real" and "imaginary," each place marking contains both quantity and type information. Complex-valued token PNs were designed to integrate seamlessly with other popular Petri net extensions such as timed nets, stochastic nets, and colored nets. This simple and intuitive application of complex numbers and complex arithmetic to PNs provides a unique modeling tool. Some examples show the capabilities of this proposed class of PNs. Note to Practitioners-Discrete-event systems are often man-made systems such as transportation systems, computer communication networks, distributed software, and manufacturing systems. They typically involve the flow of information and physical goods through a network. The flow itself evolves in continuous time but the initiation or completion of the event happens at a discrete point in time. Analyzing the system's performance is key to their successful operation. This paper presents a new approach to performance analysis with application to supply-chain management.

This paper will present a new extension to ordinary Petri nets that uses complex-valued tokens to increase their descriptive abilities while retaining their ease of analysis often lost in high-level Petri nets. By allowing two kinds of tokens, "real" and "imaginary", each place marking contains both quantity and type information. Complex Token Petri nets were designed to integrate seamlessly with other popular Petri net extensions such as timed nets, stochastic nets, and continuous nets. This simple and intuitive application of complex numbers to Petri nets provides a unique modeling tool.

The infrastructure of many nations has become a very complex inter-connection of electric power distribution systems, oil and natural gas production facilities, transportation (pipelines) of these products, water supplies, and communications. In addition, each of these systems is intertwined and heavily dependent on each other. The challenge is to model these interdependencies, identify vulnerabilities, and determine specific recovery strategies. This paper demonstrates the use of Petri nets for addressing this challenge. Petri nets are a graph-based tool and this work has shown that the Petri net incidence matrix captures the relationships between the infrastructure components. The place invariants (P-invariants) have been shown to model the interdependencies and identify vulnerabilities. The transition invariants (T-invariants) determine specific recovery strategies. In addition, the graphical nature of Petri nets allows a simple visualization of the interdependencies by observation of the token flows through the net.

Dynamic network-based decision systems search the information in the distributed databases and provide an appropriate solution for the design-supplier-manufacturing planning problem using evolutionary algorithms. The paper focuses on the development of a performance model to support such enterprise-level decision-making in network based scalable systems. Generalized Stochastic Petri Nets (GSPNs) are introduced to characterize network traffic and evolutionary algorithms. The network traffic model is based on the hyperexponential transition for analytical tractability. The algorithm model transforms the execution of the program into a stochastic activity net. The performance evaluation of the system can be explored in two directions: first, analyze and reconfigure the network connection for a specific algorithm, and second, given the network configuration, predict the performance of the algorithm. The results show that transient analysis is more important than steady-state analysis in the heavy-tailed network traffic. The paper also compares performance of the algorithms under different network configurations.

Agile electronics manufacturing requires integrated design, supply and manufacturing planning for modular products where suppliers and manufacturing resources is network distributed. This research is concerned with the modeling of such a distributed manufacturing network. The performance of network-based distributed decision systems is dominated by the network configuration and related access delays. Traffic measurement studies observed heavy-tails in the network traffic. Our basic approach is based on the quantile match to fit hyperexponential distributions to heavy-tailed distribution. We adopt the ON/OFF network traffic model and compare the fitted hyperexponential model with the heavy-tailed model. The results validate our fitting hyperexponentials. Generalized stochastic Petri nets (GSPNs) are introduced to analyze both the steady state and the transient behaviors of the distributed system. The results indicate that the transient analysis is more important than the steady-state analysis in network traffic modeling, since in most cases the distributed network does not reach the steady state.

Organizations in today's business environment often participate in short term alliances to manufacture sophisticated products. There are often a large number of potential designs for such products and no elementary technique for creating an optimal design. As a result, it is often necessary to utilize some form of computer algorithm to obtain a nearly optimal design. A variety of such algorithms exist including generic ones such as random search and genetic algorithms as well as application-specific algorithms. Any optimization algorithm will require information from a number of databases maintained by the individual companies in the alliance. Hence, the optimization is distributed over a wide area network of computers. The paper examines optimization algorithms which may be used to design printed circuit boards in this distributed manufacturing environment.

Stochastic Petri nets are strong tools to model discrete event dynamic systems. To describe the transient properties of the system, it is necessary to find the eigenvalues of the underlying Markov process. However, the state explosion problem, the stiffness problem appearing in many applications, and the intrinsic numerical instability hinder us from getting the complete eigenvalue set. In this paper, the location of the eigenvalues are obtained without generating the reachability set of the stochastic Petri net.

Stochastic Petri nets are widely used to get the steady state performance of a discrete event dynamic system. This is usually done with little concern about how fast the system reaches its steady state. The length of the transient state is known as the rise time in control theory or, the relaxation time in a Markov process. These are governed by the eigenvalue called the second dominant eigenvalues. Also, the separation of the most dominant and second dominant eigenvalue plays a role in the convergence of the numerical solution of the Markov process. A stochastic Petri net synthesis method which preserves the ergodicity and the irreducibility of the underlying Markov process, and gives the lower bound of the second dominant eigenvalue and the number of states is proposed.

In this paper, a Petri net-based perturbation analysis method with respect to structural changes is presented. The structural change of a generalized stochastic Petri net will modify its underlying reachability graph and its invariants, and so one approach is to reevaluate the entire model. However, if one uses the Petri net's structural properties, one can find the perturbed reachability graph without another analysis. Also, one can find the relationship between the original and new transition rate matrices. The net result is that less memory space is needed and less computational time is needed to get the state probability sensitivities and the performance sensitivities.>

This paper describes the implementation of a disturbance rejection controller for a 6-DOF PUMA manipulator mounted on a 3-DOF platform. A control algorithm is designed to track the desired position and attitude of the end-effector in inertial space, subject to unknown disturbances in the platform axes. Experimental results are presented for step, sinusoidal, and random disturbances in the platform rotational axis and in the neighborhood of kinematic singularities.>

Petri nets are a popular system modeling methodology, although the typical state-space explosion is problematic. An estimate of the state-space size has many uses: determining the appropriateness of a particular analysis technique; evaluating the trade-off between model detail and solution complexity; and providing data for state-space size reduction algorithms. This paper presents an estimation algorithm based on subnets and interconnections (i.e., a bottom-up approach). The algorithm allows relatively arbitrary subnets and is extendable via development of additional interconnections. Several subnets and interconnections are developed, and a multiworkcell manufacturing example is presented.>

A multiobjective approach to manufacturing process optimization is described. This approach places no restriction on the type or number of performance criteria and no a priori weights need be chosen for it since performance criteria are not combined into a single objective function. An algorithm is implemented that runs in real-time and provides immediate feedback to a process operator about the current operating point. If the current operating point is not Pareto optimal, the algorithm automatically adjusts the parameters to achieve this. If it is Pareto optimal but not desirable, the algorithm can provide information on how tradeoffs can be made so that the desired operating point is achieved. The algorithm was applied to the tuning of process inputs for the plastication and injection phases of an injection molding process. The optimization took place with respect to three quality characteristics: cycle time, flashing, and underfill. Measurement of flashing and underfill was done by the operator and both binary and fuzzy techniques were used. The algorithm was used to tune the process online, and experimental results are presented.>

The authors present the results of an investigation of the relationships between a Petri net (PN) and the size of its associated state-space. Four estimators are developed for estimating the number of states in a PN and understanding the sensitivity of this number to increases in tokens, places, and transitions. An estimator for conservative PNs demonstrated excellent accuracy. Estimators based on place boundedness and net boundedness had poor performance, but were amenable to analytical sensitivity analysis.>

An investigation into the relationships between Petri net (PN) models and their associated state-space is discussed. An algorithm to estimate an upper bound on the number of states in a PN is presented. This algorithm is based on the weight vector associated with conservative PNs. PN constructs that hinder the algorithm's accuracy are discussed. Additionally, the structural and behavioral nature of PN weighted conservatism is developed, and a clarification of a test of weighted conservativeness is presented.>

Beginning with a bounded (safe), live, or reversible Petri net as a first-level net model for a system, Petri nets are synthesized by first refining operation places through basic design modules in top-down modular ways, then adding nonshared resource places stepwise, and finally adding shared resource places step by step in a bottom-up manner. Refinement theory is extended to include reversibility of Petri nets. Parallel and sequential mutual exclusions are used to model shared resources. Design of the first-level Petri nets is discussed, and two basic kinds of Petri nets, choice-free and choice-synchronization, are given to cope with different types of manufacturing systems. The major advantages of the method are that the modeling details can be introduced in incremental ways such that complexity can be handled, and the important properties of the resulting Petri net are guaranteed so that costly mathematical analysis for boundedness, liveness, and reversibility can be avoided. A manufacturing system consisting of four machines, one assembly cell, two shared robots, and two buffers is used to illustrate the design methodology.>

A Petri-net-based integrated model for the performance analysis of network and database transactions, generated by manufacturing clients for the computer resources, which are acting as the servers, is discussed. A Petri-net-based multifaceted integrated modeling (PNBMIM) approach to investigate the relevant system integration issues between the logical and the physical access of the information in the manufacturing system is described. The PNBMIM approach proposes an integrated conceptual framework for modeling and performance (both structural and behavioral) analysis of data flow and communication flow. This framework should provide some answers to the impact of relative time-scales on the coupling and decoupling of the various levels of a computer integrated manufacturing (CIM) system and identify the time-scales where integration becomes important.>

The reduction of the state space of generalized stochastic Petri net (GSPN) models is discussed. For a certain class of GSPNs it is possible to analyze subnets in isolation by keeping the number of tokens in the net constant. The authors construct a flow equivalent net (FEN), which has the same temporal and input/output properties of the original net, but with a strongly reduced state space. The FEN is substituted back into the complement of the original net.>

Although generalized stochastic Petri nets (GSPNs) are restricted to only immediate and exponential transitions, they are used for performance analysis of a variety of systems. Flexible manufacturing systems (FMSs) typically contain nonexponential state transitions. GSPN models developed for FMSs present a concern that the above restriction limits the accuracy of performance results. Throughput subnets and s-transitions are introduced. These GSPN constructs allow nonexponential state transitions in a system to be accurately modeled within a GSPN. A GSPN performance model for an FMS example is developed using s-transitions. This system had been previously analyzed using probability theory. Performance analysis results are compared.>

A unified approach to the production planning and scheduling problem of a flexible manufacturing system with failure-prone machines is considered. The proposed method is based on the concept of Gershwin's hedging point strategy. A hierarchical controller is proposed in which the upper levels use an inventory hedging point for production planning. At the lower level of the controller the concept of a buffer hedging point is introduced and used to obtain the size of the machine buffers and to derive the schedule for the manufacturing system. The estimation of the buffer size is not based on any optimization procedures; instead, it relies on an argument that allows decoupling of the operation of every machine. The net result is a hedging point concept that is applicable to all levels of the hierarchy. It is also shown how the buffer hedging point concept is related to the just-in-time manufacturing strategy. Results are presented from a small, scaled-down computer-controlled flexible manufacturing system and from several simulated cases.>

Generalized stochastic Petri nets (GSPNs) are applied to flexible manufacturing systems (FMSs). Throughput subnets and s-transitions are presented. Two FMS examples containing nonexponential distributions, which were analyzed in previous papers by queuing theory and probability theory respectively, are treated using GSPNs developed using throughput subnets and s-transitions. The GSPN results agree with the previous results, and developing and analyzing the GSPN models are straightforward and relatively easy compared to other methodologies.>

A modeling and analysis tool based on Petri nets which allows a performance analysis of a system during the design stage is presented. The performance analysis criterion is taken as the response time of the system, i.e. the time it takes to complete a task after a command is initiated. This response time takes into account image processing time, a trajectory planning time, control execution time, etc. It permits the system designer to answer numerous 'what if' questions, e.g. what if processor speed is increased, vision processing time is reduced, robot precision is increased, more computers are added, communication protocols are changed? The net result is a common modeling methodology for handling such diverse functions as control, communication, computation, and database problems. Approaches are presented to modeling and analysis of integrated systems, and a brief discussion of Petri net theory and its benefits for modeling and analyzing complex interconnected systems consisting of several diverse functionalities is included. A case study which is based on the actual laboratory configuration is presented.>

Generalized stochastic Petri net (GSPN) modules are used as basic building blocks to model and analyze complex manufacturing systems. This modular approach facilitates model construction and helps manage the complexity of modeling large manufacturing systems. The structural analysis ensures that the model is live and bounded, which guarantees that the equivalent Markov chain (MC) is ergodic. The temporal analysis is used to derive performance measures such as average production rates and average in process inventories. The main advantage of Petri nets (PNs) over MCs is that the number of places and transitions increases only slightly as the manufacturing system complexity increases, whereas the number of states in the MC increases exponentially. In addition, there is no need to enumerate all the possible states manually since they are automatically generated from the GSPN model. As a result, PN models can still be easily obtained for complicated interconnected systems. The straightforward application of this approach is demonstrated and reviewed for several manufacturing case studies. For serial transfer lines it is proven that this modular approach results in live and bounded GSPN models. Comparisons are made with deterministic and reduced state-space models. Examples containing as many as 9614 states are presented.>

A Hamiltonian canonical formulation that yields a new and straightforward proof of the structure of the minimum-time control (MTC) law for m-link robotic manipulators is used. It is shown that the structure of the MTC law requires that at least one of the actuators always be in saturation. A numerical algorithm is presented. The algorithm converts the original problem, possibly a partially singular one, into a totally nonsingular optimal control problem by introducing a perturbed energy term in the performance index. It is shown that the solution to the perturbed problem converges to that of the MTC problem in the sense of the performance index as the perturbation parameter approaches zero. The control algorithm is used in a simulation to verify the MTC law structure.>

The authors address the problem of the structure of minimum-time control (MTC) of robotic manipulators along a specified geometric path subject to hard control constraints. By using the extended Pontryagin minimum principle (EPMP) and a set of parameterized robot dynamic equations, it is shown that the structure of the minimum-time control law requires that one and only one control torque is always in saturation on every finite time interval along its time-optimal trajectory, while the rest of the torques are adjusted so that the path constraint on the motion is not violated. This is in contrast to the point-to-point minimum-time control law, which requires that at least one of the control torques is always in saturation. Simulation results are presented to verify the structure of the MTC law.>

The authors propose an approach to systematic synthesis of Petri net models for manufacturing systems. It is based on top-down, modular, and decomposition philosophies which make the stepwise refinement of the Petri-net models possible. Using the proposed method, it is possible to obtain a Petri net model which is guaranteed to have the most important properties in the context of manufacturing: safeness, liveness, and reversibility. A formal problem statement is presented first. Then, the previous research on synthesis approaches is reviewed. Next, several modules are defined which, when combined according to a proposed algorithm, lead to the derived model. It is proven that the algorithm yields the safeness, liveness, and reversibility properties. An example of piston-rod assembly is used to demonstrate the proposed method.>

A dynamics model for a robot arm using state variables based on the Hamiltonian canonical equations is derived. From this model it is shown that the structure of the minimum-time control (MTC) law requires that at least one of the actuators is always saturated. A control algorithm for the MTC of a robot arm is presented. The algorithm converts the original problem, possibly a partially singular one, into a totally nonsingular optimal control problem by introducing a perturbed energy term in the performance index. It is shown that the solution to the perturbed problem converges to that of the MTC problem in the sense of the performance index as the perturbation parameter approaches zero. A simulation of a two-degree-of-freedom arm is performed to verify the mathematical structure of the MTC law.>

A colored Petri net (CPN) model of a cell controller capable of real-time control and monitoring of multiple workstations is described. The need to incorporate the ideas of both computer integrated manufacturing (CIM) and flexible manufacturing systems (FMS) is discussed, and the controller is based on these concepts. The CPN for the cell controller is presented and described. The controller in this case controls two workstations: the Cincinnati Milacron 5VC machining center and a robotic assembly workstation using an Adept robot. An analysis of the net is performed, and relevant portions are presented. A data structure for implementing this type of a CPN is given. The code for the controller is divided into application-dependent and -independent code. An execution algorithm is provided. The conclusions emphasize the advantages of CPNs in modeling and analysis for discrete-event control of manufacturing systems.>

This paper proposes feedback control algorithms suitable for the top level of a hierarchical approach to controlling Flexible Manufacturing Systems (FMS). Preview and state feedback control techniques are employed to regulate the inventory levels near zero. The resulting controller utilizes inventory state feedback and anticipatory demand feedforward control, referred to as preview control. The preview control takes on the form of demand filtering. Special dynamic properties of the demand filter are discussed. We show how future demand information is related to present production and inventory levels. Production constraints are explicitly handled in the development of the feedback controller. We present numerical results for a test case.

An application-independent manufacturing workstation controller is described for a general purpose computer which uses Petri nets to describe the sequencing informaiton. Several additions are made to Petri nets to allow the modeling of hierarchical systems, conflict decisions, and system actions. An application is composed of a description of the Petri net model of the system using a declarative language, and action-causing procedures written in the 'C' programming language. The Petri net determines when an action is to be done. An application is documented for a machining workstation centered around a Cincinnati Milacron SVC Machining Center.

The equations of motion for a robotic manipulator are a very lengthy and complicated set of nonlinear, highly coupled differential equations. A simplified model that reveals the dominant dynamics would be valuable for purposes of utilizing modern control theory. In this work, a method is presented for obtaining a reduced model for a nonlinear system. The structure of the simplified model is assembled from a library of the nonlinear basis terms that were present in the original model. This p-term structure is selected from the library in p-stages using a recently developed optimization scheme based on projection matrices and conjugate direction ideas. The algorithm is used to identify the dominant dynamics of several robot manipulator models and the results are verified on the GCA P300V robot in RPI's Robotics and Automation Laboratory.

This paper details the functions of a generic manufacturing workstation controller in the context of a computer integrated manufacturing (CIM) system. For each of these functions the required software and hardware performance characteristics are assessed. A brief overview of CIM is presented followed by a discussion of manufacturing workstations. The functions presented and described are task decomposition, inventory management, monitoring and control, reporting and communications. The performance attributes are presented using a qualitative scale. In software they include several characteristics of the operating system, application development potential, and communications support. The hardware attributes are discussed in terms of modularity of architecture, computing speed, memory requirements, I/O, interrupt structure, network support, remote unit support and environmental features. The results are concisely presented on two qualitative assessment matrices which match functions with performance attributes. Details supporting these assessments are presented in the text.

This work is concerned with the modeling and control of a robot that is mounted on a moving platform. The platform is subjected to random disturbances along its pitch, yaw, and roll axes. A controller is designed so that the robot can carry out tasks with respect to the robot base frame. In general, the problem is to investigate the various modeling and control issues involved in robotic systems subjected to time varying disturbances.

Due to the highly nonlinear structure of the robotic equation of motion, the exact time optimal control is so far unavailable. The high speed requirement in many applications renders PID controller unsatisfactory. Therefore, it is important to seek a suboptimal control strategy that is implementable and performs better than the PID controller. Two types of such controllers are examined in this paper. We will demonstrate the reasoning behind each approach and compare their respective strengths and flaws.