Modelling an automated storage and retrieval system using Petri nets

We investigated the feasibility of using stochastic Petri nets (SPNs) to describe the behaviours of automated storage/retrieval systems as well as to evaluate the performance of different control policies of such systems. SPNs have been studied in the past 2 decades, and have become a powerful tool in modelling concurrent and distributed systems that exhibit synchronization and contention of shared resources. It appeared that some important characteristics of AS/RS could be well modelled with SPNs. The SPN is a graph-based tool suitable for modelling systems (manufacturing, computer, biological, etc.). It can be used to model a system at different levels of abstraction. In this study, the efficiency, control rules, bay assignment, and many other performance issues associated with AS/RS have been studied in detail using SPN models. SPNs are shown to be equivalent to the stochastic processes in which embedded Markov chains can be recognized. In addition, a stochastic Petri net package, SPNP, was adopted to solve the reachability trees from which an embedded Markov chain was generated. Finally, the performance of those systems of our interest was evaluated. The unique features and flexibility of SPNs are presented. Furthermore, the SPN models for different control algorithms of an AS/RS are discussed with examples.     

Design of an automated guided vehicle-based material handling system for a flexible manufacturing system

Automated guided vehicle (AGV)-based material handling systems (MHSs), which are widely used in several flexible manufacturing system (FMS) installations, require a number of decisions to be made. These include the number of vehicles required, the track layout, traffic pattern along the AGV tracks, and solving traffic control problems. This paper addresses the key issues involved in the design and operation of AGV-based material handling systems for an FMS. The problems arising from multi-vehicle systems are analysed, and strategies for resolving them are examined using analytical and simulation models.     

Analysis of automated guided vehicle configurations in flexible manufacturing systems

Automated guided vehicle (AGV) systems complement the operation of flexible manufacturing systems (FMS) by providing integrated automated material handling that capitalizes on the system's flexibility. Previous research considering AGV systems for use in FMS installations has focused on complex control strategies to reduce the congestion problem often encountered in these systems. Recently, attention has been given to tandem system configurations that reduce congestion and simplify system control. The present study uses the simulation methodology to compare the performance of three AGV configurations under a variety of experimental conditions. The results indicate that system size, load/unload time, and machine failure rate factors have significant impacts on the operation of the systems considered. In general, with respect to due date performance, it is recommended to use the traditional configuration in small systems while using the tandem/loop configuration in larger systems. Furthermore, it is shown that the addition of the loop to the tandem configuration mitigates the sensitivity of the tandem configuration to the load/unload time factor as well as significantly improving its performance under high load/unload times. Thus, if tandem configuration is desired to reduce congestion and simplify system control, investments must be made to directly reduce the load/unload times or to construct a loop to avoid the load/unload time penalty.     

Deadlock avoidance in an automated guidance vehicle system using a coloured Petri net model

This paper addresses the problem of deadlock control in automated guided vehicle (AGV) systems for automated manufacturing systems with unidirectinal guided paths. First, a Petri net (PN) model was developed for the problem. Then, by using the PN model developed, the condition for deadlock-free operation in AGV system and a control law are presented. To avoid deadlocks in AGV systems by this law, one needs only to observe the state of the system and check the number of free spaces available in some of the circuits. It is estimated that the proposed control law is simple enough to be used in the real-time control of contemporary system configuration. Three examples are used to show the application and efficiency of the proposed control law.     

Tandem Configurations for Automated Guided Vehicle Systems and the Analysis of Single Vehicle Loops

Automated Guided Vehicle (AGV) systems continue to play a significant role in many low to medium flow manufacturing operations, including Flexible Manufacturing Systems (FMS) and other applications. The relatively inexpensive guidepath, coupled with the high degree of flexibility and control offered in vehicle routing, has made AGV systems a proven and viable handling technology for the 90's.

Traditionally, AGV systems have been implemented and analyzed assuming that every vehicle is allowed to visit any pick up/deposit point in the system. We introduce a conceptually simple and intuitive approach where the system is decomposed into non-overlapping, single-vehicle loops operating in tandem. In this paper, we also develop an analytical model to study the throughput performance of a single vehicle loop. The resulting expressions are the first closed form analytical expressions that have been obtained to determine the throughput capacity of a single vehicle operating under a specific dispatching rule in a non-deterministic environment.     

