Optimization-based computation of bounded sequences to reach target states in DESs

Abstract The enumeration of legal transition paths leading to a target state (or set of states) is of paramount importance in the control of discrete event systems, but is hindered by the state explosion problem. A method is proposed in this paper, in the context of Petri nets, to calculate and enumerate firing count vectors for which there exists at least an admissible transition sequence leading to a given target marking. The method is shown to improve the approach based on singular complementary transition invariants proposed by Kostin and combines an integer linear programming formulation that finds the shortest minimal solution and a branching procedure that realizes a partition of the solution set. The enumeration can be restricted to minimal solutions or extended to non-minimal ones. Moreover, the approach is extended by adding a further constraint that the target transition sequences should pass by intermediate markings (in a specific order or not). Finally, source, target and via markings can be replaced by sets of markings. Some analytical examples are discussed in detail to show the effectiveness of the proposed approach.