Efficient Liveness Assessment for Traffic States in Open, Irreversible, Dynamically Routed, Zone-Controlled Guidepath-Based Transport Systems

摘要

Open, irreversible, dynamically routed, zone-controlled guidepath-based transport systems model the operation of many automated unit-load material handling systems that are used in various production and distribution facilities. An important requirement for these systems is to preserve the system liveness-i.e., the ability of each system agent to reach any location of the underlying guidepath network-by blocking those traffic states that will result in deadlock and/or livelock. The remaining set of traffic states are characterized as "live." The worst-case computational complexity of the decision problem of assessing the state liveness in the considered class of transport systems is an open issue. As a first contribution of this paper, we identify an extensive subclass of these traffic states, defined through the topology of an abstracting graphical representation of the "traffic state" concept, for which the corresponding problem of liveness assessment admits a polynomial solution, and we present the relevant algorithm for this assessment. But the development of the aforementioned results has also led to a new methodological framework for representing and analyzing the qualitative dynamics of the considered transport systems with respect to the reachability and the liveness problems that are the focus of this paper. This framework can enable an effective and efficient (but maybe not polynomial-complexity) resolution of the state liveness even for those traffic states that do not belong in the primary state class that is considered in this paper; we highlight this additional possibility in the closing part of this paper.