Conflict detection of automated guided vehicles: a Petri net approach

This research project investigates and develops techniques for automatically detecting potential vehicle conflicts in an automated guided vehicle (AGV) system. Three activities are involved: (1) construction of a set of formal definitions of Petri nets for modelling AGV systems; (2) development of procedures for detection of vehicle routeing conflicts; (3) development of a simulation program of the procedure. In this paper the first two activities are discussed in detail, and examples are provided.     

FMS统一建模技术与方法

针对ＦＭＳ的组成结构及控制特点，提出了一种层次递阶的统一建模方法。以面向对象建模技术和方法为主线，通过消息传递驱动机制使各层递阶模型有机集成为统一的整体，并与实际系统中各个层次及其关系相对应，从而准确，方便地描术字ＦＭＳ的规划设计、调度控制、运行及仿真等各个过程。     

A New Method of Global Path Planning for AGV

Path planning is important in the research of a mobile robot （MR）. Methods for it have been used in different applications. An automated guided vehicle（ AGV） , which is a kind of MR, is used in a flexible manufacturing system （FMS）. Path planning for it is essential to improve the efficiency of FMS. A new method was proposed with known obstacle space FMS in this paper. FMS is described by the Augmented Pos Matrix of a Machine （ APMM ） and Relative Pos Matrix of Machines （ RPMM）, which is smaller. The optimum path can be obtained according to the probability of the path and the maximal probability path. The suggested algorithm of path planning was good performance through simulation result： simplicity, saving time and reliability.     

An heuristic for configuring a mixed uni/bidirectional flow path for an AGV system

An heuristic methodology has been developed in the present work for configuring a mixed (hybrid) uni/bidirectional flow path for an AGV material handling system. The given unidirectional flow path layout, material flow intensities and vehicle travelling time matrix among various processing centres are taken as input information to this technique. A multiplicative function of material flow intensities between any two centres is used as a criterion for selectively configuring a path as a bidirectional one. The highest such product indicates that the shorter path between that pair of centres is a strong candidate for being configured as bidirectional. The heuristic has been applied to an illustrative FMS and various alternate flow path designs have been obtained. Simulation is then performed with the aim of comparing the productive potentials of the facility when it is operated on either unidirectional, or mixed uni/bidirectional, or allbidirectional flow path design alternatives. The benefits of bidirectional flows over unidirectional counterpart are significant in terms of system throughput rates and optimal AGV fleet sizes. However, traffic control becomes an important issue as vehicle interference and blocking increases with increase in bidirectionality in the network. The decision related to location and capacity planning of vehicle buffering zones is also addressed.     

A generic Petri net model for flexible manufacturing systems and its use for FMS control software testing

Developing a flexible manufacturing system (FMS) controller is a complicated task both in the hardware development and software development. To test the control software prior to putting it into use is crucial for the development of a FMS controller. An intelligent testing environment for FMS controllers is under development, the aim of which is to reduce manual work in the testing. To reach this objective the automatic building of a behavioural model of the FMS is demanded. This paper proposes a generic Petri net (GPN) model and approach for the development of control software for FMSs. The principle of this approach is based on checking the control parts of FMSs with the help of temporal relationships between physical operations, and the specification of the FMS controller with GPN. The strategy of GPN modelling is then incorporated with more general problem solving strategies in artificial intelligence. A template is first defined for a GPN model, and then the model for FMS individuals is established in the form of instances of the template. The transitions of the GPN are represented with the proposed general expressions with two syntaxes, 'verb+ noun' and 'verb+ noun+ where', from which the GPN can be formulated. GPN makes it simple to express FMS controls, and procedural language can also be used for information processing. A case study for the testing of FMS controller software is provided to show effectiveness and cost saving over development with conventional methods in which only ordinary Petri net and procedural language are used.     

AGV controlled FMS

