The paper deals with a testbed for control development for a system of multiple mobile robots sharing a common motion space. We present a general concept of a hybrid (discrete-event/continuous-time) control system that formally ensures correct concurrent robot movement, and describe a specific solution that follows the general concept and is underway its implementation for a team of TurtleBot robots operating under ROS.

We propose a novel paradigm for conflict resolution in multivehicle traffic systems, where a number of mobile agents move freely in a finite area, with each agent following a prespecified-motion profile. The key idea behind the proposed method is the tessellation of the underlying motion area in a number of cells and the treatment of these cells as resources that must be acquired by the mobile agents for the execution of their motion profiles, according to an appropriate resource allocation protocol. We capitalize upon the existing literature on the real-time management of sequential resource allocation systems (RASs) and develop such protocols that can formally guarantee the safe and live operation of the underlying traffic system, while they remain scalable with respect to the number of the moving agents. Collective past experience with the considered policies indicates that they also provide a pretty large coverage of the RAS behavioral space that characterizes its safe and live operation. Finally, we also establish that the aforementioned approach is applicable even in traffic systems where all vehicles must be in perpetual motion until their retirement.

The safety problem in multi-vehicle systems seeks to establish collision-free and live vehicle motion, and it is a prominent problem for many configurations of these environments. Past work studying this problem in the context of free-range vehicular systems through abstractions based on Resource Allocation System (RAS) theory, has implicitly assumed that its resolution through maximally permissive supervision is NP-hard, and therefore, it has typically pursued suboptimal (i.e., more restrictive) solutions. The work presented in this paper offers formal proof to this implicit assumption, closing the apparent gap in the existing literature.

Generalized algebraic deadlock avoidance policies (DAPs) for sequential resource allocation systems (RASs) have recently been proposed as an interesting extension of the class of algebraic DAPs, that maintains the analytical representation and computational simplicity of the latter, while it guarantees completeness with respect to the maximally permissive DAP. The authors' original work that introduced these policies also provided a design methodology for them, but this methodology is limited by the fact that it necessitates the deployment of the entire state space of the considered RAS. Hence, this paper seeks the development of an alternative computational tool that can support the synthesis of correct generalized algebraic DAPs, while controlling the underlying computational complexity. More specifically, the presented correctness verification test possesses the convenient form of a mixed integer programming (MIP) formulation that employs a number of variables and constraints polynomially related to the size of the underlying RAS, and it can be readily solved through canned optimization software. Furthermore, since generalized algebraic DAPs do not admit a convenient representation in the Petri net modeling framework, an additional contribution of the presented results is that they effect the migration of the relevant past insights and developments with respect to simpler DAP classes, from the representational framework of Petri nets to that of the Deterministic Finite-State Automata.

Currently, one of the most actively researched approaches regarding the design of deadlock avoidance policies for sequential resource allocation systems is based on concepts and techniques provided by the, so called, theory of regions, that addresses the broader problem of synthesizing PN models with pre-specified behaviors. However, one limitation of the theory of regions and its aforementioned derivatives is that they cannot be applied when the target behavior has a non-convex representation in the underlying state space. In this paper, we show how this problem can be circumvented by appropriately generalizing the employed class of the candidate policies.

This paper introduces and advocates a new approach to the coordination of the motion of multiple mobile robots. In contrast to the current literature solutions, based on the execution of off-line generated plans, this work develops a state-based, closed-loop control mechanism ensuring in a provable manner the correct concurrent robot movement. The concept consists of partitioning the robots’ paths into sectors and allowing each robot to move freely within a sector, whereas sector crossing is guarded with a real-time policy that guarantees collision and deadlock avoidance.

The liveness of a closed AGV system is understood as the constant potential of each vehicle to attain any given zone in the guide path network. Based on the DES model of AGVS and the liveness condition proposed in our earlier work, we conduct a further analysis of the system behavior. The result is a general, algorithmically defined supervisor for AGVS, given in the form of the pseudo-code of a recursive parametric function. The parameter is a function that can implement various selection algorithms, and in combination with the general supervisor defines a class of particular, directly applicable supervisors of various permissiveness level. The correctness of the provided control is formally proved.

Most of the research devoted to the supervisory control for deadlock avoidance in automated manufacturing systems has employed various models that represent concurrent sequential processes. In this paper, we address this problem for compound processes, that is, sequences of operations related in the fork/join manner and interacting as consumers/producers. The abstraction is used to model the flow of materials where independently processed components can be joined together and undergo further processing as a whole (e.g., to make an assembly or for a common transport), or material units can be split up so that their components will follow separate routes (e.g., at disassembly or separate processing of parts delivered in magazines), as well as to model the flow of objects that require a temporary meeting (e.g., independently routed pallets with the base components and pallets with parts to be mounted onto the base). Each process is represented with a marked graph, and the dynamics of the system are restricted with a feasibility function ensuring the feasible access to the shared resources. Unlike in sequential processes, in the class considered here, not all processes are realizable, i.e., possess a deadlock-free execution sequence. We prove that the problem of the distinction between realizable and unrealizable systems is NP-complete (thus intractable in practice) and propose a constraint that in a sufficient way allows us to distinguish a subclass of realizable compound processes. It is shown that the optimal, i.e., the minimally restrictive, supervisory control for this subclass of processes also poses an NP-hard problem. Therefore, we propose a compromise solution: a more restrictive, yet computationally acceptable admissibility function for guarding the event occurrence. The correctness of the control is proved formally by demonstrating the liveness and reversibility of the resulting model.

The paper is twofold. First we introduce a new concept-a partially directed graph, in which an edge can be undirected or have one of the two possible directions-and examine some of its structural properties. Then we assume that the edge attribute is variable and employ the concept to build a general, discrete event model of a system of vehicles moving in a path network. We examine some dynamic properties of the model and develop a flexible, suboptimal policy ensuring safe operation of the vehicle system.

We build a discrete-event model of concurrent FMS processes and consider the problem of its safe and maximally flexible behavior. To reduce the complexity of the problem we bound the class of systems addressed by the model with the requirement that the capacity of some selected resources be greater than one. The constraint prevents the occurrence the second level deadlocks while the first level deadlocks are avoided by the means of a computationally easy, maximally permissive, real-time test. The correctness of the method is formally proved.