One of the key factors that prevent the implementation of Flexible Manufacturing Systems (FMS) is the elaborate cost associated with the control software. In a FMS there is often a wide range of equipment, such as personal computers, Programmable Logical Controllers (PLCs), CNC Machines or robots, each of these having their own 'intelligence' and library of data. Providing a means of communication between these individual controllers has traditionally been achieved using a Local Area Network (LAN). This proves more expensive when traditional manual operated machines have to be integrated into the system. The model described in this paper provides an alternative to the conventional use of a LAN in a FMS environment. In the design solution, an Automatically Guided Vehicle (AGV) is used as both the materials handling unit and the communications line linking each station to the host controller. Communications between the AGV and peripheral equipment is achieved using a standard infrared data link, eliminating hard-wiring and network protocols. A simulation model has been developed to demonstrate the feasibility of such a system, using industrial data. The software package Witness is used to develop the simulation model. The objective from developing this simulation model is to test whether an AGV is capable of meeting the demands of such a scenario. The research undertaken aims to test this by modelling an existing factory layout. Using this layout and captured machining times and part routes, from the factory database, the feasibility of such AGV controlled production system is established. The model shows that such a system is plausible in a scenario where machine times are high and the distance between machines is large.     

Conflict resolution in AGV systems

Currently, conflict-free routing in AGV systems is established by means of one of the following three approaches: (i) the problem elimination through the adoption of a segmented path flow or tandem queue configuration; (ii) the identification of imminent collisions through forward sensing and their aversion through vehicle backtracking and/or rerouting; or (iii) the imposition of zone control and extensive route pre-planning, typically based on deterministic timing of the vehicle traveling and docking stages. Among these three approaches, the segmented path flow-based approach presents the highest robustness to the system stochas-ticities/randomness, but at the cost of restricted vehicle routings and the need for complicated handling operations. This paper proposes an alternative conflict resolution strategy that will ensure robust AGV conflict resolution, while maintaining the operational flexibility provided by free vehicle travel on arbitrarily structured guidepath networks. Specifically, the approach advocated in this paper also employs zone control, but it determines vehicle routes incrementally, one zone at a time. Routing decisions are the result of a sequence of safety and performance considerations, with the former being primarily based on structural/logical rather than timing aspects of the system behavior. The resulting control problem is characterized as the AGV structural control. After defining the notion of AGV structural control, the paper proceeds to the formal characterization and analysis of the problem, and to the development of a structural control policy appropriate for the class of AGV resource allocation systems. The paper concludes with some discussion on the accommodation of emerging AGV operational features in the proposed modeling and analysis framework, and the integration of AGV structural control with the broader control of material-flow among the shop-floor workstations.     

Deadlock prediction and avoidance based on Petri nets for zone-control automated guided vehicle systems

Deadlock problems of zone-control uni-directional automated guided vehicle (AGV) systems are discussed in this paper. Deadlocks of two types in such AGV systems are first classified from the perspective of shared resources, i.e. guide-path zones and buffers. A special class of Petri nets, attributed Petri nets (APN), is defined and used to represent the current state and to generate future states of zone-control AGV systems. We propose an algorithmic procedure to predict in real time and to avoid deadlocks that are caused by sharing guide-path zones in zone-control AGV systems. The proposed algorithm utilizes the current system state and future predicted states to avoid deadlocks. These states are obtained and generated from the obtained APN. A modular approach is employed to facilitate the construction of APN models of zone-control AGV systems.     

Assembly/disassembly task planning and simulation using expert Petri nets

Automatic assembly/disassembly planning is recognized as an important tool for reducing the manufacturing costs in concurrent product and process development. This paper developed a knowledge-based expert Petri net model by incorporating expert system techniques in artificial intelligence into ordinary Petri nets for an analytical framework of understanding, representing and reasoning the assembly/disassembly tasks. Substantial extensions have been made to ordinary Petri nets by adding control places, time constraints, and place and transition knowledge annotations. The proposed expert Petri net model can be considered as the hybrid of expert systems and ordinary Petri nets. Through these extensions, the capacities of modelling and representation of ordinary Petri net models are largely enhanced, and thus the expert Petri net models are more powerful than ordinary Petri nets. Such intelligent Petri net models can combine the abilities of modelling, planning, and performance evaluation for assembly/disassembly tasks in an integrated and intuitive way, and can therefore be applied to either linear/non-linear, static/dynamic, or on-line/off-line assembly/disassembly tasks at both high and low levels. The developed assembly/disassembly planning system can generate the best strategies and plans for assembly/disassembly. The research findings are exemplified with a real assembly to show the effectiveness of the method.     

Determination of optimal AGV fleet size for an FMS

The required number of AGVs necessary to perform a given level of material handling task in an FMS environment is determined using analytical and simulation modelling. The analytical method involves consideration of load handling time, empty travel time, and waiting and blocking time. Load handling time is computed from given system parameters. Determination of empty vehicle travel is difficult due to the inherent randomness of an FMS. Several research studies for this purpose are discussed and a new model is proposed. It entails formulation of a mixed integer programme with an objective of minimizing empty trips. The constraints are in the form of upper and lower bounds placed on the total number of empty trips starting from or ending at a load transfer station. The phenomena of vehicle waiting and blocking are also discussed. The cumulative impact of these three time estimates are then translated into an initial estimate of AGV fleet size as predicted by individual models. The method is applied to an illustrative example. Finally, simulation methodology is used to validate the initial estimates of fleet size. The results indicate that the different models either under-estimate or over-estimate the actual number of vehicles required in the system. The proposed model, though under-estimates the minimum AGV requirement, yet provides results which are close to the simulation results. Hence, it can be used as an analytical tool prior to the simulation phase of AGVS design.     

Scheduling of flexible manufacturing systems based on Petri nets and hybrid heuristic search

This paper proposes and evaluates a hybrid search strategy and its application to flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for FMS scheduling, this paper presents a hybrid heuristic search strategy, which combines the heuristic A* strategy with the DF strategy based on the execution of the Petri nets. The search scheme can invoke quicker termination conditions, and the quality of the search result is controllable. To demonstrate this, the scheduling results are derived and evaluated through a simple FMS with multiple lot sizes for each job. The algorithm is also applied to a set of randomly generated more complex FMSs with such characteristics as limited buffer sizes, multiple resources, and alternative routings.     

基于动态时间窗的泊车系统路径规划研究

针对智能立体停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,采用分时利用策略,将Dijkstra算法和时间窗法有效结合,提出了一种基于动态时间窗的泊车系统路径规划方法。首先,通过引入优先级策略为接收任务的AGV设定优先级;其次,采用Dijkstra算法,按照任务优先级高低次序,依次为接受任务的AGV规划出最短可行路径;最后,在已知AGV可行路径基础上,通过对可行路径各路段的时间窗进行初始化、实时更新以及实时排布处理,实现多AGV的无冲突路径规划。为验证所提方法的可行性和有效性,以4台AGV同时工作的智能立体停车库为实例进行仿真测试。结果显示:所提出的路径规划方法不仅有效解决了目前多AGV路径规划柔性差、易出现死锁、碰撞冲突等问题,而且可在有效解决路径冲突的前提下,为接受任务的AGV规划出一条时间最短的优化路径。所提方法具有较好的鲁棒性和柔性,有效提高了智能立体停车系统整体运行效率,降低了存取车等待时间。     

Design of material transportation system for tandem automated guided vehicle systems

A new design concept of materialtransportation system is proposed on the basis of tandem automated guided vehicle (AGV) systems. The first design stage is to find the one and only one optimal transfer point for each traffic zone. All in-process parts to be moved into and out of a zone must go through the specified transfer point and parts can be moved directly to their destinations. The second design stage is to link all transfer points as a 'transportation centre' by several bidirectional tracks. This design concept can simplify material transportation system and provides accurate estimation of traffic load in a zone.     

Celeritas: a coloured Petri net approach to simulation and control of flexible manufacturing systems

In many areas of computerization today, the capabilities of hardware systems far exceed the sophistication of software systems needed for optimum control. This research is an attempt to advance software control capabilities of flexible manufacturing systems (FMSs). To this end, an FMS controller architecture, called Celeritas, has been designed and a software system conforming to this architecture has been designed and implemented. Celeritas is a generic, data-configurable FMS controller designed using the coloured Petri nets (CP-nets) modelling paradigm augmented with decision support software to provide both FMS simulation and control. Formalisms of the CP-net paradigm provide straightforward representation of both the inherent concurrency and resource conflicts present in such a complex system. Augmentations provide user-defined routines for real-time interfaces to this information which is utilized to provide resource arbitration services among jobs competing for scarce resources and overall job scheduling.